巧在最近有一个XPM解析的小项目，为了让XPM存储和绘更通用一些，得自行实现一个Hash表，
草草地写了一个，还有很多bug没解决。放上来吧，这样可以逼自己去改进
版本一开始为0.0.1。 07/03/29
还不能正常运行。
版本更新为0.0.2了。 07/03/30
bug还是存在啊。。
版本更新为0.0.3了。 07/03/31
可以运行了~~开始写一些测试和应用。这样才会有进一步的改进。
版本更新为0.0.4 。。 07/04/02
更正了一个很BT的C语言错误（由#define MAKE_JR_HASH引起），这个小hash终于可以通过自己的shell测试了。
版本更新为0.0.5。。 07/04/04
让hash.h支持C++编译器。主要修正两种语言对struct T及*T的差异处理。
更正hash.c当中jr_hash_set时的一个BUG，0.0.4版在value项不等长时会更新失败。
版本更新为0.0.6。。 07/04/04
更正hash.c当中jr_hash_get时的一个BUG，0.0.5版在删除bucket链头部时会丢失数据。
准备在hash.c中试验性地加入一些便利接口
修改代码，应对gcc -Wall的所有warnings
版本更新为0.0.7。。 07/04/25
应用块结构的特性，修正原有的一个宏bug，其实仅仅是加了一行(int i);
版本更新为0.0.8。。 07/05/17
处理很多编译警告
文件hash.h
/**jr_hash 一个通用的hash表c语言实现 此文件存于公有域，作者放弃任何版权
*以简洁代码为目标，方便加入到所有需要符号表的模块中
*使用简单的开链存储
*不对代码做太深度的优化，以保持简洁
**/
#ifndef JR_HASH_H
#define JR_HASH_H
#ifdef __cplusplus
extern "C" {
#endif
#ifdef __cplusplus
#define T jr_hash_t
typedef struct jr_hash *T;
#define TI jr_item_t
typedef struct jr_item *TI;
struct jr_item{ /* 包括长度及数据指针，通用的hash表数据项 */
void *data;
unsigned int len;
};
#else /*C interface */
#define T jr_hash_t
typedef struct T *T;
#define TI jr_item_t
typedef struct TI *TI;
typedef struct TI jr_item;
struct TI{ /* 包括长度及数据指针，通用的hash表数据项 */
void *data;
unsigned int len;
};
#endif
extern T jr_hash_init(void); /* void -> new hash :生成一个新的表 */
extern int jr_hash_free(T *); /* hash pointer -> sucess :删除一个表 */
extern int jr_hash_set(T, TI, TI); /* hash, key ,value -> success :更新或插入符号表的一个元素 */
extern TI jr_hash_get(T, TI); /* hash, key -> value or NULL :返回一个元素的值或者NULL */
extern int jr_hash_del(T, TI); /* hash, key ->sucess f:删除一个元素 */
#undef T
#undef TI
#ifdef __cplusplus
}
#endif
#endif
文件hash.c
/**jr_hash 的实现代码 此文件存于公有域，作者放弃任何版权
*以简洁代码为目标，方便加入到所有需要符号表的模块中
*使用简单的开链存储
*不对代码做太深度的优化，以保持简洁
**/
#include "hash.h"
#include <stdlib.h>
#include <string.h>
#ifdef JR_HASH_TEST
#include <stdio.h>
#endif
typedef unsigned int jr_uint;
typedef unsigned char jr_uchar;
struct jr_hash_item_t;
typedef struct jr_hash_item_t *jr_hash_item_t;
struct jr_hash_t{
jr_uint bucket_size;
jr_uint bucket_grow;
jr_uint item_count;
jr_hash_item_t *bucket;
};
struct jr_hash_item_t{
struct jr_item_t key;
struct jr_item_t value;
jr_hash_item_t next;
};
/*from effective java*/
#define JR_HASH(h,x) h = ((h*31)+(x))
#define MAKE_JR_HASH /
do{ /
jr_uint i; /
hc=7; /
pc=(jr_uchar*)key_->data; /
for (i=0; i<key_->len; ++i,++pc){ /
JR_HASH(hc,*pc); /
} /
}while(0)
jr_hash_t jr_hash_init(void){
jr_hash_t new_hash;
jr_hash_item_t* new_bucket;
jr_uint i;
new_hash = (jr_hash_t) malloc(sizeof(struct jr_hash_t));
if (NULL == new_hash)
return NULL;
new_hash->bucket_size = 32;
new_hash->bucket_grow = 0;
new_hash->item_count = 0;
new_bucket = (jr_hash_item_t*) malloc( (sizeof(jr_hash_item_t)) * new_hash->bucket_size );
if (NULL == new_bucket){
free(new_hash);
return NULL;
}
for (i=0; i < new_hash->bucket_size; ++i)
new_bucket[i] = (jr_hash_item_t)NULL;
new_hash->bucket = new_bucket;
return new_hash;
}
int jr_hash_free(jr_hash_t *phash_){
jr_uint i;
jr_hash_item_t p,head;
jr_hash_t hash;
jr_hash_item_t * bucket;
if ( (NULL==phash_) || (NULL==*phash_))
return 0;
hash = *phash_;
bucket = hash->bucket;
for (i=0; i<hash->bucket_size; ++i){
head = hash->bucket[i];
while (NULL!=head){
p = head;
head = head->next;
free(p->key.data);
free(p->value.data);
free(p);
}
}
free(bucket);
free(hash);
*phash_ = NULL;
return 1;
}
static int jr_hash_rehash(jr_hash_t hash_, jr_uint len_){
jr_uint hc; /*the hash code*/
jr_uchar *pc;
jr_uint i;
jr_hash_item_t item,head;
jr_hash_item_t * new_bucket;
jr_item_t key_;
new_bucket = (jr_hash_item_t*) malloc( (sizeof(jr_hash_item_t)) * len_ );
if (NULL==new_bucket)
return 0;
memset(new_bucket, 0, (sizeof(jr_hash_item_t)) * len_ );
for(i=0; i<hash_->bucket_size; ++i){
head = hash_->bucket[i];
if (NULL==head)
continue;
while (NULL!=head){
key_ = &head->key;
MAKE_JR_HASH;
hc = hc & (len_-1);
item = head;
head = head->next;
item->next = new_bucket[hc];
new_bucket[hc] = item;
}
}
free(hash_->bucket);
hash_->bucket = new_bucket;
hash_->bucket_size = len_;
hash_->bucket_grow = len_/5;
return 1;
}
int jr_hash_set(jr_hash_t hash_, jr_item_t key_, jr_item_t value_){
jr_uint hc; /*the hash code*/
jr_uchar *pc;
jr_hash_item_t head;
jr_uchar *buf;
if (NULL==hash_ || NULL==key_ || NULL==key_->data || NULL==value_ || NULL==value_->data) /*接口对外界不敢轻信*/
return 0;
if (hash_->bucket_size < hash_->item_count + hash_->bucket_grow){
if(!jr_hash_rehash(hash_, hash_->bucket_size*2))
return 0;
}
MAKE_JR_HASH;
hc = hc & (hash_->bucket_size-1);
head = hash_->bucket[hc];
while (NULL!=head){
if (key_->len == head->key.len && !memcmp(key_->data, head->key.data, key_->len)){
if (head->value.len < value_->len){
buf = realloc((void*)head->value.data, value_->len);
if (NULL==buf){
return 0;
}
else{
head->value.data = buf;
}
}
memmove(head->value.data, value_->data, value_->len);
head->value.len = value_->len;
return 1;
}
head = head->next;
}
head = (jr_hash_item_t) malloc(sizeof(struct jr_hash_item_t));
if (NULL==head)
return 0;
buf = (void*)malloc(key_->len);
if (NULL==buf){
free(head);
return 0;
}
head->key.data = buf;
head->key.len = key_->len;
buf = (void*)malloc(value_->len);
if (NULL==buf){
free(head->key.data);free(head);
return 0;
}
head->value.data= buf;
head->value.len = value_->len;
memmove(head->key.data, key_->data, key_->len);
memmove(head->value.data, value_->data, value_->len);
head->next = hash_->bucket[hc];
hash_->bucket[hc] = head;
++hash_->item_count;
return 1;
}
jr_item_t jr_hash_get(jr_hash_t hash_, jr_item_t key_){
jr_uint hc; /*the hash code*/
jr_uchar *pc;
jr_hash_item_t head;
if (NULL==hash_ || NULL==key_ || NULL==key_->data) /*接口对外界不敢轻信*/
return NULL;
MAKE_JR_HASH;
hc = hc & (hash_->bucket_size-1);
head = hash_->bucket[hc];
while (NULL!=head){
if (key_->len == head->key.len && !memcmp(key_->data, head->key.data, key_->len)){
return &head->value;
}
head = head->next;
}
return NULL;
}
int jr_hash_del(jr_hash_t hash_, jr_item_t key_){
jr_uint hc; /*the hash code*/
jr_uchar *pc;
jr_hash_item_t item,head;
if (NULL==hash_ || NULL==key_ || NULL==key_->data) /*接口对外界不敢轻信*/
return 0;
MAKE_JR_HASH;
hc = hc & (hash_->bucket_size-1);
head = hash_->bucket[hc];
item = head;
while (NULL!=head){
if (key_->len == head->key.len && !memcmp(key_->data, head->key.data, key_->len)){
if (item==head){
hash_->bucket[hc]=head->next;
}
item->next = head->next;
head->next=NULL;
free(head->key.data);
free(head->value.data);
free(head);
head=NULL;
--hash_->item_count;
return 1;
}
item = head;
head = head->next;
}
return 0;
}
#ifdef JR_HASH_TEST
#include<stdio.h>
#define OI(x) printf("%d/n",(x))
#define BUFLEN 1024
static void jr_hash_dump(jr_hash_t hash_){ /*for debug*/
jr_uint i;
jr_hash_item_t head;
for(i=0; i<hash_->bucket_size; ++i){
head = hash_->bucket[i];
if (NULL==head){
printf("bucket:%9d is NULL/n",i);
continue;
}
printf("bucket:%9d is:/n",i);
while (NULL!=head){
printf("%s/t:%s/n",(char *)head->key.data,(char *)head->value.data);
head = head->next;
}
}
}
int jr_hash_setii(jr_hash_t hash_, int key_, int value_){
jr_item ikey;
jr_item ival;
ival.len = ikey.len = sizeof(int);
ikey.data = &key_;
ival.data = &value_;
return jr_hash_set(hash_, &ikey, &ival);
}
int jr_hash_getii(jr_hash_t hash_, int key_, int *pvalue_){
jr_item ikey;
jr_item_t pval;
ikey.len = sizeof(int);
ikey.data = &key_;
pval = jr_hash_get(hash_, &ikey);
if (NULL!=pval){
*pvalue_ = *((int *)(pval->data));
return 1;
}
else{
return 0;
}
}
int jr_hash_setl(jr_hash_t hash_,
int key_len_, void *key_data_,
int value_len_, void *value_data_){
jr_item ikey;
jr_item ival;
ikey.len = key_len_;
ival.len = value_len_;
ikey.data = key_data_;
ival.data = value_data_;
return jr_hash_set(hash_, &ikey, &ival);
}
int jr_hash_getl(jr_hash_t hash_,
int key_len_, void *key_data_){
jr_item ikey;
ikey.len = key_len_;
ikey.data = key_data_;
return (int)jr_hash_get(hash_, &ikey);
}
int main(){
jr_hash_t h;
jr_item ikey;
jr_item ival;
jr_item_t hr;
jr_uchar *vpos,*kpos;
jr_uchar buf[BUFLEN];
h = jr_hash_init();
while(fgets(buf,BUFLEN,stdin)){
fflush(stdin);
if(strlen(buf)<2)
break;
switch(buf[0]){
case 's':/*set key value*/
strtok(buf," ");
kpos = strdup(strtok(NULL," /n"));
vpos = strdup(strtok(NULL,"/n"));
ikey.len = strlen(kpos)+1;
ikey.data = kpos;
ival.len = strlen(vpos)+1;
ival.data = vpos;
jr_hash_set(h,&ikey,&ival);
free(vpos);free(kpos);
//printf("k:%d,v:%d,l:%d,b:%d,len:%d/n",kpos-buf,vpos-buf,strlen(buf),buf,ikey.len);
break;
case 'g':/*get key =>value*/
strtok(buf," ");
kpos = strdup(strtok(NULL," /n"));
ikey.len = strlen(kpos)+1;
ikey.data = kpos;
hr = jr_hash_get(h,&ikey);
if (hr)
printf("value is:%s/n",(char *)hr->data);
free(kpos);
//printf("k:%d,v:%d,l:%d,b:%d,len:%d/n",kpos-buf,vpos-buf,strlen(buf),buf,ikey.len);
break;
case 'k':/*get key =>value*/
strtok(buf," ");
kpos = strdup(strtok(NULL," /n"));
ikey.len = strlen(kpos)+1;
ikey.data = kpos;
jr_hash_del(h,&ikey);
free(kpos);
break;
case 'd':
jr_hash_dump(h);
break;
}
//printf("%s/n",buf);
fflush(stdout);
}
jr_hash_free(&h);
return 0;
}
#endif