hashtable.h

数据结构的C语言实现

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

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


#ifndef DS_HASHTABLE_H
#define DS_HASHTABLE_H

#include "ds_define.h"


/*****************************************************************/
/*
* 哈希表节点结构
*/
/*****************************************************************/
typedef struct hashtable_node
{
	void *key,*data;//关键字和内容指针
	unsigned long hashvalue;//哈希值
	struct hashtable_node *next;//下一个节点指针，此为单链表结构
} hashtable_node;


/*****************************************************************/
/*
* 哈希表结构
*/
/*****************************************************************/
typedef struct hashtable
{
    struct hashtable_node **node_table;//指针链表，此为表格状
	unsigned int tablelength;//链表长度
	int tablelengthindex;//链表长度索引，此索引表示链表长度是2的索引次方
	unsigned int entrycount;//元素长度
	unsigned int entrylimit;//当前元素最大长度
	BOOL checkkeymutex;//是否检查关键字互斥，TRUE表示要检查，FALSE表示不检查
	unsigned long (*hashfromkey)(const void *key);//哈希方法，由外部定义
	int (*equalbykey)(const void *key1,const void *key2);//插入和搜索时使用的关键字比较方法，由外部定义
} hashtable;


/*****************************************************************/
/*
* 创建默认的关键字为int类型的哈希表
*/
/*****************************************************************/
hashtable *hashtable_create_default_intkey();

/*****************************************************************/
/*
* 创建关键字为int类型的哈希表，指定最小容纳的元素长度
* 参数说明：
* minsize：指定最小容纳的元素长度，
* 哈希表长度最大支持：minsize <= 2^32 * 0.7 (0.7为默认加载因子)，即minsize <= 2791728742
* checkkeymutex：是否关键字互斥，若确定关键字不会重复，则应传入FALSE，否则传入TRUE
  checkkeymutex为FALSE时，哈希表插入操作不检查关键字是否重复，能提高插入的性能
*/
/*****************************************************************/
hashtable *hashtable_create_intkey(unsigned int minsize,BOOL checkkeymutex);

/*****************************************************************/
/*
* 创建关键字为int类型的哈希表，指定最小容纳的元素长度及加载因子
* 参数说明：
* minsize：指定最小容纳的元素长度
* factor：加载因子，表示元素和链表实际长度的比例，此值在(0-1]之间，越大则空间利用率越高，越低则查询性能越好
* 哈希表长度最大支持：minsize/factor <= 2^32
* checkkeymutex：是否关键字互斥，若确定关键字不会重复，则应传入FALSE，否则传入TRUE
  checkkeymutex为FALSE时，哈希表插入操作不检查关键字是否重复，能提高插入的性能
*/
/*****************************************************************/
hashtable *hashtable_create_intkey_factor(unsigned int minsize,float factor,BOOL checkkeymutex);


/*****************************************************************/
/*
* 创建默认的关键字为字符串的哈希表
*/
/*****************************************************************/
hashtable *hashtable_create_default_stringkey();

/*****************************************************************/
/*
* 创建关键字为字符串的哈希表，指定最小容纳的元素长度
* 参数说明：
* minsize：指定最小容纳的元素长度，
* 哈希表长度最大支持：minsize <= 2^32 * 0.7 (0.7为默认加载因子)，即minsize <= 2791728742
* checkkeymutex：是否关键字互斥，若确定关键字不会重复，则应传入FALSE，否则传入TRUE
  checkkeymutex为FALSE时，哈希表插入操作不检查关键字是否重复，能提高插入的性能
*/
/*****************************************************************/
hashtable *hashtable_create_stringkey(unsigned int minsize,BOOL checkkeymutex);

/*****************************************************************/
/*
* 创建关键字为字符串的哈希表，指定最小容纳的元素长度及加载因子
* 参数说明：
* minsize：指定最小容纳的元素长度
* factor：加载因子，表示元素和链表实际长度的比例，此值在(0-1]之间，越大则空间利用率越高，越低则查询性能越好
* 哈希表长度最大支持：minsize/factor <= 2^32
* checkkeymutex：是否关键字互斥，若确定关键字不会重复，则应传入FALSE，否则传入TRUE
  checkkeymutex为FALSE时，哈希表插入操作不检查关键字是否重复，能提高插入的性能
*/
/*****************************************************************/
hashtable *hashtable_create_stringkey_factor(unsigned int minsize,float factor,BOOL checkkeymutex);

/*****************************************************************/
/*
* 创建哈希表
* 参数说明：
* minsize：指定最小容纳的元素长度
* 哈希表长度最大支持：minsize <= 2^32 * 0.7 (0.7为默认加载因子)，即minsize <= 2791728742
* checkkeymutex：是否关键字互斥，若确定关键字不会重复，则应传入FALSE，否则传入TRUE
  checkkeymutex为FALSE时，哈希表插入操作不检查关键字是否重复，能提高插入的性能
* hashfromkey：哈希函数
* equalbykey：关键字比较函数
*/
/*****************************************************************/
hashtable *hashtable_create(unsigned int minsize,BOOL checkkeymutex,
	unsigned int (*hashfromkey)(const void *key),int (*equalbykey)(const void *key1,const void *key2));

/*****************************************************************/
/*
* 创建哈希表
* 参数说明：
* minsize：指定最小容纳的元素长度
* factor：加载因子，表示元素和链表实际长度的比例，此值在(0-1]之间，越大则空间利用率越高，越低则查询性能越好
* 哈希表长度最大支持：minsize/factor <= 2^32
* checkkeymutex：是否关键字互斥，若确定关键字不会重复，则应传入FALSE，否则传入TRUE
  checkkeymutex为FALSE时，哈希表插入操作不检查关键字是否重复，能提高插入的性能
* hashfromkey：哈希函数
* equalbykey：关键字比较函数
*/
/*****************************************************************/
hashtable *hashtable_create_factor(unsigned int minsize,float factor,BOOL checkkeymutex,
	unsigned int (*hashfromkey)(const void *key),int (*equalbykey)(const void *key1,const void *key2));

/*****************************************************************/
/*
* 插入元素，若成功返回DS_SUCCESS，否则返回对应的错误代码
*/
/*****************************************************************/
DS_RESULT hashtable_insert(void *key,void *data,hashtable *dh);

/*****************************************************************/
/*
* 根据指定的关键字在指定的哈希表中搜索，若搜索不到则返回NULL
*/
/*****************************************************************/
void *hashtable_search_bykey(void *key,hashtable *dh);

/*****************************************************************/
/*
* 根据指定的关键字在指定的哈希表中搜索，并修改原数据为新数据，返回原数据 ，若搜索不到则返回NULL
*/
/*****************************************************************/
void *hashtable_modify_bykey(void *key,void *newvalue,hashtable *dh);

/*****************************************************************/
/*
* 删除指定的哈希表中指定的关键字的元素
* 返回值：返回此元素的指针，若找不到此元素，则返回NULL
* 参数说明：
* freedata：若为TRUE，则同时释放外部传入的key指针，否则不释放key指针
  若key指针指向栈自动分配的空间，此时freedata为TRUE时此方法将出错
*/
/*****************************************************************/
void *hashtable_remove_bykey(void *key,BOOL freekey,hashtable *dh);

/*****************************************************************/
/*
* 释放哈希表
* 参数说明：
* dh：要释放的哈希表
* freekey：若为TRUE，则同时释放外部传入的key指针，否则不释放key指针
  若key指针指向栈自动分配的空间，此时freekey为TRUE时此方法将出错
* freedata：若为TRUE，则同时释放外部传入的data指针，否则不释放data指针
  若data指针指向栈自动分配的空间，此时freedata为TRUE时此方法将出错
*/
/*****************************************************************/
void hashtable_free(hashtable *dh,BOOL freekey,BOOL freedata);



#endif