每天收获一点

摘自PHP的HASH算法实现


/*
* 头文件
* 说明：此实现不保存对象，只保存对象的引用
*/
#ifndef _HASH_H
#define _HASH_H

#ifdef __cplusplus
extern "C" {
#endif

typedef struct tagHASHBUCKET HASHBUCKET, *LPHASHBUCKET;
typedef struct tagHASHTABLE HASHTABLE, *LPHASHTABLE;

struct tagHASHBUCKET
{
unsigned long h;
unsigned int key_length;
void *data;
LPHASHBUCKET next;
LPHASHBUCKET previous;
LPHASHBUCKET conflict_next;
LPHASHBUCKET conflict_previous;
char key[1];
};

typedef unsigned long (*hash_func_t)(char *, unsigned int);

struct tagHASHTABLE
{
unsigned int table_size;
unsigned int size_index;
unsigned int elements;
hash_func_t hash;
LPHASHBUCKET p;
LPHASHBUCKET head;
LPHASHBUCKET tail;
LPHASHBUCKET *buckets;
};

extern int hash_create(LPHASHTABLE, unsigned int, hash_func_t);
extern int hash_entry(LPHASHTABLE, char *, unsigned int, void *);
extern int hash_find(LPHASHTABLE, char *, unsigned int, void **);
extern int hash_update(LPHASHTABLE, char *, unsigned int, void *);
extern int hash_remove(LPHASHTABLE, char *, unsigned int);
extern int hash_destroy(LPHASHTABLE);

#ifdef __cplusplus
};
#endif

#endif

/*
* HASH实现
*/
#include <stdlib.h>
#include <memory.h>
#include "main.h"

static unsigned int size_table[] =
{5, 11, 19, 53, 107, 223, 463, 983, 1979, 3907, 7963, 16229, 32531, 65407, 130987, 262237, 524521, 1048793, 2097397, 41941
03, 8388857, 16777447, 33554201, 67108961, 134217487, 268435697, 536870683, 1073741621, 2147483399};
#define COUNTS_OF_SIZE_TABLE (sizeof(size_table) / sizeof(size_table[0]))

static unsigned long
hashpjw(char *key, unsigned int key_length)
{
unsigned long h, g;
char *p;

h = 0;
p = key + key_length;
while (key < p)
{
h = (h << 4) + *key++;
if ((g = (h & 0xF0000000)))
{
h = h ^ (g >> 24);
h = h ^ g;
}
}

return h;
}

static int
hash_do_rehash(LPHASHTABLE pht)
{
LPHASHBUCKET p;
unsigned int index;

memset(pht->buckets, 0, sizeof(LPHASHBUCKET) * size_table[pht->size_index]);
for (p = pht->head; p; p = p->next)
{
index = p->h % pht->table_size;
p->conflict_next = 0;
p->conflict_previous = pht->buckets[index];
if (p->conflict_previous)
{
p->conflict_previous->conflict_next = p;
}
pht->buckets[index] = p;
}

return 0;
}

static int
hash_do_resize(LPHASHTABLE pht)
{
LPHASHBUCKET *pp;

if (pht->size_index < (unsigned int)COUNTS_OF_SIZE_TABLE - 1)
{
pp = (LPHASHBUCKET *)realloc(pht->buckets, size_table[pht->size_index + 1] * sizeof(LPHASHBUCKET));
if (pp)
{
pht->buckets = pp;
pht->size_index++;
pht->table_size = size_table[pht->size_index];
hash_do_rehash(pht);
return 0;
}
return -1;
}

return 0;
}

int
hash_create(LPHASHTABLE pht, unsigned int size, hash_func_t hash)
{
int i;

for (i = 0; i < COUNTS_OF_SIZE_TABLE; ++i)
{
if (size <= size_table[i])
{
size = size_table[i];
pht->size_index = i;
break;
}
}
if (i == COUNTS_OF_SIZE_TABLE)
{
size = size_table[COUNTS_OF_SIZE_TABLE - 1];
pht->size_index = COUNTS_OF_SIZE_TABLE - 1;
}

pht->buckets = (LPHASHBUCKET *)calloc(size, sizeof(LPHASHBUCKET));
if (!pht->buckets)
{
return -1;
}
pht->hash = hash? hash: hashpjw;
pht->elements = 0;
pht->head = 0;
pht->p = 0;
pht->tail = 0;
pht->table_size = size;

return 0;
}

int
hash_entry(LPHASHTABLE pht, char *key, unsigned int key_length, void *data)
{
unsigned long h;
unsigned int index;
LPHASHBUCKET p;

h = pht->hash(key, key_length);
index = h % pht->table_size;

for (p = pht->buckets[index]; p; p = p->conflict_previous)
{
if (p->h == h && p->key_length == key_length)
{
if (!memcmp(p->key, key, key_length))
{
return -1;
}
}
}

p = (LPHASHBUCKET)malloc(sizeof(HASHBUCKET) - 1 + key_length);
if (!p)
{
return -1;
}
memcpy(p->key, key, key_length);
p->key_length = key_length;
p->h = h;
p->data = data;

p->conflict_next = 0;
p->conflict_previous = pht->buckets[index];
if (p->conflict_previous)
{
p->conflict_previous->conflict_next = p;
}
p->previous = pht->tail;
p->next = 0;
pht->tail = p;
if (p->previous)
{
p->previous->next = p;
}
if (!pht->head)
{
pht->head = p;
}

pht->buckets[index] = p;
++pht->elements;
if (pht->elements > pht->table_size)
{
hash_do_resize(pht);
}

return 0;
}

int
hash_find(LPHASHTABLE pht, char *key, unsigned int key_length, void **data)
{
unsigned long h;
unsigned int index;
LPHASHBUCKET p;

h = pht->hash(key, key_length);
index = h % pht->table_size;

for (p = pht->buckets[index]; p; p = p->conflict_previous)
{
if (p->h == h && p->key_length == key_length && !memcmp(p->key, key, key_length))
{
*data = p->data;
return 0;
}
}

return -1;
}

int
hash_remove(LPHASHTABLE pht, char *key, unsigned int key_length)
{
unsigned long h;
unsigned int index;
LPHASHBUCKET p;

h = pht->hash(key, key_length);
index = h % pht->table_size;

for (p = pht->buckets[index]; p; p = p->conflict_previous)
{
if (p->h == h && p->key_length == key_length && !memcmp(p->key, key, key_length))
{
if (p->conflict_previous)
{
p->conflict_previous->conflict_next = p->conflict_next;
}
if (p->conflict_next)
{
p->conflict_next->conflict_previous = p->conflict_previous;
}
if (p->previous)
{
p->previous->next = p->next;
}
if (p->next)
{
p->next->previous = p->previous;
}
if (pht->buckets[index] == p)
{
pht->buckets[index] = p->conflict_previous;
}
if (pht->head == p)
{
pht->head = p->next;
}
if (pht->tail == p)
{
pht->tail = p->previous;
}
--pht->elements;
free(p);

return 0;
}
}

return -1;
}

int
hash_update(LPHASHTABLE pht, char *key, unsigned int key_length, void *data)
{
unsigned long h;
unsigned int index;
LPHASHBUCKET p;

h = pht->hash(key, key_length);
index = h % pht->table_size;

for (p = pht->buckets[index]; p; p = p->conflict_previous)
{
if (p->h == h && p->key_length == key_length && !memcmp(p->key, key, key_length))
{
p->data = data;
return 0;
}
}

return -1;
}

int
hash_destroy(LPHASHTABLE pht)
{
LPHASHBUCKET p, q;

p = pht->head;
while (p)
{
q = p;
p = p->next;
free(q);
}
free(pht->buckets);

return 0;
}