해시 테이블 구현

main.c

#include "PXHashTable.h"
/*** main ***/

int main(int argc, const char** argv){
	PXHashTableRef table = PXHashTableCreate(100);
	int a=1, b=2, c=3, d=4;
	PXHashTableAddItem(table,"a", (void*)&a);
	PXHashTableAddItem(table,"b", (void*)&b);
	PXHashTableAddItem(table,"b2j", (void*)&c);
	PXHashTableAddItem(table,"e", (void*)&d);
	
	printf("%d\n", *((int*)(PXHashTableGetItemForKey(table, "a"))));
	printf("%d\n", *((int*)(PXHashTableGetItemForKey(table, "b"))));
	printf("%d\n", *((int*)(PXHashTableGetItemForKey(table, "b2j"))));
	printf("%d\n", *((int*)(PXHashTableGetItemForKey(table, "e"))));

	PXHashTableRelease(table);
	return 0;
}

PXHashTable.c

/*
 * file: PXHashTable.c
 * HashTable Definition File
 * by sooop
 * 2013. 10. 24. 
 * 
 */

#include "PXHashTable.h"

/*** internal datastructure and typedefs ***/

struct _hashNode {
	struct _hashNode *next;
	char * key;
	void * value;
};
typedef struct _hashNode* PXHashNodeRef;


struct _hashTable{
	unsigned int size;
	PXHashNodeRef * buckets;
	unsigned int (*hashfunc)(const char*);
};


/*** internal function prototype ***/

static PXHashNodeRef PXHashNodeCreate(const char* key, void* value);
static void PXHashNodeRelease(PXHashNodeRef node);

/*** all function definition ***/

// API Functions

PXHashTableRef PXHashTableCreate(unsigned int size)
{
	struct _hashTable* table;
	table = (struct _hashTable*)malloc(sizeof(struct _hashTable));
	table->size = size;
	table->buckets = (PXHashNodeRef*)malloc(sizeof(PXHashNodeRef)*size);
	memset(table->buckets, 0, sizeof(PXHashNodeRef)*size);
	table->hashfunc = NULL;

	return table;
}


void PXHashTableRelease(PXHashTableRef table)
{
	struct _hashTable *_table = (struct _hashTable*)table;
	PXHashNodeRef t, n;
	int i=0;
	while(i<_table->size){
		t = _table->buckets[i];
		while(t != NULL){
			n = t->next;
			PXHashNodeRelease(t);
			t = n;
		}
		i++;
	}
	free(_table);
	table = NULL;
}


// temporary hash func (it is suck!!!)

unsigned int hashit(const char* key)
{
	return (strlen(key)) % 77;
}


BOOL PXHashTableHasKey(PXHashTableRef table,const char* key)
{
	struct _hashTable *_table = (struct _hashTable*)table;
	unsigned int h;
	if(_table->hashfunc == NULL)
	{
		h = hashit(key);
	} else {
		h = _table->hashfunc(key);
	}
	if (_table->buckets[h] == NULL) return NO;
	PXHashNodeRef t, n;
	t = _table->buckets[h];
	while(t!=NULL){
		if(!strcmp(key, t->key)) return YES;
		n = t->next;
		t = n;
	}
	return NO;
}


BOOL PXHashTableAddItem(PXHashTableRef table, const char* key, void* value)
{
	struct _hashTable *_table = (struct _hashTable*)table;
	if(PXHashTableHasKey(_table, key)) return NO;
	PXHashNodeRef node = PXHashNodeCreate(key, value);
	unsigned int h;
	if(_table->hashfunc == NULL){
		h = hashit(key);
	} else {
		h = _table->hashfunc(key);
	}

	if(_table->buckets[h] == NULL){
		_table->buckets[h] = node;
	} else {
		PXHashNodeRef n = _table->buckets[h];
		_table->buckets[h] = node;
		node->next = n;
	}
	return YES;
}


void* PXHashTableGetItemForKey(PXHashTableRef table, const char* key)
{
	struct _hashTable *_table = (struct _hashTable*)table;
	unsigned int h;
	h = (_table->hashfunc == NULL) ? hashit(key) : _table->hashfunc(key);
	PXHashNodeRef node, next;
	node = _table->buckets[h];
	while(node!=NULL){
		next = node->next;
		if(!strcmp(key, node->key)){
			return node->value;
		}
		node = next;
	}
	return NULL;
}


// Internal Functions
PXHashNodeRef PXHashNodeCreate(const char* key, void* value)
{
	PXHashNodeRef node;
	node = (PXHashNodeRef)malloc(sizeof(struct _hashNode));
	node->key = (char *)malloc(sizeof(char)*strlen(key)+1);
	strcpy(node->key, key);
	node->value=value;
	node->next = NULL;

	return node;
}


void PXHashNodeRelease(PXHashNodeRef node)
{
	free(node->key);
	free(node);
	node = NULL;
}

PXHashTable.h

/*
 * file: PXHashTable.h
 * HashTable Hader file
 * by sooop
 * 2013. 10. 24. 
 * 
 */

/*** includes ***/
#include <stdio.h>
#include <stdlib.h>
#include <mem.h>
#include <string.h>

/*** symbolic string constant ***/
#define YES ((BOOL)1)
#define NO ((BOOL)0)

/*** type definition ***/
typedef void* PXHashTableRef;
typedef unsigned char BOOL;

/*** API function declaration ***/
PXHashTableRef PXHashTableCreate(unsigned int size);
void PXHashTableRelease(PXHashTableRef table);
BOOL PXHashTableHasKey(PXHashTableRef table, const char* key);
BOOL PXHashTableAddItem(PXHashTableRef table, const char* key, void* value);
void* PXHashTableGetItemForKey(PXHashTableRef table, const char* key);