]> git.proxmox.com Git - mirror_frr.git/blame - lib/typesafe.h
projects / mirror_frr.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Merge pull request #5728 from opensourcerouting/move_rpm_to_python3
[mirror_frr.git] / lib / typesafe.h
CommitLineData
abd71baa
DL		 1/*
2 * Copyright (c) 2016-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#ifndef _FRR_TYPESAFE_H
18#define _FRR_TYPESAFE_H
19
20#include <stddef.h>
21#include <stdint.h>
22#include <stdbool.h>
23#include <assert.h>
24#include "compiler.h"
25
eea3c899
RW		 26#ifdef __cplusplus
27extern "C" {
28#endif
29
abd71baa
DL		 30/* generic macros for all list-like types */
31
81fddbe7 32#define frr_each(prefix, head, item) \
abd71baa
DL		 33 for (item = prefix##_first(head); item; \
34 item = prefix##_next(head, item))
81fddbe7 35#define frr_each_safe(prefix, head, item) \
abd71baa
DL		 36 for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe = \
37 prefix##_next_safe(head, \
38 (item = prefix##_first(head))); \
39 item; \
40 item = prefix##_safe, \
41 prefix##_safe = prefix##_next_safe(head, prefix##_safe))
81fddbe7 42#define frr_each_from(prefix, head, item, from) \
abd71baa
DL		 43 for (item = from, from = prefix##_next_safe(head, item); \
44 item; \
45 item = from, from = prefix##_next_safe(head, from))
46
47/* single-linked list, unsorted/arbitrary.
48 * can be used as queue with add_tail / pop
49 */
50
51/* don't use these structs directly */
52struct slist_item {
53 struct slist_item *next;
54};
55
56struct slist_head {
57 struct slist_item *first, **last_next;
58 size_t count;
59};
60
61static inline void typesafe_list_add(struct slist_head *head,
62 struct slist_item **pos, struct slist_item *item)
63{
64 item->next = *pos;
65 *pos = item;
66 if (pos == head->last_next)
67 head->last_next = &item->next;
68 head->count++;
69}
70
71/* use as:
72 *
73 * PREDECL_LIST(namelist)
74 * struct name {
75 * struct namelist_item nlitem;
76 * }
77 * DECLARE_LIST(namelist, struct name, nlitem)
78 */
79#define PREDECL_LIST(prefix) \
80struct prefix ## _head { struct slist_head sh; }; \
81struct prefix ## _item { struct slist_item si; };
82
83#define INIT_LIST(var) { .sh = { .last_next = &var.sh.first, }, }
84
85#define DECLARE_LIST(prefix, type, field) \
86 \
87macro_inline void prefix ## _init(struct prefix##_head *h) \
88{ \
89 memset(h, 0, sizeof(*h)); \
90 h->sh.last_next = &h->sh.first; \
91} \
92macro_inline void prefix ## _fini(struct prefix##_head *h) \
93{ \
94 memset(h, 0, sizeof(*h)); \
95} \
96macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
97{ \
98 typesafe_list_add(&h->sh, &h->sh.first, &item->field.si); \
99} \
100macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
101{ \
102 typesafe_list_add(&h->sh, h->sh.last_next, &item->field.si); \
103} \
104macro_inline void prefix ## _add_after(struct prefix##_head *h, \
105 type *after, type *item) \
106{ \
107 struct slist_item **nextp; \
108 nextp = after ? &after->field.si.next : &h->sh.first; \
109 typesafe_list_add(&h->sh, nextp, &item->field.si); \
110} \
111/* TODO: del_hint */ \
da098d78 112macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa
DL		 113{ \
114 struct slist_item **iter = &h->sh.first; \
115 while (*iter && *iter != &item->field.si) \
116 iter = &(*iter)->next; \
117 if (!*iter) \
da098d78 118 return NULL; \
abd71baa
DL		 119 h->sh.count--; \
120 *iter = item->field.si.next; \
121 if (!item->field.si.next) \
122 h->sh.last_next = iter; \
da098d78 123 return item; \
abd71baa
DL		 124} \
125macro_inline type *prefix ## _pop(struct prefix##_head *h) \
126{ \
127 struct slist_item *sitem = h->sh.first; \
128 if (!sitem) \
129 return NULL; \
130 h->sh.count--; \
131 h->sh.first = sitem->next; \
132 if (h->sh.first == NULL) \
133 h->sh.last_next = &h->sh.first; \
134 return container_of(sitem, type, field.si); \
135} \
136macro_pure type *prefix ## _first(struct prefix##_head *h) \
137{ \
138 return container_of_null(h->sh.first, type, field.si); \
139} \
140macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \
141{ \
142 struct slist_item *sitem = &item->field.si; \
143 return container_of_null(sitem->next, type, field.si); \
144} \
145macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
146{ \
147 struct slist_item *sitem; \
148 if (!item) \
149 return NULL; \
150 sitem = &item->field.si; \
151 return container_of_null(sitem->next, type, field.si); \
152} \
0ca16c58 153macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 154{ \
155 return h->sh.count; \
156} \
157/* ... */
158
fdad523b
DL		 159/* don't use these structs directly */
160struct dlist_item {
161 struct dlist_item *next;
162 struct dlist_item *prev;
163};
164
165struct dlist_head {
166 struct dlist_item hitem;
167 size_t count;
168};
169
170static inline void typesafe_dlist_add(struct dlist_head *head,
171 struct dlist_item *prev, struct dlist_item *item)
172{
173 item->next = prev->next;
174 item->next->prev = item;
175 item->prev = prev;
176 prev->next = item;
177 head->count++;
178}
179
180/* double-linked list, for fast item deletion
181 */
182#define PREDECL_DLIST(prefix) \
183struct prefix ## _head { struct dlist_head dh; }; \
184struct prefix ## _item { struct dlist_item di; };
185
186#define INIT_DLIST(var) { .dh = { \
187 .hitem = { &var.dh.hitem, &var.dh.hitem }, }, }
188
189#define DECLARE_DLIST(prefix, type, field) \
190 \
191macro_inline void prefix ## _init(struct prefix##_head *h) \
192{ \
193 memset(h, 0, sizeof(*h)); \
194 h->dh.hitem.prev = &h->dh.hitem; \
195 h->dh.hitem.next = &h->dh.hitem; \
196} \
197macro_inline void prefix ## _fini(struct prefix##_head *h) \
198{ \
199 memset(h, 0, sizeof(*h)); \
200} \
201macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
202{ \
203 typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di); \
204} \
205macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
206{ \
207 typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di); \
208} \
209macro_inline void prefix ## _add_after(struct prefix##_head *h, \
210 type *after, type *item) \
211{ \
212 struct dlist_item *prev; \
213 prev = after ? &after->field.di : &h->dh.hitem; \
214 typesafe_dlist_add(&h->dh, prev, &item->field.di); \
215} \
da098d78 216macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
fdad523b
DL		 217{ \
218 struct dlist_item *ditem = &item->field.di; \
219 ditem->prev->next = ditem->next; \
220 ditem->next->prev = ditem->prev; \
221 h->dh.count--; \
222 ditem->prev = ditem->next = NULL; \
da098d78 223 return item; \
fdad523b
DL		 224} \
225macro_inline type *prefix ## _pop(struct prefix##_head *h) \
226{ \
227 struct dlist_item *ditem = h->dh.hitem.next; \
228 if (ditem == &h->dh.hitem) \
229 return NULL; \
230 ditem->prev->next = ditem->next; \
231 ditem->next->prev = ditem->prev; \
232 h->dh.count--; \
233 return container_of(ditem, type, field.di); \
234} \
235macro_pure type *prefix ## _first(struct prefix##_head *h) \
236{ \
237 struct dlist_item *ditem = h->dh.hitem.next; \
238 if (ditem == &h->dh.hitem) \
239 return NULL; \
240 return container_of(ditem, type, field.di); \
241} \
242macro_pure type *prefix ## _next(struct prefix##_head * h, type *item) \
243{ \
244 struct dlist_item *ditem = &item->field.di; \
245 if (ditem->next == &h->dh.hitem) \
246 return NULL; \
247 return container_of(ditem->next, type, field.di); \
248} \
249macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
250{ \
251 if (!item) \
252 return NULL; \
253 return prefix ## _next(h, item); \
254} \
0ca16c58 255macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
fdad523b
DL		 256{ \
257 return h->dh.count; \
258} \
259/* ... */
260
5cb4277d
DL		 261/* note: heap currently caps out at 4G items */
262
263#define HEAP_NARY 8U
264typedef uint32_t heap_index_i;
265
266struct heap_item {
267 uint32_t index;
268};
269
270struct heap_head {
271 struct heap_item **array;
272 uint32_t arraysz, count;
273};
274
275#define HEAP_RESIZE_TRESH_UP(h) \
276 (h->hh.count + 1 >= h->hh.arraysz)
277#define HEAP_RESIZE_TRESH_DN(h) \
278 (h->hh.count == 0 || \
279 h->hh.arraysz - h->hh.count > (h->hh.count + 1024) / 2)
280
281#define PREDECL_HEAP(prefix) \
282struct prefix ## _head { struct heap_head hh; }; \
283struct prefix ## _item { struct heap_item hi; };
284
285#define INIT_HEAP(var) { }
286
287#define DECLARE_HEAP(prefix, type, field, cmpfn) \
288 \
289macro_inline void prefix ## _init(struct prefix##_head *h) \
290{ \
291 memset(h, 0, sizeof(*h)); \
292} \
293macro_inline void prefix ## _fini(struct prefix##_head *h) \
294{ \
295 assert(h->hh.count == 0); \
296 memset(h, 0, sizeof(*h)); \
297} \
298macro_inline int prefix ## __cmp(const struct heap_item *a, \
299 const struct heap_item *b) \
300{ \
301 return cmpfn(container_of(a, type, field.hi), \
302 container_of(b, type, field.hi)); \
303} \
304macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
305{ \
306 if (HEAP_RESIZE_TRESH_UP(h)) \
307 typesafe_heap_resize(&h->hh, true); \
308 typesafe_heap_pullup(&h->hh, h->hh.count, &item->field.hi, \
309 prefix ## __cmp); \
310 h->hh.count++; \
311 return NULL; \
312} \
da098d78 313macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
5cb4277d
DL		 314{ \
315 struct heap_item *other; \
316 uint32_t index = item->field.hi.index; \
317 assert(h->hh.array[index] == &item->field.hi); \
318 h->hh.count--; \
319 other = h->hh.array[h->hh.count]; \
320 if (cmpfn(container_of(other, type, field.hi), item) < 0) \
321 typesafe_heap_pullup(&h->hh, index, other, prefix ## __cmp); \
322 else \
323 typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \
324 if (HEAP_RESIZE_TRESH_DN(h)) \
325 typesafe_heap_resize(&h->hh, false); \
da098d78 326 return item; \
5cb4277d
DL		 327} \
328macro_inline type *prefix ## _pop(struct prefix##_head *h) \
329{ \
330 struct heap_item *hitem, *other; \
331 if (h->hh.count == 0) \
332 return NULL; \
333 hitem = h->hh.array[0]; \
334 h->hh.count--; \
335 other = h->hh.array[h->hh.count]; \
336 typesafe_heap_pushdown(&h->hh, 0, other, prefix ## __cmp); \
337 if (HEAP_RESIZE_TRESH_DN(h)) \
338 typesafe_heap_resize(&h->hh, false); \
339 return container_of(hitem, type, field.hi); \
340} \
341macro_pure type *prefix ## _first(struct prefix##_head *h) \
342{ \
343 if (h->hh.count == 0) \
344 return NULL; \
345 return container_of(h->hh.array[0], type, field.hi); \
346} \
347macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
348{ \
349 uint32_t idx = item->field.hi.index + 1; \
350 if (idx >= h->hh.count) \
351 return NULL; \
352 return container_of(h->hh.array[idx], type, field.hi); \
353} \
354macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
355{ \
356 if (!item) \
357 return NULL; \
358 return prefix ## _next(h, item); \
359} \
0ca16c58 360macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
5cb4277d
DL		 361{ \
362 return h->hh.count; \
363} \
364/* ... */
365
366extern void typesafe_heap_resize(struct heap_head *head, bool grow);
367extern void typesafe_heap_pushdown(struct heap_head *head, uint32_t index,
368 struct heap_item *item,
369 int (*cmpfn)(const struct heap_item *a,
370 const struct heap_item *b));
371extern void typesafe_heap_pullup(struct heap_head *head, uint32_t index,
372 struct heap_item *item,
373 int (*cmpfn)(const struct heap_item *a,
374 const struct heap_item *b));
375
abd71baa
DL		 376/* single-linked list, sorted.
377 * can be used as priority queue with add / pop
378 */
379
380/* don't use these structs directly */
381struct ssort_item {
382 struct ssort_item *next;
383};
384
385struct ssort_head {
386 struct ssort_item *first;
387 size_t count;
388};
389
390/* use as:
391 *
392 * PREDECL_SORTLIST(namelist)
393 * struct name {
394 * struct namelist_item nlitem;
395 * }
396 * DECLARE_SORTLIST(namelist, struct name, nlitem)
397 */
398#define _PREDECL_SORTLIST(prefix) \
399struct prefix ## _head { struct ssort_head sh; }; \
400struct prefix ## _item { struct ssort_item si; };
401
402#define INIT_SORTLIST_UNIQ(var) { }
403#define INIT_SORTLIST_NONUNIQ(var) { }
404
405#define PREDECL_SORTLIST_UNIQ(prefix) \
406 _PREDECL_SORTLIST(prefix)
407#define PREDECL_SORTLIST_NONUNIQ(prefix) \
408 _PREDECL_SORTLIST(prefix)
409
410#define _DECLARE_SORTLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
411 \
412macro_inline void prefix ## _init(struct prefix##_head *h) \
413{ \
414 memset(h, 0, sizeof(*h)); \
415} \
416macro_inline void prefix ## _fini(struct prefix##_head *h) \
417{ \
418 memset(h, 0, sizeof(*h)); \
419} \
420macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
421{ \
422 struct ssort_item **np = &h->sh.first; \
423 int c = 1; \
424 while (*np && (c = cmpfn_uq( \
425 container_of(*np, type, field.si), item)) < 0) \
426 np = &(*np)->next; \
427 if (c == 0) \
428 return container_of(*np, type, field.si); \
429 item->field.si.next = *np; \
430 *np = &item->field.si; \
431 h->sh.count++; \
432 return NULL; \
433} \
434macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \
435 const type *item) \
436{ \
437 struct ssort_item *sitem = h->sh.first; \
438 int cmpval = 0; \
439 while (sitem && (cmpval = cmpfn_nuq( \
4d5cf6bc 440 container_of(sitem, type, field.si), item)) < 0) \
abd71baa
DL		 441 sitem = sitem->next; \
442 return container_of_null(sitem, type, field.si); \
443} \
444macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \
445 const type *item) \
446{ \
447 struct ssort_item *prev = NULL, *sitem = h->sh.first; \
448 int cmpval = 0; \
449 while (sitem && (cmpval = cmpfn_nuq( \
4d5cf6bc 450 container_of(sitem, type, field.si), item)) < 0) \
abd71baa
DL		 451 sitem = (prev = sitem)->next; \
452 return container_of_null(prev, type, field.si); \
453} \
454/* TODO: del_hint */ \
da098d78 455macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa
DL		 456{ \
457 struct ssort_item **iter = &h->sh.first; \
458 while (*iter && *iter != &item->field.si) \
459 iter = &(*iter)->next; \
460 if (!*iter) \
da098d78 461 return NULL; \
abd71baa
DL		 462 h->sh.count--; \
463 *iter = item->field.si.next; \
da098d78 464 return item; \
abd71baa
DL		 465} \
466macro_inline type *prefix ## _pop(struct prefix##_head *h) \
467{ \
468 struct ssort_item *sitem = h->sh.first; \
469 if (!sitem) \
470 return NULL; \
471 h->sh.count--; \
472 h->sh.first = sitem->next; \
473 return container_of(sitem, type, field.si); \
474} \
475macro_pure type *prefix ## _first(struct prefix##_head *h) \
476{ \
477 return container_of_null(h->sh.first, type, field.si); \
478} \
479macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
480{ \
481 struct ssort_item *sitem = &item->field.si; \
482 return container_of_null(sitem->next, type, field.si); \
483} \
484macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
485{ \
486 struct ssort_item *sitem; \
487 if (!item) \
488 return NULL; \
489 sitem = &item->field.si; \
490 return container_of_null(sitem->next, type, field.si); \
491} \
0ca16c58 492macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 493{ \
494 return h->sh.count; \
495} \
496/* ... */
497
498#define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \
499 _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn) \
500 \
791ac7c7 501macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \
abd71baa
DL		 502{ \
503 struct ssort_item *sitem = h->sh.first; \
504 int cmpval = 0; \
505 while (sitem && (cmpval = cmpfn( \
4d5cf6bc 506 container_of(sitem, type, field.si), item)) < 0) \
abd71baa
DL		 507 sitem = sitem->next; \
508 if (!sitem || cmpval > 0) \
509 return NULL; \
510 return container_of(sitem, type, field.si); \
511} \
512/* ... */
513
514#define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \
515macro_inline int _ ## prefix ## _cmp(const type *a, const type *b) \
516{ \
517 int cmpval = cmpfn(a, b); \
518 if (cmpval) \
519 return cmpval; \
520 if (a < b) \
521 return -1; \
522 if (a > b) \
523 return 1; \
524 return 0; \
525} \
526 _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp) \
527/* ... */
528
529
530/* hash, "sorted" by hash value
531 */
532
533/* don't use these structs directly */
534struct thash_item {
535 struct thash_item *next;
536 uint32_t hashval;
537};
538
539struct thash_head {
540 struct thash_item **entries;
541 uint32_t count;
542
543 uint8_t tabshift;
544 uint8_t minshift, maxshift;
545};
546
547#define _HASH_SIZE(tabshift) \
548 ((1U << (tabshift)) >> 1)
549#define HASH_SIZE(head) \
550 _HASH_SIZE((head).tabshift)
551#define _HASH_KEY(tabshift, val) \
552 ((val) >> (33 - (tabshift)))
553#define HASH_KEY(head, val) \
554 _HASH_KEY((head).tabshift, val)
555#define HASH_GROW_THRESHOLD(head) \
556 ((head).count >= HASH_SIZE(head))
557#define HASH_SHRINK_THRESHOLD(head) \
558 ((head).count <= (HASH_SIZE(head) - 1) / 2)
559
560extern void typesafe_hash_grow(struct thash_head *head);
561extern void typesafe_hash_shrink(struct thash_head *head);
562
563/* use as:
564 *
565 * PREDECL_HASH(namelist)
566 * struct name {
567 * struct namelist_item nlitem;
568 * }
569 * DECLARE_HASH(namelist, struct name, nlitem, cmpfunc, hashfunc)
570 */
571#define PREDECL_HASH(prefix) \
572struct prefix ## _head { struct thash_head hh; }; \
573struct prefix ## _item { struct thash_item hi; };
574
575#define INIT_HASH(var) { }
576
577#define DECLARE_HASH(prefix, type, field, cmpfn, hashfn) \
578 \
579macro_inline void prefix ## _init(struct prefix##_head *h) \
580{ \
581 memset(h, 0, sizeof(*h)); \
582} \
583macro_inline void prefix ## _fini(struct prefix##_head *h) \
584{ \
585 assert(h->hh.count == 0); \
586 h->hh.minshift = 0; \
587 typesafe_hash_shrink(&h->hh); \
588 memset(h, 0, sizeof(*h)); \
589} \
590macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
591{ \
592 h->hh.count++; \
593 if (!h->hh.tabshift || HASH_GROW_THRESHOLD(h->hh)) \
594 typesafe_hash_grow(&h->hh); \
595 \
596 uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \
597 item->field.hi.hashval = hval; \
598 struct thash_item **np = &h->hh.entries[hbits]; \
599 while (*np && (*np)->hashval < hval) \
600 np = &(*np)->next; \
601 if (*np && cmpfn(container_of(*np, type, field.hi), item) == 0) { \
602 h->hh.count--; \
603 return container_of(*np, type, field.hi); \
604 } \
605 item->field.hi.next = *np; \
606 *np = &item->field.hi; \
607 return NULL; \
608} \
791ac7c7 609macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \
abd71baa
DL		 610{ \
611 if (!h->hh.tabshift) \
612 return NULL; \
613 uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \
614 struct thash_item *hitem = h->hh.entries[hbits]; \
615 while (hitem && hitem->hashval < hval) \
616 hitem = hitem->next; \
617 while (hitem && hitem->hashval == hval) { \
618 if (!cmpfn(container_of(hitem, type, field.hi), item)) \
619 return container_of(hitem, type, field.hi); \
620 hitem = hitem->next; \
621 } \
622 return NULL; \
623} \
da098d78 624macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa
DL		 625{ \
626 if (!h->hh.tabshift) \
da098d78 627 return NULL; \
abd71baa
DL		 628 uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
629 struct thash_item **np = &h->hh.entries[hbits]; \
630 while (*np && (*np)->hashval < hval) \
631 np = &(*np)->next; \
632 while (*np && *np != &item->field.hi && (*np)->hashval == hval) \
633 np = &(*np)->next; \
634 if (*np != &item->field.hi) \
da098d78 635 return NULL; \
abd71baa
DL		 636 *np = item->field.hi.next; \
637 item->field.hi.next = NULL; \
638 h->hh.count--; \
639 if (HASH_SHRINK_THRESHOLD(h->hh)) \
640 typesafe_hash_shrink(&h->hh); \
da098d78 641 return item; \
abd71baa
DL		 642} \
643macro_inline type *prefix ## _pop(struct prefix##_head *h) \
644{ \
645 uint32_t i; \
646 for (i = 0; i < HASH_SIZE(h->hh); i++) \
647 if (h->hh.entries[i]) { \
648 struct thash_item *hitem = h->hh.entries[i]; \
649 h->hh.entries[i] = hitem->next; \
650 h->hh.count--; \
651 hitem->next = NULL; \
652 if (HASH_SHRINK_THRESHOLD(h->hh)) \
653 typesafe_hash_shrink(&h->hh); \
654 return container_of(hitem, type, field.hi); \
655 } \
656 return NULL; \
657} \
658macro_pure type *prefix ## _first(struct prefix##_head *h) \
659{ \
660 uint32_t i; \
661 for (i = 0; i < HASH_SIZE(h->hh); i++) \
662 if (h->hh.entries[i]) \
663 return container_of(h->hh.entries[i], type, field.hi); \
664 return NULL; \
665} \
666macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
667{ \
668 struct thash_item *hitem = &item->field.hi; \
669 if (hitem->next) \
670 return container_of(hitem->next, type, field.hi); \
671 uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1; \
672 for (; i < HASH_SIZE(h->hh); i++) \
673 if (h->hh.entries[i]) \
674 return container_of(h->hh.entries[i], type, field.hi); \
675 return NULL; \
676} \
677macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
678{ \
679 if (!item) \
680 return NULL; \
681 return prefix ## _next(h, item); \
682} \
0ca16c58 683macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 684{ \
685 return h->hh.count; \
686} \
687/* ... */
688
689/* skiplist, sorted.
690 * can be used as priority queue with add / pop
691 */
692
693/* don't use these structs directly */
694#define SKIPLIST_MAXDEPTH 16
695#define SKIPLIST_EMBED 4
696#define SKIPLIST_OVERFLOW (SKIPLIST_EMBED - 1)
697
698struct sskip_item {
699 struct sskip_item *next[SKIPLIST_EMBED];
700};
701
702struct sskip_overflow {
703 struct sskip_item *next[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW];
704};
705
706struct sskip_head {
707 struct sskip_item hitem;
708 struct sskip_item *overflow[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW];
709 size_t count;
710};
711
712/* use as:
713 *
714 * PREDECL_SKIPLIST(namelist)
715 * struct name {
716 * struct namelist_item nlitem;
717 * }
718 * DECLARE_SKIPLIST(namelist, struct name, nlitem, cmpfunc)
719 */
720#define _PREDECL_SKIPLIST(prefix) \
721struct prefix ## _head { struct sskip_head sh; }; \
722struct prefix ## _item { struct sskip_item si; };
723
724#define INIT_SKIPLIST_UNIQ(var) { }
725#define INIT_SKIPLIST_NONUNIQ(var) { }
726
727#define _DECLARE_SKIPLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
728 \
729macro_inline void prefix ## _init(struct prefix##_head *h) \
730{ \
731 memset(h, 0, sizeof(*h)); \
732 h->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \
733 ((uintptr_t)h->sh.overflow | 1); \
734} \
735macro_inline void prefix ## _fini(struct prefix##_head *h) \
736{ \
737 memset(h, 0, sizeof(*h)); \
738} \
739macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
740{ \
741 struct sskip_item *si; \
742 si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq); \
743 return container_of_null(si, type, field.si); \
744} \
745macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \
746 const type *item) \
747{ \
748 struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \
749 &item->field.si, cmpfn_nuq); \
750 return container_of_null(sitem, type, field.si); \
751} \
752macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \
753 const type *item) \
754{ \
755 struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \
756 &item->field.si, cmpfn_nuq); \
757 return container_of_null(sitem, type, field.si); \
758} \
da098d78 759macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa 760{ \
da098d78
SW		 761 struct sskip_item *sitem = typesafe_skiplist_del(&h->sh, \
762 &item->field.si, cmpfn_uq); \
763 return container_of_null(sitem, type, field.si); \
abd71baa
DL		 764} \
765macro_inline type *prefix ## _pop(struct prefix##_head *h) \
766{ \
01734da3
DL		 767 struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \
768 return container_of_null(sitem, type, field.si); \
abd71baa
DL		 769} \
770macro_pure type *prefix ## _first(struct prefix##_head *h) \
771{ \
772 struct sskip_item *first = h->sh.hitem.next[0]; \
773 return container_of_null(first, type, field.si); \
774} \
775macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
776{ \
777 struct sskip_item *next = item->field.si.next[0]; \
778 return container_of_null(next, type, field.si); \
779} \
780macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
781{ \
782 struct sskip_item *next; \
783 next = item ? item->field.si.next[0] : NULL; \
784 return container_of_null(next, type, field.si); \
785} \
0ca16c58 786macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 787{ \
788 return h->sh.count; \
789} \
790/* ... */
791
792#define PREDECL_SKIPLIST_UNIQ(prefix) \
793 _PREDECL_SKIPLIST(prefix)
794#define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn) \
795 \
796macro_inline int prefix ## __cmp(const struct sskip_item *a, \
797 const struct sskip_item *b) \
798{ \
799 return cmpfn(container_of(a, type, field.si), \
800 container_of(b, type, field.si)); \
801} \
791ac7c7 802macro_inline type *prefix ## _find(struct prefix##_head *h, const type *item) \
abd71baa
DL		 803{ \
804 struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \
805 &item->field.si, &prefix ## __cmp); \
806 return container_of_null(sitem, type, field.si); \
807} \
808 \
809_DECLARE_SKIPLIST(prefix, type, field, \
810 prefix ## __cmp, prefix ## __cmp) \
811/* ... */
812
813#define PREDECL_SKIPLIST_NONUNIQ(prefix) \
814 _PREDECL_SKIPLIST(prefix)
815#define DECLARE_SKIPLIST_NONUNIQ(prefix, type, field, cmpfn) \
816 \
817macro_inline int prefix ## __cmp(const struct sskip_item *a, \
818 const struct sskip_item *b) \
819{ \
820 return cmpfn(container_of(a, type, field.si), \
821 container_of(b, type, field.si)); \
822} \
823macro_inline int prefix ## __cmp_uq(const struct sskip_item *a, \
824 const struct sskip_item *b) \
825{ \
826 int cmpval = cmpfn(container_of(a, type, field.si), \
827 container_of(b, type, field.si)); \
828 if (cmpval) \
829 return cmpval; \
830 if (a < b) \
831 return -1; \
832 if (a > b) \
833 return 1; \
834 return 0; \
835} \
836 \
837_DECLARE_SKIPLIST(prefix, type, field, \
838 prefix ## __cmp, prefix ## __cmp_uq) \
839/* ... */
840
841
842extern struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
843 struct sskip_item *item, int (*cmpfn)(
844 const struct sskip_item *a,
845 const struct sskip_item *b));
846extern struct sskip_item *typesafe_skiplist_find(struct sskip_head *head,
847 const struct sskip_item *item, int (*cmpfn)(
848 const struct sskip_item *a,
849 const struct sskip_item *b));
850extern struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head,
851 const struct sskip_item *item, int (*cmpfn)(
852 const struct sskip_item *a,
853 const struct sskip_item *b));
854extern struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
855 const struct sskip_item *item, int (*cmpfn)(
856 const struct sskip_item *a,
857 const struct sskip_item *b));
da098d78
SW		 858extern struct sskip_item *typesafe_skiplist_del(
859 struct sskip_head *head, struct sskip_item *item, int (*cmpfn)(
abd71baa
DL		 860 const struct sskip_item *a,
861 const struct sskip_item *b));
01734da3 862extern struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head);
abd71baa 863
eea3c899
RW		 864#ifdef __cplusplus
865}
866#endif
867
80911bc2
DL		 868/* this needs to stay at the end because both files include each other.
869 * the resolved order is typesafe.h before typerb.h
870 */
871#include "typerb.h"
872
abd71baa 873#endif /* _FRR_TYPESAFE_H */
FRRouting mirror