use hashmap for compound tag

10 files changed, 151 insertions, 60 deletions

diff --git a/src/json/print.c b/src/json/print.c
index 97ccce8..9f2931f 100644
--- a/src/json/print.c
+++ b/src/json/print.c
@@ -68,7 +68,7 @@ static bool json_print_long_array(const tagdata_t *data, const stream_t *stream)
 }
 
 static bool json_print_string(const tagdata_t *data, const stream_t *stream) {
-	if (data->string.size > 1) {
+	if (data->string.size > 0) {
 		if (printi(stream, 0, "\"%.*s\"", data->string.size, data->string.data) == false)
 			return false;
 	} else {
@@ -81,10 +81,14 @@ static bool json_print_string(const tagdata_t *data, const stream_t *stream) {
 static bool json_print_compound(const tagdata_t *data, const stream_t *stream, int depth) {
 	if (printi(stream, 0, "{\n") == false)
 		return false;
-	for (int32_t i = 0; i < data->compound.size; i++) {
-		if (i != 0 && printi(stream, 0, ",\n") == false)
+	bool first = true;
+	for (uint32_t i = 0; i < data->compound.capacity; i++) {
+		if (data->compound.entries[i].name == NULL)
+			continue;
+		if (!first && printi(stream, 0, ",\n") == false)
 			return false;
-		if (json_print_impl(&data->compound.tags[i], stream, depth + 1) == false)
+		first = false;
+		if (json_print_impl(&data->compound.entries[i], stream, depth + 1) == false)
 			return false;
 	}
 	if (printi(stream, 0, "\n") == false || printi(stream, depth, "}") == false)
diff --git a/src/json/read.c b/src/json/read.c
index ea6e106..50a5fd1 100644
--- a/src/json/read.c
+++ b/src/json/read.c
@@ -498,7 +498,10 @@ static bool json_read_list(tagdata_t *data, const stream_t *stream) {
 }
 
 static bool json_read_compound(tagdata_t *data, const stream_t *stream) {
-	
+
+	map_t map;
+	map_init(&map);
+
 	token_t next = {0};
 	if (json_next_token(&next, stream) == false) {
 		json_token_free(&next);
@@ -506,19 +509,14 @@ static bool json_read_compound(tagdata_t *data, const stream_t *stream) {
 	}
 
 	if (next.type == TOK_RBRACE) {
-		data->compound.tags = NULL;
-		data->compound.size = 0;
+		data->compound = map;
 		return true;
 	}
 
-	int capacity = 8;
-	int len = 0;
-	tag_t *tags = xalloc(capacity * sizeof(tag_t));
-
 	while (1) {
 
 		if (next.type != TOK_STRING) {
-			free(tags);
+			map_free(&map);
 			json_token_free(&next);
 			return false;
 		}
@@ -527,20 +525,20 @@ static bool json_read_compound(tagdata_t *data, const stream_t *stream) {
 		int name_len = next.data.string.len;
 
 		if (name_len < 1) {
-			free(tags);
+			map_free(&map);
 			free(name);
 			return false;
 		}
 		
 		if (json_next_token(&next, stream) == false || next.type != TOK_COLON) {
-			free(tags);
+			map_free(&map);
 			free(name);
 			return false;
 		}
 		
 		tag_t value;
 		if (json_read_value(&value, stream, NULL) == false) {
-			free(tags);
+			map_free(&map);
 			free(name);
 			return false;
 		}
@@ -548,42 +546,31 @@ static bool json_read_compound(tagdata_t *data, const stream_t *stream) {
 		value.name = name;
 		value.name_len = name_len;
 
-		if (len == capacity) {
-			capacity *= 2;
-			tags = xrealloc(tags, capacity * sizeof(tag_t));
-		}
-
-		tags[len++] = value;
+		map_put(&map, &value);
 
 		if (json_next_token(&next, stream) == false) {
-			free(tags);
-			free(value.name);
+			map_free(&map);
 			json_token_free(&next);
 			return false;
 		}
 
 		if (next.type == TOK_COMMA) {
 			if (json_next_token(&next, stream) == false) {
-				free(tags);
-				free(name);
+				map_free(&map);
 				return false;
 			}
 			continue;
 		} else if (next.type == TOK_RBRACE) {
 			break;
 		} else {
-			free(tags);
-			free(value.name);
+			map_free(&map);
 			json_token_free(&next);
 			return false;
 		}
 
 	}
 
-	data->compound.tags = xalloc(len * sizeof(tag_t));
-	data->compound.size = len;
-	memcpy(data->compound.tags, tags, len * sizeof(tag_t));
-	free(tags);
+	data->compound = map;
 
 	return true;
 }
diff --git a/src/lib.c b/src/lib.c
index 7f077ba..e6e691a 100644
--- a/src/lib.c
+++ b/src/lib.c
@@ -3,6 +3,7 @@
 #include <stdarg.h>
 #include <stdio.h>
 #include <stdlib.h>
+#include <string.h>
 
 __attribute__((__noreturn__))
 static void die() {
@@ -36,6 +37,12 @@ void *xalloc(size_t amount) {
 	return res;
 }
 
+void *xzalloc(size_t amount) {
+	void *res = xalloc(amount);
+	memset(res, 0, sizeof(amount));
+	return res;
+}
+
 void *xrealloc(void *ptr, size_t amount) {
 	void *res = realloc(ptr, amount);
 	if (res == NULL)
diff --git a/src/lib.h b/src/lib.h
index c007187..35cbc3c 100644
--- a/src/lib.h
+++ b/src/lib.h
@@ -9,4 +9,5 @@ __attribute__((__noreturn__, format(printf, 1, 2)))
 void perror_and_die(char *format, ...);
 
 void *xalloc(size_t amount);
+void *xzalloc(size_t amount);
 void *xrealloc(void *ptr, size_t amount);
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;
+}
diff --git a/src/map.h b/src/map.h
new file mode 100644
index 0000000..6672323
--- /dev/null
+++ b/src/map.h
@@ -0,0 +1,15 @@
+#pragma once
+
+#include <stdint.h>
+
+typedef struct tag_t tag_t;
+
+typedef struct {
+	uint32_t len;
+	uint32_t capacity;
+	tag_t *entries;
+} map_t;
+
+void map_init(map_t *map);
+void map_free(map_t *map);
+void map_put(map_t *map, tag_t *tag);
diff --git a/src/nbt/print.c b/src/nbt/print.c
index 4eac31f..3f687dc 100644
--- a/src/nbt/print.c
+++ b/src/nbt/print.c
@@ -64,9 +64,11 @@ static bool nbt_print_list(const tagdata_t *data, const stream_t *stream) {
 }
 
 static bool nbt_print_compound(const tagdata_t *data, const stream_t *stream) {
-	for (int32_t i = 0; i < data->compound.size; i++)
-		if (nbt_print(&data->compound.tags[i], stream) == false)
+	for (uint32_t i = 0; i < data->compound.capacity; i++) {
+		if (data->compound.entries[i].name == NULL) continue;
+		if (nbt_print(&data->compound.entries[i], stream) == false)
 			return false;
+	}
 	if (stream_write_i8(stream, TAG_END) == false)
 		return false;
 	return true;
diff --git a/src/nbt/read.c b/src/nbt/read.c
index cef04ca..38f8b14 100644
--- a/src/nbt/read.c
+++ b/src/nbt/read.c
@@ -118,44 +118,36 @@ static bool nbt_read_list(tagdata_t *data, const stream_t *stream) {
 }
 
 static bool nbt_read_compound(tagdata_t *data, const stream_t *stream) {
-	int32_t size = 0;
-	int32_t capacity = 8;
-	tag_t *tags = xalloc(capacity * sizeof(tag_t));
+
+	map_t map;
+	map_init(&map);
 
 	while (1) {
 
 		tag_t tag;
 
 		if (nbt_read_header(&tag, stream, true) == false) {
-			free(tags);
+			map_free(&map);
 			return false;
 		}
-
+		
+		if (tag.type == TAG_END)
+			break;
+		
 		if (tag.name_len < 1) {
-			free(tags);
+			map_free(&map);
 			return false;
 		}
 
-		if (tag.type == TAG_END)
-			break;
-
 		if (nbt_read_data(&tag, stream) == false) {
-			free(tags);
+			map_free(&map);
 			return false;
 		}
-		
-		if (size == capacity) {
-			capacity *= 2;
-			tags = xrealloc(tags, capacity * sizeof(tag_t));
-		}
 
-		tags[size++] = tag;
+		map_put(&map, &tag);
 	}
 
-	data->compound.size = size;
-	data->compound.tags = xalloc(size * sizeof(tag_t));
-	memcpy(data->compound.tags, tags, size * sizeof(tag_t));
-	free(tags);
+	data->compound = map;
 
 	return true;
 }
diff --git a/src/tag.c b/src/tag.c
index 25d9d32..d704b13 100644
--- a/src/tag.c
+++ b/src/tag.c
@@ -1,4 +1,5 @@
 #include "tag.h"
+#include "map.h"
 #include "nbt/nbt.h"
 #include "json/json.h"
 
@@ -28,9 +29,7 @@ void tag_free(tag_t *tag) {
 			free(tag->data.list.tags);
 			break;
         case TAG_COMPOUND:
-			for (int32_t i = 0; i < tag->data.compound.size; i++)
-				tag_free(&tag->data.compound.tags[i]);
-			free(tag->data.compound.tags);
+			map_free(&tag->data.compound);
 			break;
         case TAG_INT_ARRAY:
 			free(tag->data.i_arr.data);
diff --git a/src/tag.h b/src/tag.h
index d0033a5..81d1950 100644
--- a/src/tag.h
+++ b/src/tag.h
@@ -1,6 +1,7 @@
 #pragma once 
 
 #include "stream.h"
+#include "map.h"
 
 #include <stdint.h>
 #include <stdbool.h>
@@ -46,10 +47,7 @@ typedef union {
 		int32_t size;
 		struct tag_t *tags;
 	} list;
-	struct {
-		int32_t size;
-		struct tag_t *tags;
-	} compound;
+	map_t compound;
 	struct {
 		int32_t size;
 		int32_t *data;