#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

static double now_ms(void) {
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec * 1e3 + ts.tv_nsec / 1e6;
}

/* A tiny deterministic generator: every run performs the same work. */
static unsigned next_value(unsigned *state) {
    *state = *state * 1103515245u + 12345u;
    return *state >> 8;
}

__attribute__((noinline)) void fill_ids(unsigned *ids, size_t n) {
    unsigned state = 42;
    for (size_t i = 0; i < n; i++)
        ids[i] = next_value(&state);
}

static int compare_unsigned(const void *a, const void *b) {
    unsigned x = *(const unsigned *)a, y = *(const unsigned *)b;
    return (x > y) - (x < y);
}

__attribute__((noinline)) void sort_ids(unsigned *ids, size_t n) {
    qsort(ids, n, sizeof ids[0], compare_unsigned);
}

/* Slow version: scans the array from the start for every key. */
__attribute__((noinline)) long find_linear(const unsigned *ids, size_t n, unsigned key) {
    for (size_t i = 0; i < n; i++)
        if (ids[i] == key)
            return (long)i;
    return -1;
}

/* Fixed version: the array is already sorted, so binary search is enough. */
__attribute__((noinline)) long find_binary(const unsigned *ids, size_t n, unsigned key) {
    size_t lo = 0, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2;
        if (ids[mid] < key) lo = mid + 1;
        else hi = mid;
    }
    return (lo < n && ids[lo] == key) ? (long)lo : -1;
}

__attribute__((noinline)) unsigned long lookup_all(const unsigned *ids, size_t n, int fixed) {
    unsigned state = 7;
    unsigned long found = 0;
    for (size_t q = 0; q < n; q++) {
        /* Odd queries ask for a key that exists; even queries use a fresh value. */
        unsigned key = (q % 2) ? ids[(q * 7919) % n] : next_value(&state);
        long at = fixed ? find_binary(ids, n, key) : find_linear(ids, n, key);
        if (at >= 0)
            found++;
    }
    return found;
}

__attribute__((noinline)) unsigned long checksum(const unsigned *ids, size_t n, int rounds) {
    unsigned long sum = 0;
    for (int r = 0; r < rounds; r++)
        for (size_t i = 0; i < n; i++)
            sum = sum * 31 + (ids[i] ^ (unsigned)r);
    return sum;
}

int main(int argc, char **argv) {
    size_t n = argc > 1 ? strtoul(argv[1], NULL, 10) : 40000;
    int fixed = argc > 2 && strcmp(argv[2], "fixed") == 0;
    unsigned *ids = malloc(n * sizeof *ids);
    if (n == 0 || !ids) {
        fprintf(stderr, "usage: %s [count>0] [slow|fixed]\n", argv[0]);
        return 2;
    }
    double t0 = now_ms();
    fill_ids(ids, n);
    double t1 = now_ms();
    sort_ids(ids, n);
    double t2 = now_ms();
    unsigned long found = lookup_all(ids, n, fixed);
    double t3 = now_ms();
    unsigned long sum = checksum(ids, n, 2000);
    double t4 = now_ms();
    printf("mode=%s n=%zu found=%lu checksum=%lu\n", fixed ? "fixed" : "slow", n, found, sum);
    fprintf(stderr, "fill=%.1fms sort=%.1fms lookup=%.1fms checksum=%.1fms\n",
            t1 - t0, t2 - t1, t3 - t2, t4 - t3);
    free(ids);
    return 0;
}
