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
|
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 *int,
N int,
count int,
fn intern(self *Set, x T) *const T {
if self.set == #null {
self.set = xcalloc(self.N = 16, sizeof int);
}
if self.count == self.N / 2 {
free(self.set);
self.set = xcalloc(self.N *= 2, sizeof int);
vec_each(p, i, self.buf,
let j = Traits:hash(p) & (self.N - 1);
for ;; {
if self.set[j] == 0 {
self.set[j] = i + 1;
break;
}
j = (j + 1) & (self.N - 1);
}
)
}
let i0 u32 = Traits:hash(x) & (self.N - 1);
let i int = i0;
do {
if self.set[i] == 0 {
++self.count;
self.buf->push(Traits:dup(x));
self.set[i] = self.buf.len;
return self.buf->lastp();
} else {
let x2 = &self.buf.dat[self.set[i] - 1];
if Traits:eq(*x2, x) {
return x2;
}
}
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] == 0 {
return #f;
} else if Traits:eq(self.buf.dat[self.set[i] - 1], 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);
}
}
|
