zc_hashtable.h
/**
* hashtable
*/ #ifndef __zc_hashtable_h
#define __zc_hashtable_h typedef struct zc_hashtable_entry_s {
unsigned int hash_key;
void *key;
void *value;
struct zc_hashtable_entry_s *prev;
struct zc_hashtable_entry_s *next;
} zc_hashtable_entry_t; typedef struct zc_hashtable_s zc_hashtable_t; typedef unsigned int (*zc_hashtable_hash_fn) (const void *key);
typedef int (*zc_hashtable_equal_fn) (const void *key1, const void *key2);
typedef void(*zc_hashtable_del_fn) (void *kv); zc_hashtable_t *zc_hashtable_new(size_t a_size,
zc_hashtable_hash_fn hash_fn,
zc_hashtable_equal_fn equal_fn,
zc_hashtable_del_fn key_del_fn,
zc_hashtable_del_fn value_del_fn); void zc_hashtable_del(zc_hashtable_t *a_table);
void zc_hashtable_clean(zc_hashtable_t *a_table);
int zc_hashtable_put(zc_hashtable_t *a_table, void *a_key, void *a_value); zc_hashtable_entry_t *zc_hashtable_get_entry(zc_hashtable_t *a_table, const void *a_key); void *zc_hashtable_get(zc_hashtable_t *a_table, const void *a_key);
void zc_hashtable_remove(zc_hashtable_t *a_table, const void *a_key); zc_hashtable_entry_t *zc_hashtable_begin(zc_hashtable_t *a_table);
zc_hashtable_entry_t *zc_hashtable_next(zc_hashtable_t *a_table, zc_hashtable_entry_t *a_entry); struct zc_hashtable_s {
//记录当前element的个数
size_t nelem; zc_hashtable_entry_t **tab;
size_t tab_size; zc_hashtable_hash_fn hash;
zc_hashtable_equal_fn equal;
zc_hashtable_del_fn key_del;
zc_hashtable_del_fn value_del;
}; #define zc_hashtable_foreach(a_table, a_entry)\
for(a_entry = zc_hashtable_begin(a_table); a_entry; a_entry = zc_hashtable_next(a_table, a_entry)) unsigned int zc_hashtable_str_hash(const void *str);
int zc_hashtable_str_equal(const void *key1, const void *key2); #endif
zc_hashtable.c
#include <stdlib.h>
#include <errno.h>
#include <pthread.h> #include "zc_defs.h"
#include "zc_hashtable.h" //struct zc_hashtable_s {
// //记录当前element的个数
// size_t nelem;
//
// zc_hashtable_entry_t **tab;
// size_t tab_size;
//
// zc_hashtable_hash_fn hash;
// zc_hashtable_equal_fn equal;
// zc_hashtable_del_fn key_del;
// zc_hashtable_del_fn value_del;
//}; zc_hashtable_t *zc_hashtable_new(size_t a_size,
zc_hashtable_hash_fn hash,
zc_hashtable_equal_fn equal,
zc_hashtable_del_fn key_del,
zc_hashtable_del_fn value_del){ zc_hashtable_t *a_table;
a_table = (zc_hashtable_t *)calloc(, sizeof(zc_hashtable_t));
if(!a_table){
zc_error("calloc fail, errno[%d]", errno);
return NULL;
} a_table->tab = (zc_hashtable_entry_t **)calloc(a_size, sizeof(zc_hashtable_entry_t *));
if(!a_table->tab){
zc_error("calloc fail, errno[%d]", errno);
free(a_table);
return NULL;
}
a_table->tab_size = a_size; a_table->nelem = ;
a_table->hash = hash;
a_table->equal = equal; //these two could be NULL
a_table->key_del = key_del;
a_table->value_del = value_del; return a_table;
} void zc_hashtable_del(zc_hashtable_t *a_table){
size_t i;
zc_hashtable_entry_t *p;
zc_hashtable_entry_t *q; if(!a_table){
zc_error("a_table[%p] is NULL, just do nothing", a_table);
return ;
} for(i = ; i < a_table->tab_size; i++){
//hash conflic
for(p = (a_table->tab)[i]; p; p = q){
q = p->next;
if(a_table->key_del){
a_table->key_del(p->key);
}
if(a_table->value_del){
a_table->value_del(p->value);
}
free(p);
}
}
if(a_table->tab){
free(a_table->tab);
}
free(a_table); return;
} void zc_hashtable_clean(zc_hashtable_t *a_table){
size_t i;
zc_hashtable_entry_t *p, *q; for(i = ; i < a_table->tab_size; i++){
for(p = (a_table->tab)[i]; p; p = q){
q = p->next;
if(a_table->key_del){
a_table->key_del(p->key);
}
if(a_table->value_del){
a_table->value_del(p->value);
}
free(p);
}
(a_table->tab)[i] = NULL;
}
a_table->nelem = ; return;
} static int zc_hashtable_rehash(zc_hashtable_t *a_table){
size_t i, j, tab_size;
zc_hashtable_entry_t **tab;
zc_hashtable_entry_t *p;
zc_hashtable_entry_t *q; tab_size = * a_table->tab_size;
tab = calloc(tab_size, sizeof(zc_hashtable_t *));
if(!tab){
zc_error("calloc fail, errno[%d]", errno);
return -;
} for(i = ; i < a_table->tab_size; i++){
//优化
for(p = a_table->tab[i]; p; p = q){
q = p->next; p->prev = NULL;
p->next = NULL;
j = p->hash_key % tab_size;
if(tab[j]){
tab[j]->prev = p;
p->next = tab[j];
}
tab[j] = p;
}
}
free(a_table->tab);
a_table->tab = tab;
a_table->tab_size = tab_size; return ;
} void *zc_hashtable_get(zc_hashtable_t *a_table, const void *a_key){
size_t i;
zc_hashtable_entry_t *p = NULL; i = a_table->hash(a_key) % a_table->tab_size;
for(p = a_table->tab[i]; p; p = p->next){
if(a_table->equal(a_key, p->key)){
return p->value;
}
}
return NULL;
} int zc_hashtable_put(zc_hashtable_t *a_table, void *a_key, void *a_value){
int rc;
size_t i;
zc_hashtable_entry_t *p = NULL; i = a_table->hash(a_key) % a_table->tab_size;
for(p = a_table->tab[i]; p; p = p->next){
if(a_table->equal(a_key, p->key)){
break;
}
} //a_table->tab[i] have value
if(p){
if(a_table->key_del){
a_table->key_del(p->key);
}
if(a_table->value_del){
a_table->value_del(p->value);
}
p->key = a_key;
p->value = a_value;
return ;
}else{
if(a_table->nelem > a_table->tab_size * 1.3){
rc = zc_hashtable_rehash(a_table);
if(rc){
zc_error("rehash fail");
return -;
}
}
//如果sizeof(zc_hashtable_entry_t *) 会造成free失败
p = calloc(, sizeof(zc_hashtable_entry_t));
if(!p){
zc_error("calloc fail, errno[%d]", errno);
return -;
} p->hash_key = a_table->hash(a_key);
p->key = a_key;
p->value = a_value;
p->next = NULL;
p->prev = NULL; i = p->hash_key % a_table->tab_size;
//has value
if(a_table->tab[i]){
a_table->tab[i]->prev = p;
p->next = a_table->tab[i];
}
a_table->tab[i] = p;
a_table->nelem++;
} return ;
} void zc_hashtable_remove(zc_hashtable_t *a_table, const void *a_key){
size_t i;
zc_hashtable_entry_t *p; if(!a_table || !a_key){
zc_error("a_table[%p] or a_key[%p] is NULL, just do nothing", a_table, a_key);
return ;
}
i = a_table->hash(a_key) % a_table->tab_size;
for(p = a_table->tab[i]; p; p = p->next){
if(a_table->equal(a_key, p->key)){
break;
}
} if(!p){
zc_error("p[%p] is not found in hashtable", p);
return;
} if(a_table->key_del){
a_table->key_del(p->key);
}
if(a_table->value_del){
a_table->value_del(p->value);
} if(p->next){
p->next->prev = p->prev;
}
if(p->prev){
p->prev->next = p->next;
}else{
//notice
a_table->tab[i] = p->next;
} free(p);
a_table->nelem--; return;
} zc_hashtable_entry_t *zc_hashtable_begin(zc_hashtable_t *a_table){
size_t i;
zc_hashtable_entry_t *p;
for(i= ; i < a_table->tab_size; i++){
for(p = a_table->tab[i]; p; p->next){
if(p){
return p;
}
}
}
printf("%d\n", i);
return NULL;
} zc_hashtable_entry_t *zc_hashtable_next(zc_hashtable_t *a_table, zc_hashtable_entry_t *a_entry){
size_t i, j; if(a_entry->next){
return a_entry->next;
} i = a_entry->hash_key % a_table->tab_size; for(j = i + ; j < a_table->tab_size; j++){
if(a_table->tab[j]){
return a_table->tab[j];
}
} return NULL;
} /**************************************************hash、equal**********************************************/ int zc_hashtable_str_equal(const void *key1, const void *key2){
return (STRCMP((const char *)key1, ==, (const char *)key2));
} unsigned int zc_hashtable_str_hash(const void *str){
size_t h = ;
const char *p = (const char *)str; while(*p != '\0'){
h = ((h << ) + h) + (*p++); /* hash * 33 + c*/
} return h;
}
测试
#include <stdio.h> #include "zc_defs.h"
#include "zc_hashtable.c"
#include "zc_profile.c" void myfree(void *kv){ } int main(){
zc_hashtable_t *a_table;
zc_hashtable_entry_t *a_entry; a_table = zc_hashtable_new(,
zc_hashtable_str_hash,
zc_hashtable_str_equal,
myfree,myfree
); zc_hashtable_put(a_table, "aaa", "");
zc_hashtable_put(a_table, "bbb", "");
zc_hashtable_put(a_table, "ccc", ""); zc_hashtable_foreach(a_table, a_entry){
printf("k[%s], v[%s]\n", a_entry->key, a_entry->value);
} printf("getv[%s]\n", (char *)zc_hashtable_get(a_table, "ccc")); zc_hashtable_remove(a_table, "ccc"); zc_hashtable_foreach(a_table, a_entry){
printf("k[%s], v[%s]\n", a_entry->key, a_entry->value);
} zc_hashtable_remove(a_table, NULL);
zc_hashtable_del(NULL); zc_hashtable_del(a_table); return ;
}