#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_API(k, v, n) \
	struct n##_entry { \
		k key; \
		v val; \
		struct n##_entry *next; \
	}; \
	\
	typedef struct { \
		size_t size, \
		       capacity; \
		struct n##_entry **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_IMPL(k, v, n) \
	/* 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##_entry *)) \
		}; \
		return map->entries == NULL ? -1 : 0; \
	} \
	\
	/* Function to destroy a hashmap */ \
	void \
	n##_free(n##_t *map) \
	{ \
		for (size_t i = 0; i < map->capacity; i++) { \
			struct n##_entry *entry = map->entries[i]; \
			while (entry != NULL) { \
				struct n##_entry *next = entry->next; \
				free(entry); \
				entry = next; \
			} \
		} \
		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##_entry **new_entries = \
			calloc(new_capacity, sizeof(struct n##_entry *)); \
		if (new_entries == NULL) \
			return -1; \
		\
		for (size_t i = 0; i < map->capacity; i++) { \
			struct n##_entry *entry = map->entries[i]; \
			while (entry != NULL) { \
				struct n##_entry *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##_entry *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]; \
		while (entry != NULL) { \
			if (n##_key_iseq(entry->key, key)) { \
				entry->val = val; \
				return 0; \
			} \
			entry = entry->next; \
		} \
		\
		if ((entry = malloc(sizeof(struct n##_entry))) == 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##_entry *entry = map->entries[hash]; \
		\
		while (entry != NULL) { \
			if (n##_key_iseq(entry->key, key)) { \
				if (val != NULL) \
					*val = entry->val; \
				return true; \
			} \
			entry = entry->next; \
		} \
		\
		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##_entry *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; \
		} \
		\
		while (entry->next != NULL) { \
			if (n##_key_iseq(entry->next->key, key)) { \
				struct n##_entry *next = entry->next; \
				entry->next = next->next; \
				free(next); \
				map->size--; \
				return 0; \
			} \
			entry = entry->next; \
		} \
		\
		return -1; \
	}

#endif /* !LIBGE_GEHASHMAP_H */