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
58
59
60
61
|
use fmt;
use hash;
use hash::fnv;
use math::random;
fn test_eq(ctx: *opaque, entry: *opaque) bool =
*(ctx: *u64) == *(entry: *u64);
fn test_fnvhash(x: u64) u64 = {
let h = fnv::fnv64a();
hash::write(&h, &x: *[8]u8);
return fnv::sum64(&h);
};
fn test_garbagehash(x: u64) u64 =
0x0123456789abcdef;
fn test_table(sz: size, hash_fn: *fn(x: u64) u64, rng: *random::random) void = {
fmt::printf("{} ", sz)!;
static let array: [1024]bool = [false...];
for (let i = 0z; i < len(array); i += 1) {
array[i] = false;
};
let tab = new(0, sz);
defer finish(&tab);
for (let i = 0; i < 100000; i += 1) {
const x = random::u64n(rng, len(array): u64);
const hash = hash_fn(x);
match (get(&tab, hash, &test_eq, &x, sz)) {
case let entry: *opaque =>
assert(array[x: size]);
assert(*(entry: *u64) == x);
del(&tab, entry, sz);
array[x: size] = false;
case null =>
assert(!array[x: size]);
const entry = add(&tab, hash, sz);
array[x: size] = true;
*(entry: *u64) = x;
};
};
for (let x = 0u64; x < len(array): u64; x += 1) {
const hash = hash_fn(x);
get(&tab, hash, &test_eq, &x, sz);
};
fmt::println()!;
};
@test fn table() void = {
let rng = random::init(42);
fmt::println("fnvhash:")!;
for (let i = 8z; i < 128; i += 8)
test_table(i, &test_fnvhash, &rng);
fmt::println("garbagehash:")!;
for (let i = 8z; i < 128; i += 8)
test_table(i, &test_garbagehash, &rng);
};
|
