/*
 * swiss_sim.c -- a minimal Swiss table used to count probes, not to be fast.
 *
 * Layouts:
 *   absl16  Abseil 20260817.0 on x86-64: 16-wide SSE2 group, unaligned probe
 *           windows, capacity 2^m-1, ctrl[cap] = kSentinel, W-1 cloned bytes,
 *           H1 = hash, H2 = top 7 bits (absl/container/internal/raw_hash_set.h,
 *           hashtable_control_bytes.h).
 *   absl8   same, with Abseil's portable 8-wide SWAR group (GroupPortableImpl).
 *   go8     Go 1.24+ internal/runtime/maps: 8-slot aligned groups, capacity 2^m,
 *           probe over group indices, h1 = hash >> 7, h2 = hash & 0x7f.
 *
 * Modes:
 *   test    randomized differential test against a presence bitmap
 *   probe   groups loaded and key comparisons per lookup at fixed load factors
 *   erase   false negatives caused by different erase rules under churn
 *   churn   tombstones, in-place rehashes and growth under insert/erase churn
 *
 * Build: gcc -O2 -Wall -Wextra -msse2 -o swiss_sim swiss_sim.c
 * Run:   ./swiss_sim test && ./swiss_sim probe && ./swiss_sim erase && ./swiss_sim churn
 */
#include <emmintrin.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

enum { kEmpty = -128, kDeleted = -2, kSentinel = -1 };
enum { LAYOUT_ABSL16, LAYOUT_ABSL8, LAYOUT_GO8 };
enum { ERASE_ABSL, ERASE_NAIVE_ALIGNED, ERASE_ALWAYS_TOMBSTONE, ERASE_GO };

static const char *layout_name[] = {"absl16", "absl8", "go8"};
static const char *erase_name[] = {"abseil WasNeverFull", "aligned group has EMPTY",
                                   "always tombstone", "go (aligned group)"};

#define LSBS 0x0101010101010101ULL
#define MSBS 0x8080808080808080ULL

/* ---------- hashing and RNG ---------- */

static inline uint64_t hash64(uint64_t x) /* splitmix64 finalizer */
{
    x ^= x >> 30; x *= 0xbf58476d1ce4e5b9ULL;
    x ^= x >> 27; x *= 0x94d049bb133111ebULL;
    return x ^ (x >> 31);
}

static uint64_t rng_state;
static inline uint64_t rng(void)
{
    rng_state += 0x9e3779b97f4a7c15ULL;
    return hash64(rng_state);
}

/* ---------- group masks ---------- */

/* One abstract bit per slot: bit i (SSE2) or bit 8i+7 (SWAR). */
typedef struct { uint64_t m; int shift; } mask_t;

static inline unsigned mask_lowest(mask_t x) { return (unsigned)__builtin_ctzll(x.m) >> x.shift; }
static inline unsigned mask_highest(mask_t x) { return (unsigned)(63 - __builtin_clzll(x.m)) >> x.shift; }
static inline mask_t mask_next(mask_t x) { x.m &= x.m - 1; return x; }

static inline mask_t sse2_match(const int8_t *g, uint8_t h2)
{
    __m128i ctrl = _mm_loadu_si128((const __m128i *)g);
    __m128i eq = _mm_cmpeq_epi8(_mm_set1_epi8((char)h2), ctrl);
    return (mask_t){(uint32_t)_mm_movemask_epi8(eq), 0};
}
static inline mask_t sse2_empty(const int8_t *g)
{
    __m128i ctrl = _mm_loadu_si128((const __m128i *)g);
    return (mask_t){(uint32_t)_mm_movemask_epi8(_mm_cmpeq_epi8(_mm_set1_epi8(kEmpty), ctrl)), 0};
}
static inline mask_t sse2_empty_or_deleted(const int8_t *g)
{
    __m128i ctrl = _mm_loadu_si128((const __m128i *)g);
    return (mask_t){(uint32_t)_mm_movemask_epi8(_mm_cmpgt_epi8(_mm_set1_epi8(kSentinel), ctrl)), 0};
}

static inline uint64_t load64(const int8_t *g) { uint64_t v; memcpy(&v, g, 8); return v; }
static inline mask_t swar_match(const int8_t *g, uint8_t h2)
{
    uint64_t x = load64(g) ^ (LSBS * h2);
    return (mask_t){(x - LSBS) & ~x & MSBS, 3};
}
static inline mask_t swar_empty(const int8_t *g)
{
    uint64_t c = load64(g);
    return (mask_t){c & ~(c << 6) & MSBS, 3};
}
static inline mask_t swar_empty_or_deleted(const int8_t *g)
{
    uint64_t c = load64(g);
    return (mask_t){c & ~(c << 7) & MSBS, 3};
}

/* ---------- table ---------- */

typedef struct {
    int layout, w, erase_rule, no_grow;
    int8_t *ctrl;
    uint64_t *keys;
    size_t cap;      /* absl: 2^m-1, used as mask; go: 2^m slots */
    size_t size, deleted, growth_left;
    uint64_t groups, cmps, false_cmps;
    uint64_t rehash_inplace, grows, erase_to_empty, erase_to_deleted;
} table_t;

typedef struct { size_t off, idx; } probe_t;

static inline uint64_t h1_of(const table_t *t, uint64_t h) { return t->layout == LAYOUT_GO8 ? h >> 7 : h; }
static inline uint8_t h2_of(const table_t *t, uint64_t h) { return t->layout == LAYOUT_GO8 ? (uint8_t)(h & 0x7f) : (uint8_t)(h >> 57); }

static inline probe_t probe_start(const table_t *t, uint64_t h)
{
    if (t->layout == LAYOUT_GO8) return (probe_t){(h1_of(t, h) & (t->cap / 8 - 1)) * 8, 0};
    return (probe_t){h1_of(t, h) & t->cap, 0};
}
static inline probe_t probe_next(const table_t *t, probe_t p)
{
    if (t->layout == LAYOUT_GO8) {
        size_t gmask = t->cap / 8 - 1;
        p.idx += 1;
        p.off = (((p.off / 8) + p.idx) & gmask) * 8;
    } else {
        p.idx += (size_t)t->w;
        p.off = (p.off + p.idx) & t->cap;
    }
    return p;
}
static inline size_t slot_of(const table_t *t, size_t off, unsigned i)
{
    return t->layout == LAYOUT_GO8 ? off + i : (off + i) & t->cap;
}

static inline mask_t g_match(const table_t *t, size_t off, uint8_t h2)
{
    return t->w == 16 ? sse2_match(t->ctrl + off, h2) : swar_match(t->ctrl + off, h2);
}
static inline mask_t g_empty(const table_t *t, size_t off)
{
    return t->w == 16 ? sse2_empty(t->ctrl + off) : swar_empty(t->ctrl + off);
}
static inline mask_t g_empty_or_deleted(const table_t *t, size_t off)
{
    return t->w == 16 ? sse2_empty_or_deleted(t->ctrl + off) : swar_empty_or_deleted(t->ctrl + off);
}

static size_t num_slots(const table_t *t) { return t->cap; }
static size_t ctrl_len(const table_t *t)
{
    return t->layout == LAYOUT_GO8 ? t->cap : t->cap + 1 + (size_t)(t->w - 1);
}
static size_t growth_of(const table_t *t, size_t cap)
{
    return t->layout == LAYOUT_GO8 ? cap * 7 / 8 : cap - cap / 8;
}

/* Abseil SetCtrl: write the byte and its clone; for i >= W-1 both writes hit ctrl[i]. */
static inline void set_ctrl(table_t *t, size_t i, int8_t h)
{
    t->ctrl[i] = h;
    if (t->layout != LAYOUT_GO8)
        t->ctrl[((i - (size_t)(t->w - 1)) & t->cap) + (size_t)(t->w - 1)] = h;
}

static void table_alloc(table_t *t, size_t cap)
{
    t->cap = cap;
    t->ctrl = malloc(ctrl_len(t));
    t->keys = malloc(num_slots(t) * sizeof(uint64_t));
    if (!t->ctrl || !t->keys) { perror("malloc"); exit(1); }
    memset(t->ctrl, (unsigned char)kEmpty, ctrl_len(t));
    if (t->layout != LAYOUT_GO8) t->ctrl[cap] = kSentinel;
    t->size = t->deleted = 0;
    t->growth_left = growth_of(t, cap);
}

static void table_init(table_t *t, int layout, int erase_rule, size_t cap)
{
    memset(t, 0, sizeof *t);
    t->layout = layout;
    t->w = layout == LAYOUT_ABSL16 ? 16 : 8;
    t->erase_rule = erase_rule;
    table_alloc(t, cap);
}

static void table_free(table_t *t) { free(t->ctrl); free(t->keys); }

static long find(table_t *t, uint64_t key)
{
    uint64_t h = hash64(key);
    uint8_t h2 = h2_of(t, h);
    for (probe_t p = probe_start(t, h);; p = probe_next(t, p)) {
        t->groups++;
        for (mask_t m = g_match(t, p.off, h2); m.m; m = mask_next(m)) {
            size_t s = slot_of(t, p.off, mask_lowest(m));
            t->cmps++;
            if (t->keys[s] == key) return (long)s;
            t->false_cmps++;
        }
        if (g_empty(t, p.off).m) return -1;
        if (p.idx > num_slots(t)) { fprintf(stderr, "probe did not terminate\n"); exit(1); }
    }
}

static size_t find_first_non_full(const table_t *t, uint64_t h)
{
    for (probe_t p = probe_start(t, h);; p = probe_next(t, p)) {
        mask_t m = g_empty_or_deleted(t, p.off);
        if (m.m) return slot_of(t, p.off, mask_lowest(m));
    }
}

static void place(table_t *t, uint64_t key)
{
    uint64_t h = hash64(key);
    size_t s = find_first_non_full(t, h);
    if (t->ctrl[s] == kEmpty) t->growth_left--; else t->deleted--;
    set_ctrl(t, s, (int8_t)h2_of(t, h));
    t->keys[s] = key;
    t->size++;
}

static void rebuild(table_t *t, size_t new_cap)
{
    table_t old = *t;
    table_alloc(t, new_cap);
    for (size_t i = 0; i < num_slots(&old); i++)
        if (old.ctrl[i] >= 0) place(t, old.keys[i]);
    table_free(&old);
}

/* Abseil RehashOrGrowToNextCapacityAndPrepareInsert: squash tombstones in place
 * if size <= 25/32 of capacity, otherwise grow. (20260817.0 subtracts up to 5
 * "blocked" slots from capacity first; not modelled here.) Rebuilding into a
 * fresh array stands in for DropDeletesWithoutResize. */
static void rehash_or_grow(table_t *t)
{
    if (t->deleted > 0 && t->layout != LAYOUT_GO8 && t->size * 32 <= t->cap * 25) {
        t->rehash_inplace++;
        rebuild(t, t->cap);
    } else {
        t->grows++;
        rebuild(t, t->layout == LAYOUT_GO8 ? t->cap * 2 : t->cap * 2 + 1);
    }
}

static int insert(table_t *t, uint64_t key)
{
    if (find(t, key) >= 0) return 0;
    if (t->growth_left == 0) {
        if (t->no_grow) { fprintf(stderr, "table full\n"); exit(1); }
        rehash_or_grow(t);
    }
    place(t, key);
    return 1;
}

/* Abseil raw_hash_set.cc WasNeverFull(): look at the windows [i-W, i) and
 * [i, i+W). If the run of non-empty bytes around i is shorter than W, no probe
 * window covering i was ever completely full, so i can become kEmpty. */
static int was_never_full(const table_t *t, size_t i)
{
    size_t before = (i - (size_t)t->w) & t->cap;
    mask_t after_m = g_empty(t, i), before_m = g_empty(t, before);
    if (!after_m.m || !before_m.m) return 0;
    unsigned trailing = mask_lowest(after_m);
    unsigned leading = (unsigned)t->w - 1 - mask_highest(before_m);
    return trailing + leading < (unsigned)t->w;
}

static int erase(table_t *t, uint64_t key)
{
    long r = find(t, key);
    if (r < 0) return 0;
    size_t i = (size_t)r;
    int to_empty;
    switch (t->erase_rule) {
    case ERASE_ABSL: to_empty = was_never_full(t, i); break;
    case ERASE_NAIVE_ALIGNED:
    case ERASE_GO: to_empty = g_empty(t, i & ~(size_t)(t->w - 1)).m != 0; break;
    default: to_empty = 0; break;
    }
    if (to_empty) {
        set_ctrl(t, i, kEmpty);
        t->growth_left++;
        t->erase_to_empty++;
    } else {
        set_ctrl(t, i, kDeleted);
        t->deleted++;
        t->erase_to_deleted++;
    }
    t->size--;
    return 1;
}

static int check_invariants(const table_t *t)
{
    size_t full = 0, del = 0;
    for (size_t i = 0; i < num_slots(t); i++) {
        if (t->ctrl[i] >= 0) full++;
        else if (t->ctrl[i] == kDeleted) del++;
        else if (t->ctrl[i] != kEmpty) return 0;
    }
    if (full != t->size || del != t->deleted) return 0;
    if (t->growth_left + t->size + t->deleted != growth_of(t, t->cap)) return 0;
    if (t->layout != LAYOUT_GO8) {
        if (t->ctrl[t->cap] != kSentinel) return 0;
        for (int j = 0; j < t->w - 1; j++)
            if (t->ctrl[t->cap + 1 + (size_t)j] != t->ctrl[j]) return 0;
    }
    return 1;
}

/* ---------- mode: test ---------- */

static int run_test(void)
{
    const size_t U = 50000;
    int failures = 0;
    struct { int layout, rule; } cfg[] = {
        {LAYOUT_ABSL16, ERASE_ABSL}, {LAYOUT_ABSL8, ERASE_ABSL},
        {LAYOUT_ABSL16, ERASE_ALWAYS_TOMBSTONE}, {LAYOUT_GO8, ERASE_GO},
    };
    unsigned char *present = calloc(U, 1);
    for (size_t c = 0; c < sizeof cfg / sizeof cfg[0]; c++) {
        table_t t;
        table_init(&t, cfg[c].layout, cfg[c].rule, cfg[c].layout == LAYOUT_GO8 ? 16 : 15);
        memset(present, 0, U);
        rng_state = 42 + c;
        size_t mismatches = 0, live = 0;
        for (long step = 0; step < 3000000; step++) {
            /* bias towards growth first, then churn around ~20k live keys */
            uint64_t k = rng() % U + 1;
            unsigned op = (unsigned)(rng() % 10);
            int want_insert = live < 20000 ? op < 6 : op < 4;
            if (op >= 8) {
                if ((find(&t, k) >= 0) != present[k - 1]) mismatches++;
            } else if (want_insert) {
                int r = insert(&t, k);
                if (r == present[k - 1]) mismatches++;
                if (r) { present[k - 1] = 1; live++; }
            } else {
                int r = erase(&t, k);
                if (r != present[k - 1]) mismatches++;
                if (r) { present[k - 1] = 0; live--; }
            }
            if (step % 250000 == 0 && !check_invariants(&t)) { mismatches++; }
        }
        for (size_t k = 1; k <= U; k++)
            if ((find(&t, k) >= 0) != present[k - 1]) mismatches++;
        if (!check_invariants(&t)) mismatches++;
        printf("test %-7s %-24s live=%zu cap=%zu inplace=%llu grows=%llu mismatches=%zu\n",
               layout_name[cfg[c].layout], erase_name[cfg[c].rule], live, t.cap,
               (unsigned long long)t.rehash_inplace, (unsigned long long)t.grows, mismatches);
        failures += mismatches != 0;
        table_free(&t);
    }
    free(present);
    printf(failures ? "TEST FAILED\n" : "TEST PASSED\n");
    return failures != 0;
}

/* ---------- mode: probe ---------- */

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

typedef struct { double mean_groups, mean_false; uint32_t p99, max; } lookup_stats;

static lookup_stats measure(table_t *t, const uint64_t *keys, size_t n, uint32_t *buf)
{
    lookup_stats s = {0};
    uint64_t total_g = 0, total_f = 0;
    for (size_t i = 0; i < n; i++) {
        uint64_t g0 = t->groups, f0 = t->false_cmps;
        (void)find(t, keys[i]);
        buf[i] = (uint32_t)(t->groups - g0);
        total_g += buf[i];
        total_f += t->false_cmps - f0;
    }
    qsort(buf, n, sizeof *buf, cmp_u32);
    s.mean_groups = (double)total_g / (double)n;
    s.mean_false = (double)total_f / (double)n;
    s.p99 = buf[(size_t)((double)n * 0.99)];
    s.max = buf[n - 1];
    return s;
}

/* Scalar linear probing over the same keys: slots examined per lookup. */
static void linear_probe_stats(size_t cap, size_t n, const uint64_t *keys, const uint64_t *miss,
                               size_t nmiss, double *hit, double *mis)
{
    uint64_t *slot = calloc(cap, sizeof *slot); /* 0 = empty; keys are never 0 */
    size_t mask = cap - 1;
    for (size_t i = 0; i < n; i++) {
        size_t j = hash64(keys[i]) & mask;
        while (slot[j]) j = (j + 1) & mask;
        slot[j] = keys[i];
    }
    uint64_t total = 0;
    for (size_t i = 0; i < n; i++) {
        size_t j = hash64(keys[i]) & mask;
        total++;
        while (slot[j] != keys[i]) { j = (j + 1) & mask; total++; }
    }
    *hit = (double)total / (double)n;
    total = 0;
    for (size_t i = 0; i < nmiss; i++) {
        size_t j = hash64(miss[i]) & mask;
        total++;
        while (slot[j]) { j = (j + 1) & mask; total++; }
    }
    *mis = (double)total / (double)nmiss;
    free(slot);
}

static uint64_t nonzero_key(void)
{
    uint64_t k;
    do k = rng(); while (k == 0);
    return k;
}

static int run_probe(void)
{
    const double loads[] = {0.5, 0.75, 0.875};
    const size_t nmiss = 1u << 20;
    const size_t cap_pow2 = 1u << 20;
    uint64_t *keys = malloc(cap_pow2 * sizeof *keys);
    uint64_t *miss = malloc(nmiss * sizeof *miss);
    uint32_t *buf = malloc(cap_pow2 * sizeof *buf);

    printf("probe: capacity 2^20-1 (absl) / 2^20 (go, linear); %zu miss lookups; seed 1\n", nmiss);
    printf("%-7s %-6s | %-28s | %-28s\n", "layout", "load", "hit: groups mean/p99/max, false cmp",
           "miss: groups mean/p99/max, false cmp");
    for (int L = 0; L < 3; L++) {
        for (size_t li = 0; li < sizeof loads / sizeof loads[0]; li++) {
            table_t t;
            size_t cap = L == LAYOUT_GO8 ? cap_pow2 : cap_pow2 - 1;
            table_init(&t, L, ERASE_ABSL, cap);
            t.no_grow = 1;
            rng_state = 1;
            size_t n = (size_t)(loads[li] * (double)cap);
            for (size_t i = 0; i < n; i++) { keys[i] = nonzero_key(); place(&t, keys[i]); }
            for (size_t i = 0; i < nmiss; i++) miss[i] = nonzero_key();
            lookup_stats h = measure(&t, keys, n, buf);
            lookup_stats m = measure(&t, miss, nmiss, buf);
            printf("%-7s %-6.3f | %5.3f / %2u / %2u  %7.4f     | %5.3f / %2u / %2u  %7.4f\n",
                   layout_name[L], loads[li], h.mean_groups, h.p99, h.max, h.mean_false,
                   m.mean_groups, m.p99, m.max, m.mean_false);
            table_free(&t);
        }
    }
    printf("\nlinear probing, one slot per step (Knuth: hit (1+1/(1-a))/2, miss (1+1/(1-a)^2)/2)\n");
    for (size_t li = 0; li < sizeof loads / sizeof loads[0]; li++) {
        rng_state = 1;
        size_t n = (size_t)(loads[li] * (double)cap_pow2);
        for (size_t i = 0; i < n; i++) keys[i] = nonzero_key();
        for (size_t i = 0; i < nmiss; i++) miss[i] = nonzero_key();
        double hit, mis, a = (double)n / (double)cap_pow2;
        linear_probe_stats(cap_pow2, n, keys, miss, nmiss, &hit, &mis);
        printf("linear  %-6.3f | slots hit %6.3f (theory %6.3f) | slots miss %7.3f (theory %7.3f)\n",
               loads[li], hit, (1 + 1 / (1 - a)) / 2, mis, (1 + 1 / ((1 - a) * (1 - a))) / 2);
    }
    free(keys); free(miss); free(buf);
    return 0;
}

/* ---------- mode: erase ---------- */

static int run_erase(void)
{
    const int rules[] = {ERASE_NAIVE_ALIGNED, ERASE_ABSL, ERASE_ALWAYS_TOMBSTONE};
    const size_t cap = (1u << 15) - 1, n = 22000; /* load 0.671 */
    const long steps = 1000000;
    uint64_t *live = malloc(n * sizeof *live);
    printf("erase: absl16, capacity %zu, %zu live keys (load %.3f), %ld erase+insert+lookup steps, seed 7\n",
           cap, n, (double)n / (double)cap, steps);
    for (size_t r = 0; r < sizeof rules / sizeof rules[0]; r++) {
        table_t t;
        table_init(&t, LAYOUT_ABSL16, rules[r], cap);
        rng_state = 7;
        for (size_t i = 0; i < n; i++) { live[i] = nonzero_key(); insert(&t, live[i]); }
        t.erase_to_empty = t.erase_to_deleted = 0;
        uint64_t false_neg = 0, failed_erase = 0;
        for (long s = 0; s < steps; s++) {
            size_t v = rng() % n;
            if (!erase(&t, live[v])) failed_erase++;
            live[v] = nonzero_key();
            insert(&t, live[v]);
            if (find(&t, live[rng() % n]) < 0) false_neg++;
        }
        double tot = (double)(t.erase_to_empty + t.erase_to_deleted);
        printf("%-24s | erase->EMPTY %5.1f%% | failed erase %6llu | lookup false negatives %6llu | "
               "in-place rehash %4llu | grows %llu\n",
               erase_name[rules[r]], 100.0 * (double)t.erase_to_empty / tot,
               (unsigned long long)failed_erase, (unsigned long long)false_neg,
               (unsigned long long)t.rehash_inplace, (unsigned long long)t.grows);
        table_free(&t);
    }
    free(live);
    return 0;
}

/* ---------- mode: churn ---------- */

static int run_churn(void)
{
    const double fills[] = {0.50, 0.70, 0.78, 0.80, 0.86};
    const size_t cap0 = (1u << 16) - 1;
    const size_t nmiss = 1u << 14;
    const int samples = 20;
    uint64_t *miss = malloc(nmiss * sizeof *miss);
    uint32_t *buf = malloc(nmiss * sizeof *buf);
    printf("churn: absl16 with WasNeverFull, start capacity %zu, 20*n erase+insert pairs, seed 11\n", cap0);
    printf("miss groups and tombstones are averaged over %d samples (one every n pairs)\n", samples);
    printf("%-6s %-6s | %-7s %-7s %-5s | %-12s | %-15s | %-17s | %s\n", "n/cap", "n", "cap_end", "inplace",
           "grows", "erase->EMPTY", "tombstones/cap", "miss groups churn", "miss groups fresh");
    for (size_t f = 0; f < sizeof fills / sizeof fills[0]; f++) {
        size_t n = (size_t)(fills[f] * (double)cap0);
        uint64_t *live = malloc(n * sizeof *live);
        table_t t;
        table_init(&t, LAYOUT_ABSL16, ERASE_ABSL, cap0);
        rng_state = 11;
        for (size_t i = 0; i < n; i++) { live[i] = nonzero_key(); insert(&t, live[i]); }
        if (t.cap != cap0) { fprintf(stderr, "unexpected growth during fill\n"); return 1; }
        t.erase_to_empty = t.erase_to_deleted = 0;
        double sum_groups = 0, sum_tomb = 0;
        for (int smp = 0; smp < samples; smp++) {
            for (size_t s = 0; s < n; s++) {
                size_t v = rng() % n;
                erase(&t, live[v]);
                live[v] = nonzero_key();
                insert(&t, live[v]);
            }
            for (size_t i = 0; i < nmiss; i++) miss[i] = nonzero_key();
            sum_groups += measure(&t, miss, nmiss, buf).mean_groups;
            sum_tomb += (double)t.deleted / (double)t.cap;
        }
        /* same n, same final capacity, built without any erase */
        table_t fresh;
        table_init(&fresh, LAYOUT_ABSL16, ERASE_ABSL, t.cap);
        for (size_t i = 0; i < n; i++) place(&fresh, live[i]);
        for (size_t i = 0; i < nmiss; i++) miss[i] = nonzero_key();
        double fresh_groups = measure(&fresh, miss, nmiss, buf).mean_groups;
        printf("%-6.2f %-6zu | %-7zu %-7llu %-5llu | %11.1f%% | %14.3f | %17.3f | %.3f\n", fills[f], n, t.cap,
               (unsigned long long)t.rehash_inplace, (unsigned long long)t.grows,
               100.0 * (double)t.erase_to_empty / (double)(t.erase_to_empty + t.erase_to_deleted),
               sum_tomb / samples, sum_groups / samples, fresh_groups);
        table_free(&fresh);
        table_free(&t);
        free(live);
    }
    free(miss); free(buf);
    return 0;
}

int main(int argc, char **argv)
{
    const char *mode = argc > 1 ? argv[1] : "test";
    if (!strcmp(mode, "test")) return run_test();
    if (!strcmp(mode, "probe")) return run_probe();
    if (!strcmp(mode, "erase")) return run_erase();
    if (!strcmp(mode, "churn")) return run_churn();
    fprintf(stderr, "usage: %s test|probe|erase|churn\n", argv[0]);
    return 2;
}