assembly-hashmap 0.1.0

A single-threaded u64→u64 hashmap with x86-64 assembly operations and Rust-side growth.
Documentation
#include "hashmap.h"

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MODEL_MAX 2048
#define RANDOM_KEYS 1500
#define RANDOM_OPS 60000

typedef struct {
    int used;
    uint64_t key;
    uint64_t val;
} ModelSlot;

typedef struct {
    ModelSlot s[MODEL_MAX];
    size_t n;
} Model;

static ModelSlot *model_find(Model *m, uint64_t key) {
    for (size_t i = 0; i < MODEL_MAX; i++) {
        if (m->s[i].used && m->s[i].key == key) {
            return &m->s[i];
        }
    }
    return NULL;
}

static hm_option model_put(Model *m, uint64_t key, uint64_t val) {
    hm_option o = {0, 0};
    ModelSlot *e = model_find(m, key);
    if (e) {
        o.present = 1;
        o.value = e->val;
        e->val = val;
        return o;
    }
    for (size_t i = 0; i < MODEL_MAX; i++) {
        if (!m->s[i].used) {
            m->s[i].used = 1;
            m->s[i].key = key;
            m->s[i].val = val;
            m->n++;
            return o;
        }
    }
    abort();
}

static hm_option model_get(Model *m, uint64_t key) {
    hm_option o = {0, 0};
    ModelSlot *e = model_find(m, key);
    if (e) {
        o.present = 1;
        o.value = e->val;
    }
    return o;
}

static hm_option model_remove(Model *m, uint64_t key) {
    hm_option o = {0, 0};
    ModelSlot *e = model_find(m, key);
    if (e) {
        o.present = 1;
        o.value = e->val;
        e->used = 0;
        m->n--;
    }
    return o;
}

static void eq_opt(const char *what, hm_option a, hm_option b) {
    if (a.present != b.present || (a.present && a.value != b.value)) {
        fprintf(stderr, "FAIL %s: got (%llu,%llu) want (%llu,%llu)\n", what,
                (unsigned long long)a.present, (unsigned long long)a.value,
                (unsigned long long)b.present, (unsigned long long)b.value);
        exit(1);
    }
}

static uint64_t rng(uint64_t *s) {
    uint64_t x = *s;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    *s = x;
    return x;
}

static void test_basic(void) {
    HashMap *m = hm_create(8);
    assert(m);
    assert(hm_len(m) == 0);

    hm_option o = hm_get(m, 1);
    assert(!o.present);

    o = hm_put(m, 1, 10);
    assert(!o.present);
    o = hm_get(m, 1);
    assert(o.present && o.value == 10);

    o = hm_put(m, 1, 11);
    assert(o.present && o.value == 10);
    o = hm_get(m, 1);
    assert(o.present && o.value == 11);

    o = hm_remove(m, 1);
    assert(o.present && o.value == 11);
    o = hm_get(m, 1);
    assert(!o.present);
    o = hm_remove(m, 1);
    assert(!o.present);

    hm_put(m, 2, 20);
    hm_put(m, 3, 30);
    assert(hm_get(m, 2).value == 20);
    assert(hm_get(m, 3).value == 30);
    hm_remove(m, 2);
    assert(!hm_get(m, 2).present);
    assert(hm_get(m, 3).present && hm_get(m, 3).value == 30);

    hm_destroy(m);
    puts("ok basic");
}

static void test_many(void) {
    /* Deliberately overprovision the raw fixed table: resize/rebuild policy is
     * now owned by the Rust wrapper, not this native unit test. */
    HashMap *m = hm_create(4096);
    Model model;
    memset(&model, 0, sizeof(model));
    uint64_t st = 0x9e3779b97f4a7c15ull;

    /* RANDOM_KEYS stays below hm_capacity so a legitimate insert never fails
     * for lack of room, which would diverge from the model for the wrong
     * reason. */
    for (int i = 0; i < RANDOM_OPS; i++) {
        uint64_t op = rng(&st) % 10;
        uint64_t key = rng(&st) % RANDOM_KEYS;
        uint64_t val = rng(&st);
        if (op < 5) {
            eq_opt("put", hm_put(m, key, val), model_put(&model, key, val));
        } else if (op < 8) {
            eq_opt("get", hm_get(m, key), model_get(&model, key));
        } else {
            eq_opt("remove", hm_remove(m, key), model_remove(&model, key));
        }
        if (hm_len(m) != model.n) {
            fprintf(stderr, "len mismatch %zu vs %zu\n", hm_len(m), model.n);
            exit(1);
        }
    }

    for (uint64_t k = 0; k < RANDOM_KEYS; k++) {
        eq_opt("final get", hm_get(m, k), model_get(&model, k));
    }
    hm_destroy(m);
    puts("ok random");
}

static void test_tombstones(void) {
    HashMap *m = hm_create(64);
    for (uint64_t i = 0; i < 50; i++) {
        hm_put(m, i, i * 3);
    }
    for (uint64_t i = 0; i < 50; i += 2) {
        hm_option o = hm_remove(m, i);
        assert(o.present && o.value == i * 3);
    }
    for (uint64_t i = 1; i < 50; i += 2) {
        hm_option o = hm_get(m, i);
        assert(o.present && o.value == i * 3);
    }
    for (uint64_t i = 0; i < 50; i += 2) {
        assert(!hm_get(m, i).present);
        hm_put(m, i, 1000 + i);
    }
    for (uint64_t i = 0; i < 50; i++) {
        uint64_t expect = (i % 2 == 0) ? 1000 + i : i * 3;
        hm_option o = hm_get(m, i);
        assert(o.present && o.value == expect);
    }
    hm_destroy(m);
    puts("ok tombstones");
}

static void test_full(void) {
    HashMap *m = hm_create(16);
    size_t cap = hm_capacity(m);
    for (uint64_t i = 0; i < cap; i++) {
        hm_option o = hm_put(m, i + 1, i + 100);
        assert(!o.present);
    }
    assert(hm_len(m) == cap);
    for (uint64_t i = 0; i < cap; i++) {
        hm_option o = hm_get(m, i + 1);
        assert(o.present && o.value == i + 100);
    }
    hm_option o = hm_put(m, 1, 999);
    assert(o.present && o.value == 100);
    o = hm_put(m, cap + 50, 1);
    assert(o.present == 2);
    assert(hm_len(m) == cap);
    assert(!hm_get(m, cap + 50).present);
    hm_destroy(m);
    puts("ok full");
}

static void test_compound_and_iteration(void) {
    HashMap *m = hm_create(32);
    assert(!hm_contains(m, 7));

    hm_option o = hm_put_if_absent(m, 7, 70);
    assert(o.present == 0);
    assert(hm_contains(m, 7));
    o = hm_put_if_absent(m, 7, 700);
    assert(o.present == 1 && o.value == 70);
    assert(hm_get(m, 7).value == 70);

    o = hm_get_or_insert(m, 8, 80);
    assert(o.present == 0);
    o = hm_get_or_insert(m, 8, 800);
    assert(o.present == 1 && o.value == 80);

    o = hm_replace(m, 7, 71);
    assert(o.present == 1 && o.value == 70);
    o = hm_replace(m, 9, 90);
    assert(o.present == 0 && !hm_contains(m, 9));

    size_t cursor = 0;
    size_t count = 0;
    uint64_t key = 0;
    uint64_t value = 0;
    uint64_t sum = 0;
    while (hm_iter_next(m, &cursor, &key, &value)) {
        count++;
        sum += key + value;
    }
    assert(count == 2 && sum == 7 + 71 + 8 + 80);

    hm_clear(m);
    assert(hm_len(m) == 0);
    assert(!hm_contains(m, 7));
    cursor = 0;
    assert(!hm_iter_next(m, &cursor, &key, &value));
    hm_destroy(m);
    puts("ok compound/iteration/clear");
}

static void test_zero_key(void) {
    HashMap *m = hm_create(4);
    hm_put(m, 0, 42);
    hm_option o = hm_get(m, 0);
    assert(o.present && o.value == 42);
    o = hm_remove(m, 0);
    assert(o.present && o.value == 42);
    assert(!hm_get(m, 0).present);
    hm_destroy(m);
    puts("ok zero key");
}

int main(void) {
    test_basic();
    test_zero_key();
    test_tombstones();
    test_full();
    test_compound_and_iteration();
    test_many();
    puts("all tests passed");
    return 0;
}