]>
Commit | Line | Data |
---|---|---|
abd71baa DL |
1 | /* |
2 | * Copyright (c) 2019 David Lamparter, for NetDEF, Inc. | |
3 | * | |
4 | * Permission to use, copy, modify, and distribute this software for any | |
5 | * purpose with or without fee is hereby granted, provided that the above | |
6 | * copyright notice and this permission notice appear in all copies. | |
7 | * | |
8 | * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES | |
9 | * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF | |
10 | * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR | |
11 | * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES | |
12 | * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN | |
13 | * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF | |
14 | * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. | |
15 | */ | |
16 | ||
2618a52e DL |
17 | #ifdef HAVE_CONFIG_H |
18 | #include "config.h" | |
19 | #endif | |
20 | ||
abd71baa DL |
21 | #include <stdlib.h> |
22 | #include <string.h> | |
23 | ||
24 | #include "typesafe.h" | |
25 | #include "memory.h" | |
26 | ||
27 | DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket") | |
28 | DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow") | |
5cb4277d | 29 | DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array") |
abd71baa DL |
30 | |
31 | #if 0 | |
32 | static void hash_consistency_check(struct thash_head *head) | |
33 | { | |
34 | uint32_t i; | |
35 | struct thash_item *item, *prev; | |
36 | ||
37 | for (i = 0; i < HASH_SIZE(*head); i++) { | |
38 | item = head->entries[i]; | |
39 | prev = NULL; | |
40 | while (item) { | |
41 | assert(HASH_KEY(*head, item->hashval) == i); | |
42 | assert(!prev || item->hashval >= prev->hashval); | |
43 | prev = item; | |
44 | item = item->next; | |
45 | } | |
46 | } | |
47 | } | |
48 | #else | |
49 | #define hash_consistency_check(x) | |
50 | #endif | |
51 | ||
52 | void typesafe_hash_grow(struct thash_head *head) | |
53 | { | |
54 | uint32_t newsize = head->count, i, j; | |
55 | uint8_t newshift, delta; | |
56 | ||
57 | hash_consistency_check(head); | |
58 | ||
59 | newsize |= newsize >> 1; | |
60 | newsize |= newsize >> 2; | |
61 | newsize |= newsize >> 4; | |
62 | newsize |= newsize >> 8; | |
63 | newsize |= newsize >> 16; | |
64 | newsize++; | |
65 | newshift = __builtin_ctz(newsize) + 1; | |
66 | ||
67 | if (head->maxshift && newshift > head->maxshift) | |
68 | newshift = head->maxshift; | |
69 | if (newshift == head->tabshift) | |
70 | return; | |
71 | newsize = _HASH_SIZE(newshift); | |
72 | ||
73 | head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries, | |
74 | sizeof(head->entries[0]) * newsize); | |
75 | memset(head->entries + HASH_SIZE(*head), 0, | |
76 | sizeof(head->entries[0]) * | |
77 | (newsize - HASH_SIZE(*head))); | |
78 | ||
79 | delta = newshift - head->tabshift; | |
80 | ||
81 | i = HASH_SIZE(*head); | |
82 | if (i == 0) | |
83 | goto out; | |
84 | do { | |
85 | struct thash_item **apos, *item; | |
86 | ||
87 | i--; | |
88 | apos = &head->entries[i]; | |
89 | ||
90 | for (j = 0; j < (1U << delta); j++) { | |
91 | item = *apos; | |
92 | *apos = NULL; | |
93 | ||
94 | head->entries[(i << delta) + j] = item; | |
95 | apos = &head->entries[(i << delta) + j]; | |
96 | ||
97 | while ((item = *apos)) { | |
98 | uint32_t midbits; | |
99 | midbits = _HASH_KEY(newshift, item->hashval); | |
100 | midbits &= (1 << delta) - 1; | |
101 | if (midbits > j) | |
102 | break; | |
103 | apos = &item->next; | |
104 | } | |
105 | } | |
106 | } while (i > 0); | |
107 | ||
108 | out: | |
109 | head->tabshift = newshift; | |
110 | hash_consistency_check(head); | |
111 | } | |
112 | ||
113 | void typesafe_hash_shrink(struct thash_head *head) | |
114 | { | |
115 | uint32_t newsize = head->count, i, j; | |
116 | uint8_t newshift, delta; | |
117 | ||
118 | hash_consistency_check(head); | |
119 | ||
120 | if (!head->count) { | |
121 | XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries); | |
122 | head->tabshift = 0; | |
123 | return; | |
124 | } | |
125 | ||
126 | newsize |= newsize >> 1; | |
127 | newsize |= newsize >> 2; | |
128 | newsize |= newsize >> 4; | |
129 | newsize |= newsize >> 8; | |
130 | newsize |= newsize >> 16; | |
131 | newsize++; | |
132 | newshift = __builtin_ctz(newsize) + 1; | |
133 | ||
134 | if (head->minshift && newshift < head->minshift) | |
135 | newshift = head->minshift; | |
136 | if (newshift == head->tabshift) | |
137 | return; | |
138 | newsize = _HASH_SIZE(newshift); | |
139 | ||
140 | delta = head->tabshift - newshift; | |
141 | ||
142 | for (i = 0; i < newsize; i++) { | |
143 | struct thash_item **apos = &head->entries[i]; | |
144 | ||
145 | for (j = 0; j < (1U << delta); j++) { | |
146 | *apos = head->entries[(i << delta) + j]; | |
147 | while (*apos) | |
148 | apos = &(*apos)->next; | |
149 | } | |
150 | } | |
151 | head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries, | |
152 | sizeof(head->entries[0]) * newsize); | |
153 | head->tabshift = newshift; | |
154 | ||
155 | hash_consistency_check(head); | |
156 | } | |
157 | ||
158 | /* skiplist */ | |
159 | ||
160 | static inline struct sskip_item *sl_level_get(struct sskip_item *item, | |
161 | size_t level) | |
162 | { | |
163 | if (level < SKIPLIST_OVERFLOW) | |
164 | return item->next[level]; | |
165 | if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1)) | |
166 | return item->next[level]; | |
167 | ||
168 | uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; | |
169 | ptrval &= UINTPTR_MAX - 3; | |
170 | struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; | |
171 | return oflow->next[level - SKIPLIST_OVERFLOW]; | |
172 | } | |
173 | ||
174 | static inline void sl_level_set(struct sskip_item *item, size_t level, | |
175 | struct sskip_item *value) | |
176 | { | |
177 | if (level < SKIPLIST_OVERFLOW) | |
178 | item->next[level] = value; | |
179 | else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1)) | |
180 | item->next[level] = value; | |
181 | else { | |
182 | uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; | |
183 | ptrval &= UINTPTR_MAX - 3; | |
184 | struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; | |
185 | oflow->next[level - SKIPLIST_OVERFLOW] = value; | |
186 | } | |
187 | } | |
188 | ||
189 | struct sskip_item *typesafe_skiplist_add(struct sskip_head *head, | |
190 | struct sskip_item *item, | |
191 | int (*cmpfn)(const struct sskip_item *a, | |
192 | const struct sskip_item *b)) | |
193 | { | |
194 | size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel; | |
195 | struct sskip_item *prev = &head->hitem, *next, *auxprev, *auxnext; | |
196 | int cmpval; | |
197 | ||
198 | /* level / newlevel are 1-counted here */ | |
199 | newlevel = __builtin_ctz(random()) + 1; | |
200 | if (newlevel > SKIPLIST_MAXDEPTH) | |
201 | newlevel = SKIPLIST_MAXDEPTH; | |
202 | ||
203 | next = NULL; | |
204 | while (level >= newlevel) { | |
205 | next = sl_level_get(prev, level - 1); | |
206 | if (!next) { | |
207 | level--; | |
208 | continue; | |
209 | } | |
210 | cmpval = cmpfn(next, item); | |
211 | if (cmpval < 0) { | |
212 | prev = next; | |
213 | continue; | |
214 | } else if (cmpval == 0) { | |
215 | return next; | |
216 | } | |
217 | level--; | |
218 | } | |
219 | ||
220 | /* check for duplicate item - could be removed if code doesn't rely | |
221 | * on it, but not really work the complication. */ | |
222 | auxlevel = level; | |
223 | auxprev = prev; | |
224 | while (auxlevel) { | |
225 | auxlevel--; | |
226 | auxnext = sl_level_get(auxprev, auxlevel); | |
227 | cmpval = 1; | |
228 | while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) { | |
229 | auxprev = auxnext; | |
230 | auxnext = sl_level_get(auxprev, auxlevel); | |
231 | } | |
232 | if (cmpval == 0) | |
233 | return auxnext; | |
234 | }; | |
235 | ||
236 | head->count++; | |
237 | memset(item, 0, sizeof(*item)); | |
238 | if (newlevel > SKIPLIST_EMBED) { | |
239 | struct sskip_overflow *oflow; | |
240 | oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *) | |
241 | * (newlevel - SKIPLIST_OVERFLOW)); | |
242 | item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *) | |
243 | ((uintptr_t)oflow | 1); | |
244 | } | |
245 | ||
246 | sl_level_set(item, level, next); | |
247 | sl_level_set(prev, level, item); | |
248 | /* level is now 0-counted and < newlevel*/ | |
249 | while (level) { | |
250 | level--; | |
251 | next = sl_level_get(prev, level); | |
252 | while (next && cmpfn(next, item) < 0) { | |
253 | prev = next; | |
254 | next = sl_level_get(prev, level); | |
255 | } | |
256 | ||
257 | sl_level_set(item, level, next); | |
258 | sl_level_set(prev, level, item); | |
259 | }; | |
260 | return NULL; | |
261 | } | |
262 | ||
263 | /* NOTE: level counting below is 1-based since that makes the code simpler! */ | |
264 | ||
265 | struct sskip_item *typesafe_skiplist_find(struct sskip_head *head, | |
266 | const struct sskip_item *item, int (*cmpfn)( | |
267 | const struct sskip_item *a, | |
268 | const struct sskip_item *b)) | |
269 | { | |
270 | size_t level = SKIPLIST_MAXDEPTH; | |
271 | struct sskip_item *prev = &head->hitem, *next; | |
272 | int cmpval; | |
273 | ||
274 | while (level) { | |
275 | next = sl_level_get(prev, level - 1); | |
276 | if (!next) { | |
277 | level--; | |
278 | continue; | |
279 | } | |
280 | cmpval = cmpfn(next, item); | |
281 | if (cmpval < 0) { | |
282 | prev = next; | |
283 | continue; | |
284 | } | |
285 | if (cmpval == 0) | |
286 | return next; | |
287 | level--; | |
288 | } | |
289 | return NULL; | |
290 | } | |
291 | ||
292 | struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head, | |
293 | const struct sskip_item *item, int (*cmpfn)( | |
294 | const struct sskip_item *a, | |
295 | const struct sskip_item *b)) | |
296 | { | |
297 | size_t level = SKIPLIST_MAXDEPTH; | |
298 | struct sskip_item *prev = &head->hitem, *next; | |
299 | int cmpval; | |
300 | ||
301 | while (level) { | |
302 | next = sl_level_get(prev, level - 1); | |
303 | if (!next) { | |
304 | level--; | |
305 | continue; | |
306 | } | |
307 | cmpval = cmpfn(next, item); | |
308 | if (cmpval < 0) { | |
309 | prev = next; | |
310 | continue; | |
311 | } | |
312 | if (cmpval == 0) | |
313 | return next; | |
314 | level--; | |
315 | } | |
316 | return next; | |
317 | } | |
318 | ||
319 | struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head, | |
320 | const struct sskip_item *item, int (*cmpfn)( | |
321 | const struct sskip_item *a, | |
322 | const struct sskip_item *b)) | |
323 | { | |
324 | size_t level = SKIPLIST_MAXDEPTH; | |
325 | struct sskip_item *prev = &head->hitem, *next, *best = NULL; | |
326 | int cmpval; | |
327 | ||
328 | while (level) { | |
329 | next = sl_level_get(prev, level - 1); | |
330 | if (!next) { | |
331 | level--; | |
332 | continue; | |
333 | } | |
334 | cmpval = cmpfn(next, item); | |
335 | if (cmpval < 0) { | |
336 | best = prev = next; | |
337 | continue; | |
338 | } | |
339 | level--; | |
340 | } | |
341 | return best; | |
342 | } | |
343 | ||
da098d78 SW |
344 | struct sskip_item *typesafe_skiplist_del( |
345 | struct sskip_head *head, struct sskip_item *item, | |
346 | int (*cmpfn)(const struct sskip_item *a, const struct sskip_item *b)) | |
abd71baa DL |
347 | { |
348 | size_t level = SKIPLIST_MAXDEPTH; | |
349 | struct sskip_item *prev = &head->hitem, *next; | |
350 | int cmpval; | |
da098d78 | 351 | bool found = false; |
abd71baa DL |
352 | |
353 | while (level) { | |
354 | next = sl_level_get(prev, level - 1); | |
355 | if (!next) { | |
356 | level--; | |
357 | continue; | |
358 | } | |
359 | if (next == item) { | |
360 | sl_level_set(prev, level - 1, | |
361 | sl_level_get(item, level - 1)); | |
362 | level--; | |
da098d78 | 363 | found = true; |
abd71baa DL |
364 | continue; |
365 | } | |
366 | cmpval = cmpfn(next, item); | |
367 | if (cmpval < 0) { | |
368 | prev = next; | |
369 | continue; | |
370 | } | |
371 | level--; | |
372 | } | |
373 | ||
da098d78 SW |
374 | if (!found) |
375 | return NULL; | |
376 | ||
abd71baa DL |
377 | /* TBD: assert when trying to remove non-existing item? */ |
378 | head->count--; | |
379 | ||
380 | if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) { | |
381 | uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; | |
382 | ptrval &= UINTPTR_MAX - 3; | |
383 | struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; | |
384 | XFREE(MTYPE_SKIPLIST_OFLOW, oflow); | |
385 | } | |
386 | memset(item, 0, sizeof(*item)); | |
da098d78 SW |
387 | |
388 | return item; | |
abd71baa | 389 | } |
01734da3 DL |
390 | |
391 | struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head) | |
392 | { | |
393 | size_t level = SKIPLIST_MAXDEPTH; | |
394 | struct sskip_item *prev = &head->hitem, *next, *item; | |
395 | ||
396 | item = sl_level_get(prev, 0); | |
397 | if (!item) | |
398 | return NULL; | |
399 | ||
400 | do { | |
401 | level--; | |
402 | ||
403 | next = sl_level_get(prev, level); | |
404 | if (next != item) | |
405 | continue; | |
406 | ||
407 | sl_level_set(prev, level, sl_level_get(item, level)); | |
408 | } while (level); | |
409 | ||
410 | head->count--; | |
411 | ||
412 | if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) { | |
413 | uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW]; | |
414 | ptrval &= UINTPTR_MAX - 3; | |
415 | struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval; | |
416 | XFREE(MTYPE_SKIPLIST_OFLOW, oflow); | |
417 | } | |
418 | memset(item, 0, sizeof(*item)); | |
419 | ||
420 | return item; | |
421 | } | |
5cb4277d DL |
422 | |
423 | /* heap */ | |
424 | ||
425 | #if 0 | |
426 | static void heap_consistency_check(struct heap_head *head, | |
427 | int (*cmpfn)(const struct heap_item *a, | |
428 | const struct heap_item *b), | |
429 | uint32_t pos) | |
430 | { | |
431 | uint32_t rghtpos = pos + 1; | |
432 | uint32_t downpos = HEAP_NARY * (pos + 1); | |
433 | ||
434 | if (pos + 1 > ~0U / HEAP_NARY) | |
435 | downpos = ~0U; | |
436 | ||
437 | if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) { | |
438 | assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0); | |
439 | heap_consistency_check(head, cmpfn, rghtpos); | |
440 | } | |
441 | if (downpos < head->count) { | |
442 | assert(cmpfn(head->array[downpos], head->array[pos]) >= 0); | |
443 | heap_consistency_check(head, cmpfn, downpos); | |
444 | } | |
445 | } | |
446 | #else | |
447 | #define heap_consistency_check(head, cmpfn, pos) | |
448 | #endif | |
449 | ||
450 | void typesafe_heap_resize(struct heap_head *head, bool grow) | |
451 | { | |
452 | uint32_t newsize; | |
453 | ||
454 | if (grow) { | |
455 | newsize = head->arraysz; | |
456 | if (newsize <= 36) | |
457 | newsize = 72; | |
458 | else if (newsize < 262144) | |
459 | newsize += newsize / 2; | |
460 | else if (newsize < 0xaaaa0000) | |
461 | newsize += newsize / 3; | |
462 | else | |
463 | assert(!newsize); | |
464 | } else if (head->count > 0) { | |
465 | newsize = head->count; | |
466 | } else { | |
467 | XFREE(MTYPE_HEAP_ARRAY, head->array); | |
468 | head->arraysz = 0; | |
469 | return; | |
470 | } | |
471 | ||
472 | newsize += HEAP_NARY - 1; | |
473 | newsize &= ~(HEAP_NARY - 1); | |
474 | if (newsize == head->arraysz) | |
475 | return; | |
c258527b | 476 | |
5cb4277d DL |
477 | head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array, |
478 | newsize * sizeof(struct heap_item *)); | |
479 | head->arraysz = newsize; | |
480 | } | |
481 | ||
482 | void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos, | |
483 | struct heap_item *item, | |
484 | int (*cmpfn)(const struct heap_item *a, | |
485 | const struct heap_item *b)) | |
486 | { | |
487 | uint32_t rghtpos, downpos, moveto; | |
488 | ||
489 | while (1) { | |
490 | /* rghtpos: neighbor to the "right", inside block of NARY. | |
491 | * may be invalid if last in block, check nary_last() | |
492 | * downpos: first neighbor in the "downwards" block further | |
493 | * away from the root | |
494 | */ | |
495 | rghtpos = pos + 1; | |
496 | ||
497 | /* make sure we can use the full 4G items */ | |
498 | downpos = HEAP_NARY * (pos + 1); | |
499 | if (pos + 1 > ~0U / HEAP_NARY) | |
500 | /* multiplication overflowed. ~0U is guaranteed | |
501 | * to be an invalid index; size limit is enforced in | |
502 | * resize() | |
503 | */ | |
504 | downpos = ~0U; | |
505 | ||
506 | /* only used on break */ | |
507 | moveto = pos; | |
508 | ||
509 | #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1) | |
510 | if (downpos >= head->count | |
511 | || cmpfn(head->array[downpos], item) >= 0) { | |
512 | /* not moving down; either at end or down is >= item */ | |
513 | if (nary_last(pos) || rghtpos >= head->count | |
514 | || cmpfn(head->array[rghtpos], item) >= 0) | |
515 | /* not moving right either - got our spot */ | |
516 | break; | |
517 | ||
518 | moveto = rghtpos; | |
519 | ||
520 | /* else: downpos is valid and < item. choose between down | |
521 | * or right (if the latter is an option) */ | |
522 | } else if (nary_last(pos) || cmpfn(head->array[rghtpos], | |
523 | head->array[downpos]) >= 0) | |
524 | moveto = downpos; | |
525 | else | |
526 | moveto = rghtpos; | |
527 | #undef nary_last | |
528 | ||
529 | head->array[pos] = head->array[moveto]; | |
530 | head->array[pos]->index = pos; | |
531 | pos = moveto; | |
532 | } | |
533 | ||
534 | head->array[moveto] = item; | |
535 | item->index = moveto; | |
536 | ||
537 | heap_consistency_check(head, cmpfn, 0); | |
538 | } | |
539 | ||
540 | void typesafe_heap_pullup(struct heap_head *head, uint32_t pos, | |
541 | struct heap_item *item, | |
542 | int (*cmpfn)(const struct heap_item *a, | |
543 | const struct heap_item *b)) | |
544 | { | |
545 | uint32_t moveto; | |
546 | ||
547 | while (pos != 0) { | |
548 | if ((pos & (HEAP_NARY - 1)) == 0) | |
549 | moveto = pos / HEAP_NARY - 1; | |
550 | else | |
551 | moveto = pos - 1; | |
552 | ||
553 | if (cmpfn(head->array[moveto], item) <= 0) | |
554 | break; | |
555 | ||
556 | head->array[pos] = head->array[moveto]; | |
557 | head->array[pos]->index = pos; | |
558 | ||
559 | pos = moveto; | |
560 | } | |
561 | ||
562 | head->array[pos] = item; | |
563 | item->index = pos; | |
564 | ||
565 | heap_consistency_check(head, cmpfn, 0); | |
566 | } |