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
|
import "vec.hff";
import "all.hff";
// KTraits:
// :hash(K) u32
// :eq(T, T) bool
// :dup(T) T
struct Set<T, Traits> {
buf Vec<T>,
set **const T,
N int,
count int,
fn intern(self *Set, x T) *const T {
if self.set == #null {
self.set = xcalloc(self.N = 16, sizeof *T);
}
if self.count == self.N / 2 {
free(self.set);
self.set = xcalloc(self.N *= 2, sizeof *T);
vec_each(p, i, self.buf,
let i = Traits:hash(p) & (self.N - 1);
for ;; {
if self.set[i] == #null {
self.set[i] = &self.buf.dat[i];
break;
}
i = (i + 1) & (self.N - 1);
}
)
}
let i0 u32 = Traits:hash(x) & (self.N - 1);
let i int = i0;
do {
if self.set[i] == #null {
++self.count;
self.buf->push(Traits:dup(x));
return self.set[i] = &self.buf.dat[self.buf.len - 1];
} else if Traits:eq(*self.set[i], x) {
return self.set[i];
}
i = (i + 1) & (self.N - 1);
} while i != i0;
assert(#f, "unreachable");
}
fn contains(self *Set, x T) bool {
let i0 u32 = Traits:hash(x) & (self.N - 1);
let i int = i0;
do {
if self.set[i] == #null {
return #f;
} else if Traits:eq(*self.set[i], x) {
return #t;
}
i = (i + 1) & (self.N - 1);
} while i != i0;
assert(#f, "unreachable");
}
fn put(self *Set, x T) void {
self->intern(x);
}
}
|
