hashtable.c

数据结构的C语言实现

/*****************************************************************/
/*
* Copyright (c) 2008,北京归创科技有限公司技术部
* All rights reserved.
* 
* 文件名称：hashtable.c
* 用    途：哈希表的实现
* 创建日期：2008年5月29日
*/

/*****************************************************************/


#include "hashtable.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <assert.h>


const unsigned int default_minsize = 100;
const float default_factor = 0.7;
const BOOL default_checkkeymutex = TRUE;


//DJB string hash
static unsigned long default_hashfromstringkey(const void *key)
{
    char *str = (char *)key;
    unsigned long hash = 5381;
    int c;
    while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    return hash;
}

static int default_equalstringkeys(const void *key1,const void *key2)
{
    return strcmp((char *)key1,(char *)key2);
}
//Thomas Wang int hash
static unsigned long default_hashfromintkey(const void *key)
{
    int k = (int)key;
	k = ~k + (k << 15); // key = (key << 15) - key - 1;
    k = k ^ (k >> 12);
    k = k + (k << 2);
    k = k ^ (k >> 4);
    k = k * 2057; // key = (key + (key << 3)) + (key << 11);
    k = k ^ (k >> 16);
    return (unsigned long)k;
}
static int default_equalintkeys(const void *key1,const void *key2)
{
	return (int)key1 == (int)key2 ? 0 : 1;
}

static unsigned int gettableindex(unsigned long hashvalue,int tablelengthindex)
{
	return hashvalue - ( hashvalue >> tablelengthindex << tablelengthindex );//取模运算
	//return (unsigned int)(hashvalue % (unsigned long)tablelength);
}

static DS_RESULT hashtable_expand(hashtable *dh)
{
	hashtable_node *dh_node;
	unsigned int t_index,index,newsize;
	BOOL freetable = FALSE;
	hashtable_node **newtable;
	if((dh->tablelengthindex + 1) > 32) return DS_TABLELENGTH_LIMIT;
	newsize = dh->tablelength << 1;//链表长度增加一倍
	newtable = (hashtable_node **)malloc(sizeof(hashtable_node *) * newsize);
	if(newtable) 
	{
		memset(newtable,0,sizeof(hashtable_node *) * newsize);
		freetable = TRUE;
	}
	else 
	{
		newtable = (hashtable_node **)realloc(dh->node_table,sizeof(hashtable_node *) * newsize);
		if(newtable) 
		{
			memset(dh->node_table + sizeof(hashtable_node *) * dh->tablelength,0,
				sizeof(hashtable_node *) * ( newsize - dh->tablelength));
		}
	}
	if(newtable)
	{
        for(t_index = 0; t_index < dh->tablelength; t_index++)
		{
			while((dh_node = dh->node_table[t_index]) != NULL)
			{
				dh->node_table[t_index] = dh_node->next;
				index = gettableindex(dh->hashfromkey(dh_node->key),dh->tablelengthindex + 1);
				dh_node->next = newtable[index];
                newtable[index] = dh_node;
			}
		}
		if(freetable) free(dh->node_table);
		dh->node_table = newtable;
		dh->tablelength = newsize;
		dh->tablelengthindex++;
		dh->entrylimit *= 2;
		return DS_SUCCESS;
	}
	else 
	{
		return DS_MEMORY_ERROR;
	}
}

hashtable *hashtable_create_default_intkey()
{
    return hashtable_create_factor(default_minsize,default_factor,default_checkkeymutex,
		default_hashfromintkey,default_equalintkeys);
}
hashtable *hashtable_create_intkey(unsigned int minsize,BOOL checkkeymutex)
{
	return hashtable_create_factor(minsize,default_factor,checkkeymutex,
		default_hashfromintkey,default_equalintkeys);
}

hashtable *hashtable_create_intkey_factor(unsigned int minsize,float factor,BOOL checkkeymutex)
{
	return hashtable_create_factor(minsize,factor,checkkeymutex,
		default_hashfromintkey,default_equalintkeys);
}

hashtable *hashtable_create_default_stringkey()
{
	return hashtable_create_factor(default_minsize,default_factor,default_checkkeymutex,
		default_hashfromstringkey,default_equalstringkeys);
}

hashtable *hashtable_create_stringkey(unsigned int minsize,BOOL checkkeymutex)
{
    return hashtable_create_factor(minsize,default_factor,checkkeymutex,
		default_hashfromstringkey,default_equalstringkeys);
}

hashtable *hashtable_create_stringkey_factor(unsigned int minsize,float factor,BOOL checkkeymutex)
{
	return hashtable_create_factor(minsize,factor,checkkeymutex,
		default_hashfromstringkey,default_equalstringkeys);
}

hashtable *hashtable_create(unsigned int minsize,BOOL checkkeymutex,
	unsigned int (*hashfromkey)(void *key),int (*equalbykey)(void *key1,void *key2))
{
	return hashtable_create_factor(minsize,default_factor,checkkeymutex,
		hashfromkey,equalbykey);
}

hashtable *hashtable_create_factor(unsigned int minsize,float factor,BOOL checkkeymutex,
	unsigned int (*hashfromkey)(void *key),int (*equalbykey)(void *key1,void *key2))
{
	long lsize;
	unsigned int index,size;
	hashtable *dh;
	lsize = minsize/factor;
	if(lsize > (1u << 31)) return NULL;//1u == (unsigned int)1 1u << 31 = 4294967296
	for(index = 0; index < 32; index++)
	{
		if((1u << index ) >= lsize) 
		{
			lsize = 1u << index;
			break;
		}
	}
	size = (unsigned int)lsize;
	dh = MALLOC(hashtable,1);
	if(!dh) return NULL;
	dh->node_table = (hashtable_node **)malloc(sizeof(hashtable_node *) * size);
	if(!dh->node_table) return NULL;
	memset(dh->node_table,0,sizeof(hashtable_node *) * size);
	dh->tablelength = size;
	dh->tablelengthindex = index;
	dh->entrycount = 0;
	dh->entrylimit = (unsigned int)(size*factor);
	dh->checkkeymutex = checkkeymutex;
	dh->hashfromkey = hashfromkey;
	dh->equalbykey = equalbykey;
	return dh;
}

DS_RESULT hashtable_insert(void *key,void *data,hashtable *dh)
{
	hashtable_node *dh_node,*dh_newnode;
	unsigned int t_index;
	DS_RESULT r;
	assert(dh);
	if((dh->entrycount + 1) > dh->entrylimit) 
	{
		r = hashtable_expand(dh);
		if(r != DS_SUCCESS) return r;
	}
	if(dh->checkkeymutex)
	{
		if(hashtable_search_bykey(key,dh) != NULL) return DS_DUPLICATE_KEY;
	}
	dh_newnode = MALLOC(hashtable_node,1);
	if(!dh_newnode) return DS_MEMORY_ERROR;
	dh_newnode->key = key;
	dh_newnode->data = data;
	dh_newnode->hashvalue = dh->hashfromkey(key);
	t_index = gettableindex(dh_newnode->hashvalue,dh->tablelengthindex);
	dh_newnode->next = *(dh->node_table+t_index);
    *(dh->node_table+t_index) = dh_newnode;
	dh->entrycount++;
	return DS_SUCCESS;
}

void *hashtable_search_bykey(void *key,hashtable *dh)
{
	hashtable_node *dh_node;
	unsigned int t_index;
	unsigned long hv;
	assert(dh);
	hv = dh->hashfromkey(key);
	t_index = gettableindex(hv,dh->tablelengthindex);
    dh_node = *(dh->node_table+t_index);
	while(dh_node) 
	{
		if(dh_node->hashvalue == hv && dh->equalbykey(key,dh_node->key) == 0) return dh_node->data;
		dh_node = dh_node->next;
	}
	return NULL;
}
void *hashtable_modify_bykey(void *key,void *newvalue,hashtable *dh)
{
	hashtable_node *dh_node;
	unsigned int t_index;
	unsigned long hv;
	void *oldvalue;
	assert(dh);
	hv = dh->hashfromkey(key);
	t_index = gettableindex(hv,dh->tablelengthindex);
    dh_node = *(dh->node_table+t_index);
	while(dh_node)
	{
		if(dh_node->hashvalue == hv && dh->equalbykey(key,dh_node->key) == 0)
		{
			oldvalue = dh_node->data;
			dh_node->data = newvalue;
			return oldvalue;
		}
		dh_node = dh_node->next;
	}
	return NULL;
}

void *hashtable_remove_bykey(void *key,BOOL freekey,hashtable *dh)
{
	hashtable_node *dh_node,*dh_prenode;
	unsigned int t_index;
	assert(dh);
	t_index = gettableindex(dh->hashfromkey(key),dh->tablelengthindex);
	if(!dh->node_table[t_index]) return NULL;
	else
	{
        dh_prenode = dh->node_table[t_index];
		dh_node = dh_prenode;
		while(dh_node) 
		{
			if(dh->equalbykey(key,dh_node->key) == 0) 
			{
				if(dh_prenode == dh_node) dh_prenode = dh_node->next;
				else dh_prenode->next = dh_node->next;
				if(freekey) free(dh_node->key);
				dh->entrycount--;
				return dh_node->data;
			}
			else 
			{
				dh_prenode = dh_node;
				dh_node = dh_node->next;
			}
		}
		return NULL;
	}
}

void hashtable_free(hashtable *dh,BOOL freekey,BOOL freedata)
{
    hashtable_node *dh_node,*dh_nextnode;
	unsigned int t_index;
	if(!dh) return;
	for(t_index = 0; t_index < dh->tablelength; t_index++)
	{
		if(!dh->node_table[t_index]) continue;
		dh_node = dh->node_table[t_index];
		while(dh_node) 
		{
			dh_nextnode = dh_node->next;
			if(freekey) free(dh_node->key);
			if(freedata) free(dh_node->data);
			free(dh_node);
			dh_node = dh_nextnode;
		}
	}
	free(dh->node_table);
	free(dh);
}