use hashmap for compound tag

1 files changed, 86 insertions, 0 deletions

diff --git a/src/map.c b/src/map.c
new file mode 100644
index 0000000..0c6d4f2
--- /dev/null
+++ b/src/map.c
@@ -0,0 +1,86 @@
+#include "map.h"
+#include "lib.h"
+#include "tag.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+void map_init(map_t *map) {
+	map->len = 0;
+	map->capacity = 0;
+	map->entries = NULL;
+}
+
+void map_free(map_t *map) {
+	if (map->entries == NULL)
+		return;
+	for (uint32_t i = 0; i < map->capacity; i++) {
+		if (map->entries[i].name != NULL)
+			tag_free(&map->entries[i]);
+	}
+	free(map->entries);
+}
+
+static uint32_t hash(const char *name, uint16_t len) {
+    uint32_t hash = 2166136261u;
+    while(len > 0) {
+        hash ^= (uint8_t)(*name);
+        hash *= 16777619;
+        name++;
+		len--;
+    }
+    return hash;
+}
+
+static tag_t *map_find(tag_t *entries, uint32_t capacity, tag_t *tag) {
+	uint32_t index = hash(tag->name, tag->name_len) % capacity;
+	while(true) {
+		tag_t *entry = &entries[index];
+		if (entry->name == NULL) {
+			return entry;
+		} else if (
+			entry->name_len == tag->name_len && 
+			memcmp(entry->name, tag->name, tag->name_len) == 0
+		) {
+			return entry;
+		}
+		index += 1;
+		index %= capacity;
+	}
+}
+
+static void map_grow(map_t *map, uint32_t capacity) {
+	tag_t *entries = xzalloc(capacity * sizeof(tag_t));
+	for (uint32_t i = 0; i < capacity; i++) {
+		entries[i].name = NULL;
+		entries[i].name_len = 0;
+	}
+	map->len = 0;
+	for (uint32_t i = 0; i < map->capacity; i++) {
+		tag_t *tag = &map->entries[i];
+		if (tag->name == NULL) continue;
+
+		tag_t *dest = map_find(entries, capacity, tag);
+		*dest = *tag;
+		map->len++;
+	}
+	free(map->entries);
+
+	map->entries = entries;
+	map->capacity = capacity;
+}
+
+void map_put(map_t *map, tag_t *tag) {
+	if (map->len + 1 > map->capacity * 0.75) {
+		int capacity = (map->capacity == 0 ? 8 : (2 * map->capacity));
+		map_grow(map, capacity);
+	}
+	tag_t *dest = map_find(map->entries, map->capacity, tag);
+	if (dest->name == NULL) {
+		map->len++;
+	} else {
+		tag_free(dest);
+	}
+	*dest = *tag;
+}