tiny hash map library

hash.c

/* experimental hash library in ANSI C
 * @author silverweed
 * @license GNU GPL v3
 */
#include "hash.h"
#include <stdlib.h>

#define DEBUG 1

#if DEBUG >= 1
#include <stdio.h>
#endif

static int bucket_get_int(const Bucket *bkt, const char *key);
static float bucket_get_float(const Bucket *bkt, const char *key);
static double bucket_get_double(const Bucket *bkt, const char *key);
static char bucket_get_char(const Bucket *bkt, const char *key);
static char* bucket_get_string(const Bucket *bkt, const char *key);

/*****************************************/
/********** Hash table methods ***********/
/*****************************************/


/** Creates a new hashtable, zeroes all its buckets and returns
  * a pointer to it.
  */
HashTable* new_hash_table() {
	HashTable *tab = (HashTable*)malloc(sizeof(HashTable));
	unsigned short i;
	for (i = 0; i < MAP_N_BUCKETS; ++i) {
		tab->buckets[i].elems = 0;
		tab->buckets[i].list = NULL;
	}
	return tab;
}

/** Removes an element from the hash table and deallocates it */
void hash_remove(HashTable *table, const char *key) {
	map_hash_t h = calc_hash(key);
	BucketElement *it = table->buckets[h].list;
	BucketElement *tmp;
	if (strcmp(it->key, key) == 0) {
		if (it->val.stringval != NULL) 
			free(it->val.stringval);
		table->buckets[h].list = it->next;
		free(it->key);
		free(it);
		return;
	}
	for ( ; it != NULL; it = it->next) {
		if (it->next->key == key) {
			tmp = it->next;
			if (tmp->val.stringval != NULL)
				free(tmp->val.stringval);
			it->next = tmp->next;
			free(tmp->key);
			free(tmp);
			return;
		}
	}
}

/** Inserts a new string in the hash table */
void hash_put_int(HashTable *table, const char *key, int val) {
	map_hash_t h = calc_hash(key);
	/** Check if this value was already in map */
	BucketElement *elem = bucket_get_element(&table->buckets[h], key);
#if DEBUG >= 2
	fprintf(stderr, "hash_put: key = %s, val = %d, hash = %d\n", key, val, h);
#endif
	if (elem != NULL) 
		elem->val.intval = val;
	else
		bucket_push_front_int(&table->buckets[h], key, val);
}

void hash_put_float(HashTable *table, const char *key, float val) {
	map_hash_t h = calc_hash(key);
	BucketElement *elem = bucket_get_element(&table->buckets[h], key);
#if DEBUG >= 2
	fprintf(stderr, "hash_put: key = %s, val = %f, hash = %d\n", key, val, h);
#endif
	if (elem != NULL)
		elem->val.floatval = val;
	else
		bucket_push_front_float(&table->buckets[h], key, val);
}

void hash_put_double(HashTable *table, const char *key, double val) {
	map_hash_t h = calc_hash(key);
	BucketElement *elem = bucket_get_element(&table->buckets[h], key);
#if DEBUG >= 2
	fprintf(stderr, "hash_put: key = %s, val = %f, hash = %d\n", key, val, h);
#endif
	if (elem != NULL)
		elem->val.doubleval = val;
	else
		bucket_push_front_double(&table->buckets[h], key, val);
}

void hash_put_char(HashTable *table, const char *key, char val) {
	map_hash_t h = calc_hash(key);
	BucketElement *elem = bucket_get_element(&table->buckets[h], key);
#if DEBUG >= 2
	fprintf(stderr, "hash_put: key = %s, val = %c, hash = %d\n", key, val, h);
#endif
	if (elem != NULL)
		elem->val.charval = val;
	else
		bucket_push_front_char(&table->buckets[h], key, val);
}

void hash_put_string(HashTable *table, const char *key, char *val) {
	map_hash_t h = calc_hash(key);
	BucketElement *elem = bucket_get_element(&table->buckets[h], key);
#if DEBUG >= 2
	fprintf(stderr, "hash_put: key = %s, val = %s, hash = %d\n", key, val, h);
#endif
	if (elem != NULL) {
		elem->val.stringval = (char*)malloc(sizeof(val));
		strcpy(elem->val.stringval, val);
	} else
		bucket_push_front_string(&table->buckets[h], key, val);
}

int hash_get_int(const HashTable *table, const char *key) {
	map_hash_t h = calc_hash(key);
	return bucket_get_int(&table->buckets[h], key);
}

float hash_get_float(const HashTable *table, const char *key) {
	map_hash_t h = calc_hash(key);
	return bucket_get_float(&table->buckets[h], key);
}

double hash_get_double(const HashTable *table, const char *key) {
	map_hash_t h = calc_hash(key);
	return bucket_get_double(&table->buckets[h], key);
}

char hash_get_char(const HashTable *table, const char *key) {
	map_hash_t h = calc_hash(key);
	return bucket_get_char(&table->buckets[h], key);
}

char* hash_get_string(const HashTable *table, const char *key) {
	map_hash_t h = calc_hash(key);
	return bucket_get_string(&table->buckets[h], key);
}

/*********************************/
/******** Bucket methods *********/
/*********************************/

/** Allocates a new bucket element containing `str` and returns its pointer */
BucketElement* new_bucket_element_int(const char *str, int val) {
	BucketElement *elem = (BucketElement*)malloc(sizeof(BucketElement));
	elem->key = (char*)malloc(sizeof(char)*strlen(str));
	strcpy(elem->key, str);
	elem->val.stringval = NULL;
	elem->val.intval = val;
	elem->next = NULL;
	return elem;
}

BucketElement* new_bucket_element_float(const char *str, float val) {
	BucketElement *elem = (BucketElement*)malloc(sizeof(BucketElement));
	elem->key = (char*)malloc(sizeof(char)*strlen(str));
	strcpy(elem->key, str);
	elem->val.stringval = NULL;
	elem->val.floatval = val;
	elem->next = NULL;
	return elem;
}

BucketElement* new_bucket_element_double(const char *str, double val) {
	BucketElement *elem = (BucketElement*)malloc(sizeof(BucketElement));
	elem->key = (char*)malloc(sizeof(char)*strlen(str));
	strcpy(elem->key, str);
	elem->val.stringval = NULL;
	elem->val.doubleval = val;
	elem->next = NULL;
	return elem;
}

BucketElement* new_bucket_element_char(const char *str, char val) {
	BucketElement *elem = (BucketElement*)malloc(sizeof(BucketElement));
	elem->key = (char*)malloc(sizeof(char)*strlen(str));
	strcpy(elem->key, str);
	elem->val.stringval = NULL;
	elem->val.charval = val;
	elem->next = NULL;
	return elem;
}

BucketElement* new_bucket_element_string(const char *str, char *val) {
	BucketElement *elem = (BucketElement*)malloc(sizeof(BucketElement));
	elem->key = (char*)malloc(sizeof(char)*strlen(str));
	strcpy(elem->key, str);
	elem->val.stringval = (char*)malloc(sizeof(char)*strlen(str));
	strcpy(elem->val.stringval, val);
	elem->next = NULL;
	return elem;
}

/** Adds an element in the head of a bucket. */
void bucket_push_front_int(Bucket *bkt, const char *key, int val) {
	BucketElement *elem = new_bucket_element_int(key, val);
	elem->next = bkt->list;
	bkt->list = elem;
}

void bucket_push_front_float(Bucket *bkt, const char *key, float val) {
	BucketElement *elem = new_bucket_element_float(key, val);
	elem->next = bkt->list;
	bkt->list = elem;
}

void bucket_push_front_double(Bucket *bkt, const char *key, double val) {
	BucketElement *elem = new_bucket_element_double(key, val);
	elem->next = bkt->list;
	bkt->list = elem;
}

void bucket_push_front_char(Bucket *bkt, const char *key, char val) {
	BucketElement *elem = new_bucket_element_char(key, val);
	elem->next = bkt->list;
	bkt->list = elem;
}

void bucket_push_front_string(Bucket *bkt, const char *key, char *val) {
	BucketElement *elem = new_bucket_element_string(key, val);
	elem->next = bkt->list;
	bkt->list = elem;
}

/** Retreives an element by key from a given bucket */
BucketElement* bucket_get_element(const Bucket *bkt, const char *key) {
	BucketElement *bp;
#if DEBUG >= 1
	int k = 0;
#endif
	for (bp = bkt->list; bp != NULL; bp = bp->next) {
		if (strcmp(bp->key, key) == 0) {
#if DEBUG >= 1
			fprintf(stderr, "map: found %s after %d elements\n", key, k);
#endif
			return bp;
		}
#if DEBUG >= 1
		++k;
#endif
	}
	return NULL;
}

/** Retreives an element value by key from a given bucket */
static int bucket_get_int(const Bucket *bkt, const char *key) {
	BucketElement *elem = bucket_get_element(bkt, key);
	return elem == NULL ? 0 : elem->val.intval;
}

static float bucket_get_float(const Bucket *bkt, const char *key) {
	BucketElement *elem = bucket_get_element(bkt, key);
	return elem == NULL ? 0. : elem->val.floatval;
}

static double bucket_get_double(const Bucket *bkt, const char *key) {
	BucketElement *elem = bucket_get_element(bkt, key);
	return elem == NULL ? 0. : elem->val.doubleval;
}

static char bucket_get_char(const Bucket *bkt, const char *key) {
	BucketElement *elem = bucket_get_element(bkt, key);
	return elem == NULL ? '\0' : elem->val.charval;
}

static char* bucket_get_string(const Bucket *bkt, const char *key) {
	BucketElement *elem = bucket_get_element(bkt, key);
	return elem == NULL ? NULL : elem->val.stringval;
}
/***********************************/
/******** Other functions **********/
/***********************************/

map_hash_t calc_hash(const char *str) {
	map_hash_t h, i;
	const unsigned int l = strlen(str);
	for (i = 0, h = 0; i < l; ++i) {
		h += (unsigned int)str[i];
	}
	return h % MAP_N_BUCKETS;
}

hash.h

/* experimental hash library in ANSI C
 * @author silverweed
 * @license GNU GPL v3
 */
#pragma once

#include <string.h>

#define MAP_N_BUCKETS 256

typedef unsigned short map_hash_t;

/** Map entry char* => T */
typedef struct BucketElement {
	char *key;
	union {
		int intval;
		char charval;
		float floatval;
		double doubleval;
		char* stringval;
	} val;
	struct BucketElement *next;
} BucketElement;

typedef struct {
	BucketElement *list;
	unsigned int elems;
} Bucket;

typedef struct {
	Bucket buckets[MAP_N_BUCKETS];
} HashTable;


/*** Hash table methods ***/
HashTable* new_hash_table();

void hash_remove(HashTable *table, const char *key);

void hash_put_int(HashTable *table, const char *key, int val);
void hash_put_float(HashTable *table, const char *key, float val);
void hash_put_double(HashTable *table, const char *key, double val);
void hash_put_char(HashTable *table, const char *key, char val);
void hash_put_string(HashTable *table, const char *key, char *val);

int hash_get_int(const HashTable *table, const char *key);
float hash_get_float(const HashTable *table, const char *key);
double hash_get_double(const HashTable *table, const char *key);
char hash_get_char(const HashTable *table, const char *key);
char* hash_get_string(const HashTable *table, const char *key);

/*** Bucket methods ***/
BucketElement* new_bucket_element_int(const char *key, int val);
BucketElement* new_bucket_element_float(const char *key, float val);
BucketElement* new_bucket_element_double(const char *key, double val);
BucketElement* new_bucket_element_char(const char *key, char val);
BucketElement* new_bucket_element_string(const char *key, char *val);

void bucket_push_front_int(Bucket *bkt, const char *key, int val);
void bucket_push_front_float(Bucket *bkt, const char *key, float val);
void bucket_push_front_double(Bucket *bkt, const char *key, double val);
void bucket_push_front_char(Bucket *bkt, const char *key, char val);
void bucket_push_front_string(Bucket *bkt, const char *key, char *val);

BucketElement *bucket_get_element(const Bucket *bkt, const char *key);

/*** Other ***/
map_hash_t calc_hash(const char *str);