Line data Source code
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 :
17 : #ifdef HAVE_CONFIG_H
18 : #include "config.h"
19 : #endif
20 :
21 : #include <stdlib.h>
22 : #include <string.h>
23 : #include <assert.h>
24 :
25 : #include "typesafe.h"
26 : #include "memory.h"
27 : #include "network.h"
28 :
29 670 : DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket");
30 670 : DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow");
31 670 : DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array");
32 :
33 : struct slist_item typesafe_slist_sentinel = { NULL };
34 :
35 0 : bool typesafe_list_member(const struct slist_head *head,
36 : const struct slist_item *item)
37 : {
38 0 : struct slist_item *fromhead = head->first;
39 0 : struct slist_item **fromnext = (struct slist_item **)&item->next;
40 :
41 0 : while (fromhead != _SLIST_LAST) {
42 0 : if (fromhead == item || fromnext == head->last_next)
43 : return true;
44 :
45 0 : fromhead = fromhead->next;
46 0 : if (!*fromnext || *fromnext == _SLIST_LAST)
47 : break;
48 0 : fromnext = &(*fromnext)->next;
49 : }
50 :
51 : return false;
52 : }
53 :
54 0 : bool typesafe_dlist_member(const struct dlist_head *head,
55 : const struct dlist_item *item)
56 : {
57 0 : const struct dlist_item *fromhead = head->hitem.next;
58 0 : const struct dlist_item *fromitem = item->next;
59 :
60 0 : if (!item->prev || !item->next)
61 : return false;
62 :
63 0 : while (fromhead != &head->hitem && fromitem != item) {
64 0 : if (fromitem == &head->hitem || fromhead == item)
65 : return true;
66 0 : fromhead = fromhead->next;
67 0 : fromitem = fromitem->next;
68 : }
69 :
70 : return false;
71 : }
72 :
73 : #if 0
74 : static void hash_consistency_check(struct thash_head *head)
75 : {
76 : uint32_t i;
77 : struct thash_item *item, *prev;
78 :
79 : for (i = 0; i < HASH_SIZE(*head); i++) {
80 : item = head->entries[i];
81 : prev = NULL;
82 : while (item) {
83 : assert(HASH_KEY(*head, item->hashval) == i);
84 : assert(!prev || item->hashval >= prev->hashval);
85 : prev = item;
86 : item = item->next;
87 : }
88 : }
89 : }
90 : #else
91 : #define hash_consistency_check(x)
92 : #endif
93 :
94 6919 : void typesafe_hash_grow(struct thash_head *head)
95 : {
96 6919 : uint32_t newsize = head->count, i, j;
97 6919 : uint8_t newshift, delta;
98 :
99 6919 : hash_consistency_check(head);
100 :
101 6919 : newsize |= newsize >> 1;
102 6919 : newsize |= newsize >> 2;
103 6919 : newsize |= newsize >> 4;
104 6919 : newsize |= newsize >> 8;
105 6919 : newsize |= newsize >> 16;
106 6919 : newsize++;
107 6919 : newshift = __builtin_ctz(newsize) + 1;
108 :
109 6919 : if (head->maxshift && newshift > head->maxshift)
110 6919 : newshift = head->maxshift;
111 6919 : if (newshift == head->tabshift)
112 : return;
113 6919 : newsize = _HASH_SIZE(newshift);
114 :
115 6919 : head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
116 : sizeof(head->entries[0]) * newsize);
117 6919 : memset(head->entries + HASH_SIZE(*head), 0,
118 : sizeof(head->entries[0]) *
119 6919 : (newsize - HASH_SIZE(*head)));
120 :
121 6919 : delta = newshift - head->tabshift;
122 :
123 6919 : i = HASH_SIZE(*head);
124 6919 : if (i == 0)
125 2784 : goto out;
126 20046 : do {
127 20046 : struct thash_item **apos, *item;
128 :
129 20046 : i--;
130 20046 : apos = &head->entries[i];
131 :
132 60138 : for (j = 0; j < (1U << delta); j++) {
133 40092 : item = *apos;
134 40092 : *apos = NULL;
135 :
136 40092 : head->entries[(i << delta) + j] = item;
137 40092 : apos = &head->entries[(i << delta) + j];
138 :
139 56003 : while ((item = *apos)) {
140 22914 : uint32_t midbits;
141 22914 : midbits = _HASH_KEY(newshift, item->hashval);
142 22914 : midbits &= (1 << delta) - 1;
143 22914 : if (midbits > j)
144 : break;
145 15911 : apos = &item->next;
146 : }
147 : }
148 20046 : } while (i > 0);
149 :
150 4135 : out:
151 6919 : head->tabshift = newshift;
152 6919 : hash_consistency_check(head);
153 : }
154 :
155 14372 : void typesafe_hash_shrink(struct thash_head *head)
156 : {
157 14372 : uint32_t newsize = head->count, i, j;
158 14372 : uint8_t newshift, delta;
159 :
160 14372 : hash_consistency_check(head);
161 :
162 14372 : if (!head->count) {
163 10340 : XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries);
164 10340 : head->tabshift = 0;
165 10340 : return;
166 : }
167 :
168 4032 : newsize |= newsize >> 1;
169 4032 : newsize |= newsize >> 2;
170 4032 : newsize |= newsize >> 4;
171 4032 : newsize |= newsize >> 8;
172 4032 : newsize |= newsize >> 16;
173 4032 : newsize++;
174 4032 : newshift = __builtin_ctz(newsize) + 1;
175 :
176 4032 : if (head->minshift && newshift < head->minshift)
177 4032 : newshift = head->minshift;
178 4032 : if (newshift == head->tabshift)
179 : return;
180 4032 : newsize = _HASH_SIZE(newshift);
181 :
182 4032 : delta = head->tabshift - newshift;
183 :
184 23792 : for (i = 0; i < newsize; i++) {
185 19760 : struct thash_item **apos = &head->entries[i];
186 :
187 59280 : for (j = 0; j < (1U << delta); j++) {
188 39520 : *apos = head->entries[(i << delta) + j];
189 55248 : while (*apos)
190 15728 : apos = &(*apos)->next;
191 : }
192 : }
193 4032 : head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
194 : sizeof(head->entries[0]) * newsize);
195 4032 : head->tabshift = newshift;
196 :
197 14372 : hash_consistency_check(head);
198 : }
199 :
200 : /* skiplist */
201 :
202 29406 : static inline struct sskip_item *sl_level_get(const struct sskip_item *item,
203 : size_t level)
204 : {
205 28387 : if (level < SKIPLIST_OVERFLOW)
206 7355 : return item->next[level];
207 21032 : if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
208 : return item->next[level];
209 :
210 20958 : uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
211 20958 : ptrval &= UINTPTR_MAX - 3;
212 20958 : struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
213 20958 : return oflow->next[level - SKIPLIST_OVERFLOW];
214 : }
215 :
216 4713 : static inline void sl_level_set(struct sskip_item *item, size_t level,
217 : struct sskip_item *value)
218 : {
219 4713 : if (level < SKIPLIST_OVERFLOW)
220 4155 : item->next[level] = value;
221 558 : else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
222 37 : item->next[level] = value;
223 : else {
224 521 : uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
225 521 : ptrval &= UINTPTR_MAX - 3;
226 521 : struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
227 521 : oflow->next[level - SKIPLIST_OVERFLOW] = value;
228 : }
229 4713 : }
230 :
231 795 : struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
232 : struct sskip_item *item,
233 : int (*cmpfn)(const struct sskip_item *a,
234 : const struct sskip_item *b))
235 : {
236 795 : size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel;
237 795 : struct sskip_item *prev = &head->hitem, *next, *auxprev, *auxnext;
238 795 : int cmpval;
239 :
240 : /* level / newlevel are 1-counted here */
241 795 : newlevel = __builtin_ctz(frr_weak_random()) + 1;
242 795 : if (newlevel > SKIPLIST_MAXDEPTH)
243 0 : newlevel = SKIPLIST_MAXDEPTH;
244 :
245 795 : next = NULL;
246 13075 : while (level >= newlevel) {
247 12280 : next = sl_level_get(prev, level - 1);
248 12280 : if (!next) {
249 11615 : level--;
250 11615 : continue;
251 : }
252 665 : cmpval = cmpfn(next, item);
253 665 : if (cmpval < 0) {
254 336 : prev = next;
255 336 : continue;
256 329 : } else if (cmpval == 0) {
257 0 : return next;
258 : }
259 : level--;
260 : }
261 :
262 : /* check for duplicate item - could be removed if code doesn't rely
263 : * on it, but not really work the complication. */
264 : auxlevel = level;
265 : auxprev = prev;
266 1571 : while (auxlevel) {
267 776 : auxlevel--;
268 776 : auxnext = sl_level_get(auxprev, auxlevel);
269 776 : cmpval = 1;
270 908 : while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) {
271 132 : auxprev = auxnext;
272 132 : auxnext = sl_level_get(auxprev, auxlevel);
273 : }
274 776 : if (cmpval == 0)
275 0 : return auxnext;
276 795 : };
277 :
278 795 : head->count++;
279 795 : memset(item, 0, sizeof(*item));
280 795 : if (newlevel > SKIPLIST_EMBED) {
281 45 : struct sskip_overflow *oflow;
282 45 : oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *)
283 : * (newlevel - SKIPLIST_OVERFLOW));
284 45 : item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *)
285 45 : ((uintptr_t)oflow | 1);
286 : }
287 :
288 795 : sl_level_set(item, level, next);
289 795 : sl_level_set(prev, level, item);
290 : /* level is now 0-counted and < newlevel*/
291 1571 : while (level) {
292 776 : level--;
293 776 : next = sl_level_get(prev, level);
294 908 : while (next && cmpfn(next, item) < 0) {
295 132 : prev = next;
296 132 : next = sl_level_get(prev, level);
297 : }
298 :
299 776 : sl_level_set(item, level, next);
300 776 : sl_level_set(prev, level, item);
301 : };
302 : return NULL;
303 : }
304 :
305 : /* NOTE: level counting below is 1-based since that makes the code simpler! */
306 :
307 0 : const struct sskip_item *typesafe_skiplist_find(
308 : const struct sskip_head *head,
309 : const struct sskip_item *item, int (*cmpfn)(
310 : const struct sskip_item *a,
311 : const struct sskip_item *b))
312 : {
313 0 : size_t level = SKIPLIST_MAXDEPTH;
314 0 : const struct sskip_item *prev = &head->hitem, *next;
315 0 : int cmpval;
316 :
317 0 : while (level) {
318 0 : next = sl_level_get(prev, level - 1);
319 0 : if (!next) {
320 0 : level--;
321 0 : continue;
322 : }
323 0 : cmpval = cmpfn(next, item);
324 0 : if (cmpval < 0) {
325 0 : prev = next;
326 0 : continue;
327 : }
328 0 : if (cmpval == 0)
329 0 : return next;
330 : level--;
331 : }
332 : return NULL;
333 : }
334 :
335 0 : const struct sskip_item *typesafe_skiplist_find_gteq(
336 : const struct sskip_head *head,
337 : const struct sskip_item *item, int (*cmpfn)(
338 : const struct sskip_item *a,
339 : const struct sskip_item *b))
340 : {
341 0 : size_t level = SKIPLIST_MAXDEPTH;
342 0 : const struct sskip_item *prev = &head->hitem, *next;
343 0 : int cmpval;
344 :
345 0 : while (level) {
346 0 : next = sl_level_get(prev, level - 1);
347 0 : if (!next) {
348 0 : level--;
349 0 : continue;
350 : }
351 0 : cmpval = cmpfn(next, item);
352 0 : if (cmpval < 0) {
353 0 : prev = next;
354 0 : continue;
355 : }
356 0 : if (cmpval == 0)
357 0 : return next;
358 : level--;
359 : }
360 : return next;
361 : }
362 :
363 0 : const struct sskip_item *typesafe_skiplist_find_lt(
364 : const struct sskip_head *head,
365 : const struct sskip_item *item, int (*cmpfn)(
366 : const struct sskip_item *a,
367 : const struct sskip_item *b))
368 : {
369 0 : size_t level = SKIPLIST_MAXDEPTH;
370 0 : const struct sskip_item *prev = &head->hitem, *next, *best = NULL;
371 0 : int cmpval;
372 :
373 0 : while (level) {
374 0 : next = sl_level_get(prev, level - 1);
375 0 : if (!next) {
376 0 : level--;
377 0 : continue;
378 : }
379 0 : cmpval = cmpfn(next, item);
380 0 : if (cmpval < 0) {
381 0 : best = prev = next;
382 0 : continue;
383 : }
384 : level--;
385 : }
386 0 : return best;
387 : }
388 :
389 0 : struct sskip_item *typesafe_skiplist_del(
390 : struct sskip_head *head, struct sskip_item *item,
391 : int (*cmpfn)(const struct sskip_item *a, const struct sskip_item *b))
392 : {
393 0 : size_t level = SKIPLIST_MAXDEPTH;
394 0 : struct sskip_item *prev = &head->hitem, *next;
395 0 : int cmpval;
396 0 : bool found = false;
397 :
398 0 : while (level) {
399 0 : next = sl_level_get(prev, level - 1);
400 0 : if (!next) {
401 0 : level--;
402 0 : continue;
403 : }
404 0 : if (next == item) {
405 0 : sl_level_set(prev, level - 1,
406 : sl_level_get(item, level - 1));
407 0 : level--;
408 0 : found = true;
409 0 : continue;
410 : }
411 0 : cmpval = cmpfn(next, item);
412 0 : if (cmpval < 0) {
413 0 : prev = next;
414 0 : continue;
415 : }
416 : level--;
417 : }
418 :
419 0 : if (!found)
420 : return NULL;
421 :
422 : /* TBD: assert when trying to remove non-existing item? */
423 0 : head->count--;
424 :
425 0 : if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
426 0 : uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
427 0 : ptrval &= UINTPTR_MAX - 3;
428 0 : struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
429 0 : XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
430 : }
431 0 : memset(item, 0, sizeof(*item));
432 :
433 0 : return item;
434 : }
435 :
436 1019 : struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head)
437 : {
438 1019 : size_t level = SKIPLIST_MAXDEPTH;
439 1019 : struct sskip_item *prev = &head->hitem, *next, *item;
440 :
441 1019 : item = sl_level_get(prev, 0);
442 1019 : if (!item)
443 : return NULL;
444 :
445 12720 : do {
446 12720 : level--;
447 :
448 12720 : next = sl_level_get(prev, level);
449 12720 : if (next != item)
450 11149 : continue;
451 :
452 1571 : sl_level_set(prev, level, sl_level_get(item, level));
453 12720 : } while (level);
454 :
455 795 : head->count--;
456 :
457 795 : if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
458 45 : uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
459 45 : ptrval &= UINTPTR_MAX - 3;
460 45 : struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
461 45 : XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
462 : }
463 795 : memset(item, 0, sizeof(*item));
464 :
465 795 : return item;
466 : }
467 :
468 : /* heap */
469 :
470 : #if 0
471 : static void heap_consistency_check(struct heap_head *head,
472 : int (*cmpfn)(const struct heap_item *a,
473 : const struct heap_item *b),
474 : uint32_t pos)
475 : {
476 : uint32_t rghtpos = pos + 1;
477 : uint32_t downpos = HEAP_NARY * (pos + 1);
478 :
479 : if (pos + 1 > ~0U / HEAP_NARY)
480 : downpos = ~0U;
481 :
482 : if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) {
483 : assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0);
484 : heap_consistency_check(head, cmpfn, rghtpos);
485 : }
486 : if (downpos < head->count) {
487 : assert(cmpfn(head->array[downpos], head->array[pos]) >= 0);
488 : heap_consistency_check(head, cmpfn, downpos);
489 : }
490 : }
491 : #else
492 : #define heap_consistency_check(head, cmpfn, pos)
493 : #endif
494 :
495 436 : void typesafe_heap_resize(struct heap_head *head, bool grow)
496 : {
497 436 : uint32_t newsize;
498 :
499 436 : if (grow) {
500 218 : newsize = head->arraysz;
501 218 : if (newsize <= 36)
502 : newsize = 72;
503 0 : else if (newsize < 262144)
504 0 : newsize += newsize / 2;
505 0 : else if (newsize < 0xaaaa0000)
506 0 : newsize += newsize / 3;
507 : else
508 0 : assert(!newsize);
509 218 : } else if (head->count > 0) {
510 : newsize = head->count;
511 : } else {
512 218 : XFREE(MTYPE_HEAP_ARRAY, head->array);
513 218 : head->arraysz = 0;
514 218 : return;
515 : }
516 :
517 218 : newsize += HEAP_NARY - 1;
518 218 : newsize &= ~(HEAP_NARY - 1);
519 218 : if (newsize == head->arraysz)
520 : return;
521 :
522 218 : head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array,
523 : newsize * sizeof(struct heap_item *));
524 218 : head->arraysz = newsize;
525 : }
526 :
527 6176 : void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos,
528 : struct heap_item *item,
529 : int (*cmpfn)(const struct heap_item *a,
530 : const struct heap_item *b))
531 : {
532 20894 : uint32_t rghtpos, downpos, moveto;
533 :
534 35612 : while (1) {
535 : /* rghtpos: neighbor to the "right", inside block of NARY.
536 : * may be invalid if last in block, check nary_last()
537 : * downpos: first neighbor in the "downwards" block further
538 : * away from the root
539 : */
540 20894 : rghtpos = pos + 1;
541 :
542 : /* make sure we can use the full 4G items */
543 20894 : downpos = HEAP_NARY * (pos + 1);
544 20894 : if (pos + 1 > ~0U / HEAP_NARY)
545 : /* multiplication overflowed. ~0U is guaranteed
546 : * to be an invalid index; size limit is enforced in
547 : * resize()
548 : */
549 0 : downpos = ~0U;
550 :
551 : /* only used on break */
552 20894 : moveto = pos;
553 :
554 : #define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
555 20894 : if (downpos >= head->count
556 3042 : || cmpfn(head->array[downpos], item) >= 0) {
557 : /* not moving down; either at end or down is >= item */
558 18108 : if (nary_last(pos) || rghtpos >= head->count
559 12925 : || cmpfn(head->array[rghtpos], item) >= 0)
560 : /* not moving right either - got our spot */
561 : break;
562 :
563 : moveto = rghtpos;
564 :
565 : /* else: downpos is valid and < item. choose between down
566 : * or right (if the latter is an option) */
567 5555 : } else if (nary_last(pos) || cmpfn(head->array[rghtpos],
568 2769 : head->array[downpos]) >= 0)
569 : moveto = downpos;
570 : else
571 : moveto = rghtpos;
572 : #undef nary_last
573 :
574 14718 : head->array[pos] = head->array[moveto];
575 14718 : head->array[pos]->index = pos;
576 14718 : pos = moveto;
577 : }
578 :
579 6176 : head->array[moveto] = item;
580 6176 : item->index = moveto;
581 :
582 6176 : heap_consistency_check(head, cmpfn, 0);
583 6176 : }
584 :
585 7006 : void typesafe_heap_pullup(struct heap_head *head, uint32_t pos,
586 : struct heap_item *item,
587 : int (*cmpfn)(const struct heap_item *a,
588 : const struct heap_item *b))
589 : {
590 7006 : uint32_t moveto;
591 :
592 21198 : while (pos != 0) {
593 19121 : if ((pos & (HEAP_NARY - 1)) == 0)
594 1575 : moveto = pos / HEAP_NARY - 1;
595 : else
596 17546 : moveto = pos - 1;
597 :
598 19121 : if (cmpfn(head->array[moveto], item) <= 0)
599 : break;
600 :
601 14192 : head->array[pos] = head->array[moveto];
602 14192 : head->array[pos]->index = pos;
603 :
604 14192 : pos = moveto;
605 : }
606 :
607 7006 : head->array[pos] = item;
608 7006 : item->index = pos;
609 :
610 7006 : heap_consistency_check(head, cmpfn, 0);
611 7006 : }
|
