Genesis commit

7 files changed, 372 insertions, 0 deletions

diff --git a/.gitignore b/.gitignore
new file mode 100644
index 0000000..1844d93
--- /dev/null
+++ b/.gitignore
@@ -0,0 +1,3 @@
+examples/*
+!examples/Makefile
+!examples/*.c
diff --git a/LICENSE b/LICENSE
new file mode 100644
index 0000000..6117b2a
--- /dev/null
+++ b/LICENSE
@@ -0,0 +1,14 @@
+BSD Zero Clause License
+
+Copyright (c) 2022 Thomas Voss
+
+Permission to use, copy, modify, and/or distribute this software for any
+purpose with or without fee is hereby granted.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
+AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
+LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
+OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
+PERFORMANCE OF THIS SOFTWARE.
diff --git a/Makefile b/Makefile
new file mode 100644
index 0000000..b89064d
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,16 @@
+.POSIX:
+
+PREFIX  = /usr/local
+DPREFIX = ${DESTDIR}${PREFIX}
+MANDIR  = ${DPREFIX}/share/man
+
+GDIR = /usr/share/groff/site-tmac
+DGDIR = ${DESTDIR}${GDIR}
+
+install:
+	mkdir -p ${DPREFIX}/include ${DGDIR}
+	cp src/gehashmap.h ${DPREFIX}/include
+	#cp man/*.3 ${MANDIR}/man3
+	#cp man/*.3head ${MANDIR}/man3head
+	#sed '/^\.ds doc-str-Lb-liblux/d' ${GDIR}/mdoc.local >${DGDIR}/mdoc.local
+	#grep -v '^\.\\"' man/Lb-desc.tmac >>${DGDIR}/mdoc.local
diff --git a/examples/Makefile b/examples/Makefile
new file mode 100644
index 0000000..0d87a45
--- /dev/null
+++ b/examples/Makefile
@@ -0,0 +1,2 @@
+all:
+	cc -Og -g -ggdb gehashmap.c -o gehashmap
diff --git a/examples/gehashmap.c b/examples/gehashmap.c
new file mode 100644
index 0000000..f216d00
--- /dev/null
+++ b/examples/gehashmap.c
@@ -0,0 +1,42 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+size_t hash(char *);
+
+#define GEHASHMAP_NAME funmap
+#define GEHASHMAP_KEY_T char *
+#define GEHASHMAP_VAL_T int
+#define GEHASHMAP_CMP_FUNC  (int  (*)(char *, char *)) strcmp
+#define GEHASHMAP_FREE_FUNC (void (*)(char *)) free
+#define GEHASHMAP_HASH_FUNC hash
+#include <gehashmap.h>
+
+size_t
+hash(char *s)
+{
+	char c;
+	size_t x = 5381;
+
+	while (c = *s++)
+		x = ((x << 5) + x) + c;
+
+	return x;
+}
+
+int
+main(void)
+{
+	int n;
+	funmap_t *map;
+
+	funmap_new(map = malloc(sizeof(funmap_t)));
+	funmap_put(map, strdup("Thomas Voß"),  5);
+	funmap_put(map, strdup("THOMAS VOẞ"),  6);
+	funmap_put(map, strdup("Thomas Voss"), 7);
+	funmap_get(map, "Thomas Voß",  &n); printf("Thomas Voß  -> ‚%d‘\n", n);
+	funmap_get(map, "THOMAS VOẞ",  &n); printf("THOMAS VOẞ  -> ‚%d‘\n", n);
+	funmap_get(map, "Thomas Voss", &n); printf("Thomas Voss -> ‚%d‘\n", n);
+	funmap_free(map);
+	free(map);
+}
diff --git a/man/Lb-desc.tmac b/man/Lb-desc.tmac
new file mode 100644
index 0000000..5393d37
--- /dev/null
+++ b/man/Lb-desc.tmac
@@ -0,0 +1,5 @@
+.\" This is the description that is printed when the .Lb macro is invoked with
+.\" “liblux” as an argument.  The general format for the output of the .Lb macro
+.\" is:
+.\" 	‹Description› (‹Library Name›, ‹Linker Flag›)
+.ds doc-str-Lb-libge Generic Data Structures Library (libge, \-lge)
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