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
62
63
64
65
66
67
|
import "all.hff";
// KTraits:
// :hash(K) u32
// :eq(T, T) bool
struct Map<K, V, KTraits> {
keys *K,
vals *V,
bitmap *u8,
N int,
count int,
fn _iempty(self *Map, i int) bool {
return (self.bitmap[i/8] & (1 << (i%8))) == 0;
}
fn get(self *Map, key K) *V {
if self.N == 0 {
return #null;
}
let i0 u32 = KTraits:hash(key);
let i = i0 & (self.N - 1);
do {
if self->_iempty(i) {
return #null;
} else if KTraits:eq(self.keys[i], key) {
return &self.vals[i];
}
i = (i + 1) & (self.N - 1);
} while i != i0;
assert(#f, "unreachable");
}
fn get_slot(self *Map, key K) *V {
if self.keys == #null {
assert(self.vals == #null and self.bitmap == #null and self.N == 0 and self.count == 0,
"?");
self.keys = xcalloc(self.N = 16, sizeof K);
self.vals = xcalloc(self.N, sizeof V);
self.bitmap = xcalloc(self.N / 8, 1);
}
if self.count == self.N / 2 {
// rehash
}
let i0 u32 = KTraits:hash(key);
let i = i0 & (self.N - 1);
do {
if self->_iempty(i) {
self.bitmap[i/8] |= (1 << (i%8));
++self.count;
self.vals[i] = {};
return &self.vals[i];
} else if KTraits:eq(self.keys[i], key) {
return &self.vals[i];
}
i = (i + 1) & (self.N - 1);
} while i != i0;
assert(#f, "unreachable");
}
fn put(self *Map, key K, val V) void {
*self->get_slot(key) = val;
}
}
|
