寫了個小小的c語言hash table實現,用單鏈表處理沖突.
lh_strhash 函數是從網上copy的, 已記不清來源了.
hash.h
/*
* Write :Gan Jian Hui
* Date : 2006/07/18
* Description : hash table manager
*
*
*/
#ifndef _LINUX_GHASH_H_
#define _LINUX_GHASH_H_
#include
/*#include */
#ifndef __USE_ISOC99
#define inline
#endif
#define create_hashtable(hsize) hash_create(lh_strhash, equal_str, hsize)
/*
* hash function
*/
unsigned int lh_strhash(void *src) ;
int equal_str(void *k1, void *k2) ;
struct hashentry ;
struct _hashtable ;
typedef struct _hashtable hashtable ;
/*
* Description :Create hash table
*
* sizeof(struct _hashtable) = 16
* sizeof(void *)= 4
* tab->hashlist size= 4*size
*
*/
hashtable *hash_create(unsigned int (*keyfunc)(void *),
int (*comparefunc)(void *,void *),
int size) ;
/*
*
*Desc : free hash table
*
*/
void hash_free(hashtable *tab) ;
/*
*Desc : Insert Data to hash table
*
*
*/
void hash_insert(void *key, void *data, hashtable *tab) ;
/*
*
*Desc :Remove Item from hash table
*
*
*/
void hash_remove(void *key, hashtable *tab) ;
void *hash_value(void *key, hashtable *tab) ;
void hash_for_each_do (hashtable *tab, int (cb)(void *, void *)) ;
int hash_count(hashtable *tab) ;
#endif
hash.c
/*
* Write :Gan Jian Hui
* Date : 2006/07/18
* Description : hash table manager
*
*
*/
#include
#ifdef DMALLOC
#include
#else
#include
#endif
#include "hash.h"
#include "comm.h"
#ifndef __USE_ISOC99
#define inline
#endif
/*
*
* list for hash data
*/
struct hashentry
{
void *key ;
void *data ;
struct hashentry *next ;
};
struct _hashtable
{
unsigned int (*gethash)(void *);
int (*compare)(void *,void *);
int hashsize ;
int count ;
struct hashentry **hashlist ; /* store data */
} ;
#define hashindex(key, tab) ((tab->gethash) (key) % (tab->hashsize -1))
/* #define dumplog printf */
/*
* hash function
*/
unsigned int lh_strhash(void *src)
{
int i,l;
unsigned long ret=0;
unsigned short *s;
char *str = (char *)src ;
if (str == NULL) return(0);
l=(strlen(str)+1)/2;
s=(unsigned short *)str;
for (i=0; i ret^=(s[i]<<(i&0x0f));
return(ret);
}
int equal_str(void *k1, void *k2)
{
return (0 == strcmp((char *)k1,(char *)k2)) ;
}
/*
*
* end hash function
*/
/*
*Desc : new hash entry
*
*/
inline struct hashentry *hashentry_new(void *key, void *data)
{
struct hashentry *new = malloc(sizeof(struct hashentry)) ;
new->key = key ;
new->data = data ;
new->next = NULL ;
return new ;
}
void hlist_append(struct hashentry **root, void *key, void *data)
{
struct hashentry *l, *pos ;
l = hashentry_new(key,data) ;
if (*root == NULL) {
*root = l ;
} else {
for(pos= *root; pos->next != NULL ; pos = pos->next ) ;
pos->next = l ;
}
}
int hlist_update(struct hashentry *root, void *key, void *data,
int (*compare)(void *,void *))
{
struct hashentry *pos ;
for(pos= root; pos != NULL; pos = pos->next ) {
if ( compare(key, pos->key) ) {
free(pos->data) ;
pos->data = data ;
free(key) ;
return 0 ;
}
}
return -1 ;
}
/*
*Desc :free hash entry
*
*/
inline struct hashentry *hashentry_free(struct hashentry *h)
{
struct hashentry *next = h->next ;
DEBUG_DUMP("free hash entry [%p]\n" ,h);
free(h->key) ;
free(h->data) ;
free(h) ;
h=NULL ;
return (next) ;
}
int hlist_remove(struct hashentry **root, void *key,
int (*compare)(void *,void *))
{
struct hashentry *pos ,*prev ;
if (NULL == *root) return -1 ;
/* the root */
if (compare((*root)->key, key)) {
*root = hashentry_free(*root) ;
return 0 ;
}
/* the second */
prev = *root ;
for (pos = prev->next; NULL != pos; pos = pos->next) {
if (compare(pos->key, key)) {
prev->next = hashentry_free(pos);
return 0 ;
}
prev =pos ;
} ;
return -1 ;
}
#define hashindex(key, tab) ((tab->gethash) (key) % (tab->hashsize -1))
/*
* Description :Create hash table
*
* sizeof(struct _hashtable) = 16
* sizeof(void *)= 4
* tab->hashlist size= 4*size
*
*/
hashtable *hash_create(unsigned int (*keyfunc)(void *),
int (*comparefunc)(void *,void *),
int size)
{
int len = sizeof(struct hashentry *) * size ;
int i ;
hashtable *tab = malloc( sizeof(hashtable) );
memset(tab,0, sizeof(hashtable)) ;
tab->hashlist = malloc(len) ;
DEBUG_DUMP("hsize:%d listsize %d\n",len,sizeof(void *)) ;
if (tab->hashlist == NULL) {
DEBUG_DUMP("malloc hash table list error\n");
free(tab) ;
return NULL;
}
memset(tab->hashlist, 0, len ) ;
for (i=0; ihashlist[i] = NULL ;
tab->compare = comparefunc ;
tab->gethash = keyfunc ;
tab->hashsize = size ;
tab->count = 0 ;
return tab ;
}
/*
*
*Desc : free hash table
*
*/
void hash_free(hashtable *tab)
{
int i ;
struct hashentry *pos;
for (i=0; i< tab->hashsize ; i++)
for (pos = tab->hashlist[ i ] ; NULL != pos; pos = hashentry_free(pos)) ;
free(tab->hashlist) ;
free(tab) ;
tab =NULL ;
}
/*
*Desc : Insert Data to hash table
*
*
*/
void hash_insert(void *key, void *data, hashtable *tab)
{
unsigned int index = hashindex(key,tab) ;
struct hashentry *root = tab->hashlist[ index ] ;
if ( hlist_update(root, key, data, tab->compare ) != 0 ) {
hlist_append(&(tab->hashlist[ index ]), key, data ) ;
tab->count ++ ;
}
}
/*
*
*Desc :Remove Item from hash table
*
*
*/
void hash_remove(void *key, hashtable *tab)
{
unsigned int index = hashindex(key,tab) ;
if (hlist_remove(&(tab->hashlist[ index ]), key, tab->compare) ==0) {
tab->count -- ;
}
}
void *hash_value(void *key, hashtable *tab)
{
struct hashentry *pos ;
unsigned int index = hashindex(key,tab) ;
for (pos = tab->hashlist[ index ]; NULL != pos; pos = pos->next) {
if (tab->compare(key, pos->key)) {
return (pos->data) ;
}
}
return NULL ;
}
/*
*
*
*/
void hash_for_each_do (hashtable *tab, int (cb)(void *, void *))
{
int i =0 ;
struct hashentry *pos ;
for (i=0; i < tab->hashsize; i++) {
for (pos = tab->hashlist[ i ] ; NULL != pos; pos=pos->next ) {
cb(pos->key, pos->data) ;
}
}
}
/*
#define hash_count(tab) (tab->count)
*/
inline int hash_count(hashtable *tab)
{
return tab->count ;
}
test.c
#ifdef DMALLOC
#include
#else
#include
#endif
#include
#include
#include "hash.h"
#define maxhash 10
int work(void *key,void *data)
{
printf("%-8s-> %s\n",(char *)key,(char *)data) ;
return 0;
}
int main(int argc,char *argv[])
{
int i ;
char key[20] ;
char data[20] ;
memset(key,0,20);
memset(data,0,20);
hashtable *tab = create_hashtable(10) ;
for (i=0; i sprintf(key,"key%d",i) ;
sprintf(data,"the line no: %d",i) ;
hash_insert((void *)strdup(key), (void *)strdup(data), tab) ;
}
/* hash_remove("key3",tab) ;
// */
printf("remove key4\n") ;
hash_remove("key4",tab) ;
for (i=0 ;i {
sprintf(key,"key%d",i) ;
printf("%s->%s\n",key,(char *) hash_value(key,tab));
}
hash_remove("key4",tab) ;
hash_remove("key4",tab) ;
printf("%s->%s\n","this is ", (char *) hash_value("this is ",tab));
printf("\n\n") ;
hash_for_each_do(tab,work) ;
printf("size %d\n" ,hash_count(tab)) ;
hash_free(tab) ;
/* exit(EXIT_SUCCESS) ; */
exit(0) ;
}
