-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathhash_test.c
57 lines (54 loc) · 1.67 KB
/
hash_test.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include "hash.h"
#include "test.h"
#include <stdlib.h>
static _Bool match_pointee(int val, void *ctx) {
return val == *(int const*)ctx;
}
static void test(int const n, unsigned (*hash_fn)(int)) {
struct hash h = {0};
for (int i = 0; i < n; i += 2) {
expect(!hash_lookup(h, hash_fn(i), match_pointee, &i));
hash_insert(&h, hash_fn(i), i);
expect( hash_lookup(h, hash_fn(i), match_pointee, &i));
}
for (int i = 0; i < n; i += 1) {
expect( hash_lookup(h, hash_fn(i), match_pointee, &i));
i++;
expect(!hash_lookup(h, hash_fn(i), match_pointee, &i));
}
for (int i = 0; i < n; i += 2) {
expect(hash_lookup(h, hash_fn(i), NULL, (void*)(intptr_t)i));
}
free(h.data);
}
static void bench(int const n, unsigned (*hash_fn)(int), int loops) {
struct hash h = {0};
for (int i = 0; i < n; i += 2) {
hash_insert(&h, hash_fn(i), i);
}
while (loops --> 0) {
for (int i = 0; i < n; i++) {
(void)hash_lookup(h, hash_fn(i), NULL, (void*)(intptr_t)i);
}
}
free(h.data);
}
#if defined(__clang__)
__attribute__((no_sanitize("unsigned-integer-overflow", "unsigned-shift-base")))
#endif
static unsigned murmur3_scramble(int x) {
unsigned bits = (unsigned)x * 0xcc9e2d51;
bits = (bits << 15) | (bits >> 17);
return bits * 0x1b873593;
}
static unsigned zero(int x) { (void)x; return 0; }
static unsigned identity(int x) { return (unsigned)x; }
int main(int argc, char* argv[]) {
test( 100, zero);
test( 10000, identity);
test(1000000, murmur3_scramble);
if (argc > 1) {
bench(100, murmur3_scramble, atoi(argv[1]));
}
return 0;
}