BadVPN – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | /** |
2 | * @file CHash_impl.h |
||
3 | * @author Ambroz Bizjak <ambrop7@gmail.com> |
||
4 | * |
||
5 | * @section LICENSE |
||
6 | * |
||
7 | * Redistribution and use in source and binary forms, with or without |
||
8 | * modification, are permitted provided that the following conditions are met: |
||
9 | * 1. Redistributions of source code must retain the above copyright |
||
10 | * notice, this list of conditions and the following disclaimer. |
||
11 | * 2. Redistributions in binary form must reproduce the above copyright |
||
12 | * notice, this list of conditions and the following disclaimer in the |
||
13 | * documentation and/or other materials provided with the distribution. |
||
14 | * 3. Neither the name of the author nor the |
||
15 | * names of its contributors may be used to endorse or promote products |
||
16 | * derived from this software without specific prior written permission. |
||
17 | * |
||
18 | * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND |
||
19 | * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED |
||
20 | * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE |
||
21 | * DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY |
||
22 | * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES |
||
23 | * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
||
24 | * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND |
||
25 | * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
||
26 | * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
||
27 | * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
||
28 | */ |
||
29 | |||
30 | #include "CHash_header.h" |
||
31 | |||
32 | static void CHash_assert_valid_entry (CHashArg arg, CHashRef entry) |
||
33 | { |
||
34 | ASSERT(entry.link != CHashNullLink()) |
||
35 | ASSERT(entry.ptr == CHASH_PARAM_DEREF(arg, entry.link)) |
||
36 | } |
||
37 | |||
38 | static CHashLink CHashNullLink (void) |
||
39 | { |
||
40 | return CHASH_PARAM_NULL; |
||
41 | } |
||
42 | |||
43 | static CHashRef CHashNullRef (void) |
||
44 | { |
||
45 | CHashRef entry = {NULL, CHashNullLink()}; |
||
46 | return entry; |
||
47 | } |
||
48 | |||
49 | static int CHashIsNullLink (CHashLink link) |
||
50 | { |
||
51 | return (link == CHashNullLink()); |
||
52 | } |
||
53 | |||
54 | static int CHashIsNullRef (CHashRef ref) |
||
55 | { |
||
56 | return CHashIsNullLink(ref.link); |
||
57 | } |
||
58 | |||
59 | static CHashRef CHashDerefMayNull (CHashArg arg, CHashLink link) |
||
60 | { |
||
61 | if (link == CHashNullLink()) { |
||
62 | return CHashNullRef(); |
||
63 | } |
||
64 | |||
65 | CHashRef entry = {CHASH_PARAM_DEREF(arg, link), link}; |
||
66 | ASSERT(entry.ptr) |
||
67 | |||
68 | return entry; |
||
69 | } |
||
70 | |||
71 | static CHashRef CHashDerefNonNull (CHashArg arg, CHashLink link) |
||
72 | { |
||
73 | ASSERT(link != CHashNullLink()) |
||
74 | |||
75 | CHashRef entry = {CHASH_PARAM_DEREF(arg, link), link}; |
||
76 | ASSERT(entry.ptr) |
||
77 | |||
78 | return entry; |
||
79 | } |
||
80 | |||
81 | static int CHash_Init (CHash *o, size_t num_buckets) |
||
82 | { |
||
83 | if (num_buckets == 0) { |
||
84 | num_buckets = 1; |
||
85 | } |
||
86 | |||
87 | o->num_buckets = num_buckets; |
||
88 | |||
89 | o->buckets = (CHashLink *)BAllocArray(o->num_buckets, sizeof(o->buckets[0])); |
||
90 | if (!o->buckets) { |
||
91 | return 0; |
||
92 | } |
||
93 | |||
94 | for (size_t i = 0; i < o->num_buckets; i++) { |
||
95 | o->buckets[i] = CHashNullLink(); |
||
96 | } |
||
97 | |||
98 | return 1; |
||
99 | } |
||
100 | |||
101 | static void CHash_Free (CHash *o) |
||
102 | { |
||
103 | BFree(o->buckets); |
||
104 | } |
||
105 | |||
106 | static int CHash_Insert (CHash *o, CHashArg arg, CHashRef entry, CHashRef *out_existing) |
||
107 | { |
||
108 | CHash_assert_valid_entry(arg, entry); |
||
109 | |||
110 | size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets; |
||
111 | |||
112 | CHashLink link = o->buckets[index]; |
||
113 | while (link != CHashNullLink()) { |
||
114 | CHashRef cur = CHashDerefNonNull(arg, link); |
||
115 | if (CHASH_PARAM_COMPARE_ENTRIES(arg, cur, entry)) { |
||
116 | if (out_existing) { |
||
117 | *out_existing = cur; |
||
118 | } |
||
119 | return 0; |
||
120 | } |
||
121 | link = CHash_next(cur); |
||
122 | } |
||
123 | |||
124 | CHash_next(entry) = o->buckets[index]; |
||
125 | o->buckets[index] = entry.link; |
||
126 | |||
127 | return 1; |
||
128 | } |
||
129 | |||
130 | static void CHash_InsertMulti (CHash *o, CHashArg arg, CHashRef entry) |
||
131 | { |
||
132 | CHash_assert_valid_entry(arg, entry); |
||
133 | |||
134 | size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets; |
||
135 | |||
136 | CHashRef prev = CHashNullRef(); |
||
137 | CHashLink link = o->buckets[index]; |
||
138 | while (link != CHashNullLink()) { |
||
139 | CHashRef cur = CHashDerefNonNull(arg, link); |
||
140 | if (CHASH_PARAM_COMPARE_ENTRIES(arg, cur, entry)) { |
||
141 | break; |
||
142 | } |
||
143 | prev = cur; |
||
144 | link = CHash_next(cur); |
||
145 | } |
||
146 | |||
147 | if (link == CHashNullLink() || prev.link == CHashNullLink()) { |
||
148 | CHash_next(entry) = o->buckets[index]; |
||
149 | o->buckets[index] = entry.link; |
||
150 | } else { |
||
151 | CHash_next(entry) = link; |
||
152 | CHash_next(prev) = entry.link; |
||
153 | } |
||
154 | } |
||
155 | |||
156 | static void CHash_Remove (CHash *o, CHashArg arg, CHashRef entry) |
||
157 | { |
||
158 | CHash_assert_valid_entry(arg, entry); |
||
159 | |||
160 | size_t index = CHASH_PARAM_ENTRYHASH(arg, entry) % o->num_buckets; |
||
161 | |||
162 | CHashRef prev = CHashNullRef(); |
||
163 | CHashLink link = o->buckets[index]; |
||
164 | while (link != entry.link) { |
||
165 | CHashRef cur = CHashDerefNonNull(arg, link); |
||
166 | prev = cur; |
||
167 | link = CHash_next(cur); |
||
168 | ASSERT(link != CHashNullLink()) |
||
169 | } |
||
170 | |||
171 | if (prev.link == CHashNullLink()) { |
||
172 | o->buckets[index] = CHash_next(entry); |
||
173 | } else { |
||
174 | CHash_next(prev) = CHash_next(entry); |
||
175 | } |
||
176 | } |
||
177 | |||
178 | static CHashRef CHash_Lookup (const CHash *o, CHashArg arg, CHashKey key) |
||
179 | { |
||
180 | size_t hash = CHASH_PARAM_KEYHASH(arg, key); |
||
181 | size_t index = hash % o->num_buckets; |
||
182 | |||
183 | CHashLink link = o->buckets[index]; |
||
184 | while (link != CHashNullLink()) { |
||
185 | CHashRef cur = CHashDerefNonNull(arg, link); |
||
186 | #if CHASH_PARAM_ENTRYHASH_IS_CHEAP |
||
187 | if (CHASH_PARAM_ENTRYHASH(arg, cur) == hash && CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) { |
||
188 | #else |
||
189 | if (CHASH_PARAM_COMPARE_KEY_ENTRY(arg, key, cur)) { |
||
190 | #endif |
||
191 | return cur; |
||
192 | } |
||
193 | link = CHash_next(cur); |
||
194 | } |
||
195 | |||
196 | return CHashNullRef(); |
||
197 | } |
||
198 | |||
199 | static CHashRef CHash_GetNextEqual (const CHash *o, CHashArg arg, CHashRef entry) |
||
200 | { |
||
201 | CHash_assert_valid_entry(arg, entry); |
||
202 | |||
203 | CHashLink next = CHash_next(entry); |
||
204 | |||
205 | if (next == CHashNullLink()) { |
||
206 | return CHashNullRef(); |
||
207 | } |
||
208 | |||
209 | CHashRef next_ref = CHashDerefNonNull(arg, next); |
||
210 | if (!CHASH_PARAM_COMPARE_ENTRIES(arg, next_ref, entry)) { |
||
211 | return CHashNullRef(); |
||
212 | } |
||
213 | |||
214 | return next_ref; |
||
215 | } |
||
216 | |||
217 | static int CHash_MultiplyBuckets (CHash *o, CHashArg arg, int exp) |
||
218 | { |
||
219 | ASSERT(exp > 0) |
||
220 | |||
221 | size_t new_num_buckets = o->num_buckets; |
||
222 | while (exp-- > 0) { |
||
223 | if (new_num_buckets > SIZE_MAX / 2) { |
||
224 | return 0; |
||
225 | } |
||
226 | new_num_buckets *= 2; |
||
227 | } |
||
228 | |||
229 | CHashLink *new_buckets = (CHashLink *)BReallocArray(o->buckets, new_num_buckets, sizeof(new_buckets[0])); |
||
230 | if (!new_buckets) { |
||
231 | return 0; |
||
232 | } |
||
233 | o->buckets = new_buckets; |
||
234 | |||
235 | for (size_t i = o->num_buckets; i < new_num_buckets; i++) { |
||
236 | o->buckets[i] = CHashNullLink(); |
||
237 | } |
||
238 | |||
239 | for (size_t i = 0; i < o->num_buckets; i++) { |
||
240 | CHashRef prev = CHashNullRef(); |
||
241 | CHashLink link = o->buckets[i]; |
||
242 | |||
243 | while (link != CHashNullLink()) { |
||
244 | CHashRef cur = CHashDerefNonNull(arg, link); |
||
245 | link = CHash_next(cur); |
||
246 | |||
247 | size_t new_index = CHASH_PARAM_ENTRYHASH(arg, cur) % new_num_buckets; |
||
248 | if (new_index == i) { |
||
249 | prev = cur; |
||
250 | continue; |
||
251 | } |
||
252 | |||
253 | if (CHashIsNullRef(prev)) { |
||
254 | o->buckets[i] = CHash_next(cur); |
||
255 | } else { |
||
256 | CHash_next(prev) = CHash_next(cur); |
||
257 | } |
||
258 | |||
259 | CHash_next(cur) = o->buckets[new_index]; |
||
260 | o->buckets[new_index] = cur.link; |
||
261 | } |
||
262 | } |
||
263 | |||
264 | for (size_t i = o->num_buckets; i < new_num_buckets; i++) { |
||
265 | CHashLink new_bucket_link = CHashNullLink(); |
||
266 | |||
267 | CHashLink link = o->buckets[i]; |
||
268 | while (link != CHashNullLink()) { |
||
269 | CHashRef cur = CHashDerefNonNull(arg, link); |
||
270 | link = CHash_next(cur); |
||
271 | |||
272 | CHash_next(cur) = new_bucket_link; |
||
273 | new_bucket_link = cur.link; |
||
274 | } |
||
275 | |||
276 | o->buckets[i] = new_bucket_link; |
||
277 | } |
||
278 | |||
279 | o->num_buckets = new_num_buckets; |
||
280 | |||
281 | return 1; |
||
282 | } |
||
283 | |||
284 | static void CHash_Verify (const CHash *o, CHashArg arg) |
||
285 | { |
||
286 | ASSERT_FORCE(o->num_buckets > 0) |
||
287 | ASSERT_FORCE(o->buckets) |
||
288 | |||
289 | for (size_t i = 0; i < o->num_buckets; i++) { |
||
290 | CHashRef cur = CHashDerefMayNull(arg, o->buckets[i]); |
||
291 | CHashRef same_first = cur; |
||
292 | |||
293 | while (!CHashIsNullRef(cur)) { |
||
294 | size_t index = CHASH_PARAM_ENTRYHASH(arg, cur) % o->num_buckets; |
||
295 | ASSERT_FORCE(index == i) |
||
296 | |||
297 | if (!CHASH_PARAM_COMPARE_ENTRIES(arg, cur, same_first)) { |
||
298 | same_first = cur; |
||
299 | } |
||
300 | |||
301 | CHashRef ccur = CHashDerefNonNull(arg, o->buckets[i]); |
||
302 | while (ccur.link != same_first.link) { |
||
303 | ASSERT_FORCE(!CHASH_PARAM_COMPARE_ENTRIES(arg, ccur, cur)) |
||
304 | ccur = CHashDerefMayNull(arg, CHash_next(ccur)); |
||
305 | } |
||
306 | |||
307 | cur = CHashDerefMayNull(arg, CHash_next(cur)); |
||
308 | } |
||
309 | } |
||
310 | } |
||
311 | |||
312 | #include "CHash_footer.h" |