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