path: root/src/gehashmap.h

/* Include guard */

#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

/* As a result of preprocessor _stuff_, we need 2 macros to properly concatinate
 * things as we would expect.  GEHASHMAP_CONCAT() is what we use when we want to
 * concatinate things, so GEHASHMAP_CONCAT(GEHASHMAP_INITIAL_SIZE, f) would give
 * us “16f”.  GEHASHMAP_FUNC_NAME() gives us function names, so
 * GEHASHMAP_FUNC_NAME(put) gives us the name of the function to put new items
 * into the current hashmap.
 */
#define GEHASHMAP_CONCAT_HELPER(x, y) x ## y
#define GEHASHMAP_CONCAT(x, y)        GEHASHMAP_CONCAT_HELPER(x, y)
#define GEHASHMAP_FUNC_NAME(x)        GEHASHMAP_CONCAT(GEHASHMAP_NAME, _ ## x)

#endif /* !GEHASHMAP_H */



/* The type of the hashmap keys */
#ifndef GEHASHMAP_KEY_T
	#error "Type for the hashmap key was not set"
#endif

/* The type of the hashmap values */
#ifndef GEHASHMAP_VAL_T
	#error "Type for the hashmap value was not set"
#endif

/* The name of the hashmap.  If set to “foo” then the resulting hashmap type
 * name would be “foo_t” and the get function would be called “foo_get()”.
 */
#ifndef GEHASHMAP_NAME
	#error "Name for the hashmap type was not set"
#endif

/* The key comparison function.  This function should have the following
 * signature:
 *
 *     int function_name(GEHASHMAP_KEY_T, GEHASHMAP_KEY_T);
 *
 * If the two keys are the same, this function should return 0.  This is to stay
 * compatible with the strcmp() function.
 */
#ifndef GEHASHMAP_CMP_FUNC
	#error "Comparison function for the hashmap key was not set"
#endif

/* The key hashing function.  This function should have the following signature:
 *
 *     size_t function_name(GEHASHMAP_KEY_T);
 *
 * This function should return a hash of the given key.  It is used for indexing
 * the hashmap.
 */
#ifndef GEHASHMAP_HASH_FUNC
	#error "Hashing function for the hashmap key was not set"
#endif

/* The key freeing function.  This function should have the following signature:
 *
 *     void function_name(GEHASHMAP_KEY_T);
 *
 * This function should free the given key, just like the free() function.  This
 * is used when destroying a hashmap.  If you use a hashmap key that doesn’t
 * need freeing (like integers) you probably just want to make this a function
 * that does nothing.
 */
#ifndef GEHASHMAP_FREE_FUNC
	#error "Freeing function for the hashmap key was not set"
#endif

/* GEHASHMAP_ENTRY_T is the type representing entries in the hashmap while
 * GEHASHMAP_T is the type representing the hashmap itself.  If GEHASHMAP_NAME
 * is set to “foo” then GEHASHMAP_ENTRY_T will be “struct foo_entry” and
 * GEHASHMAP_T will be “foo_t”.
 */
#define GEHASHMAP_ENTRY_T GEHASHMAP_CONCAT(struct GEHASHMAP_NAME, _entry)
#define GEHASHMAP_T       GEHASHMAP_CONCAT(GEHASHMAP_NAME, _t)

/* A hashmap entry */
GEHASHMAP_ENTRY_T {
	GEHASHMAP_KEY_T    key;   /* This entries key */
	GEHASHMAP_VAL_T    val;   /* This entries value */
	GEHASHMAP_ENTRY_T *next;  /* Pointer to the next entry */
};

/* The hashmap */
typedef struct {
	size_t              size;      /* The number of elements */
	size_t              capacity;  /* The capacity of the hashmap */
	GEHASHMAP_ENTRY_T **entries;   /* A 2D array of hashmap entries */
} GEHASHMAP_T;

int    (*gehashmap_cmp_func)(GEHASHMAP_KEY_T,
                             GEHASHMAP_KEY_T)  = GEHASHMAP_CMP_FUNC;
void   (*gehashmap_free_func)(GEHASHMAP_KEY_T) = GEHASHMAP_FREE_FUNC;
size_t (*gehashmap_hash_func)(GEHASHMAP_KEY_T) = GEHASHMAP_HASH_FUNC;

/* 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
GEHASHMAP_FUNC_NAME(new)(GEHASHMAP_T *map)
{
	*map = (GEHASHMAP_T) {
		.size     = 0,
		.capacity = GEHASHMAP_INITIAL_SIZE,
		.entries  = calloc(GEHASHMAP_INITIAL_SIZE,
		                   sizeof(GEHASHMAP_ENTRY_T *))
	};
	return map->entries == NULL ? -1 : 0;
}

/* Function to destroy a hashmap */
void
GEHASHMAP_FUNC_NAME(free)(GEHASHMAP_T *map)
{
	for (size_t i = 0; i < map->capacity; i++) {
		GEHASHMAP_ENTRY_T *entry = map->entries[i];
		while (entry != NULL) {
			GEHASHMAP_ENTRY_T *next = entry->next;
			gehashmap_free_func(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
GEHASHMAP_FUNC_NAME(resize)(GEHASHMAP_T *map, size_t new_capacity)
{
	GEHASHMAP_ENTRY_T **new_entries = calloc(new_capacity,
	                                         sizeof(GEHASHMAP_ENTRY_T *));
	if (new_entries == NULL)
		return -1;

	for (size_t i = 0; i < map->capacity; i++) {
		GEHASHMAP_ENTRY_T *entry = map->entries[i];
		while (entry != NULL) {
			GEHASHMAP_ENTRY_T *next = entry->next;
			size_t hash = gehashmap_hash_func(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
GEHASHMAP_FUNC_NAME(put)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key,
                                           GEHASHMAP_VAL_T val)
{
	size_t hash;
	GEHASHMAP_ENTRY_T *entry;

	if (map->size + 1 > map->capacity * GEHASHMAP_LOAD_FACTOR) {
		if (GEHASHMAP_FUNC_NAME(resize)(map, map->capacity * 2) == -1)
			return -1;
	}

	hash = gehashmap_hash_func(key) % map->capacity;
	entry = map->entries[hash];
	while (entry != NULL) {
		if (gehashmap_cmp_func(entry->key, key) == 0) {
			entry->val = val;
			return 0;
		}
		entry = entry->next;
	}

	if ((entry = malloc(sizeof(GEHASHMAP_ENTRY_T))) == 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
GEHASHMAP_FUNC_NAME(get)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key,
                                           GEHASHMAP_VAL_T *val)
{
	size_t hash = gehashmap_hash_func(key) % map->capacity;
	GEHASHMAP_ENTRY_T *entry = map->entries[hash];

	while (entry != NULL) {
		if (gehashmap_cmp_func(entry->key, key) == 0) {
			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 get() function that
 * passes NULL as the last argument.
 */
static inline bool
GEHASHMAP_FUNC_NAME(has)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key)
{
	return GEHASHMAP_FUNC_NAME(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 gehashmap_free_func().  On error -1 is returned, otherwise 0
 * is returned.
 */
int
GEHASHMAP_FUNC_NAME(remove)(GEHASHMAP_T *map, GEHASHMAP_KEY_T key)
{
	size_t hash = gehashmap_hash_func(key) % map->capacity;
	GEHASHMAP_ENTRY_T *entry;

	if ((entry = map->entries[hash]) == NULL)
		return -1;

	if (gehashmap_cmp_func(entry->key, key) == 0) {
		map->entries[hash] = entry->next;
		gehashmap_free_func(entry->key);
		free(entry);
		map->size--;
		return 0;
	}

	while (entry->next != NULL) {
		if (gehashmap_cmp_func(entry->next->key, key) == 0) {
			GEHASHMAP_ENTRY_T *next = entry->next;
			entry->next = next->next;
			gehashmap_free_func(next->key);
			free(next);
			map->size--;
			return 0;
		}
		entry = entry->next;
	}

	return -1;
}

/* Undefine everything */
#undef GEHASHMAP_KEY_T
#undef GEHASHMAP_VAL_T
#undef GEHASHMAP_NAME
#undef GEHASHMAP_CMP_FUNC
#undef GEHASHMAP_HASH_FUNC
#undef GEHASHMAP_FREE_FUNC
#undef GEHASHMAP_ENTRY_T
#undef GEHASHMAP_T