diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/gehashmap.h | 290 |
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 |