diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/gehashmap.h | 139 |
1 files changed, 69 insertions, 70 deletions
diff --git a/src/gehashmap.h b/src/gehashmap.h index c5d2cf2..832d047 100644 --- a/src/gehashmap.h +++ b/src/gehashmap.h @@ -4,36 +4,27 @@ #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 - -/* 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. +/* 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 n##_remove() in the loop). + * 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) + 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. + * 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; \ + for ((e) = (m).__ents[__ge_i], (t) = (e) ? (e)->__next : NULL; \ (e) != NULL; \ - (e) = (t), (t) = (e) ? (e)->next : NULL) + (e) = (t), (t) = (e) ? (e)->__next : NULL) #define GEHASHMAP_DEF(k, v, n) \ GEHASHMAP_DEF_API(k, v, n) \ @@ -42,23 +33,27 @@ #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; \ - v val; \ - struct n_e *next; \ + 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, \ - __cap; \ - struct n_e **__ents; \ + size_t __size, /* The number of used buckets */ \ + __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); \ - 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); \ @@ -72,13 +67,17 @@ * returned. */ \ int \ - n##_new(n_t *map) \ + 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 = GEHASHMAP_INITIAL_SIZE, \ - .__ents = calloc(GEHASHMAP_INITIAL_SIZE, \ - sizeof(struct n_e *)) \ + .__size = 0, \ + .__cap = cap, \ + .__ents = calloc(cap, sizeof(struct n_e *)), \ + .__loadf = loadf \ }; \ return map->__ents == NULL ? -1 : 0; \ } \ @@ -93,35 +92,6 @@ 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 @@ -133,13 +103,13 @@ size_t hash; \ struct n_e *ent; \ \ - if (map->__size + 1 > map->__cap * GEHASHMAP_LOAD_FACTOR) { \ + 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) { \ + for (ent = map->__ents[hash]; ent != NULL; ent = ent->__next) { \ if (n##_key_iseq(ent->key, key)) { \ ent->val = val; \ return 0; \ @@ -151,7 +121,7 @@ \ ent->key = key; \ ent->val = val; \ - ent->next = map->__ents[hash]; \ + ent->__next = map->__ents[hash]; \ map->__ents[hash] = ent; \ map->__size++; \ \ @@ -169,7 +139,7 @@ struct n_e *ent; \ size_t hash = n##_key_hash(key) % map->__cap; \ \ - for (ent = map->__ents[hash]; ent != NULL; ent = ent->next) { \ + for (ent = map->__ents[hash]; ent != NULL; ent = ent->__next) { \ if (n##_key_iseq(ent->key, key)) { \ if (val != NULL) \ *val = ent->val; \ @@ -204,16 +174,16 @@ return -1; \ \ if (n##_key_iseq(ent->key, key)) { \ - map->__ents[hash] = ent->next; \ + 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; \ + 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; \ @@ -221,6 +191,35 @@ } \ \ 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 */ |