hash.c

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// Chained hashmap.
//
// TODO Keep load-factor constant
// TODO Use union instead of void*
struct my_hash_node
{
	void* key;
	void* value;

	struct my_hash_node* next;
};

struct my_hash
{
	struct my_hash_node** bucket_list;
	int num_slots;
};

typedef int (*my_hash_hash_func)(int m, const void* key, void* userdata);
typedef int (*my_hash_cmp_func)(const void* a, const void* b, void* userdata);

static struct my_hash*
my_hash_new (int capacity)
{
	struct my_hash *hash;
	
	hash = (struct my_hash*) malloc (sizeof (struct my_hash));
	if (hash == NULL)
		return NULL;

	hash->num_slots = capacity;
	hash->bucket_list = (struct my_hash_node**) calloc 
		(capacity, sizeof (struct my_hash_node*));

	if (hash->bucket_list == NULL)
	{
		free (hash);
		return NULL;
	}

	return hash;
}

static void
my_hash_drop (struct my_hash* hash)
{
	int i;

	for (i = 0; i < hash->num_slots; ++i)
	{
		struct my_hash_node *node = hash->bucket_list[i];
		for (; node != NULL; node = node->next)
			free (node);
	}

	free (hash);
}

static void*
my_hash_get (struct my_hash* hash, void* key,
	           my_hash_hash_func hfunc, my_hash_cmp_func cmp,
		         void* userdata1, void* userdata2)
{
	int hashcode = hfunc (hash->num_slots, key, userdata1);
	struct my_hash_node *node = hash->bucket_list[hashcode];

	if (node == NULL)
		return NULL;
	else if (node->next == NULL)
		return node->value;

	// If there's a collision, use the comparator function.
	for (; node != NULL; node = node->next)
	{
		if (cmp (node->key, key, userdata2) == 0)
			return node->value;
	}

	return NULL;
}

static void
my_hash_put (struct my_hash* hash, void* key, void* value,
	           my_hash_hash_func hfunc, my_hash_cmp_func cmp,
		         void* userdata1, void* userdata2)
{
	int hashcode = hfunc (hash->num_slots, key, userdata1);
	struct my_hash_node *node = hash->bucket_list[hashcode]; 

	if (node == NULL)
	{
		node = (struct my_hash_node*) malloc (sizeof (struct my_hash_node));

		node->key = key;
		node->value = value;
		node->next = NULL;

		hash->bucket_list[hashcode] = node;	
	} else if (node->next == NULL)
	{
		node->value = value;
	} else
	{
		for (; node != NULL; node = node->next)
		{
			if (cmp (node->key, key, userdata2) == 0)
			{
				node->value = value;
				return;
			} else if (node->next == NULL)
			{
				struct my_hash_node *next;
				
				// A node with that key wasn't found, so adding a new one.
				next = (struct my_hash_node*) malloc (sizeof (struct my_hash_node));

				next->key = key;
				next->value = value;
				next->next = NULL;

				// Make it the last one to collide.
				node->next = next;
			}
		}
	}
}

static void
my_hash_delete (struct my_hash* hash, void* key,
                my_hash_hash_func hfunc, my_hash_cmp_func cmp,
                void *userdata1, void *userdata2)
{
	int hashcode = hfunc (hash->num_slots, key, userdata1);
	
	struct my_hash_node *node = hash->bucket_list[hashcode];

	if (node->next == NULL)
	{
		free (node);
		
		hash->bucket_list[hashcode] = NULL;
	} else {
		struct my_hash_node *prev = NULL;
		
		for (; node != NULL; node = node->next)
		{
			if (cmp (key, node->key, userdata2) == 0)
			{
				if (prev == NULL)
				{
					hash->bucket_list[hashcode] = prev->next;
				} else {
					prev->next = node->next;
				}

				free (node);
				return;
			}
			prev = node;
		}
	}
}

static int
string_hash (int m, const void* key, void* userdata)
{
	const char* str = key;
	const size_t len = strlen(str);
	
  int p = 31;
	int hash = 0;
	int p_pow = 1;

	for (size_t i = 0; i < len; ++i)
	{
		hash += (hash + str[i] * p_pow) % m;
		p_pow = (p_pow * p) % m;
	}

	return hash;
}

static int
string_cmp(const void* a, const void* b, void* userdata)
{
	return strcmp (a, b);
}

#define my_hash_get_str(hash, key) my_hash_get((hash), (key), string_hash, string_cmp, NULL, NULL)
#define my_hash_put_str(hash, key, value) my_hash_put((hash), (key), (value), string_hash, string_cmp, NULL, NULL)
#define my_hash_delete_str(hash, key) my_hash_delete((hash), (key), string_hash, string_cmp, NULL, NULL)

int main()
{
	struct my_hash* hash = my_hash_new(100);

	my_hash_put_str (hash, "I want to", "love somebody");
	
	printf ("I want to: %s\n", (char*) my_hash_get_str(hash, "I want to"));

	my_hash_delete_str(hash, "I want to");

	// This should print null.
	printf ("I want to: %p\n", (char*) my_hash_get_str(hash, "I want to"));
}