/* * Originally from apache 2.0 * Modifications for general use by */ /* Copyright 2000-2004 The Apache Software Foundation * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * * http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #include #include #include "hash.h" #ifdef HASH_TIMESTAMP #include #endif #ifdef HASH_COPYKEYS #define KEY_DATA(he) (void*)(((unsigned char*)(he)) + sizeof(*(he))) #else #define KEY_DATA(he) ((he)->key) #endif /* * The internal form of a hash table. * * The table is an array indexed by the hash of the key; collisions * are resolved by hanging a linked list of hash entries off each * element of the array. Although this is a really simple design it * isn't too bad given that pools have a low allocation overhead. */ typedef struct hash_entry_t hash_entry_t; struct hash_entry_t { hash_entry_t* next; unsigned int hash; #ifndef HASH_COPYKEYS const void* key; size_t klen; #endif const void* val; #ifdef HASH_TIMESTAMP time_t stamp; #endif }; /* * 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 * hash_next(). */ struct hash_index_t { hash_t* ht; hash_entry_t* ths; hash_entry_t* next; unsigned int index; }; /* * The size of the array is always a power of two. We use the maximum * index rather than the size so that we can use bitwise-AND for * modular arithmetic. * The count of hash entries may be greater depending on the chosen * collision rate. */ struct hash_t { hash_entry_t** array; hash_index_t iterator; /* For hash_first(...) */ unsigned int count; unsigned int max; #ifdef HASH_COPYKEYS unsigned int klen; #endif #ifdef HASH_CALLBACKS hash_free_val_t f_free; void* arg; #endif }; #define INITIAL_MAX 15 /* tunable == 2^n - 1 */ /* * Hash creation functions. */ static hash_entry_t** alloc_array(hash_t* ht, unsigned int max) { return malloc(sizeof(*(ht->array)) * (max + 1)); } #ifdef HASH_CALLBACKS #ifdef HASH_COPYKEYS hash_t* hash_create(size_t klen, hash_free_val_t f_free, void* arg) #else hash_t* hash_create(hash_free_val_t f_free, void* arg) #endif #else #ifdef HASH_COPYKEYS hash_t* hash_create(size_t klen) #else hash_t* hash_create() #endif #endif { hash_t* ht = malloc(sizeof(hash_t)); if(ht) { ht->count = 0; ht->max = INITIAL_MAX; ht->array = alloc_array(ht, ht->max); #ifdef HASH_COPYKEYS ht->klen = klen; #endif #ifdef HASH_CALLBACKS ht->f_free = f_free; ht->arg = arg; #endif if(!ht->array) { free(ht); return NULL; } } return ht; } void hash_free(hash_t* ht) { hash_index_t* hi; for(hi = hash_first(ht); hi; hi = hash_next(hi)) { #ifdef HASH_CALLBACKS if(hi->ths->val && ht->f_free) ht->f_free(ht->arg, (void*)hi->ths->val); #endif free(hi->ths); } if(ht->array) free(ht->array); free(ht); } /* * Hash iteration functions. */ hash_index_t* hash_next(hash_index_t* hi) { 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; } hash_index_t* hash_first(hash_t* ht) { hash_index_t* hi = &ht->iterator; hi->ht = ht; hi->index = 0; hi->ths = NULL; hi->next = NULL; return hash_next(hi); } #ifdef HASH_COPYKEYS void* hash_this(hash_index_t* hi, const void** key) #else void* hash_this(hash_index_t* hi, const void** key, size_t* klen) #endif { if(key) *key = KEY_DATA(hi->ths); #ifndef HASH_COPYKEYS if(klen) *klen = hi->ths->klen; #endif return (void*)hi->ths->val; } /* * Expanding a hash table */ static int expand_array(hash_t* ht) { hash_index_t* hi; hash_entry_t** new_array; unsigned int new_max; new_max = ht->max * 2 + 1; new_array = alloc_array(ht, new_max); if(!new_array) return 0; for(hi = hash_first(ht); hi; hi = hash_next(hi)) { 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); ht->array = new_array; ht->max = new_max; return 1; } /* * This is where we keep the details of the hash function and control * the maximum collision rate. * * If val is non-NULL it creates and initializes a new hash entry if * there isn't already one there; it returns an updatable pointer so * that hash entries can be removed. */ #ifdef HASH_COPYKEYS static hash_entry_t** find_entry(hash_t* ht, const void* key, const void* val) #else static hash_entry_t** find_entry(hash_t* ht, const void* key, size_t klen, const void* val) #endif { hash_entry_t** hep; hash_entry_t* he; const unsigned char* p; unsigned int hash; size_t i; #ifdef HASH_COPYKEYS size_t klen = ht->klen; #endif /* * 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 * . * * 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 */ hash = 0; #ifndef HASH_COPYKEYS if(klen == HASH_KEY_STRING) { for(p = key; *p; p++) hash = hash * 33 + *p; klen = p - (const unsigned char *)key; } else #endif { 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 && #ifndef HASH_COPYKEYS he->klen == klen && #endif memcmp(KEY_DATA(he), key, klen) == 0) break; } if(he || !val) return hep; /* add a new entry for non-NULL val */ #ifdef HASH_COPYKEYS he = malloc(sizeof(*he) + klen); #else he = malloc(sizeof(*he)); #endif if(he) { #ifdef HASH_COPYKEYS /* Key data points past end of entry */ memcpy(KEY_DATA(he), key, klen); #else /* Key points to external data */ he->key = key; he->klen = klen; #endif he->next = NULL; he->hash = hash; he->val = val; #ifdef HASH_TIMESTAMP he->stamp = 0; #endif *hep = he; ht->count++; } return hep; } #ifdef HASH_COPYKEYS void* hash_get(hash_t* ht, const void *key) { hash_entry_t** he = find_entry(ht, key, NULL); #else void* hash_get(hash_t* ht, const void *key, size_t klen) { hash_entry_t** he = find_entry(ht, key, klen, NULL); #endif if(he && *he) return (void*)((*he)->val); else return NULL; } #ifdef HASH_COPYKEYS int hash_set(hash_t* ht, const void* key, void* val) { hash_entry_t** hep = find_entry(ht, key, val); #else int hash_set(hash_t* ht, const void* key, size_t klen, void* val) { hash_entry_t** hep = find_entry(ht, key, klen, val); #endif if(hep && *hep) { #ifdef HASH_CALLBACKS if((*hep)->val && (*hep)->val != val && ht->f_free) ht->f_free(ht->arg, (void*)((*hep)->val)); #endif /* replace entry */ (*hep)->val = val; #ifdef HASH_TIMESTAMP /* Update or set the timestamp */ (*hep)->stamp = time(NULL); #endif /* check that the collision rate isn't too high */ if(ht->count > ht->max) { if(!expand_array(ht)) return 0; } return 1; } return 0; } #ifdef HASH_COPYKEYS void* hash_rem(hash_t* ht, const void* key) { hash_entry_t** hep = find_entry(ht, key, NULL); #else void* hash_rem(hash_t* ht, const void* key, size_t klen) { hash_entry_t** hep = find_entry(ht, key, klen, NULL); #endif void* val = NULL; if(hep && *hep) { hash_entry_t* old = *hep; *hep = (*hep)->next; --ht->count; val = (void*)old->val; free(old); } return val; } unsigned int hash_count(hash_t* ht) { return ht->count; } #ifdef HASH_TIMESTAMP int hash_purge(hash_t* ht, time_t stamp) { hash_index_t* hi; int r = 0; void* val; for(hi = hash_first(ht); hi; hi = hash_next(hi)) { if(hi->ths->stamp < stamp) { /* No need to check for errors as we're deleting */ #ifdef HASH_COPYKEYS val = hash_rem(ht, KEY_DATA(hi->ths)); #else val = hash_rem(ht, hi->ths->key, hi->ths->klen); #endif #ifdef HASH_CALLBACKS if(val && ht->f_free) (ht->f_free)(ht->arg, val); #endif r++; } } return r; } #ifdef HASH_COPYKEYS void hash_touch(hash_t* ht, const void* key) { hash_entry_t** hep = find_entry(ht, key, NULL); #else void hash_touch(hash_t* ht, const void* key, size_t* klen) { hash_entry_t** hep = find_entry(ht, key, klen, NULL); #endif if(hep && *hep) ((*hep)->stamp) = time(NULL); } int hash_bump(hash_t* ht) { hash_index_t* hi; void* key = NULL; void* val = NULL; time_t least = 0; #ifndef HASH_COPYKEYS size_t klen = 0; #endif for(hi = hash_first(ht); hi; hi = hash_next(hi)) { if(least == 0 || hi->ths->stamp < least) { least = hi->ths->stamp; key = KEY_DATA(hi->ths); #ifndef HASH_COPYKEYS klen = hi->this->klen; #endif } } if(key) { #ifdef HASH_COPYKEYS val = hash_rem(ht, key); #else val = hash_rem(ht, key, klen); #endif #ifdef HASH_CALLBACKS if(val && ht->f_free) (ht->f_free)(ht->arg, (void*)val); #endif return 1; } return 0; } #endif /* HASH_TIMESTAMP */