#ifndef GEHASHMAP_H
#define 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

#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); \
	void   n##_key_free(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; \
				n##_key_free(entry->key); \
				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 value was dynamically allocated it will not be freed.  The key
	 * will be freed however as per n##_key_free().  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; \
			n##_key_free(entry->key); \
			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; \
				n##_key_free(next->key); \
				free(next); \
				map->size--; \
				return 0; \
			} \
			entry = entry->next; \
		} \
		\
		return -1; \
	}

#endif /* !GEHASHMAP_H */