#ifndef LIBGE_GEHASHMAP_H #define LIBGE_GEHASHMAP_H #include #include /* 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 /* The GEHASHMAP_FOREACH() macro takes 2 arguments. The first argument “entry” * is a “struct n##_entry *”. This variable will be set to point to the next * hashmap entry each iteration. The second argument “map” is a pointer to the * hashmap to iterate over. * * This macro is unsafe to use when modifying the hashmap inplace (i.e. when * calling n##_remove() in the loop). */ #define GEHASHMAP_FOREACH(entry, map) \ for (size_t _gehashmap_i = 0; \ _gehashmap_i < (map)->capacity; \ _gehashmap_i++) \ for ((entry) = (map)->entries[_gehashmap_i]; \ (entry) != NULL; \ (entry) = (entry)->next) /* The GEHASHMAP_FOREACH_SAFE() macro is identical to the GEHASHMAP_FOREACH() * macro except it takes an additional “tmp” argument. This argument is of the * same type as “entry” (a “struct n##_entry *”) and shouldn’t be interacted * with by the library user. This macro allows you to modify the hashmap * inplace while iterating. */ #define GEHASHMAP_FOREACH_SAFE(entry, tmp, map) \ for (size_t _gehashmap_i = 0; \ _gehashmap_i < (map)->capacity; \ _gehashmap_i++) \ for ((entry) = (map)->entries[_gehashmap_i], \ (tmp) = (entry) ? (entry)->next : NULL; \ (entry) != NULL; \ (entry) = (tmp), \ (tmp) = (entry) ? (entry)->next : NULL) #define GEHASHMAP_DEF(k, v, n) \ GEHASHMAP_DEF_API(k, v, n) \ GEHASHMAP_DEF_IMPL(k, v, n) #define GEHASHMAP_DEF_API(k, v, n) \ GEHASHMAP_DEF_API_HELPER(k, v, n, n##_t, n##_entry) #define GEHASHMAP_DEF_API_HELPER(k, v, n, n_t, n_e) \ struct n_e { \ k key; \ v val; \ struct n_e *next; \ }; \ \ typedef struct { \ size_t size, \ capacity; \ struct n_e **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); \ size_t n##_key_hash(k); #define GEHASHMAP_DEF_IMPL(k, v, n) \ GEHASHMAP_DEF_IMPL_HELPER(k, v, n, n##_t, n##_entry) #define GEHASHMAP_DEF_IMPL_HELPER(k, v, n, n_t, n_e) \ /* 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_e *)) \ }; \ return map->entries == NULL ? -1 : 0; \ } \ \ /* Function to destroy a hashmap */ \ void \ n##_free(n_t *map) \ { \ struct n_e *entry, *tmp; \ GEHASHMAP_FOREACH_SAFE(entry, tmp, map) \ free(entry); \ 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_e **new_entries = \ calloc(new_capacity, sizeof(struct n_e *)); \ if (new_entries == NULL) \ return -1; \ \ for (size_t i = 0; i < map->capacity; i++) { \ struct n_e *entry = map->entries[i]; \ while (entry != NULL) { \ struct n_e *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_e *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]; \ for (; entry != NULL; entry = entry->next) { \ if (n##_key_iseq(entry->key, key)) { \ entry->val = val; \ return 0; \ } \ } \ \ if ((entry = malloc(sizeof(struct n_e))) == 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_e *entry = map->entries[hash]; \ \ for (; entry != NULL; entry = entry->next) { \ if (n##_key_iseq(entry->key, key)) { \ if (val != NULL) \ *val = entry->val; \ return true; \ } \ } \ \ 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 n##_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 key or value were dynamically allocated they will not be freed. * 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_e *entry; \ \ if ((entry = map->entries[hash]) == NULL) \ return -1; \ \ if (n##_key_iseq(entry->key, key)) { \ map->entries[hash] = entry->next; \ free(entry); \ map->size--; \ return 0; \ } \ \ for (; entry->next != NULL; entry = entry->next) { \ if (n##_key_iseq(entry->next->key, key)) { \ struct n_e *next = entry->next; \ entry->next = next->next; \ free(next); \ map->size--; \ return 0; \ } \ } \ \ return -1; \ } #endif /* !LIBGE_GEHASHMAP_H */