From fc2dd1171212f0e72d4169ad2964d0a712dfba23 Mon Sep 17 00:00:00 2001
From: Thomas Voss <mail@thomasvoss.com>
Date: Fri, 23 Dec 2022 23:14:04 +0100
Subject: Totally rework the gehashmap implementation
---
examples/gehashmap.c | 31 ++--
src/gehashmap.h | 470 +++++++++++++++++++++------------------------------
2 files changed, 214 insertions(+), 287 deletions(-)
diff --git a/examples/gehashmap.c b/examples/gehashmap.c
index f216d00..b0763ac 100644
--- a/examples/gehashmap.c
+++ b/examples/gehashmap.c
@@ -2,18 +2,25 @@
#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>
+GEHASHMAP_API(char *, int, funmap);
+GEHASHMAP_IMPL(char *, int, funmap);
+
+bool
+funmap_key_iseq(char *a, char *b)
+{
+ return strcmp(a, b) == 0;
+}
+
+void
+funmap_key_free(char *s)
+{
+ free(s);
+}
+
size_t
-hash(char *s)
+funmap_key_hash(char *s)
{
char c;
size_t x = 5381;
@@ -31,9 +38,9 @@ main(void)
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_set(map, strdup("Thomas Voß"), 5);
+ funmap_set(map, strdup("THOMAS VOẞ"), 6);
+ funmap_set(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);
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 */
--
cgit v1.2.3