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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
import "common.hff";
import "util.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 h u32 = KTraits:hash(key);
let i = h & (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 != h;
assert(#f, "unreachable1");
}
fn _reallockvb(self *Map) void {
// keys, vals, bitmap are in a contiguous memory allocation,
// XXX ^ alignment
let p = xcalloc((self.N * (sizeof K + sizeof V)) + (self.N / 8), 1);
self.keys = p;
self.vals = as(*V)(self.keys + self.N);
self.bitmap = as(*u8)(self.vals + self.N);
}
fn _rehash(self *Map, newN int) void {
let oldks = self.keys,
oldvs = self.vals,
oldbmp = self.bitmap;
self.N *= 2;
self->_reallockvb();
for let i = 0; i < self.N / 2; ++i {
let k = oldks[i],
v = oldvs[i],
b = (oldbmp[i/8] & (1 << (i%8))) != 0;
if (b) {
let h u32 = KTraits:hash(k);
let j = h & (self.N - 1);
for ;; {
if self->_iempty(j) {
self.keys[j] = k;
self.vals[j] = v;
self.bitmap[j/8] |= 1 << (j%8);
break;
} else if KTraits:eq(self.keys[j], k) {
assert(#f, "unreachable2");
}
j = (j + 1) & (self.N - 1);
}
}
}
free(oldks);
}
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.N = 16;
_reallockvb(self);
}
if self.count == self.N / 2 {
self->_rehash(self.N * 2);
}
let h u32 = KTraits:hash(key);
let i = h & (self.N - 1);
do {
if self->_iempty(i) {
self.bitmap[i/8] |= (1 << (i%8));
++self.count;
self.keys[i] = key;
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 != h;
assert(#f, "unreachable3");
}
fn put(self *Map, key K, val V) *V {
let slot = self->get_slot(key);
*slot = val;
return slot;
}
fn clear(self *Map) void {
free(self.keys);
*self = {};
}
}
defmacro map_each(v, k, map, &body) [
let $m = (map);
for let $i = 0; $i < $m.N; ++$i {
if $m->_iempty($i) {
continue;
}
let k = $m.keys[$i];
let v = $m.vals[$i];
body;
}
]
|
