diff options
Diffstat (limited to 'module/hash.c')
| -rw-r--r-- | module/hash.c | 512 |
1 files changed, 275 insertions, 237 deletions
diff --git a/module/hash.c b/module/hash.c index 512a914..84d57a2 100644 --- a/module/hash.c +++ b/module/hash.c @@ -1,6 +1,6 @@ /* * Copyright (c) 2004, Stefan Walter - * All rights reserved. + * Copyright (c) 2011, Collabora Ltd. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions @@ -52,11 +52,12 @@ */ #include <sys/types.h> + +#include <assert.h> #include <stdlib.h> #include <string.h> -#include "hash.h" -#define KEY_DATA(he) ((he)->key) +#include "hash.h" /* * The internal form of a hash table. @@ -67,30 +68,14 @@ * isn't too bad given that pools have a low allocation overhead. */ -typedef struct hsh_entry_t hsh_entry_t; +typedef struct hash_entry hash_entry_t; -struct hsh_entry_t -{ - hsh_entry_t* next; - unsigned int hash; - const void* key; - size_t klen; - const void* val; -}; - -/* - * Data structure for iterating through a hash table. - * - * We keep a pointer to the next hash entry here to allow the current - * hash entry to be freed or otherwise mangled between calls to - * hsh_next(). - */ -struct hsh_index_t +struct hash_entry { - hsh_t* ht; - hsh_entry_t* ths; - hsh_entry_t* next; - unsigned int index; + hash_entry_t* next; + unsigned int hash; + void* key; + void* val; }; /* @@ -100,15 +85,16 @@ struct hsh_index_t * The count of hash entries may be greater depending on the chosen * collision rate. */ -struct hsh_t -{ - hsh_entry_t** array; - hsh_index_t iterator; /* For hsh_first(...) */ - unsigned int count; - unsigned int max; +struct hash { + hash_entry_t** array; + unsigned int count; + unsigned int max; + hash_hash_func hash_func; + hash_equal_func equal_func; + hash_destroy_func key_destroy_func; + hash_destroy_func value_destroy_func; }; - #define INITIAL_MAX 15 /* tunable == 2^n - 1 */ #define int_malloc malloc #define int_calloc calloc @@ -118,109 +104,121 @@ struct hsh_t * Hash creation functions. */ -static hsh_entry_t** alloc_array(hsh_t* ht, unsigned int max) +static hash_entry_t** +alloc_array(hash_t* ht, unsigned int max) { - return (hsh_entry_t**)int_calloc(sizeof(*(ht->array)), (max + 1)); + return (hash_entry_t**)int_calloc (sizeof (*(ht->array)), (max + 1)); } -hsh_t* hsh_create() +hash_t* +hash_create (hash_hash_func hash_func, + hash_equal_func equal_func, + hash_destroy_func key_destroy_func, + hash_destroy_func value_destroy_func) { - hsh_t* ht = int_malloc(sizeof(hsh_t)); - if(ht) - { - ht->count = 0; - ht->max = INITIAL_MAX; - ht->array = alloc_array(ht, ht->max); - if(!ht->array) - { - int_free(ht); - return NULL; - } - } - return ht; + hash_t* ht; + + assert (hash_func); + assert (equal_func); + + ht = int_malloc (sizeof (hash_t)); + if (ht) { + ht->count = 0; + ht->max = INITIAL_MAX; + ht->hash_func = hash_func; + ht->equal_func = equal_func; + ht->key_destroy_func = key_destroy_func; + ht->value_destroy_func = value_destroy_func; + ht->array = alloc_array (ht, ht->max); + if (!ht->array) { + int_free (ht); + return NULL; + } + } + return ht; } -void hsh_free(hsh_t* ht) +void +hash_free (hash_t* ht) { - hsh_index_t* hi; + hash_iter_t hi; + + if (!ht) + return; - for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) - int_free(hi->ths); + hash_iterate (ht, &hi); + while (hash_next (&hi, NULL, NULL)) { + if (ht->key_destroy_func) + ht->key_destroy_func (hi.ths->key); + if (ht->value_destroy_func) + ht->value_destroy_func (hi.ths->val); + } - if(ht->array) - int_free(ht->array); + if (ht->array) + int_free (ht->array); - int_free(ht); + int_free (ht); } /* * Hash iteration functions. */ - -hsh_index_t* hsh_next(hsh_index_t* hi) +int +hash_next (hash_iter_t* hi, void **key, void **value) { - hi->ths = hi->next; - while(!hi->ths) - { - if(hi->index > hi->ht->max) - return NULL; - - hi->ths = hi->ht->array[hi->index++]; - } - hi->next = hi->ths->next; - return hi; -} - -hsh_index_t* hsh_first(hsh_t* ht) -{ - hsh_index_t* hi = &ht->iterator; - - hi->ht = ht; - hi->index = 0; - hi->ths = NULL; - hi->next = NULL; - return hsh_next(hi); + hi->ths = hi->next; + while (!hi->ths) { + if (hi->index > hi->ht->max) + return 0; + hi->ths = hi->ht->array[hi->index++]; + } + hi->next = hi->ths->next; + if (key) + *key = hi->ths->key; + if (value) + *value = hi->ths->val; + return 1; } -void* hsh_this(hsh_index_t* hi, const void** key, size_t* klen) +void +hash_iterate (hash_t* ht, hash_iter_t *hi) { - if(key) - *key = KEY_DATA(hi->ths); - if(klen) - *klen = hi->ths->klen; - return (void*)hi->ths->val; + hi->ht = ht; + hi->index = 0; + hi->ths = NULL; + hi->next = NULL; } - /* * Expanding a hash table */ -static int expand_array(hsh_t* ht) +static int +expand_array (hash_t* ht) { - hsh_index_t* hi; - hsh_entry_t** new_array; - unsigned int new_max; + hash_iter_t hi; + hash_entry_t** new_array; + unsigned int new_max; - new_max = ht->max * 2 + 1; - new_array = alloc_array(ht, new_max); + new_max = ht->max * 2 + 1; + new_array = alloc_array (ht, new_max); - if(!new_array) - return 0; + if(!new_array) + return 0; - for(hi = hsh_first(ht); hi; hi = hsh_next(hi)) - { - unsigned int i = hi->ths->hash & new_max; - hi->ths->next = new_array[i]; - new_array[i] = hi->ths; - } + hash_iterate (ht, &hi); + while (hash_next (&hi, NULL, NULL)) { + unsigned int i = hi.ths->hash & new_max; + hi.ths->next = new_array[i]; + new_array[i] = hi.ths; + } - if(ht->array) - free(ht->array); + if(ht->array) + int_free (ht->array); - ht->array = new_array; - ht->max = new_max; - return 1; + ht->array = new_array; + ht->max = new_max; + return 1; } /* @@ -232,151 +230,96 @@ static int expand_array(hsh_t* ht) * that hash entries can be removed. */ -static hsh_entry_t** find_entry(hsh_t* ht, const void* key, size_t klen, const void* val) +static hash_entry_t** +find_entry (hash_t* ht, const void* key, void* val) { - hsh_entry_t** hep; - hsh_entry_t* he; - const unsigned char* p; - unsigned int hash; - size_t i; - - /* - * This is the popular `times 33' hash algorithm which is used by - * perl and also appears in Berkeley DB. This is one of the best - * known hash functions for strings because it is both computed - * very fast and distributes very well. - * - * The originator may be Dan Bernstein but the code in Berkeley DB - * cites Chris Torek as the source. The best citation I have found - * is "Chris Torek, Hash function for text in C, Usenet message - * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich - * Salz's USENIX 1992 paper about INN which can be found at - * <http://citeseer.nj.nec.com/salz92internetnews.html>. - * - * The magic of number 33, i.e. why it works better than many other - * constants, prime or not, has never been adequately explained by - * anyone. So I try an explanation: if one experimentally tests all - * multipliers between 1 and 256 (as I did while writing a low-level - * data structure library some time ago) one detects that even - * numbers are not useable at all. The remaining 128 odd numbers - * (except for the number 1) work more or less all equally well. - * They all distribute in an acceptable way and this way fill a hash - * table with an average percent of approx. 86%. - * - * If one compares the chi^2 values of the variants (see - * Bob Jenkins ``Hashing Frequently Asked Questions'' at - * http://burtleburtle.net/bob/hash/hashfaq.html for a description - * of chi^2), the number 33 not even has the best value. But the - * number 33 and a few other equally good numbers like 17, 31, 63, - * 127 and 129 have nevertheless a great advantage to the remaining - * numbers in the large set of possible multipliers: their multiply - * operation can be replaced by a faster operation based on just one - * shift plus either a single addition or subtraction operation. And - * because a hash function has to both distribute good _and_ has to - * be very fast to compute, those few numbers should be preferred. - * - * -- Ralf S. Engelschall <rse@engelschall.com> - */ - hash = 0; - - if(klen == HSH_KEY_STRING) - { - for(p = key; *p; p++) - hash = hash * 33 + *p; - - klen = p - (const unsigned char *)key; - } - else - { - for(p = key, i = klen; i; i--, p++) - hash = hash * 33 + *p; - } - - /* scan linked list */ - for(hep = &ht->array[hash & ht->max], he = *hep; - he; hep = &he->next, he = *hep) - { - if(he->hash == hash && - he->klen == klen && - memcmp(KEY_DATA(he), key, klen) == 0) - break; - } - - if(he || !val) - return hep; - - /* add a new entry for non-NULL val */ - he = int_malloc(sizeof(*he)); - - if(he) - { - /* Key points to external data */ - he->key = key; - he->klen = klen; - - he->next = NULL; - he->hash = hash; - he->val = val; - - *hep = he; - ht->count++; - } - - return hep; -} + hash_entry_t** hep; + hash_entry_t* he; + unsigned int hash; + + /* Perform the hashing */ + hash = ht->hash_func (key); + + /* scan linked list */ + for (hep = &ht->array[hash & ht->max], he = *hep; + he; hep = &he->next, he = *hep) { + if(he->hash == hash && ht->equal_func (he->key, key)) + break; + } -void* hsh_get(hsh_t* ht, const void *key, size_t klen) -{ - hsh_entry_t** he = find_entry(ht, key, klen, NULL); + if(he || !val) + return hep; + + /* add a new entry for non-NULL val */ + he = int_malloc (sizeof (*he)); + + if(he) { + he->key = (void*)key; + he->next = NULL; + he->hash = hash; + he->val = val; - if(he && *he) - return (void*)((*he)->val); - else - return NULL; + *hep = he; + ht->count++; + } + + return hep; } -int hsh_set(hsh_t* ht, const void* key, size_t klen, void* val) +void* +hash_get (hash_t* ht, const void *key) { - hsh_entry_t** hep = find_entry(ht, key, klen, val); - - if(hep && *hep) - { - /* replace entry */ - (*hep)->val = val; + hash_entry_t** he = find_entry (ht, key, NULL); + if (he && *he) + return (void*)((*he)->val); + else + return NULL; +} - /* check that the collision rate isn't too high */ - if(ht->count > ht->max) - { - if(!expand_array(ht)) - return 0; - } +int +hash_set (hash_t* ht, void* key, void* val) +{ + hash_entry_t** hep = find_entry (ht, key, val); + if(hep && *hep) { + /* replace entry */ + (*hep)->val = val; + + /* check that the collision rate isn't too high */ + if (ht->count > ht->max) { + if (!expand_array (ht)) + return 0; + } - return 1; - } + return 1; + } - return 0; + return 0; } -void* hsh_rem(hsh_t* ht, const void* key, size_t klen) +int +hash_remove (hash_t* ht, const void* key) { - hsh_entry_t** hep = find_entry(ht, key, klen, NULL); - void* val = NULL; - - if(hep && *hep) - { - hsh_entry_t* old = *hep; - *hep = (*hep)->next; - --ht->count; - val = (void*)old->val; - free(old); - } - - return val; + hash_entry_t** hep = find_entry (ht, key, NULL); + + if (hep && *hep) { + hash_entry_t* old = *hep; + *hep = (*hep)->next; + --ht->count; + if (ht->key_destroy_func) + ht->key_destroy_func (old->key); + if (ht->value_destroy_func) + ht->value_destroy_func (old->val); + free (old); + return 1; + } + + return 0; } -void hsh_clear(hsh_t* ht) +void +hash_clear (hash_t* ht) { - hsh_entry_t *he, *next; + hash_entry_t *he, *next; int i; /* Free all entries in the array */ @@ -384,17 +327,112 @@ void hsh_clear(hsh_t* ht) he = ht->array[i]; while (he) { next = he->next; + if (ht->key_destroy_func) + ht->key_destroy_func (he->key); + if (ht->value_destroy_func) + ht->value_destroy_func (he->val); free (he); he = next; } } - memset (ht->array, 0, ht->max * sizeof (hsh_entry_t*)); + memset (ht->array, 0, ht->max * sizeof (hash_entry_t*)); ht->count = 0; } -unsigned int hsh_count(hsh_t* ht) +unsigned int +hash_count (hash_t* ht) +{ + return ht->count; +} + +unsigned int +hash_string_hash (const void *string) +{ + unsigned int hash; + const unsigned char *p; + + assert (string); + + /* + * This is the popular `times 33' hash algorithm which is used by + * perl and also appears in Berkeley DB. This is one of the best + * known hash functions for strings because it is both computed + * very fast and distributes very well. + * + * The originator may be Dan Bernstein but the code in Berkeley DB + * cites Chris Torek as the source. The best citation I have found + * is "Chris Torek, Hash function for text in C, Usenet message + * <27038@mimsy.umd.edu> in comp.lang.c , October, 1990." in Rich + * Salz's USENIX 1992 paper about INN which can be found at + * <http://citeseer.nj.nec.com/salz92internetnews.html>. + * + * The magic of number 33, i.e. why it works better than many other + * constants, prime or not, has never been adequately explained by + * anyone. So I try an explanation: if one experimentally tests all + * multipliers between 1 and 256 (as I did while writing a low-level + * data structure library some time ago) one detects that even + * numbers are not useable at all. The remaining 128 odd numbers + * (except for the number 1) work more or less all equally well. + * They all distribute in an acceptable way and this way fill a hash + * table with an average percent of approx. 86%. + * + * If one compares the chi^2 values of the variants (see + * Bob Jenkins ``Hashing Frequently Asked Questions'' at + * http://burtleburtle.net/bob/hash/hashfaq.html for a description + * of chi^2), the number 33 not even has the best value. But the + * number 33 and a few other equally good numbers like 17, 31, 63, + * 127 and 129 have nevertheless a great advantage to the remaining + * numbers in the large set of possible multipliers: their multiply + * operation can be replaced by a faster operation based on just one + * shift plus either a single addition or subtraction operation. And + * because a hash function has to both distribute good _and_ has to + * be very fast to compute, those few numbers should be preferred. + * + * -- Ralf S. Engelschall <rse@engelschall.com> + */ + + hash = 0; + + for(p = string; *p; p++) + hash = hash * 33 + *p; + + return hash; +} + +int +hash_string_equal (const void *string_one, const void *string_two) +{ + assert (string_one); + assert (string_two); + + return strcmp (string_one, string_two) == 0; +} + +unsigned int +hash_ulongptr_hash (const void *to_ulong) +{ + assert (to_ulong); + return (unsigned int)*((unsigned long*)to_ulong); +} + +int +hash_ulongptr_equal (const void *ulong_one, const void *ulong_two) +{ + assert (ulong_one); + assert (ulong_two); + return *((unsigned long*)ulong_one) == *((unsigned long*)ulong_two); +} + +unsigned int +hash_direct_hash (const void *ptr) +{ + return (unsigned int)ptr; +} + +int +hash_direct_equal (const void *ptr_one, const void *ptr_two) { - return ht->count; + return ptr_one == ptr_two; } |