diff options
author | Bojan Smojver <bojan@apache.org> | 2012-01-30 07:06:08 +0000 |
---|---|---|
committer | Bojan Smojver <bojan@apache.org> | 2012-01-30 07:06:08 +0000 |
commit | 33d5d0819139d5eee8ae45395fd8869aca273bc5 (patch) | |
tree | abe2de7c1c12623d5a1ed5ef48a8a08f00efd505 /tables | |
parent | 613430bd3be266a1d8d11eb5be6517f0e233e942 (diff) | |
download | apr-33d5d0819139d5eee8ae45395fd8869aca273bc5.tar.gz |
Backport r1236970, r1237078 and r1237507 from trunk.
Randomise hashes by providing a seed (initial hash value).
git-svn-id: https://svn.apache.org/repos/asf/apr/apr/branches/1.5.x@1237546 13f79535-47bb-0310-9956-ffa450edef68
Diffstat (limited to 'tables')
-rw-r--r-- | tables/apr_hash.c | 38 |
1 files changed, 28 insertions, 10 deletions
diff --git a/tables/apr_hash.c b/tables/apr_hash.c index b2990ba64..9851b9ec8 100644 --- a/tables/apr_hash.c +++ b/tables/apr_hash.c @@ -18,6 +18,7 @@ #include "apr_general.h" #include "apr_pools.h" +#include "apr_time.h" #include "apr_hash.h" @@ -78,7 +79,7 @@ struct apr_hash_t { apr_pool_t *array_pool; apr_hash_entry_t **array; apr_hash_index_t iterator; /* For apr_hash_first(NULL, ...) */ - unsigned int count, max; + unsigned int count, max, seed; apr_hashfunc_t hash_func; apr_hash_entry_t *free; /* List of recycled entries */ }; @@ -99,6 +100,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool) { apr_pool_t *array_pool; apr_hash_t *ht; + apr_time_t now = apr_time_now(); if (apr_pool_create(&array_pool, pool) != APR_SUCCESS) return NULL; @@ -109,8 +111,11 @@ APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool) ht->free = NULL; ht->count = 0; ht->max = INITIAL_MAX; + ht->seed = (unsigned int)((now >> 32) ^ now ^ (apr_uintptr_t)pool ^ + (apr_uintptr_t)ht ^ (apr_uintptr_t)&now) - 1; ht->array = alloc_array(ht, ht->max); - ht->hash_func = apr_hashfunc_default; + ht->hash_func = NULL; + return ht; } @@ -196,10 +201,9 @@ static void expand_array(apr_hash_t *ht) apr_pool_destroy(old_array_pool); } -APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, - apr_ssize_t *klen) +static unsigned int hashfunc_default(const char *char_key, apr_ssize_t *klen, + unsigned int hash) { - unsigned int hash = 0; const unsigned char *key = (const unsigned char *)char_key; const unsigned char *p; apr_ssize_t i; @@ -241,7 +245,7 @@ APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, * * -- Ralf S. Engelschall <rse@engelschall.com> */ - + if (*klen == APR_HASH_KEY_STRING) { for (p = key; *p; p++) { hash = hash * 33 + *p; @@ -257,6 +261,11 @@ APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, return hash; } +APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, + apr_ssize_t *klen) +{ + return hashfunc_default(char_key, klen, 0); +} /* * This is where we keep the details of the hash function and control @@ -275,7 +284,10 @@ static apr_hash_entry_t **find_entry(apr_hash_t *ht, apr_hash_entry_t **hep, *he; unsigned int hash; - hash = ht->hash_func(key, &klen); + if (ht->hash_func) + hash = ht->hash_func(key, &klen); + else + hash = hashfunc_default(key, &klen, ht->seed); /* scan linked list */ for (hep = &ht->array[hash & ht->max], he = *hep; @@ -321,6 +333,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_copy(apr_pool_t *pool, ht->free = NULL; ht->count = orig->count; ht->max = orig->max; + ht->seed = orig->seed; ht->hash_func = orig->hash_func; ht->array = alloc_array(ht, ht->max); @@ -418,7 +431,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, apr_hash_entry_t *new_vals = NULL; apr_hash_entry_t *iter; apr_hash_entry_t *ent; - unsigned int i,j,k; + unsigned int i, j, k, hash; #if APR_POOL_DEBUG /* we don't copy keys and values, so it's necessary that @@ -450,6 +463,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, if (base->count + overlay->count > res->max) { res->max = res->max * 2 + 1; } + res->seed = base->seed; res->array = alloc_array(res, res->max); if (base->count + overlay->count) { new_vals = apr_palloc(p, sizeof(apr_hash_entry_t) * @@ -471,7 +485,11 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, for (k = 0; k <= overlay->max; k++) { for (iter = overlay->array[k]; iter; iter = iter->next) { - i = iter->hash & res->max; + if (res->hash_func) + hash = res->hash_func(iter->key, &iter->klen); + else + hash = hashfunc_default(iter->key, &iter->klen, res->seed); + i = hash & res->max; for (ent = res->array[i]; ent; ent = ent->next) { if ((ent->klen == iter->klen) && (memcmp(ent->key, iter->key, iter->klen) == 0)) { @@ -489,7 +507,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge(apr_pool_t *p, new_vals[j].klen = iter->klen; new_vals[j].key = iter->key; new_vals[j].val = iter->val; - new_vals[j].hash = iter->hash; + new_vals[j].hash = hash; new_vals[j].next = res->array[i]; res->array[i] = &new_vals[j]; res->count++; |