#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(e, m) \ for (size_t __ge_i = 0; __ge_i < (m).__cap; __ge_i++) \ for ((e) = (m).__ents[__ge_i]; (e) != NULL; (e) = (e)->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(e, t, m) \ for (size_t __ge_i = 0; __ge_i < (m).__cap; __ge_i++) \ for ((e) = (m).__ents[__ge_i], (t) = (e) ? (e)->next : NULL; \ (e) != NULL; \ (e) = (t), (t) = (e) ? (e)->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, \ __cap; \ struct n_e **__ents; \ } 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, \ .__cap = GEHASHMAP_INITIAL_SIZE, \ .__ents = calloc(GEHASHMAP_INITIAL_SIZE, \ sizeof(struct n_e *)) \ }; \ return map->__ents == NULL ? -1 : 0; \ } \ \ /* Function to destroy a hashmap */ \ void \ n##_free(n_t *map) \ { \ struct n_e *ent, *tmp; \ GEHASHMAP_FOREACH_SAFE(ent, tmp, *map) \ free(ent); \ free(map->__ents); \ } \ \ /* 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 ncap) \ { \ struct n_e **nents = calloc(ncap, sizeof(struct n_e *)); \ if (nents == NULL) \ return -1; \ \ for (size_t i = 0; i < map->__cap; i++) { \ struct n_e *ent = map->__ents[i]; \ while (ent != NULL) { \ struct n_e *next = ent->next; \ size_t hash = n##_key_hash(ent->key) % ncap; \ ent->next = nents[hash]; \ nents[hash] = ent; \ ent = next; \ } \ } \ \ free(map->__ents); \ map->__ents = nents; \ map->__cap = ncap; \ \ 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 *ent; \ \ if (map->__size + 1 > map->__cap * GEHASHMAP_LOAD_FACTOR) { \ if (n##_resize(map, map->__cap * 2) == -1) \ return -1; \ } \ \ hash = n##_key_hash(key) % map->__cap; \ for (ent = map->__ents[hash]; ent != NULL; ent = ent->next) { \ if (n##_key_iseq(ent->key, key)) { \ ent->val = val; \ return 0; \ } \ } \ \ if ((ent = malloc(sizeof(struct n_e))) == NULL) \ return -1; \ \ ent->key = key; \ ent->val = val; \ ent->next = map->__ents[hash]; \ map->__ents[hash] = ent; \ 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) \ { \ struct n_e *ent; \ size_t hash = n##_key_hash(key) % map->__cap; \ \ for (ent = map->__ents[hash]; ent != NULL; ent = ent->next) { \ if (n##_key_iseq(ent->key, key)) { \ if (val != NULL) \ *val = ent->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) \ { \ struct n_e *ent; \ size_t hash = n##_key_hash(key) % map->__cap; \ \ if ((ent = map->__ents[hash]) == NULL) \ return -1; \ \ if (n##_key_iseq(ent->key, key)) { \ map->__ents[hash] = ent->next; \ free(ent); \ map->__size--; \ return 0; \ } \ \ for (; ent->next != NULL; ent = ent->next) { \ if (n##_key_iseq(ent->next->key, key)) { \ struct n_e *next = ent->next; \ ent->next = next->next; \ free(next); \ map->__size--; \ return 0; \ } \ } \ \ return -1; \ } #endif /* !LIBGE_GEHASHMAP_H */