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