Totally rework the gehashmap implementation

1 files changed, 195 insertions, 275 deletions

diff --git a/src/gehashmap.h b/src/gehashmap.h
index 1f7048c..4cd35e2 100644
--- a/src/gehashmap.h
+++ b/src/gehashmap.h
@@ -1,5 +1,3 @@
-/* Include guard */
-
 #ifndef GEHASHMAP_H
 #define GEHASHMAP_H
 
@@ -13,278 +11,200 @@
 #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;
-		}
+#define GEHASHMAP_API(k, v, n) \
+	struct n##_entry { \
+		k key; \
+		v val; \
+		struct n##_entry *next; \
+	}; \
+	\
+	typedef struct { \
+		size_t size, \
+		       capacity; \
+		struct n##_entry **entries; \
+	} n##_t; \
+	\
+	void   n##_free(n##_t *); \
+	bool   n##_get(n##_t *, k, v *); \
+	bool   n##_has(n##_t *, k); \
+	int    n##_new(n##_t *); \
+	int    n##_set(n##_t *, k, v); \
+	int    n##_remove(n##_t *, k); \
+	int    n##_resize(n##_t *, size_t); \
+	bool   n##_key_iseq(k, k); \
+	void   n##_key_free(k); \
+	size_t n##_key_hash(k);
+
+#define GEHASHMAP_IMPL(k, v, n) \
+	/* 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 \
+	n##_new(n##_t *map) \
+	{ \
+		*map = (n##_t) { \
+			.size     = 0, \
+			.capacity = GEHASHMAP_INITIAL_SIZE, \
+			.entries  = calloc(GEHASHMAP_INITIAL_SIZE, \
+					   sizeof(struct n##_entry *)) \
+		}; \
+		return map->entries == NULL ? -1 : 0; \
+	} \
+	\
+	/* Function to destroy a hashmap */ \
+	void \
+	n##_free(n##_t *map) \
+	{ \
+		for (size_t i = 0; i < map->capacity; i++) { \
+			struct n##_entry *entry = map->entries[i]; \
+			while (entry != NULL) { \
+				struct n##_entry *next = entry->next; \
+				n##_key_free(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 \
+	n##_resize(n##_t *map, size_t new_capacity) \
+	{ \
+		struct n##_entry **new_entries = \
+			calloc(new_capacity, sizeof(struct n##_entry *)); \
+		if (new_entries == NULL) \
+			return -1; \
+		\
+		for (size_t i = 0; i < map->capacity; i++) { \
+			struct n##_entry *entry = map->entries[i]; \
+			while (entry != NULL) { \
+				struct n##_entry *next = entry->next; \
+				size_t hash = n##_key_hash(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 \
+	n##_set(n##_t *map, k key, v val) \
+	{ \
+		size_t hash; \
+		struct n##_entry *entry; \
+		\
+		if (map->size + 1 > map->capacity * GEHASHMAP_LOAD_FACTOR) { \
+			if (n##_resize(map, map->capacity * 2) == -1) \
+				return -1; \
+		} \
+		\
+		hash = n##_key_hash(key) % map->capacity; \
+		entry = map->entries[hash]; \
+		while (entry != NULL) { \
+			if (n##_key_iseq(entry->key, key)) { \
+				entry->val = val; \
+				return 0; \
+			} \
+			entry = entry->next; \
+		} \
+		\
+		if ((entry = malloc(sizeof(struct n##_entry))) == 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 \
+	n##_get(n##_t *map, k key, v *val) \
+	{ \
+		size_t hash = n##_key_hash(key) % map->capacity; \
+		struct n##_entry *entry = map->entries[hash]; \
+		\
+		while (entry != NULL) { \
+			if (n##_key_iseq(entry->key, key)) { \
+				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. \
+	 */ \
+	bool \
+	n##_has(n##_t *map, k key) \
+	{ \
+		return n##_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 n##_key_free().  On error -1 is \
+	 * returned, otherwise 0 is returned. \
+	 */ \
+	int \
+	n##_remove(n##_t *map, k key) \
+	{ \
+		size_t hash = n##_key_hash(key) % map->capacity; \
+		struct n##_entry *entry; \
+		\
+		if ((entry = map->entries[hash]) == NULL) \
+			return -1; \
+		\
+		if (n##_key_iseq(entry->key, key)) { \
+			map->entries[hash] = entry->next; \
+			n##_key_free(entry->key); \
+			free(entry); \
+			map->size--; \
+			return 0; \
+		} \
+		\
+		while (entry->next != NULL) { \
+			if (n##_key_iseq(entry->next->key, key)) { \
+				struct n##_entry *next = entry->next; \
+				entry->next = next->next; \
+				n##_key_free(next->key); \
+				free(next); \
+				map->size--; \
+				return 0; \
+			} \
+			entry = entry->next; \
+		} \
+		\
+		return -1; \
 	}
 
-	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
+#endif /* !GEHASHMAP_H */