#ifndef LIBGE_GEHASHMAP_H #define LIBGE_GEHASHMAP_H #include #include /* The GEHASHMAP_FOREACH() macro takes two arguments. The first argument ‘e’ is * a pointer to a hashmap entry. The second argument ‘m’ is the hashmap itself. * The hashmap must not be a pointer. * * This macro is unsafe to use when modifying the hashmap inplace (i.e. when * calling mapname_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 ‘t’ argument. This argument is of the * same type as ‘e’ 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) \ /* A structure representing an entry in the hashmap */ \ struct n_e { \ k key; /* The entry key */ \ v val; /* The entry value */ \ struct n_e *__next; /* The next entry in this bucket */ \ }; \ \ /* A structure representing an actual hashmap */ \ typedef struct { \ size_t __size, /* The number of elements in the map */ \ __cap; /* The number of allocated buckets */ \ double __loadf; /* The % of the hashmap that must be * filled before the map grows */ \ struct n_e **__ents; /* The hashmap buckets */ \ } n_t; \ \ int n##_new(n_t *, size_t, double); \ void n##_free(n_t *); \ int n##_set(n_t *, k, v); \ bool n##_get(n_t *, k, v *); \ bool n##_has(n_t *, k); \ size_t n##_size(n_t *); \ 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, size_t cap, double loadf) \ { \ if (cap == 0) \ cap = 16; \ if (loadf == 0) \ loadf = 0.75f; \ *map = (n_t) { \ .__size = 0, \ .__cap = cap, \ .__ents = calloc(cap, sizeof(struct n_e *)), \ .__loadf = loadf \ }; \ 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 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 * map->__loadf) { \ 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 get the number of elements in a hashmap. */ \ size_t \ n##_size(n_t *map) \ { \ return map->__size; \ } \ \ /* 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; \ } \ \ /* 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; \ } #endif /* !LIBGE_GEHASHMAP_H */