summaryrefslogtreecommitdiff
path: root/src/gehashmap.h
diff options
context:
space:
mode:
authorThomas Voss <mail@thomasvoss.com> 2022-12-21 23:14:57 +0100
committerThomas Voss <mail@thomasvoss.com> 2022-12-21 23:14:57 +0100
commit9baa39e871c2ed9934e3e1c381f3f38927346bf6 (patch)
treea2eb3d2943719a70242d27b133c39e1dcb8ee088 /src/gehashmap.h
Genesis commit
Diffstat (limited to 'src/gehashmap.h')
-rw-r--r--src/gehashmap.h290
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