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
|
import "vec.hff";
#{
Traits:hash(K) u32
:eq(T, T) bool
:dup(T) T // useful to strdup strings before interning them
}
struct Set<T, Traits> {
buf Vec<T>,
set *int,
N int,
count int,
fn _nexthash(h *u32) u32 {
// return *h = (*h * 1664525) + 1013904223u; // double hashing
return ++*h; // linear probing
}
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 h = Traits:hash(p);
let j = h & (self.N - 1);
for ;; {
if self.set[j] == 0 {
self.set[j] = i + 1;
break;
}
j = _nexthash(&h) & (self.N - 1);
}
}
}
let h u32 = Traits:hash(x);
let i = h & (self.N - 1);
let n = 0;
for ;; {
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;
}
}
++n;
i = _nexthash(&h) & (self.N - 1);
}
}
fn contains(self *Set, x T) bool {
if self.N == 0 { return #f; }
let h u32 = Traits:hash(x);
let i = h & (self.N - 1);
for ;; {
if self.set[i] == 0 {
return #f;
} else if Traits:eq(self.buf.dat[self.set[i] - 1], x) {
return #t;
}
i = _nexthash(&h) & (self.N - 1);
}
}
fn put(self *Set, x T) void {
self->intern(x);
}
fn clear(self *Set) void {
self.buf->clear();
free(self.set);
*self = {};
}
}
defmacro set_each(v, Set, &body) [
let $s = (Set);
for let $i = 0; $i < $s.N; ++$i {
let $idx = $s.set[$i];
if $idx > 0 {
let v = $s.buf.dat[$idx - 1];
body;
}
}
]
|
