Generic Hash Table

hash.c

#include "hash.h"

table *
ht_init(int num, size_t type_size, int key_len, void *hf, void *pf)
{
	size_t total_size;	
	total_size = sizeof(table);			/* table */
	total_size += sizeof(char) * num * key_len; 	/* keys */
	total_size += (type_size * num); 		/* values */		
	table *ht = malloc(total_size);
	ht->size = num;	
	ht->key_len = key_len;
	ht->hashfunc = hf;
	ht->probefunc = pf;
	ht->keys = (char *) (ht + 1);
	ht->values = (char *) (ht->keys + num * key_len);
	return ht;
}

void
ht_free(table *ht)
{
	free(ht);
}

ulong 
ht_hash(const char *key)
{
	int c;
	unsigned long hash = 5381;
	while ((c = *key++))
		hash = ((hash << 5) + hash) + c;
	return hash;
}

char *
ht_key_idx(table *ht, ulong idx)
{
	return &ht->keys[idx * ht->key_len];
}

ulong
ht_lin_probe(table *ht, const char *key, bool error_on_blank)
{
	ulong k = ht->hashfunc(key) % ht->size;
	for (int j=0; j<ht->size; j++) {
		if (*ht_key_idx(ht, k) == '\0')
			/* blank */
			return error_on_blank ? -1 : k;
		if (strncmp(ht_key_idx(ht, k), key, ht->key_len-1) == 0)
			/* key exists */
			return k;
		k = (k + 1) % ht->size;
	}
	/* table is full */
	return -1; 
}

ulong
ht_quad_probe(table *ht, const char *key, bool error_on_blank)
{
	ulong k = ht->hashfunc(key);
	ulong i = k % ht->size;
	for (int j=1; j<=ht->size; j++) {
		if (*ht_key_idx(ht, i) == '\0')
			/* blank */
			return error_on_blank ? -1 : i; 
		if (strncmp(ht_key_idx(ht, i), key, ht->key_len-1) == 0)
			/* key exists */
			return i;
		i = ( k + j * j ) % ht->size;
	}
	/* table is full */
	return -1; 
}

ulong
ht_add_key(table *ht, const char *key)
{
	ulong i = ht->probefunc(ht, key, false);
	if (i == -1) {			
		fprintf(stderr, "HT ERROR: table full.\n");
		exit(1);
	}
	strncpy(ht_key_idx(ht, i), key, ht->key_len-1);
	ht_key_idx(ht, i+1)[-1] = '\0';
	return i;
}

ulong 
ht_get_key(table *ht, const char *key)
{
	ulong i = ht->probefunc(ht, key, true);
	if (i == -1) {
		fprintf(stderr, "HT KEY ERROR: \"%s\"\n", key);
		exit(1);
	}
	return i;
}

void
ht_del_key(table *ht, const char *key)
{
	ulong i = ht_get_key(ht, key);
	*ht_key_idx(ht, i) = '\0';
}

bool
ht_has_key(table *ht, const char *key)
{
	return ht->probefunc(ht, key, 1) != -1;
}

hash.h

#ifndef HASH_H
#define HASH_H

/*
 * hash.h -- generic closed hash table implementation.
 * constant memory, linear/quadratic probing, variable max keylength 
 * by sixthgear.
 */

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

typedef unsigned long ulong;

typedef struct table {
	ulong (*probefunc)(struct table *, const char *, bool);
	ulong (*hashfunc)(const char *);
	int size;
	int key_len;
	char *keys;
	void *values;
} table;

table * ht_init(int num, size_t type_size, int key_len, void *hf, void *pf);
char * ht_key_idx(table *ht, ulong idx);
ulong ht_add_key(table *ht, const char *key);
ulong ht_get_key(table *ht, const char *key);
void ht_del_key(table *ht, const char *key);
void ht_free(table *ht);
ulong ht_hash(const char *key);
ulong ht_lin_probe(table *ht, const char *key, bool error_on_blank);
ulong ht_quad_probe(table *ht, const char *key, bool error_on_blank);
bool ht_has_key(table *ht, const char *key);

#define HT_GENERATE_TYPE(TYPE, NAME)						\
	 									\
extern table *									\
ht_init_##NAME(int num, int key_len, void *hf, void *pf) 			\
{ 										\
	return ht_init(num, sizeof(TYPE), key_len, hf, pf);			\
}										\
										\
extern void									\
ht_add_##NAME(table *ht, const char *key, TYPE value)				\
{										\
	((TYPE *) ht->values)[ht_add_key(ht, key)] = value;			\
}										\
										\
extern TYPE									\
ht_get_##NAME(table *ht, const char *key)					\
{										\
	return ((TYPE *) ht->values)[ht_get_key(ht, key)];			\
}                                                                               \
                                                                                \
extern void									\
ht_del_##NAME(table *ht, const char *key)					\
{										\
	ht_del_key(ht, key);							\
}

#endif

hash_test.c

#include <stdlib.h>
#include <stdio.h>
#include "hash.h"

HT_GENERATE_TYPE(int, int);
HT_GENERATE_TYPE(float, float); 

int 
main()
{
	table *hti = ht_init_int(3700, 32, ht_hash, ht_lin_probe);
	table *htf = ht_init_float(23, 32, ht_hash, ht_quad_probe);
	
	ht_add_int(hti, "hello", 100);
	ht_add_int(hti, "hellote", 150);
	ht_add_int(hti, "world!", 200);
	ht_add_int(hti, "foo", 300);
	ht_add_int(hti, "a", 1);
	ht_add_int(hti, "b", 2);
	ht_add_int(hti, "c", 3);
	ht_add_int(hti, "d", 4);	
	ht_add_int(hti, "e", 5);
	ht_add_int(hti, "f", 6);
	ht_add_int(hti, "g", 7);
	ht_del_int(hti, "g");		
	// ht_get_int(hti, "hello");
	
	ht_add_float(htf, "hello", 10.0/3);
	ht_add_float(htf, "world!", 67.2);
	ht_add_float(htf, "foo", 11.111);
	
	// ht_get_float(htf, "hello");
	
	printf("\nINTS:\n");
	for (int i=0; i<hti->size; i++) {
		char *key = (char *) hti->keys + i * hti->key_len;
		if (!key[0]) continue; 
		int val = *((int *)hti->values + i);
		printf("%d: '%s': %d\n", i, key, val);
	}		
	
	printf("\nFLOATS:\n");
	for (int i=0; i<htf->size; i++) {
		char *key = (char *) htf->keys + i * htf->key_len;
		if (!key[0]) continue; 
		float val = *((float *)htf->values + i);
		printf("%d: '%s': %f\n", i, key, val);
	}		
		
	ht_free(hti);
	ht_free(htf);
		
	return 0;
}

out.txt

INTS:
70: 'a': 1
71: 'b': 2
72: 'c': 3
73: 'd': 4
74: 'e': 5
75: 'f': 6
349: 'foo': 300
2741: 'hello': 100
2978: 'hellote': 150
3050: 'world!': 200

FLOATS:
2: 'foo': 11.111000
5: 'hello': 3.333333
21: 'world!': 67.199997