X-Git-Url: https://git.liburcu.org/?p=urcu.git;a=blobdiff_plain;f=tests%2Ftest_urcu_hash.c;h=44b9531b2fb8080b1a7e5bf02320669374f5bc6e;hp=2750dd3c6527a35bcb75c28b3fa9fe5a08d18aa4;hb=3eca1b8cce5630bcbd865a8d30855c996bc021c3;hpb=abc490a1549a926de13f29c938d8d6635429e096 diff --git a/tests/test_urcu_hash.c b/tests/test_urcu_hash.c index 2750dd3..44b9531 100644 --- a/tests/test_urcu_hash.c +++ b/tests/test_urcu_hash.c @@ -181,22 +181,148 @@ void rcu_copy_mutex_unlock(void) } } +/* + * Hash function + * Source: http://burtleburtle.net/bob/c/lookup3.c + * Originally Public Domain + */ + +#define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) + +#define mix(a, b, c) \ +do { \ + a -= c; a ^= rot(c, 4); c += b; \ + b -= a; b ^= rot(a, 6); a += c; \ + c -= b; c ^= rot(b, 8); b += a; \ + a -= c; a ^= rot(c, 16); c += b; \ + b -= a; b ^= rot(a, 19); a += c; \ + c -= b; c ^= rot(b, 4); b += a; \ +} while (0) + +#define final(a, b, c) \ +{ \ + c ^= b; c -= rot(b, 14); \ + a ^= c; a -= rot(c, 11); \ + b ^= a; b -= rot(a, 25); \ + c ^= b; c -= rot(b, 16); \ + a ^= c; a -= rot(c, 4);\ + b ^= a; b -= rot(a, 14); \ + c ^= b; c -= rot(b, 24); \ +} + +static __attribute__((unused)) +uint32_t hash_u32( + const uint32_t *k, /* the key, an array of uint32_t values */ + size_t length, /* the length of the key, in uint32_ts */ + uint32_t initval) /* the previous hash, or an arbitrary value */ +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + (((uint32_t) length) << 2) + initval; + + /*----------------------------------------- handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 3; + k += 3; + } + + /*----------------------------------- handle the last 3 uint32_t's */ + switch (length) { /* all the case statements fall through */ + case 3: c += k[2]; + case 2: b += k[1]; + case 1: a += k[0]; + final(a, b, c); + case 0: /* case 0: nothing left to add */ + break; + } + /*---------------------------------------------- report the result */ + return c; +} + +static +void hashword2( + const uint32_t *k, /* the key, an array of uint32_t values */ + size_t length, /* the length of the key, in uint32_ts */ + uint32_t *pc, /* IN: seed OUT: primary hash value */ + uint32_t *pb) /* IN: more seed OUT: secondary hash value */ +{ + uint32_t a, b, c; + + /* Set up the internal state */ + a = b = c = 0xdeadbeef + ((uint32_t) (length << 2)) + *pc; + c += *pb; + + /*----------------------------------------- handle most of the key */ + while (length > 3) { + a += k[0]; + b += k[1]; + c += k[2]; + mix(a, b, c); + length -= 3; + k += 3; + } + + /*----------------------------------- handle the last 3 uint32_t's */ + switch (length) { /* all the case statements fall through */ + case 3: c += k[2]; + case 2: b += k[1]; + case 1: a += k[0]; + final(a, b, c); + case 0: /* case 0: nothing left to add */ + break; + } + /*---------------------------------------------- report the result */ + *pc = c; + *pb = b; +} + +#if (CAA_BITS_PER_LONG == 32) static -unsigned long test_hash(void *_hashseed, void *_key) +unsigned long test_hash(void *_key, size_t length, unsigned long seed) { - unsigned long seed = (unsigned long) _hashseed; unsigned long key = (unsigned long) _key; unsigned long v; - v = key ^ seed; - v ^= v << 8; - v ^= v << 16; - v ^= v << 27; - v ^= v >> 8; - v ^= v >> 16; - v ^= v >> 27; + assert(length == sizeof(unsigned long)); + return hash_u32(&v, 1, seed); +} +#else +static +unsigned long test_hash(void *_key, size_t length, unsigned long seed) +{ + union { + uint64_t v64; + uint32_t v32[2]; + } v; + union { + uint64_t v64; + uint32_t v32[2]; + } key; + + assert(length == sizeof(unsigned long)); + v.v64 = (uint64_t) seed; + key.v64 = (uint64_t) _key; + hashword2(key.v32, 2, &v.v32[0], &v.v32[1]); + return v.v64; +} +#endif - return v; +static +unsigned long test_compare(void *key1, size_t key1_len, + void *key2, size_t key2_len) +{ + if (unlikely(key1_len != key2_len)) + return -1; + assert(key1_len == sizeof(unsigned long)); + if (key1 == key2) + return 0; + else + return 1; } void *thr_reader(void *_count) @@ -219,7 +345,8 @@ void *thr_reader(void *_count) for (;;) { rcu_read_lock(); node = ht_lookup(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL)); + (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), + sizeof(void *)); if (node == NULL) lookup_fail++; else @@ -276,20 +403,20 @@ void *thr_writer(void *_count) rcu_read_lock(); ht_node_init(node, (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), + sizeof(void *), (void *) 0x42); - ret = ht_add(test_ht, node); + ret = ht_add_unique(test_ht, node); rcu_read_unlock(); - if (ret == -EEXIST) { - free(node); + if (ret) nr_addexist++; - } else { + else nr_add++; - } } else { /* May delete */ rcu_read_lock(); node = ht_lookup(test_ht, - (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL)); + (void *)(unsigned long)(rand_r(&rand_lookup) % RAND_POOL), + sizeof(void *)); if (node) ret = ht_remove(test_ht, node); else @@ -429,7 +556,7 @@ int main(int argc, char **argv) tid_writer = malloc(sizeof(*tid_writer) * nr_writers); count_reader = malloc(sizeof(*count_reader) * nr_readers); count_writer = malloc(sizeof(*count_writer) * nr_writers); - test_ht = ht_new(test_hash, (void *) 0x42, + test_ht = ht_new(test_hash, test_compare, 0x42UL, HASH_SIZE, call_rcu); next_aff = 0; @@ -466,10 +593,10 @@ int main(int argc, char **argv) exit(1); tot_writes += count_writer[i]; } - rcu_register_thread(); ret = ht_destroy(test_ht); - rcu_unregister_thread(); - + if (ret) + printf("WARNING: nodes left in the hash table upon destroy\n"); + printf_verbose("final delete: %d items\n", ret); printf_verbose("total number of reads : %llu, writes %llu\n", tot_reads, tot_writes);