hash.c

/*
* list_head-like hash table implementation
* Author: Gyeonghwan Hong <[email protected]>
* Original Author: Tony Thompson <[email protected]>
*/

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

/* 
* Hash functions uses golden ratio prime.
* 2^31 + 2^29 - 2^25 + 2^22 - 2^19 - 2^16 + 1 
*/
#define GOLDEN_RATIO_PRIME_32 0x9e370001UL

#undef offsetof
#define offsetof(type, member) ((size_t) &((type *)0)->member)

#undef container_of
#define container_of(ptr,type,member) \
	      ((type*)((char*)(const typeof(((type*)0)->member)*)ptr-offsetof(type,member)))

struct htable_entry_s {
	long key;
	struct htable_entry_s *next;
};

typedef struct htable_entry_s htable_entry_t;

struct htable_s {
	int size;
	struct htable_entry_s **table;	
};

typedef struct htable_s htable_t;


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

	htable_t *hashtable = NULL;
	int i;

	if( size < 1 ) return NULL;

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

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

	hashtable->size = size;

	return hashtable;	
}

/* Hash an integer value for a particular hash table. */
int ht_hash( htable_t *hashtable, long key ) {
	unsigned long int hashval;
	hashval = key * GOLDEN_RATIO_PRIME_32;
	return hashval % hashtable->size;
}

/* Set a new entry. */
void ht_set_newentry( long key, htable_entry_t *newentry ) {
	/* entry should be allocated in ahead. */
	newentry->key = key;
	newentry->next = NULL;
}

/* Insert a new entry into a hash table if do not exist. */
void ht_set( htable_t *hashtable, long key, htable_entry_t *newentry ) {
	int bin = 0;
	htable_entry_t *next = NULL;
	htable_entry_t *last = NULL;

	bin = ht_hash( hashtable, key );

	next = hashtable->table[ bin ];

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

	/* There's already an entry. Let's remove the entry in ahead. */
	if( next != NULL && (key == next->key)) {
		htable_entry_t *newnext = next->next;

		if(hashtable->table[bin] == next)
			hashtable->table[bin] = newnext;
		else
			last->next = newnext;
	}

	/* Set the new entry. */
	ht_set_newentry( key, newentry );

	/* We're at the start of the linked list in this bin. */
	if( next == hashtable->table[ bin ] ) {
		newentry->next = next;
		hashtable->table[ bin ] = newentry;

		/* We're at the end of the linked list in this bin. */
	} else if ( next == NULL ) {
		last->next = newentry;

		/* We're in the middle of the list. */
	} else  {
		newentry->next = next;
		last->next = newentry;
	}
}

/* Retrieve an entry from a hash table. */
htable_entry_t *ht_get( htable_t *hashtable, long key ) {
	int bin = 0;
	htable_entry_t *resentry;

	bin = ht_hash( hashtable, key );

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

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

	} else {
		return resentry;
	}
	
}

/* Remove an entry from a hash table. (by key) */
htable_entry_t* ht_remove_by_key(htable_t *hashtable, long key) {
	int bin = 0;
	htable_entry_t *next = NULL;
	htable_entry_t *last = NULL;

	bin = ht_hash( hashtable, key );

	next = hashtable->table[ bin ];

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

	/* If there's the entry, remove the entry. */
	if( next != NULL && (key == next->key)) {
		htable_entry_t *newnext = next->next;

		if(hashtable->table[bin] == next)
			hashtable->table[bin] = newnext;
		else
			last->next = newnext;

		/* Deallocation cannot be done here. */
		return next;
	} else {
		return NULL;
	}
}

htable_entry_t* ht_remove_by_entry(htable_t *hashtable, htable_entry_t* entry) {
	long key = entry->key;
	return ht_remove_by_key(hashtable, key);
}

/***** Customized entry code from here *****/
struct test_entry_s {
	/* You can define your own data structure here. */
	char* value;

	/* At last, you should insert hashtable entry structure here. */
	htable_entry_t htable_entry;
};
typedef struct test_entry_s test_entry_t;

/* Make your own new entry. */
test_entry_t* make_test_entry(htable_t* hashtable, long key, char* value) {
	test_entry_t* newentry;
	
	/* Make a new entry. */
	if((newentry = malloc(sizeof(test_entry_t))) == NULL) {
			return NULL;
	}
	
	if((newentry->value = strdup(value)) == NULL) {
		return NULL;
	}

	/* Put the entry into hashtable. */
	ht_set(hashtable, key, &(newentry->htable_entry));

	return newentry;
}

/* Get a customized entry from hashtable by integer key. */
test_entry_t* get_test_entry(htable_t* hashtable, long key) {
	htable_entry_t* hentry;
	hentry = ht_get(hashtable, key);
	if(hentry == NULL)
		return NULL;

	/* By container_of, you can recover your own entry from common hashtable entry. */
	return (test_entry_t*)container_of(hentry, test_entry_t, htable_entry);
}

/* Remove customized entry by key. */
void remove_test_entry_by_key(htable_t* hashtable, long key) {
	htable_entry_t* hentry;
	hentry = ht_remove_by_key(hashtable, key);
	free((test_entry_t*)container_of(hentry, test_entry_t, htable_entry));
}

/* Remove customized entry. */
void remove_test_entry(htable_t* hashtable, test_entry_t* entry) {
	htable_entry_t* hentry;
	hentry = ht_remove_by_entry(hashtable, &(entry->htable_entry));
	free((test_entry_t*)container_of(hentry, test_entry_t, htable_entry));
}

/* Test main function */
int main( int argc, char **argv ) {

	htable_t* hashtable = ht_create(65536);

	test_entry_t* entry_to_delete;

	make_test_entry(hashtable, 123, "inky");
	make_test_entry(hashtable, 456, "pinky");
	make_test_entry(hashtable, 789, "blinky");
	entry_to_delete = make_test_entry(hashtable, 369, "floyd");

	printf("%s\n", get_test_entry(hashtable, 123)->value );
	printf("%s\n", get_test_entry(hashtable, 456)->value );
	printf("%s\n", get_test_entry(hashtable, 789)->value );
	printf("%s\n", get_test_entry(hashtable, 369)->value );

	remove_test_entry(hashtable, entry_to_delete);

	printf("%s\n", get_test_entry(hashtable, 123)->value );
	printf("%s\n", get_test_entry(hashtable, 456)->value );
	printf("%s\n", get_test_entry(hashtable, 789)->value );
	printf("It will be null: %x\n", (int)get_test_entry(hashtable, 369) );

	return 0;
}