A quick hashtable implementation in c.

hash.c

#define _XOPEN_SOURCE 500 /* Enable certain library functions (strdup) on linux.  See feature_test_macros(7) */

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

struct entry_s {
	char *key;
	char *value;
	struct entry_s *next;
};

typedef struct entry_s entry_t;

struct hashtable_s {
	int size;
	struct entry_s **table;	
};

typedef struct hashtable_s hashtable_t;


/* Create a new hashtable. */
hashtable_t *ht_create( int size ) {

	hashtable_t *hashtable = NULL;
	int i;

	if( size < 1 ) return NULL;

	/* Allocate the table itself. */
	if( ( hashtable = malloc( sizeof( hashtable_t ) ) ) == NULL ) {
		return NULL;
	}

	/* Allocate pointers to the head nodes. */
	if( ( hashtable->table = malloc( sizeof( entry_t * ) * size ) ) == NULL ) {
		return NULL;
	}
	for( i = 0; i < size; i++ ) {
		hashtable->table[i] = NULL;
	}

	hashtable->size = size;

	return hashtable;	
}

/* Hash a string for a particular hash table. */
int ht_hash( hashtable_t *hashtable, char *key ) {

	unsigned long int hashval;
	int i = 0;

	/* Convert our string to an integer */
	while( hashval < ULONG_MAX && i < strlen( key ) ) {
		hashval = hashval << 8;
		hashval += key[ i ];
		i++;
	}

	return hashval % hashtable->size;
}

/* Create a key-value pair. */
entry_t *ht_newpair( char *key, char *value ) {
	entry_t *newpair;

	if( ( newpair = malloc( sizeof( entry_t ) ) ) == NULL ) {
		return NULL;
	}

	if( ( newpair->key = strdup( key ) ) == NULL ) {
		return NULL;
	}

	if( ( newpair->value = strdup( value ) ) == NULL ) {
		return NULL;
	}

	newpair->next = NULL;

	return newpair;
}

/* Insert a key-value pair into a hash table. */
void ht_set( hashtable_t *hashtable, char *key, char *value ) {
	int bin = 0;
	entry_t *newpair = NULL;
	entry_t *next = NULL;
	entry_t *last = NULL;

	bin = ht_hash( hashtable, key );

	next = hashtable->table[ bin ];

	while( next != NULL && next->key != NULL && strcmp( key, next->key ) > 0 ) {
		last = next;
		next = next->next;
	}

	/* There's already a pair.  Let's replace that string. */
	if( next != NULL && next->key != NULL && strcmp( key, next->key ) == 0 ) {

		free( next->value );
		next->value = strdup( value );

	/* Nope, could't find it.  Time to grow a pair. */
	} else {
		newpair = ht_newpair( key, value );

		/* We're at the start of the linked list in this bin. */
		if( next == hashtable->table[ bin ] ) {
			newpair->next = next;
			hashtable->table[ bin ] = newpair;
	
		/* We're at the end of the linked list in this bin. */
		} else if ( next == NULL ) {
			last->next = newpair;
	
		/* We're in the middle of the list. */
		} else  {
			newpair->next = next;
			last->next = newpair;
		}
	}
}

/* Retrieve a key-value pair from a hash table. */
char *ht_get( hashtable_t *hashtable, char *key ) {
	int bin = 0;
	entry_t *pair;

	bin = ht_hash( hashtable, key );

	/* Step through the bin, looking for our value. */
	pair = hashtable->table[ bin ];
	while( pair != NULL && pair->key != NULL && strcmp( key, pair->key ) > 0 ) {
		pair = pair->next;
	}

	/* Did we actually find anything? */
	if( pair == NULL || pair->key == NULL || strcmp( key, pair->key ) != 0 ) {
		return NULL;

	} else {
		return pair->value;
	}
	
}


int main( int argc, char **argv ) {

	hashtable_t *hashtable = ht_create( 65536 );

	ht_set( hashtable, "key1", "inky" );
	ht_set( hashtable, "key2", "pinky" );
	ht_set( hashtable, "key3", "blinky" );
	ht_set( hashtable, "key4", "floyd" );

	printf( "%s\n", ht_get( hashtable, "key1" ) );
	printf( "%s\n", ht_get( hashtable, "key2" ) );
	printf( "%s\n", ht_get( hashtable, "key3" ) );
	printf( "%s\n", ht_get( hashtable, "key4" ) );

	return 0;
}

odp_version.c

/* OpenDataPlane version of the Hashtable */
/*
 * The Keys are embedded in the entry_t structure
 * Which helps to reduce the memory fragmentation and improves
 * locality.
 */


#include <odp.h>

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

struct entry_s {
	uint8_t klen;
	uint8_t key[39];
	void *value;
	struct entry_s *next;
	odp_buffer_t buffer;
};

typedef struct entry_s entry_t;
typedef entry_t* entry_p;

struct hashtable_s {
	uint32_t size;
	struct entry_s **table;	
	odp_pool_t pool;
};

typedef struct hashtable_s hashtable_t;



/* Create a new hashtable. */
hashtable_t *ht_create( uint32_t size , odp_pool_t pool ) {

	hashtable_t *hashtable = NULL;
	int i;

	if( size < 1 ) return NULL;

	/* Allocate the table itself. */
	if( ( hashtable = malloc( sizeof( hashtable_t ) ) ) == NULL ) {
		return NULL;
	}

	/* Allocate pointers to the head nodes. */
	if( ( hashtable->table = malloc( sizeof(void*) * size ) ) == NULL ) {
		return NULL;
	}
	for( i = 0; i < size; i++ ) {
		hashtable->table[i] = NULL;
	}

	hashtable->size = size;
	hashtable->pool = pool;

	return hashtable;	
}

/* Hash a string for a particular hash table. */
uint32_t ht_hash( hashtable_t *hashtable,const uint8_t *key, uint8_t klen ) {
	const uint64_t  MagicPrime = 0x00000100000001b3;
	uint64_t        Hash       = 0xcbf29ce484222325;
	for ( ; klen; klen--,key++) 
		Hash = (Hash * MagicPrime) ^ *key;
	return Hash % hashtable->size;
}

int ht_keycheck(const uint8_t *key, uint8_t klen, const entry_t* ent){
	if(klen!=ent->klen)return 0;
	int i=0;
	for(;i<klen;++i)
		if(key[i]!=ent->key[i])return 0;
	return 1;
}

/* Create a key-value pair. */
entry_t *ht_newpair(hashtable_t* hashtable, const uint8_t *key, uint8_t klen, void *value ) {
	int i;
	entry_t *newpair;

	odp_buffer_t buf = odp_buffer_alloc(hashtable->pool);
	if(buf == ODP_BUFFER_INVALID) return NULL;

	newpair = odp_buffer_addr(buf);
	newpair->buffer = buf;

	newpair->klen = klen;
	for(i=0;i<klen;++i)
		newpair->key[i]=key[i];

	newpair->value = value;

	newpair->next = NULL;

	return newpair;
}

/* Insert a key-value pair into a hash table. */
int ht_set( hashtable_t *hashtable, const uint8_t *key, uint8_t klen, void *value, void **old_value ) {
	uint32_t bin = 0;
	entry_p newpair,next,first;

	bin = ht_hash( hashtable, key, klen );

	first = next = hashtable->table[ bin ];

	while( next != NULL ){
		if(ht_keycheck(key,klen,next)){
			*old_value = next->value;
			next->value = value;
			return 1; // return 1;
		}
		next = next->next;
	}
	*old_value = NULL;
	newpair = ht_newpair(hashtable, key, klen, value );
	if(newpair==NULL)
		return 0;

	newpair->next = first;
	hashtable->table[ bin ] = newpair;

	return 1;
}

/* Retrieve a key-value pair from a hash table. */
void *ht_get( hashtable_t *hashtable, const uint8_t *key, uint8_t klen ) {
	int bin = 0;
	entry_t *pair;

	bin = ht_hash( hashtable, key, klen );

	/* Step through the bin, looking for our value. */
	pair = hashtable->table[ bin ];
	while( pair != NULL ){
		if(ht_keycheck(key,klen,pair)){
			return pair->value;
		}
		pair = pair->next;
	}

	return NULL;
}
/* Delete a key-value pair from a hash table. */
void *ht_rem( hashtable_t *hashtable, const uint8_t *key, uint8_t klen ) {
	int bin = 0;
	void* value;
	entry_t *pair,**prev;

	bin = ht_hash( hashtable, key, klen );

	/* Step through the bin, looking for our value. */
	prev = &hashtable->table[ bin ];
	pair = *prev;
	while( pair != NULL ){
		if(ht_keycheck(key,klen,pair)){
			value = pair->value;
			*prev = pair->next;
			odp_buffer_free(pair->buffer);
			return value;
		}
		prev = &pair->next;
		pair = *prev;
	}

	return NULL;
}


#define HT_SET(hashtable,key,value) ht_set(hashtable,key,sizeof(key)-1,value,&x)
#define HT_GET(hashtable,key) ht_get(hashtable,key,sizeof(key)-1)
#define HT_REM(hashtable,key) ht_rem(hashtable,key,sizeof(key)-1)
#define V v?v:"(nil)"

int main(){
	odp_pool_param_t params;
	odp_pool_t pool;
	void* x = NULL;
	char* v;

	odp_init_global(NULL, NULL);
	odp_init_local(ODP_THREAD_CONTROL);

	odp_pool_param_init(&params);
	params.buf.align = 8;
	params.buf.size = sizeof(entry_t);
	params.buf.num = 1<<20;
	params.type = ODP_POOL_PACKET;
	pool = odp_pool_create("hashtab",&params);

	hashtable_t *hashtable = ht_create( 65536, pool );

	printf("HT_SET\n");
	HT_SET( hashtable, "key1", "inky" );
	HT_SET( hashtable, "key2", "pinky" );
	HT_SET( hashtable, "key3", "blinky" );
	HT_SET( hashtable, "key4", "floyd" );

	HT_REM( hashtable, "key3" );

	printf("HT_GET\n");
	v = HT_GET( hashtable, "key1" ); printf( "%s\n", V );
	v = HT_GET( hashtable, "key2" ); printf( "%s\n", V );
	v = HT_GET( hashtable, "key3" ); printf( "%s\n", V );
	v = HT_GET( hashtable, "key4" ); printf( "%s\n", V );
	return 0;
}