path: root/src/gehashmap.h

#ifndef LIBGE_GEHASHMAP_H
#define LIBGE_GEHASHMAP_H

#include <stdbool.h>
#include <stdlib.h>

/* 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 *);                                                 \
	bool   n##_empty(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 check if a hashmap is empty . */                         \
	bool                                                                    \
	n##_empty(n_t *map)                                                     \
	{                                                                       \
		return map->__size == 0;                                        \
	}                                                                       \
	                                                                        \
	/* 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 */