hamt.c

#include <stdio.h>
#include <string.h>
#include <stdint.h>

static uint64_t hash_str(char *data) {
    uint64_t prime = 0x100000001b3;
    uint64_t hash = 0xcbf29ce484222325;
    for (size_t i = 0; data[i]; i++) {
        hash ^= (unsigned char)data[i];
        hash *= prime;
    }
    return hash;
}

struct Hamt {
    struct Hamt *children[2];
    char *key;
    int value;
};
static struct Hamt **hamt_find_indirect(struct Hamt *root, char *key) {
    uint64_t hash = hash_str(key);
    struct Hamt **hamt = &root;
    while (*(hamt = &(*hamt)->children[hash & 1])) {
        if (strcmp((*hamt)->key, key) == 0) {
            break;
        }
        hash >>= 1;
    }
    return hamt;
}
static struct Hamt *hamt_find(struct Hamt *root, char *key) {
    return *hamt_find_indirect(root, key);
}
static void hamt_add(struct Hamt *root, struct Hamt *add) {
    struct Hamt **found = hamt_find_indirect(root, add->key);
    if (!*found) {
        *found = add;
    }
}

int main() {
    struct Hamt root = {0};
    struct Hamt a = {
        .key = "a",
        .value = 1,
    };
    hamt_add(&root, &a);
    struct Hamt b = {
        .key = "b",
        .value = 2,
    };
    hamt_add(&root, &b);
    struct Hamt c = {
        .key = "c",
        .value = 3,
    };
    hamt_add(&root, &c);
    printf("%d\n", hamt_find(&root, "a")->value);
    printf("%d\n", hamt_find(&root, "b")->value);
    printf("%d\n", hamt_find(&root, "c")->value);
}