Define a proper hash table library

Define a proper hash table library, instead of the current ad hoc stuff
used for both labels and macros.  This only implements the actual
library; it is not yet used.

We use a CRC64 as a prehash.  This is almost certainly overkill,
although it is rather efficient (except, arguably, the table lookup)
on 64-bit platforms, and not all that bad on 32-bit platforms.  All we
really need is a function which produces two independent 32-bit
results which are used as the primary and secondary hash
respectively.  Either way, the prehash function is easily replacable
if/when we have a quicker alternative.

1 files changed, 40 insertions, 0 deletions

diff --git a/hashtbl.h b/hashtbl.h
new file mode 100644
index 0000000..cc3daff
--- /dev/null
+++ b/hashtbl.h
@@ -0,0 +1,40 @@
+/*
+ * hashtbl.h
+ *
+ * Efficient dictionary hash table class.
+ */
+
+#ifndef NASM_HASHTBL_H
+#define NASM_HASHTBL_H
+
+#include <inttypes.h>
+#include <stddef.h>
+#include "nasmlib.h"
+
+struct hash_tbl_node {
+    uint64_t hash;
+    const char *key;
+    void *data;
+};
+
+struct hash_table {
+    struct hash_tbl_node *table;
+    size_t load;
+    size_t size;
+    size_t max_load;
+};
+
+struct hash_insert {
+    uint64_t hash;
+    struct hash_table *head;
+    struct hash_tbl_node *where;
+};
+
+uint64_t crc64(const char *string);
+struct hash_table *hash_init(void);
+void *hash_find(struct hash_table *head, const char *string,
+		struct hash_insert *insert);
+void hash_add(struct hash_insert *insert, const char *string, void *data);
+void hash_free(struct hash_table *head, void (*free_func)(char *, void *));
+
+#endif /* NASM_HASHTBL_H */