From 495913bfaec0ff19107f0cc903ba1d6eade03709 Mon Sep 17 00:00:00 2001 From: Mathieu Desnoyers Date: Sun, 29 Apr 2012 16:49:10 -0400 Subject: [PATCH] rculfhash tests: add long hash chains tests Signed-off-by: Mathieu Desnoyers --- tests/test_urcu_hash.c | 7 +++++++ tests/test_urcu_hash.h | 29 +++++++++++++++++++++++++++-- 2 files changed, 34 insertions(+), 2 deletions(-) diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index 3c7cc35..accf3c1 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -114,6 +114,7 @@ unsigned long init_pool_size = DEFAULT_RAND_POOL, lookup_pool_size = DEFAULT_RAND_POOL, write_pool_size = DEFAULT_RAND_POOL; int validate_lookup; +unsigned long nr_hash_chains; /* 0: normal table, other: number of hash chains */ int count_pipe[2]; @@ -290,6 +291,7 @@ printf(" [not -u nor -s] Add entries (supports redundant keys).\n"); printf(" [-O size] Init pool size.\n"); printf(" [-V] Validate lookups of init values (use with filled init pool, same lookup range, with different write range).\n"); printf(" [-U] Uniqueness test.\n"); + printf(" [-C] Number of hash chains.\n"); printf("\n\n"); } @@ -456,6 +458,9 @@ int main(int argc, char **argv) case 'U': test_choice = TEST_HASH_UNIQUE; break; + case 'C': + nr_hash_chains = atol(argv[++i]); + break; } } @@ -528,6 +533,8 @@ int main(int argc, char **argv) lookup_pool_offset, lookup_pool_size); printf_verbose("Update pool size offset %lu size %lu.\n", write_pool_offset, write_pool_size); + printf_verbose("Number of hash chains: %lu.\n", + nr_hash_chains); printf_verbose("thread %-6s, thread id : %lx, tid %lu\n", "main", pthread_self(), (unsigned long)gettid()); diff --git a/tests/test_urcu_hash.h b/tests/test_urcu_hash.h index a935e94..083e71c 100644 --- a/tests/test_urcu_hash.h +++ b/tests/test_urcu_hash.h @@ -169,6 +169,8 @@ extern unsigned long init_pool_size, write_pool_size; extern int validate_lookup; +extern unsigned long nr_hash_chains; + extern int count_pipe[2]; static inline void loop_sleep(unsigned long l) @@ -323,7 +325,7 @@ void hashword2( #if (CAA_BITS_PER_LONG == 32) static inline -unsigned long test_hash(const void *_key, size_t length, unsigned long seed) +unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed) { unsigned int key = (unsigned int) _key; @@ -332,7 +334,7 @@ unsigned long test_hash(const void *_key, size_t length, unsigned long seed) } #else static inline -unsigned long test_hash(const void *_key, size_t length, unsigned long seed) +unsigned long test_hash_mix(const void *_key, size_t length, unsigned long seed) { union { uint64_t v64; @@ -351,6 +353,29 @@ unsigned long test_hash(const void *_key, size_t length, unsigned long seed) } #endif +/* + * Hash function with nr_hash_chains != 0 for testing purpose only! + * Creates very long hash chains, deteriorating the hash table into a + * few linked lists, depending on the nr_hash_chains value. The purpose + * of this test is to check how the hash table behaves with hash chains + * containing different values, which is a rare case in a normal hash + * table. + */ +static inline +unsigned long test_hash(const void *_key, size_t length, + unsigned long seed) +{ + if (nr_hash_chains == 0) { + return test_hash_mix(_key, length, seed); + } else { + unsigned long v; + + assert(length == sizeof(unsigned long)); + v = (unsigned long) _key; + return v % nr_hash_chains; + } +} + unsigned long test_compare(const void *key1, size_t key1_len, const void *key2, size_t key2_len); -- 2.34.1