1 files changed, 113 insertions, 0 deletions
diff --git a/plugins/static/hashtable.h b/plugins/static/hashtable.h
new file mode 100644
index 0000000..670eac6
--- /dev/null
+++ b/plugins/static/hashtable.h
@@ -0,0 +1,113 @@
+#pragma once
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "memory.h"
+
+
+inline size_t string_hash_func(const char *key) {
+	size_t h = 0;
+	for (; *key; key++) h = ((h << 9) | (h >> (64 - 9))) ^ *key;
+	return h;
+}
+
+// API:
+//  table prefix_make()
+//  void prefix_destroy(table)
+//  value* prefix_find(table*, const char *key)
+//  void prefix_insert(table*, const char *key, value)
+//  bool prefix_erase(table*, const char *key)
+#define HASHTABLE_DEFINE(prefix_, value_t_) \
+	struct prefix_ ## internal_table_entry { \
+		char *key; \
+		value_t_ value; \
+	}; \
+	\
+	struct prefix_ ## table { \
+		size_t size, load; /* size is always a power of 2 */ \
+		struct prefix_ ## internal_table_entry *values; \
+	}; \
+	\
+	struct prefix_ ## table prefix_ ## make(void) { \
+		struct prefix_ ## table ht; \
+		ht.size = 8; \
+		ht.load = 0; \
+		ht.values = malloc(ht.size, struct prefix_ ## internal_table_entry); \
+		for (size_t i = 0; i < ht.size; i++) ht.values[i].key = NULL; \
+		return ht; \
+	} \
+	\
+	void prefix_ ## destroy(struct prefix_ ## table ht) { \
+		for (size_t i = 0; i < ht.size; i++) free(ht.values[i].key); \
+		free(ht.values); \
+	} \
+	\
+	size_t prefix_ ## internal_probe_index(const struct prefix_ ## table *ht, const char *key) { \
+		size_t h = string_hash_func(key) % ht->size; \
+		for (size_t i = 0; i < ht->size; i++) { \
+			if (!ht->values[h].key || strcmp(ht->values[h].key, key) == 0) return h; \
+			h = (h + i) % ht->size;  /* quadratic probing with index h + 1/2 i + 1/2 i^2 */ \
+		} \
+		assert(false);  /* cannot happen unless the table is full, which we don't allow */ \
+	} \
+	\
+	void prefix_ ## internal_grow_table(struct prefix_ ## table *ht); \
+	\
+	/* Returns pointer to value in table */ \
+	value_t_* prefix_ ## find(struct prefix_ ## table *ht, const char *key) { \
+		size_t idx = prefix_ ## internal_probe_index(ht, key); \
+		if (ht->values[idx].key) return &ht->values[idx].value; \
+		return NULL; \
+	} \
+	\
+	/* Overwrites the existing value if already present */ \
+	void prefix_ ## insert_nostrdup(struct prefix_ ## table *ht, char *key, value_t_ value) { \
+		fprintf(stderr, "HT insert nostrdup load=%zu size=%zu\n", ht->load, ht->size); \
+		if (ht->load * 4 >= ht->size * 3) prefix_ ## internal_grow_table(ht); \
+		size_t idx = prefix_ ## internal_probe_index(ht, key); \
+		if (!ht->values[idx].key) { \
+			ht->values[idx].key = key; \
+			ht->load++; \
+		} \
+		ht->values[idx].value = value; \
+	} \
+	\
+	/* Overwrites the existing value if already present */ \
+	void prefix_ ## insert(struct prefix_ ## table *ht, const char *key, value_t_ value) { \
+		fprintf(stderr, "HT insert load=%zu size=%zu\n", ht->load, ht->size); \
+		if (ht->load * 4 >= ht->size * 3) prefix_ ## internal_grow_table(ht); \
+		size_t idx = prefix_ ## internal_probe_index(ht, key); \
+		if (!ht->values[idx].key) { \
+			ht->values[idx].key = strdup(key); \
+			ht->load++; \
+		} \
+		ht->values[idx].value = value; \
+	} \
+	\
+	/* Returns whether the element was indeed present */ \
+	bool prefix_ ## erase(struct prefix_ ## table *ht, const char *key) { \
+		size_t idx = prefix_ ## internal_probe_index(ht, key); \
+		if (!ht->values[idx].key) return false; \
+		free(ht->values[idx].key); \
+		ht->values[idx].key = NULL; \
+		ht->load--; \
+		fprintf(stderr, "HT erase, afterwards load=%zu size=%zu\n", ht->load, ht->size); \
+		return true; \
+	} \
+	\
+	void prefix_ ## internal_grow_table(struct prefix_ ## table *ht) { \
+		fprintf(stderr, "HT grow load=%zu size=%zu\n", ht->load, ht->size); \
+		assert(ht->size * 2 != 0); \
+		struct prefix_ ## table ht2; \
+		ht2.size = ht->size * 2; \
+		ht2.load = 0; \
+		ht2.values = malloc(ht2.size, struct prefix_ ## internal_table_entry); \
+		for (size_t i = 0; i < ht2.size; i++) ht2.values[i].key = NULL; \
+		for (size_t i = 0; i < ht->size; i++) { \
+			if (ht->values[i].key) prefix_ ## insert_nostrdup(&ht2, ht->values[i].key, ht->values[i].value); \
+		} \
+		free(ht->values); \
+		*ht = ht2; \
+	}