path: root/src/gehashmap.h

#ifndef LIBGE_GEHASHMAP_H
#define LIBGE_GEHASHMAP_H

#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.
 *
 * This macro is unsafe to use when modifying the hashmap inplace (i.e. when
 * calling n##_remove() in the loop).
 */
#define GEHASHMAP_FOREACH(entry, map)                                           \
	for (size_t _gehashmap_i = 0;                                           \
	     _gehashmap_i < (map)->capacity;                                    \
	     _gehashmap_i++)                                                    \
		for ((entry) = (map)->entries[_gehashmap_i];                    \
		     (entry) != NULL;                                           \
		     (entry) = (entry)->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(entry, tmp, map)                                 \
	for (size_t _gehashmap_i = 0;                                           \
	     _gehashmap_i < (map)->capacity;                                    \
	     _gehashmap_i++)                                                    \
		for ((entry) = (map)->entries[_gehashmap_i],                    \
		     (tmp) = (entry) ? (entry)->next : NULL;                    \
		     (entry) != NULL;                                           \
		     (entry) = (tmp),                                           \
		     (tmp) = (entry) ? (entry)->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,                                                    \
		       capacity;                                                \
		struct n_e **entries;                                           \
	} 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,                                          \
			.capacity = GEHASHMAP_INITIAL_SIZE,                     \
			.entries  = calloc(GEHASHMAP_INITIAL_SIZE,              \
					   sizeof(struct n_e *))                \
		};                                                              \
		return map->entries == NULL ? -1 : 0;                           \
	}                                                                       \
	                                                                        \
	/* Function to destroy a hashmap */                                     \
	void                                                                    \
	n##_free(n_t *map)                                                      \
	{                                                                       \
		struct n_e *entry, *tmp;                                        \
		GEHASHMAP_FOREACH_SAFE(entry, tmp, map)                         \
			free(entry);                                            \
		free(map->entries);                                             \
	}                                                                       \
	                                                                        \
	/* 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 new_capacity)                               \
	{                                                                       \
		struct n_e **new_entries =                                      \
			calloc(new_capacity, sizeof(struct n_e *));             \
		if (new_entries == NULL)                                        \
			return -1;                                              \
		                                                                \
		for (size_t i = 0; i < map->capacity; i++) {                    \
			struct n_e *entry = map->entries[i];                    \
			while (entry != NULL) {                                 \
				struct n_e *next = entry->next;                 \
				size_t hash = n##_key_hash(entry->key)          \
					      % new_capacity;                   \
				entry->next = new_entries[hash];                \
				new_entries[hash] = entry;                      \
				entry = next;                                   \
			}                                                       \
		}                                                               \
		                                                                \
		free(map->entries);                                             \
		map->entries = new_entries;                                     \
		map->capacity = new_capacity;                                   \
		                                                                \
		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 *entry;                                              \
		                                                                \
		if (map->size + 1 > map->capacity * GEHASHMAP_LOAD_FACTOR) {    \
			if (n##_resize(map, map->capacity * 2) == -1)           \
				return -1;                                      \
		}                                                               \
		                                                                \
		hash = n##_key_hash(key) % map->capacity;                       \
		entry = map->entries[hash];                                     \
		for (; entry != NULL; entry = entry->next) {                    \
			if (n##_key_iseq(entry->key, key)) {                    \
				entry->val = val;                               \
				return 0;                                       \
			}                                                       \
		}                                                               \
		                                                                \
		if ((entry = malloc(sizeof(struct n_e))) == NULL)               \
			return -1;                                              \
		                                                                \
		entry->key = key;                                               \
		entry->val = val;                                               \
		entry->next = map->entries[hash];                               \
		map->entries[hash] = entry;                                     \
		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)                                        \
	{                                                                       \
		size_t hash = n##_key_hash(key) % map->capacity;                \
		struct n_e *entry = map->entries[hash];                         \
		                                                                \
		for (; entry != NULL; entry = entry->next) {                    \
			if (n##_key_iseq(entry->key, key)) {                    \
				if (val != NULL)                                \
					*val = entry->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)                                             \
	{                                                                       \
		size_t hash = n##_key_hash(key) % map->capacity;                \
		struct n_e *entry;                                              \
		                                                                \
		if ((entry = map->entries[hash]) == NULL)                       \
			return -1;                                              \
		                                                                \
		if (n##_key_iseq(entry->key, key)) {                            \
			map->entries[hash] = entry->next;                       \
			free(entry);                                            \
			map->size--;                                            \
			return 0;                                               \
		}                                                               \
		                                                                \
		for (; entry->next != NULL; entry = entry->next) {              \
			if (n##_key_iseq(entry->next->key, key)) {              \
				struct n_e *next = entry->next;                 \
				entry->next = next->next;                       \
				free(next);                                     \
				map->size--;                                    \
				return 0;                                       \
			}                                                       \
		}                                                               \
		                                                                \
		return -1;                                                      \
	}

#endif /* !LIBGE_GEHASHMAP_H */