Genesis commit

1 files changed, 290 insertions, 0 deletions

diff --git a/src/gehashmap.h b/src/gehashmap.h
new file mode 100644
index 0000000..1f7048c
--- /dev/null
+++ b/src/gehashmap.h
@@ -0,0 +1,290 @@
+/* Include guard */
+
+#ifndef GEHASHMAP_H
+#define GEHASHMAP_H
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+/* GEHASHMAP_INITIAL_SIZE is the initial capacity in items that a newly created
+ * hashmap can hold.  GEHASHMAP_LOAD_FACTOR is the % of the hashmap that can be
+ * filled before we resize it to hold more items.
+ */
+#define GEHASHMAP_INITIAL_SIZE 16
+#define GEHASHMAP_LOAD_FACTOR  0.75
+
+/* As a result of preprocessor _stuff_, we need 2 macros to properly concatinate
+ * things as we would expect.  GEHASHMAP_CONCAT() is what we use when we want to
+ * concatinate things, so GEHASHMAP_CONCAT(GEHASHMAP_INITIAL_SIZE, f) would give
+ * us “16f”.  GEHASHMAP_FUNC_NAME() gives us function names, so
+ * GEHASHMAP_FUNC_NAME(put) gives us the name of the function to put new items
+ * into the current hashmap.
+ */
+#define GEHASHMAP_CONCAT_HELPER(x, y) x ## y
+#define GEHASHMAP_CONCAT(x, y)        GEHASHMAP_CONCAT_HELPER(x, y)
+#define GEHASHMAP_FUNC_NAME(x)        GEHASHMAP_CONCAT(GEHASHMAP_NAME, _ ## x)
+
+#endif /* !GEHASHMAP_H */
+
+
+
+/* The type of the hashmap keys */
+#ifndef GEHASHMAP_KEY_T
+	#error "Type for the hashmap key was not set"
+#endif
+
+/* The type of the hashmap values */
+#ifndef GEHASHMAP_VAL_T
+	#error "Type for the hashmap value was not set"
+#endif
+
+/* The name of the hashmap.  If set to “foo” then the resulting hashmap type
+ * name would be “foo_t” and the get function would be called “foo_get()”.
+ */
+#ifndef GEHASHMAP_NAME
+	#error "Name for the hashmap type was not set"
+#endif
+
+/* The key comparison function.  This function should have the following
+ * signature:
+ *
+ *     int function_name(GEHASHMAP_KEY_T, GEHASHMAP_KEY_T);
+ *
+ * If the two keys are the same, this function should return 0.  This is to stay
+ * compatible with the strcmp() function.
+ */
+#ifndef GEHASHMAP_CMP_FUNC
+	#error "Comparison function for the hashmap key was not set"
+#endif
+
+/* The key hashing function.  This function should have the following signature:
+ *
+ *     size_t function_name(GEHASHMAP_KEY_T);
+ *
+ * This function should return a hash of the given key.  It is used for indexing
+ * the hashmap.
+ */
+#ifndef GEHASHMAP_HASH_FUNC
+	#error "Hashing function for the hashmap key was not set"
+#endif
+
+/* The key freeing function.  This function should have the following signature:
+ *
+ *     void function_name(GEHASHMAP_KEY_T);
+ *
+ * This function should free the given key, just like the free() function.  This
+ * is used when destroying a hashmap.  If you use a hashmap key that doesn’t
+ * need freeing (like integers) you probably just want to make this a function
+ * that does nothing.
+ */
+#ifndef GEHASHMAP_FREE_FUNC
+	#error "Freeing function for the hashmap key was not set"
+#endif
+
+/* GEHASHMAP_ENTRY_T is the type representing entries in the hashmap while
+ * GEHASHMAP_T is the type representing the hashmap itself.  If GEHASHMAP_NAME
+ * is set to “foo” then GEHASHMAP_ENTRY_T will be “struct foo_entry” and
+ * GEHASHMAP_T will be “foo_t”.
+ */
+#define GEHASHMAP_ENTRY_T GEHASHMAP_CONCAT(struct GEHASHMAP_NAME, _entry)
+#define GEHASHMAP_T       GEHASHMAP_CONCAT(GEHASHMAP_NAME, _t)
+
+/* A hashmap entry */
+GEHASHMAP_ENTRY_T {
+	GEHASHMAP_KEY_T    key;   /* This entries key */
+	GEHASHMAP_VAL_T    val;   /* This entries value */
+	GEHASHMAP_ENTRY_T *next;  /* Pointer to the next entry */
+};
+
+/* The hashmap */
+typedef struct {
+	size_t              size;      /* The number of elements */
+	size_t              capacity;  /* The capacity of the hashmap */
+	GEHASHMAP_ENTRY_T **entries;   /* A 2D array of hashmap entries */
+} GEHASHMAP_T;
+
+int    (*gehashmap_cmp_func)(GEHASHMAP_KEY_T,
+                             GEHASHMAP_KEY_T)  = GEHASHMAP_CMP_FUNC;
+void   (*gehashmap_free_func)(GEHASHMAP_KEY_T) = GEHASHMAP_FREE_FUNC;
+size_t (*gehashmap_hash_func)(GEHASHMAP_KEY_T) = GEHASHMAP_HASH_FUNC;
+
+/* Function to initialize a new hashmap.  Allocation of the hashmap is left up
+ * to the library user.  On error -1 is returned, otherwise 0 is returned.
+ */
+int
+GEHASHMAP_FUNC_NAME(new)(GEHASHMAP_T *map)
+{
+	*map = (GEHASHMAP_T) {
+		.size     = 0,
+		.capacity = GEHASHMAP_INITIAL_SIZE,
+		.entries  = calloc(GEHASHMAP_INITIAL_SIZE,
+		                   sizeof(GEHASHMAP_ENTRY_T *))
+	};
+	return map->entries == NULL ? -1 : 0;
+}
+
+/* Function to destroy a hashmap */
+void
+GEHASHMAP_FUNC_NAME(free)(GEHASHMAP_T *map)
+{
+	for (size_t i = 0; i < map->capacity; i++) {
+		GEHASHMAP_ENTRY_T *entry = map->entries[i];
+		while (entry != NULL) {
+			GEHASHMAP_ENTRY_T *next = entry->next;
+			gehashmap_free_func(entry->key);
+			free(entry);
+			entry = next;
+		}
+	}
+	free(map->entries);
+}
+
+/* Function to resize a hashmap.  This function should not really be touched by
+ * the library user basically ever.  On error -1 is returned, otherwise 0 is
+ * returned.
+ */
+int
+GEHASHMAP_FUNC_NAME(resize)(GEHASHMAP_T *map, size_t new_capacity)
+{
+	GEHASHMAP_ENTRY_T **new_entries = calloc(new_capacity,
+	                                         sizeof(GEHASHMAP_ENTRY_T *));
+	if (new_entries == NULL)
+		return -1;
+
+	for (size_t i = 0; i < map->capacity; i++) {
+		GEHASHMAP_ENTRY_T *entry = map->entries[i];
+		while (entry != NULL) {
+			GEHASHMAP_ENTRY_T *next = entry->next;
+			size_t hash = gehashmap_hash_func(entry->key)
+			              % new_capacity;
+			entry->next = new_entries[hash];
+			new_entries[hash] = entry;
+			entry = next;
+		}
+	}
+
+	free(map->entries);
+	map->entries = new_entries;
+	map->capacity = new_capacity;
+
+	return 0;
+}
+
+/* Function to put a key/value pair into a hashmap.  The key is put into the
+ * hashmap as is, so the user may need to allocate the key themselves if a stack
+ * allocated key is not appropriate.  On error -1 is returned, otherwise 0 is
+ * returned.
+ */
+int
+GEHASHMAP_FUNC_NAME(put)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key,
+                                           GEHASHMAP_VAL_T val)
+{
+	size_t hash;
+	GEHASHMAP_ENTRY_T *entry;
+
+	if (map->size + 1 > map->capacity * GEHASHMAP_LOAD_FACTOR) {
+		if (GEHASHMAP_FUNC_NAME(resize)(map, map->capacity * 2) == -1)
+			return -1;
+	}
+
+	hash = gehashmap_hash_func(key) % map->capacity;
+	entry = map->entries[hash];
+	while (entry != NULL) {
+		if (gehashmap_cmp_func(entry->key, key) == 0) {
+			entry->val = val;
+			return 0;
+		}
+		entry = entry->next;
+	}
+
+	if ((entry = malloc(sizeof(GEHASHMAP_ENTRY_T))) == NULL)
+		return -1;
+
+	entry->key = key;
+	entry->val = val;
+	entry->next = map->entries[hash];
+	map->entries[hash] = entry;
+	map->size++;
+
+	return 0;
+}
+
+/* Function to get an element from the hashmap.  If “val” is NULL then no value
+ * will be retrieved.  If an element with the given key is found in the hashmap
+ * the function returns true, otherwise false is returned.
+ */
+bool
+GEHASHMAP_FUNC_NAME(get)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key,
+                                           GEHASHMAP_VAL_T *val)
+{
+	size_t hash = gehashmap_hash_func(key) % map->capacity;
+	GEHASHMAP_ENTRY_T *entry = map->entries[hash];
+
+	while (entry != NULL) {
+		if (gehashmap_cmp_func(entry->key, key) == 0) {
+			if (val != NULL)
+				*val = entry->val;
+			return true;
+		}
+		entry = entry->next;
+	}
+
+	return false;
+}
+
+/* Function to check if an element with a given key is contained within a
+ * hashmap.  This is just a more readable wrapper around the get() function that
+ * passes NULL as the last argument.
+ */
+static inline bool
+GEHASHMAP_FUNC_NAME(has)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key)
+{
+	return GEHASHMAP_FUNC_NAME(get)(map, key, NULL);
+}
+
+/* Function to remove an element with a given key from a hashmap.  If the value
+ * was dynamically allocated it will not be freed.  The key will be freed
+ * however as per gehashmap_free_func().  On error -1 is returned, otherwise 0
+ * is returned.
+ */
+int
+GEHASHMAP_FUNC_NAME(remove)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key)
+{
+	size_t hash = gehashmap_hash_func(key) % map->capacity;
+	GEHASHMAP_ENTRY_T *entry;
+
+	if ((entry = map->entries[hash]) == NULL)
+		return -1;
+
+	if (gehashmap_cmp_func(entry->key, key) == 0) {
+		map->entries[hash] = entry->next;
+		gehashmap_free_func(entry->key);
+		free(entry);
+		map->size--;
+		return 0;
+	}
+
+	while (entry->next != NULL) {
+		if (gehashmap_cmp_func(entry->next->key, key) == 0) {
+			GEHASHMAP_ENTRY_T *next = entry->next;
+			entry->next = next->next;
+			gehashmap_free_func(next->key);
+			free(next);
+			map->size--;
+			return 0;
+		}
+		entry = entry->next;
+	}
+
+	return -1;
+}
+
+/* Undefine everything */
+#undef GEHASHMAP_KEY_T
+#undef GEHASHMAP_VAL_T
+#undef GEHASHMAP_NAME
+#undef GEHASHMAP_CMP_FUNC
+#undef GEHASHMAP_HASH_FUNC
+#undef GEHASHMAP_FREE_FUNC
+#undef GEHASHMAP_ENTRY_T
+#undef GEHASHMAP_T