1 files changed, 215 insertions, 0 deletions
diff --git a/utils/hashmap.c b/utils/hashmap.c
new file mode 100644
index 000000000..7ed19946b
--- /dev/null
+++ b/utils/hashmap.c
@@ -0,0 +1,215 @@
+/*
+ * Copyright 2020 Daniel Silverstone <dsilvers@netsurf-browser.org>
+ *
+ * This file is part of NetSurf, http://www.netsurf-browser.org/
+ *
+ * NetSurf is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; version 2 of the License.
+ *
+ * NetSurf is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "utils/hashmap.h"
+
+/**
+ * The default number of buckets in the hashmaps we create.
+ */
+#define DEFAULT_HASHMAP_BUCKETS (4091)
+
+/**
+ * Hashmaps have chains of entries in buckets.
+ */
+typedef struct hashmap_entry_s {
+	struct hashmap_entry_s **prevptr;
+	struct hashmap_entry_s *next;
+	void *key;
+	void *value;
+	uint32_t key_hash;
+} hashmap_entry_t;
+
+/**
+ * The content of a hashmap
+ */
+struct hashmap_s {
+	/**
+	 * The parameters to be used for this hashmap
+	 */
+	hashmap_parameters_t *params;
+	
+	/**
+	 * The buckets for the hash chains
+	 */
+	hashmap_entry_t **buckets;
+	
+	/**
+	 * The number of buckets in this map
+	 */
+	uint32_t bucket_count;
+};
+
+/* Exported function, documented in hashmap.h */
+hashmap_t *
+hashmap_create(hashmap_parameters_t *params)
+{
+	hashmap_t *ret = malloc(sizeof(hashmap_t));
+
+	ret->params = params;
+	ret->bucket_count = DEFAULT_HASHMAP_BUCKETS;
+	ret->buckets = malloc(ret->bucket_count * sizeof(hashmap_entry_t *));
+	memset(ret->buckets, 0, ret->bucket_count * sizeof(hashmap_entry_t *));
+
+	if (ret->buckets == NULL) {
+		free(ret);
+		return NULL;
+	}
+	
+	return ret;
+}
+
+/* Exported function, documented in hashmap.h */
+void
+hashmap_destroy(hashmap_t *hashmap)
+{
+	uint32_t bucket;
+	hashmap_entry_t *entry;
+
+	for (bucket = 0; bucket < hashmap->bucket_count; bucket++) {
+		for (entry = hashmap->buckets[bucket];
+		     entry != NULL;
+		     entry = entry->next) {
+			hashmap->params->value_destroy(entry->value);
+			hashmap->params->key_destroy(entry->key);
+			free(entry);
+		}
+	}
+
+	free(hashmap->buckets);
+	free(hashmap);
+}
+
+/* Exported function, documented in hashmap.h */
+void *
+hashmap_lookup(hashmap_t *hashmap, void *key)
+{
+	uint32_t hash = hashmap->params->key_hash(key);
+	hashmap_entry_t *entry = hashmap->buckets[hash % hashmap->bucket_count];
+
+	for(;entry != NULL; entry = entry->next) {
+		if (entry->key_hash == hash) {
+			if (hashmap->params->key_eq(key, entry->key)) {
+				return entry->value;
+			}
+		}
+	}
+
+	return NULL;
+}
+
+/* Exported function, documented in hashmap.h */
+void *
+hashmap_insert(hashmap_t *hashmap, void *key)
+{
+	uint32_t hash = hashmap->params->key_hash(key);
+	uint32_t bucket = hash % hashmap->bucket_count;
+	hashmap_entry_t *entry = hashmap->buckets[bucket];
+	void *new_key, *new_value;
+
+	for(;entry != NULL; entry = entry->next) {
+		if (entry->key_hash == hash) {
+			if (hashmap->params->key_eq(key, entry->key)) {
+				/* This key is already here */
+				new_key = hashmap->params->key_clone(key);
+				if (new_key == NULL) {
+					/* Allocation failed */
+					return NULL;
+				}
+				new_value = hashmap->params->value_alloc(entry->key);
+				if (new_value == NULL) {
+					/* Allocation failed */
+					hashmap->params->key_destroy(new_key);
+					return NULL;
+				}
+				hashmap->params->value_destroy(entry->value);
+				hashmap->params->key_destroy(entry->key);
+				entry->value = new_value;
+				entry->key = new_key;
+				return entry->value;
+			}
+		}
+	}
+
+	/* The key was not found in the map, so allocate a new entry */
+	entry = malloc(sizeof(*entry));
+
+	if (entry == NULL) {
+		return NULL;
+	}
+	
+	memset(entry, 0, sizeof(*entry));
+
+	entry->key = hashmap->params->key_clone(key);
+	if (entry->key == NULL) {
+		goto err;
+	}
+	entry->key_hash = hash;
+
+	entry->value = hashmap->params->value_alloc(entry->key);
+	if (entry->value == NULL) {
+		goto err;
+	}
+
+	entry->prevptr = &(hashmap->buckets[bucket]);
+	entry->next = hashmap->buckets[bucket];
+	if (entry->next != NULL) {
+		entry->next->prevptr = &entry->next;
+	}
+
+	hashmap->buckets[bucket] = entry;
+	
+	return entry->value;
+
+err:
+	if (entry->value != NULL)
+		hashmap->params->value_destroy(entry->value);
+	if (entry->key != NULL)
+		hashmap->params->key_destroy(entry->key);
+	free(entry);
+
+	return NULL;
+}
+
+/* Exported function, documented in hashmap.h */
+bool
+hashmap_remove(hashmap_t *hashmap, void *key)
+{
+	uint32_t hash = hashmap->params->key_hash(key);
+	
+	hashmap_entry_t *entry = hashmap->buckets[hash % hashmap->bucket_count];
+
+	for(;entry != NULL; entry = entry->next) {
+		if (entry->key_hash == hash) {
+			if (hashmap->params->key_eq(key, entry->key)) {
+				hashmap->params->value_destroy(entry->value);
+				hashmap->params->key_destroy(entry->key);
+				if (entry->next != NULL) {
+					entry->next->prevptr = entry->prevptr;
+				}
+				*entry->prevptr = entry->next;
+				free(entry);
+				return true;
+			}
+		}
+	}
+
+	return false;
+}