/* * 头文件 * 说明:此实现不保存对象,只保存对象的引用 */ #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; }

|