#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) {
HashMap *m = hm_create(4096);
Model model;
memset(&model, 0, sizeof(model));
uint64_t st = 0x9e3779b97f4a7c15ull;
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;
}