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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
|
struct StringSetFindResult {
isize hash_index;
isize entry_prev;
isize entry_index;
};
struct StringSetEntry {
HashKey key;
isize next;
String value;
};
struct StringSet {
Array<isize> hashes;
Array<StringSetEntry> entries;
};
void string_set_init (StringSet *s, gbAllocator a, isize capacity = 16);
void string_set_destroy(StringSet *s);
void string_set_add (StringSet *s, String str);
bool string_set_exists (StringSet *s, String str);
void string_set_remove (StringSet *s, String str);
void string_set_clear (StringSet *s);
void string_set_grow (StringSet *s);
void string_set_rehash (StringSet *s, isize new_count);
gb_inline void string_set_init(StringSet *s, gbAllocator a, isize capacity) {
array_init(&s->hashes, a);
array_init(&s->entries, a);
}
gb_inline void string_set_destroy(StringSet *s) {
array_free(&s->entries);
array_free(&s->hashes);
}
gb_internal isize string_set__add_entry(StringSet *s, HashKey key) {
StringSetEntry e = {};
e.key = key;
e.next = -1;
array_add(&s->entries, e);
return s->entries.count-1;
}
gb_internal StringSetFindResult string_set__find(StringSet *s, HashKey key) {
StringSetFindResult fr = {-1, -1, -1};
if (s->hashes.count > 0) {
// fr.hash_index = u128_to_i64(key.key % u128_from_i64(s->hashes.count));
fr.hash_index = key.key % s->hashes.count;
fr.entry_index = s->hashes[fr.hash_index];
while (fr.entry_index >= 0) {
if (hash_key_equal(s->entries[fr.entry_index].key, key)) {
return fr;
}
fr.entry_prev = fr.entry_index;
fr.entry_index = s->entries[fr.entry_index].next;
}
}
return fr;
}
gb_internal StringSetFindResult string_set__find_from_entry(StringSet *s, StringSetEntry *e) {
StringSetFindResult fr = {-1, -1, -1};
if (s->hashes.count > 0) {
fr.hash_index = e->key.key % s->hashes.count;
fr.entry_index = s->hashes[fr.hash_index];
while (fr.entry_index >= 0) {
if (&s->entries[fr.entry_index] == e) {
return fr;
}
fr.entry_prev = fr.entry_index;
fr.entry_index = s->entries[fr.entry_index].next;
}
}
return fr;
}
gb_internal b32 string_set__full(StringSet *s) {
return 0.75f * s->hashes.count <= s->entries.count;
}
gb_inline void string_set_grow(StringSet *s) {
isize new_count = ARRAY_GROW_FORMULA(s->entries.count);
string_set_rehash(s, new_count);
}
void string_set_rehash(StringSet *s, isize new_count) {
isize i, j;
StringSet ns = {};
string_set_init(&ns, s->hashes.allocator);
array_resize(&ns.hashes, new_count);
array_reserve(&ns.entries, s->entries.count);
for (i = 0; i < new_count; i++) {
ns.hashes[i] = -1;
}
for (i = 0; i < s->entries.count; i++) {
StringSetEntry *e = &s->entries[i];
StringSetFindResult fr;
if (ns.hashes.count == 0) {
string_set_grow(&ns);
}
fr = string_set__find(&ns, e->key);
j = string_set__add_entry(&ns, e->key);
if (fr.entry_prev < 0) {
ns.hashes[fr.hash_index] = j;
} else {
ns.entries[fr.entry_prev].next = j;
}
ns.entries[j].next = fr.entry_index;
ns.entries[j].value = e->value;
if (string_set__full(&ns)) {
string_set_grow(&ns);
}
}
string_set_destroy(s);
*s = ns;
}
gb_inline bool string_set_exists(StringSet *s, String str) {
HashKey key = hash_string(str);
isize index = string_set__find(s, key).entry_index;
return index >= 0;
}
void string_set_add(StringSet *s, String str) {
isize index;
StringSetFindResult fr;
HashKey key = hash_string(str);
if (s->hashes.count == 0) {
string_set_grow(s);
}
fr = string_set__find(s, key);
if (fr.entry_index >= 0) {
index = fr.entry_index;
} else {
index = string_set__add_entry(s, key);
if (fr.entry_prev >= 0) {
s->entries[fr.entry_prev].next = index;
} else {
s->hashes[fr.hash_index] = index;
}
}
s->entries[index].value = str;
if (string_set__full(s)) {
string_set_grow(s);
}
}
void string_set__erase(StringSet *s, StringSetFindResult fr) {
StringSetFindResult last;
if (fr.entry_prev < 0) {
s->hashes[fr.hash_index] = s->entries[fr.entry_index].next;
} else {
s->entries[fr.entry_prev].next = s->entries[fr.entry_index].next;
}
if (fr.entry_index == s->entries.count-1) {
array_pop(&s->entries);
return;
}
s->entries[fr.entry_index] = s->entries[s->entries.count-1];
last = string_set__find(s, s->entries[fr.entry_index].key);
if (last.entry_prev >= 0) {
s->entries[last.entry_prev].next = fr.entry_index;
} else {
s->hashes[last.hash_index] = fr.entry_index;
}
}
void string_set_remove(StringSet *s, String str) {
HashKey key = hash_string(str);
StringSetFindResult fr = string_set__find(s, key);
if (fr.entry_index >= 0) {
string_set__erase(s, fr);
}
}
gb_inline void string_set_clear(StringSet *s) {
array_clear(&s->hashes);
array_clear(&s->entries);
}
|
