Return-Path: X-Original-To: apmail-apr-commits-archive@www.apache.org Delivered-To: apmail-apr-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 3F28B92BB for ; Sat, 28 Jan 2012 03:23:55 +0000 (UTC) Received: (qmail 38601 invoked by uid 500); 28 Jan 2012 03:23:45 -0000 Delivered-To: apmail-apr-commits-archive@apr.apache.org Received: (qmail 38502 invoked by uid 500); 28 Jan 2012 03:23:35 -0000 Mailing-List: contact commits-help@apr.apache.org; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: Reply-To: dev@apr.apache.org List-Id: Delivered-To: mailing list commits@apr.apache.org Received: (qmail 38495 invoked by uid 99); 28 Jan 2012 03:23:33 -0000 Received: from athena.apache.org (HELO athena.apache.org) (140.211.11.136) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 28 Jan 2012 03:23:33 +0000 X-ASF-Spam-Status: No, hits=-2000.0 required=5.0 tests=ALL_TRUSTED X-Spam-Check-By: apache.org Received: from [140.211.11.4] (HELO eris.apache.org) (140.211.11.4) by apache.org (qpsmtpd/0.29) with ESMTP; Sat, 28 Jan 2012 03:23:32 +0000 Received: from eris.apache.org (localhost [127.0.0.1]) by eris.apache.org (Postfix) with ESMTP id 1B22423889E7 for ; Sat, 28 Jan 2012 03:23:12 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r1236970 - in /apr/apr/trunk: tables/apr_hash.c test/testhash.c Date: Sat, 28 Jan 2012 03:23:11 -0000 To: commits@apr.apache.org From: bojan@apache.org X-Mailer: svnmailer-1.0.8-patched Message-Id: <20120128032312.1B22423889E7@eris.apache.org> Author: bojan Date: Sat Jan 28 03:23:11 2012 New Revision: 1236970 URL: http://svn.apache.org/viewvc?rev=1236970&view=rev Log: Randomise hashes by providing a seed (initial hash value). Modified: apr/apr/trunk/tables/apr_hash.c apr/apr/trunk/test/testhash.c Modified: apr/apr/trunk/tables/apr_hash.c URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_hash.c?rev=1236970&r1=1236969&r2=1236970&view=diff ============================================================================== --- apr/apr/trunk/tables/apr_hash.c (original) +++ apr/apr/trunk/tables/apr_hash.c Sat Jan 28 03:23:11 2012 @@ -18,6 +18,7 @@ #include "apr_general.h" #include "apr_pools.h" +#include "apr_time.h" #include "apr_hash.h" @@ -75,7 +76,7 @@ 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; + unsigned int count, max, seed; apr_hashfunc_t hash_func; apr_hash_entry_t *free; /* List of recycled entries */ }; @@ -95,13 +96,18 @@ static apr_hash_entry_t **alloc_array(ap APR_DECLARE(apr_hash_t *) apr_hash_make(apr_pool_t *pool) { apr_hash_t *ht; + apr_time_t now = apr_time_now(); + ht = apr_palloc(pool, sizeof(apr_hash_t)); ht->pool = 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; } @@ -201,10 +207,10 @@ static void expand_array(apr_hash_t *ht) ht->max = new_max; } -APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, - apr_ssize_t *klen) +static unsigned int apr_hashfunc_default_internal(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; @@ -246,7 +252,7 @@ APR_DECLARE_NONSTD(unsigned int) apr_has * * -- Ralf S. Engelschall */ - + if (*klen == APR_HASH_KEY_STRING) { for (p = key; *p; p++) { hash = hash * 33 + *p; @@ -262,6 +268,11 @@ APR_DECLARE_NONSTD(unsigned int) apr_has return hash; } +APR_DECLARE_NONSTD(unsigned int) apr_hashfunc_default(const char *char_key, + apr_ssize_t *klen) +{ + return apr_hashfunc_default_internal(char_key, klen, 0); +} /* * This is where we keep the details of the hash function and control @@ -280,7 +291,10 @@ static apr_hash_entry_t **find_entry(apr 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 = apr_hashfunc_default_internal(key, &klen, ht->seed); /* scan linked list */ for (hep = &ht->array[hash & ht->max], he = *hep; @@ -322,6 +336,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_copy( ht->free = NULL; ht->count = orig->count; ht->max = orig->max; + ht->seed = orig->seed; ht->hash_func = orig->hash_func; ht->array = (apr_hash_entry_t **)((char *)ht + sizeof(apr_hash_t)); @@ -419,7 +434,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge 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 @@ -447,6 +462,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge 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) * @@ -468,7 +484,12 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge 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 = apr_hashfunc_default_internal(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)) { @@ -486,7 +507,7 @@ APR_DECLARE(apr_hash_t *) apr_hash_merge 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++; Modified: apr/apr/trunk/test/testhash.c URL: http://svn.apache.org/viewvc/apr/apr/trunk/test/testhash.c?rev=1236970&r1=1236969&r2=1236970&view=diff ============================================================================== --- apr/apr/trunk/test/testhash.c (original) +++ apr/apr/trunk/test/testhash.c Sat Jan 28 03:23:11 2012 @@ -438,6 +438,79 @@ static void overlay_same(abts_case *tc, ABTS_STR_EQUAL(tc, "#entries 5\n", StrArray[5]); } +static void overlay_fetch(abts_case *tc, void *data) +{ + apr_hash_t *base = NULL; + apr_hash_t *overlay = NULL; + apr_hash_t *result = NULL; + int count; + + base = apr_hash_make(p); + overlay = apr_hash_make(p); + ABTS_PTR_NOTNULL(tc, base); + ABTS_PTR_NOTNULL(tc, overlay); + + apr_hash_set(base, "base1", APR_HASH_KEY_STRING, "value1"); + apr_hash_set(base, "base2", APR_HASH_KEY_STRING, "value2"); + apr_hash_set(base, "base3", APR_HASH_KEY_STRING, "value3"); + apr_hash_set(base, "base4", APR_HASH_KEY_STRING, "value4"); + apr_hash_set(base, "base5", APR_HASH_KEY_STRING, "value5"); + + apr_hash_set(overlay, "overlay1", APR_HASH_KEY_STRING, "value1"); + apr_hash_set(overlay, "overlay2", APR_HASH_KEY_STRING, "value2"); + apr_hash_set(overlay, "overlay3", APR_HASH_KEY_STRING, "value3"); + apr_hash_set(overlay, "overlay4", APR_HASH_KEY_STRING, "value4"); + apr_hash_set(overlay, "overlay5", APR_HASH_KEY_STRING, "value5"); + + result = apr_hash_overlay(p, overlay, base); + + count = apr_hash_count(result); + ABTS_INT_EQUAL(tc, 10, count); + + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(result, "base1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(result, "base2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(result, "base3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(result, "base4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(result, "base5", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(result, "overlay1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(result, "overlay2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(result, "overlay3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(result, "overlay4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(result, "overlay5", APR_HASH_KEY_STRING)); + + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(base, "base1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(base, "base2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(base, "base3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(base, "base4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(base, "base5", APR_HASH_KEY_STRING)); + + ABTS_STR_EQUAL(tc, "value1", + apr_hash_get(overlay, "overlay1", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value2", + apr_hash_get(overlay, "overlay2", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value3", + apr_hash_get(overlay, "overlay3", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value4", + apr_hash_get(overlay, "overlay4", APR_HASH_KEY_STRING)); + ABTS_STR_EQUAL(tc, "value5", + apr_hash_get(overlay, "overlay5", APR_HASH_KEY_STRING)); +} + abts_suite *testhash(abts_suite *suite) { suite = ADD_SUITE(suite) @@ -461,6 +534,7 @@ abts_suite *testhash(abts_suite *suite) abts_run_test(suite, overlay_empty, NULL); abts_run_test(suite, overlay_2unique, NULL); abts_run_test(suite, overlay_same, NULL); + abts_run_test(suite, overlay_fetch, NULL); return suite; }