summaryrefslogtreecommitdiff
path: root/src/gehashmap.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/gehashmap.h')
-rw-r--r--src/gehashmap.h139
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 */