update mempool and add implement hash array mapped trie (not integrated)

1 files changed, 45 insertions, 0 deletions

diff --git a/src/hamt.h b/src/hamt.h
new file mode 100644
index 0000000..6ef27ba
--- /dev/null
+++ b/src/hamt.h
@@ -0,0 +1,45 @@
+#ifndef HAMT_H
+#define HAMT_H
+
+#include <stdint.h>
+
+typedef struct hamt *hamt_t;
+
+// tagged pointer to either
+// hamt_item or hamt_nodelist
+typedef uintptr_t hamtptr_t;
+
+struct hamt_item {
+    uint32_t refs;
+
+    void *key;
+    void *data;
+    struct hamt_item *next;
+};
+
+struct hamt_nodelist {
+    uint32_t refs;
+
+    uint64_t bitmask;
+    hamtptr_t *list;
+};
+
+typedef int (*hamt_equal_fn)(void *key1, void *key2);
+typedef uint32_t (*hamt_hash_fn)(void *key);
+
+struct hamt {
+    hamt_equal_fn equal_fn;
+    hamt_hash_fn hash_fn;
+
+    hamtptr_t root;
+};
+
+hamt_t hamt_create(hamt_equal_fn equal_fn, hamt_hash_fn hash_fn);
+void hamt_destroy(hamt_t hamt);
+
+hamt_t hamt_clone(hamt_t src);
+
+int hamt_get(hamt_t hamt, void *key, void **data);
+int hamt_set(hamt_t hamt, void *key, void *data, void **keyptr, void **prevdata);
+
+#endif