/* 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 "apr_private.h" #include "apr_general.h" #include "apr_pools.h" #include "apr_hash.h" #if APR_HAVE_STDLIB_H #include #endif #if APR_HAVE_STRING_H #include #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 apr_hash_entry_t apr_hash_entry_t; struct apr_hash_entry_t { apr_hash_entry_t *next; unsigned int hash; const void *key; apr_ssize_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 * apr_hash_next(). */ struct apr_hash_index_t { apr_hash_t *ht; apr_hash_entry_t *this, *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 apr_hash_t { apr_pool_t *pool; apr_hash_entry_t **array; apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */ unsigned int count, max; }; #define INITIAL_MAX 15 /* tunable == 2^n - 1 */ /* * Hash creation functions. */ static apr_hash_entry_t **alloc_array(apr_hash_t *ht, unsigned int max) 24 { 24 return apr_pcalloc(ht->pool, sizeof(*ht->array) * (max + 1)); } APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool) 18 { 18 apr_hash_t *ht; 18 ht = apr_palloc(pool, sizeof(apr_hash_t)); 18 ht->pool = pool; 18 ht->count = 0; 18 ht->max = INITIAL_MAX; 18 ht->array = alloc_array(ht, ht->max); 18 return ht; } /* * Hash iteration functions. */ APR_DECLARE(apr_hash_index_t *) apr_hash_next(apr_hash_index_t *hi) 247 { 247 hi->this = hi->next; 551 while (!hi->this) { 312 if (hi->index > hi->ht->max) 8 return NULL; 304 hi->this = hi->ht->array[hi->index++]; } 239 hi->next = hi->this->next; 239 return hi; } APR_DECLARE(apr_hash_index_t *) apr_hash_first(apr_pool_t *p, apr_hash_t *ht) 8 { 8 apr_hash_index_t *hi; 8 if (p) 5 hi = apr_palloc(p, sizeof(*hi)); else 3 hi = &ht->iterator; 8 hi->ht = ht; 8 hi->index = 0; 8 hi->this = NULL; 8 hi->next = NULL; 8 return apr_hash_next(hi); } APR_DECLARE(void) apr_hash_this(apr_hash_index_t *hi, const void **key, apr_ssize_t *klen, void **val) 127 { 127 if (key) *key = hi->this->key; 127 if (klen) *klen = hi->this->klen; 127 if (val) *val = (void *)hi->this->val; } /* * Expanding a hash table */ static void expand_array(apr_hash_t *ht) 3 { 3 apr_hash_index_t *hi; 3 apr_hash_entry_t **new_array; 3 unsigned int new_max; 3 new_max = ht->max * 2 + 1; 3 new_array = alloc_array(ht, new_max); 115 for (hi = apr_hash_first(NULL, ht); hi; hi = apr_hash_next(hi)) { 112 unsigned int i = hi->this->hash & new_max; 112 hi->this->next = new_array[i]; 112 new_array[i] = hi->this; } 3 ht->array = new_array; 3 ht->max = new_max; } /* * 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. */ static apr_hash_entry_t **find_entry(apr_hash_t *ht, const void *key, apr_ssize_t klen, const void *val) 165 { 165 apr_hash_entry_t **hep, *he; 165 const unsigned char *p; 165 unsigned int hash; 165 apr_ssize_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 * . * * 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 */ 165 hash = 0; 165 if (klen == APR_HASH_KEY_STRING) { 395 for (p = key; *p; p++) { 330 hash = hash * 33 + *p; } 65 klen = p - (const unsigned char *)key; } else { 500 for (p = key, i = klen; i; i--, p++) { 400 hash = hash * 33 + *p; } } /* scan linked list */ 200 for (hep = &ht->array[hash & ht->max], he = *hep; he; hep = &he->next, he = *hep) { 52 if (he->hash == hash && he->klen == klen && memcmp(he->key, key, klen) == 0) 17 break; } 165 if (he || !val) 23 return hep; /* add a new entry for non-NULL values */ 142 he = apr_palloc(ht->pool, sizeof(*he)); 142 he->next = NULL; 142 he->hash = hash; 142 he->key = key; 142 he->klen = klen; 142 he->val = val; 142 *hep = he; 142 ht->count++; 142 return hep; } APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool, const apr_hash_t *orig) ###### { ###### apr_hash_t *ht; ###### apr_hash_entry_t *new_vals; ###### unsigned int i, j; ###### ht = apr_palloc(pool, sizeof(apr_hash_t) + sizeof(*ht->array) * (orig->max + 1) + sizeof(apr_hash_entry_t) * orig->count); ###### ht->pool = pool; ###### ht->count = orig->count; ###### ht->max = orig->max; ###### ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t)); ###### new_vals = (apr_hash_entry_t *)((char *)(ht) + sizeof(apr_hash_t) + sizeof(*ht->array) * (orig->max + 1)); ###### j = 0; ###### for (i = 0; i <= ht->max; i++) { ###### apr_hash_entry_t **new_entry = &(ht->array[i]); ###### apr_hash_entry_t *orig_entry = orig->array[i]; ###### while (orig_entry) { ###### *new_entry = &new_vals[j++]; ###### (*new_entry)->hash = orig_entry->hash; ###### (*new_entry)->key = orig_entry->key; ###### (*new_entry)->klen = orig_entry->klen; ###### (*new_entry)->val = orig_entry->val; ###### new_entry = &((*new_entry)->next); ###### orig_entry = orig_entry->next; } ###### *new_entry = NULL; } ###### return ht; } APR_DECLARE(void *) apr_hash_get(apr_hash_t *ht, const void *key, apr_ssize_t klen) 18 { 18 apr_hash_entry_t *he; 18 he = *find_entry(ht, key, klen, NULL); 18 if (he) 12 return (void *)he->val; else 6 return NULL; } APR_DECLARE(void) apr_hash_set(apr_hash_t *ht, const void *key, apr_ssize_t klen, const void *val) 147 { 147 apr_hash_entry_t **hep; 147 hep = find_entry(ht, key, klen, val); 147 if (*hep) { 147 if (!val) { /* delete entry */ 1 *hep = (*hep)->next; 1 --ht->count; } else { /* replace entry */ 146 (*hep)->val = val; /* check that the collision rate isn't too high */ 146 if (ht->count > ht->max) { 3 expand_array(ht); } } } /* else key not present and val==NULL */ } APR_DECLARE(unsigned int) apr_hash_count(apr_hash_t *ht) 6 { 6 return ht->count; } APR_DECLARE(apr_hash_t*) apr_hash_overlay(apr_pool_t *p, const apr_hash_t *overlay, const apr_hash_t *base) 3 { 3 return apr_hash_merge(p, overlay, base, NULL, NULL); } APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, const apr_hash_t *overlay, const apr_hash_t *base, void * (*merger)(apr_pool_t *p, const void *key, apr_ssize_t klen, const void *h1_val, const void *h2_val, const void *data), const void *data) 3 { 3 apr_hash_t *res; 3 apr_hash_entry_t *new_vals = NULL; 3 apr_hash_entry_t *iter; 3 apr_hash_entry_t *ent; 3 unsigned int i,j,k; #ifdef POOL_DEBUG /* we don't copy keys and values, so it's necessary that * overlay->a.pool and base->a.pool have a life span at least * as long as p */ if (!apr_pool_is_ancestor(overlay->pool, p)) { fprintf(stderr, "apr_hash_overlay: overlay's pool is not an ancestor of p\n"); abort(); } if (!apr_pool_is_ancestor(base->pool, p)) { fprintf(stderr, "apr_hash_overlay: base's pool is not an ancestor of p\n"); abort(); } #endif 3 res = apr_palloc(p, sizeof(apr_hash_t)); 3 res->pool = p; 3 res->count = base->count; 3 res->max = (overlay->max > base->max) ? overlay->max : base->max; 3 if (base->count + overlay->count > res->max) { ###### res->max = res->max * 2 + 1; } 3 res->array = alloc_array(res, res->max); 3 if (base->count + overlay->count) { 3 new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * (base->count + overlay->count)); } 3 j = 0; 51 for (k = 0; k <= base->max; k++) { 63 for (iter = base->array[k]; iter; iter = iter->next) { 15 i = iter->hash & res->max; 15 new_vals[j].klen = iter->klen; 15 new_vals[j].key = iter->key; 15 new_vals[j].val = iter->val; 15 new_vals[j].hash = iter->hash; 15 new_vals[j].next = res->array[i]; 15 res->array[i] = &new_vals[j]; 15 j++; } } 51 for (k = 0; k <= overlay->max; k++) { 58 for (iter = overlay->array[k]; iter; iter = iter->next) { 10 i = iter->hash & res->max; 10 for (ent = res->array[i]; ent; ent = ent->next) { 5 if ((ent->klen == iter->klen) && (memcmp(ent->key, iter->key, iter->klen) == 0)) { 5 if (merger) { ###### ent->val = (*merger)(p, iter->key, iter->klen, iter->val, ent->val, data); } else { 5 ent->val = iter->val; } 5 break; } } 10 if (!ent) { 5 new_vals[j].klen = iter->klen; 5 new_vals[j].key = iter->key; 5 new_vals[j].val = iter->val; 5 new_vals[j].hash = iter->hash; 5 new_vals[j].next = res->array[i]; 5 res->array[i] = &new_vals[j]; 5 res->count++; 5 j++; } } } 3 return res; } ###### APR_POOL_IMPLEMENT_ACCESSOR(hash)