|
#include <string.h>
#ifdef DMALLOC
#include <dmalloc.h>
#else
#include <stdlib.h>
#endif
#include "hash.h"
#ifndef __USE_ISOC99
#define inline
#endif
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;
};
#define hashindex(key, tab) ((tab->gethash)(key) % (tab->hashsize -1))
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 < l; i++)
ret ^= s[i]<<(i&0x0f);
return(ret);
}
int equal_str(void *k1, void *k2)
{
return (0 == strcmp((char *)k1, (char *)k2));
}
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;
}
inline struct hashentry *hashentry_free(struct hashentry *h)
{
struct hashentry *next = h->next;
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;
if (compare((*root)->key, key)) {
*root = hashentry_free(*root);
return 0;
}
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;
}
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);
if (tab->hashlist == NULL) {
free(tab);
return NULL;
}
memset(tab->hashlist, 0, len );
for (i = 0; i < size; i++)
tab->hashlist[i] = NULL ;
tab->compare = comparefunc;
tab->gethash = keyfunc;
tab->hashsize = size;
tab->count = 0;
return tab;
}
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;
}
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 ) { //(1)
hlist_append(&(tab->hashlist[index]), key, data );
tab->count++;
}
}
//(1) 查看Hash Table中是否存在键值为key的项，如果有则替换该键值所对应的value，否则调用hlist_append为key, data生成新的hashentry并插入相应的队列中。
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);
}
}
}
inline int hash_count(hashtable *tab)
{
return tab->count;
}
/*hash.h*/
#ifndef _LINUX_GHASH_H_
#define _LINUX_GHASH_H_
#include <string.h>
#ifndef __USE_ISOC99
#define inline
#endif
//Tomoka Asagi 麻木明香
#define create_hashtable(hsize) \
hash_create(lh_strhash, equal_str, hsize)
unsigned int lh_strhash(void *src);
int equal_str(void *k1, void *k2);
struct hashentry;
struct _hashtable;
typedef struct _hashtable hashtable;
hashtable *hash_create(unsigned int (*keyfunc)(void *),
int (*comparefunc)(void *,void *),
int size);
void hash_free(hashtable *tab);
void hash_insert(void *key, void *data, hashtable *tab);
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
/*hashfunc.c*/
unsigned int RSHash(char* str, unsigned int len)
{
unsigned int b = 378551;
unsigned int a = 63689;
unsigned int hash = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = hash * a + (*str);
a = a * b;
}
return hash;
}
/* End Of RS Hash Function */
unsigned int JSHash(char* str, unsigned int len)
{
unsigned int hash = 1315423911;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash ^= ((hash << 5) + (*str) + (hash >> 2));
}
return hash;
}
/* End Of JS Hash Function */
unsigned int PJWHash(char* str, unsigned int len)
{
const unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
const unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4);
const unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);
const unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = (hash << OneEighth) + (*str);
if((test = hash & HighBits) != 0)
{
hash = (( hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}
return hash;
}
/* End Of P. J. Weinberger Hash Function */
unsigned int ELFHash(char* str, unsigned int len)
{
unsigned int hash = 0;
unsigned int x = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = (hash << 4) + (*str);
if((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
}
hash &= ~x;
}
return hash;
}
/* End Of ELF Hash Function */
unsigned int BKDRHash(char* str, unsigned int len)
{
unsigned int seed = 131; /* 31 131 1313 13131 131313 etc.. */
unsigned int hash = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = (hash * seed) + (*str);
}
return hash;
}
/* End Of BKDR Hash Function */
unsigned int SDBMHash(char* str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = (*str) + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
/* End Of SDBM Hash Function */
unsigned int DJBHash(char* str, unsigned int len)
{
unsigned int hash = 5381;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = ((hash << 5) + hash) + (*str);
}
return hash;
}
/* End Of DJB Hash Function */
unsigned int DEKHash(char* str, unsigned int len)
{
unsigned int hash = len;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ (*str);
}
return hash;
}
/* End Of DEK Hash Function */
unsigned int BPHash(char* str, unsigned int len)
{
unsigned int hash = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash = hash << 7 ^ (*str);
}
return hash;
}
/* End Of BP Hash Function */
unsigned int FNVHash(char* str, unsigned int len)
{
const unsigned int fnv_prime = 0x811C9DC5;
unsigned int hash = 0;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash *= fnv_prime;
hash ^= (*str);
}
return hash;
}
/* End Of FNV Hash Function */
unsigned int APHash(char* str, unsigned int len)
{
unsigned int hash = 0xAAAAAAAA;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ (*str) * (hash >> 3)) :
(~((hash << 11) + (*str) ^ (hash >> 5)));
}
return hash;
}
/* End Of AP Hash Function */
/*main.c*/
#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <process.h>
#include <time.h>
#include "hash.h"
#include "mysql/include/mysql.h"
#define hash_max 1000000
unsigned char get_value();
int my_rand(int min, int max);
unsigned char get_intbits(int a);
//哈希
unsigned int hash_func(char* str, unsigned int len)
{
unsigned int hash = 0xAAAAAAAA;
unsigned int i = 0;
for(i = 0; i < len; str++, i++)
{
hash ^= ((i & 1) == 0) ? ( (hash << 7) ^ (*str) * (hash >> 3)) :
(~((hash << 11) + (*str) ^ (hash >> 5)));
}
return hash;
}
int work(void *key, void *data)
{
printf("%s->%s\n",(char *)key, (char *)data);
return 0;
}
int main()
{
int i;
char key[20];
char data[20];
memset(key, 0, 20);
memset(data, 0, 20);
hashtable *tab = create_hashtable(hash_max);
for (i = 0; i <hash_max; i++) {
//srand(time(NULL));
//sprintf(key, "key%d", rand()+i);
sprintf(key, "key%d", i);
sprintf(data, "the line no: %d", i);
hash_insert((void *)strdup(key), (void *)strdup(data), tab);
}
/*printf("remove key4\n");
hash_remove("key4", tab);
printf("key -> value\n");
for (i = 0; i < 10; i++) {
sprintf(key, "key%d", i);
printf("%s->%s\n", key, (char *)hash_value(key, tab));
}
printf("\n");
printf("%s->%s\n", "this is ", (char *)hash_value("this is ", tab));
printf("\n");*/
//hash_for_each_do(tab, work);
printf("current i %d\n", i);
printf("size %d\n", hash_count(tab));
hash_free(tab);
exit(0);
}
unsigned char get_value()
{
if (rand() % 2 == 0)
{
return 1;
}
else
{
return 0;
}
}
int my_rand(int min, int max)
{
return rand();
}
unsigned char get_intbits(int a)
{
int i = 1;
while(1)
{
if (a < 10) return i;
a = (int)a/10;
i++;
}
}
下面的是测试
/*test.c*/
#include "zhash.h"
int main(int argc, char **argv)
{
hashtable *tab = hash_create(MAXHASHSIZE);
unsigned int mac[ETH_ALEN]={0x00,0x68,0x30,0x3b,0x2a,0x56};
unsigned int ipaddr[4]={0xC0,0xA8,0x01,0x01};
unsigned int mac1[ETH_ALEN]={0x00,0x69,0x30,0x3b,0x2a,0x42};
unsigned int ipaddr1[4]={0xC0,0xA8,0x01,0x02};
char key[5];
// char key1[5];
memset(key,0,5);
// memset(key1,0,5);
sprintf(key,"%.2x%.2x",mac[4],mac[5]);
hash_insert((void *)key,(void *)ipaddr,(void *)mac,tab);
sprintf(key,"%.2x%.2x",mac1[4],mac1[5]);
hash_insert((void *)key,(void *)ipaddr1,(void *)mac1,tab);
hash_print(tab);
return 0;
}
//另外的HASH算法
#include "zhash.h"
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 < l; i++)
ret ^= s[i]<<(i&0x0f);
return(ret);
}
int equal_str(void *k1, void *k2)
{
return (0 == strcmp((char *)k1, (char *)k2));
}
hashentry *hlist_new(void *key, void *ipaddr, void *mac)
{
hashentry *new = (hashentry *)malloc(sizeof(hashentry));
new->key = key;
new->ipaddr = ipaddr;
new->mac = mac;
new->next = NULL;
return new;
}
void hlist_append(hashentry **root, void *key, void *ipaddr, void *mac)
{
hashentry *new, *pos;
new = hlist_new(key, ipaddr, mac);
if(*root == NULL)
{
*root = new;
}
else
{
pos = *root;
while(pos->next != NULL)
pos = pos->next;
pos->next = new;
}
}
bool hlist_update(hashentry *root, void *key,void *ipaddr,void *mac,int (*compare)(void *,void *))
{
hashentry *pos;
for(pos = root; pos != NULL; pos = pos->next)
{
if(compare(key,pos->key))
{
// free(pos->ipaddr);
// free(pos->mac);
pos->ipaddr = ipaddr;
pos->mac = mac;
// free(key);
return TRUE;
}
}
return FALSE;
}
void hash_insert(void *key, void *ipaddr, void *mac, hashtable *tab)
{
unsigned int index = hashindex(key, tab);
hashentry *root = tab->hashlist[index];
if(!(hlist_update(root, key, ipaddr, mac, tab->compare)))
{
hlist_append(&tab->hashlist[index],key,ipaddr, mac);
tab->count++;
}
}
hashtable *hash_create_t(unsigned int (*keyfunc)(void *),
int (*comparefunc)(void *,void *),
int size)
{
int i;
int len = sizeof(hashentry *) * size;
hashtable *tab = (hashtable *)malloc(sizeof(hashtable));
memset (tab, 0, sizeof(hashtable *));
tab->hashlist = (hashentry**)malloc(len);
if(tab->hashlist == NULL)
{
free(tab);
return NULL;
}
memset(tab->hashlist,0,len);
for(i = 0; i<size; i++)
{
tab->hashlist[i] = NULL;
}
tab->gethash = keyfunc;
tab->compare = comparefunc;
tab->hashsize = size;
tab->count = 0;
return tab;
}
void hash_print(hashtable *tab)
{
int i;
int *p;
hashentry *temp;
printf("index\t%-20s\t%-20s\n","mac","ipaddr");
for(i = 0; i < MAXHASHSIZE; i++)
{
temp = tab->hashlist[i];
if(temp == NULL)
printf("%-d\t%-20s\t%-20s\n",i,"NULL","NULL");
else
printf("%d\t",i);
while(temp != NULL)
{
p = (int *)(temp->mac);
printf("%.2x:%.2x:%.2x:%.2x:%.2x:%.2x\t",p[0],p[1],p[2],p[3],p[4],p[5]);
p = (int *)(temp->ipaddr);
const char *format = (temp->next == NULL)?("%d.%d.%d.%d\n"):("%d.%d.%d.%d -->\n\t");
printf(format,p[0],p[1],p[2],p[3]);
temp = temp->next;
}
}
}
/*
void help()
{
printf("command: \n");
printf(" -insert\n");
printf("\t--usage: insert mac ipaddr eg. insert 00:11:22:33:44:55 192.168.0.1\n");
printf("\t--description: insert mac,ip to hash table,mac divided by \":\",and ip by \".\"\n");
printf(" -del\n");
printf("\t--usage:del key eg.del 4455\n");
printf("\t--description: delete from hash table,key is the last 16 bits of mac\n");
printf(" -print\n");
printf("\t--usage: print\n");
printf("\t--description: print all over the hash table\n");
}*/
/*zhash.h头文件*/
|
