]>
git.proxmox.com Git - mirror_frr.git/blob - lib/typesafe.h
2 * Copyright (c) 2016-2019 David Lamparter, for NetDEF, Inc.
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.
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.
17 #ifndef _FRR_TYPESAFE_H
18 #define _FRR_TYPESAFE_H
30 /* generic macros for all list-like types */
32 #define frr_each(prefix, head, item) \
33 for (item = prefix##_first(head); item; \
34 item = prefix##_next(head, item))
35 #define frr_each_safe(prefix, head, item) \
36 for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe = \
37 prefix##_next_safe(head, \
38 (item = prefix##_first(head))); \
40 item = prefix##_safe, \
41 prefix##_safe = prefix##_next_safe(head, prefix##_safe))
42 #define frr_each_from(prefix, head, item, from) \
43 for (item = from, from = prefix##_next_safe(head, item); \
45 item = from, from = prefix##_next_safe(head, from))
48 /* non-const variants. these wrappers are the same for all the types, so
49 * bundle them together here.
51 #define TYPESAFE_FIRST_NEXT(prefix, type) \
52 macro_pure type *prefix ## _first(struct prefix##_head *h) \
54 return (type *)prefix ## _const_first(h); \
56 macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
58 return (type *)prefix ## _const_next(h, item); \
61 #define TYPESAFE_FIND(prefix, type) \
62 macro_inline type *prefix ## _find(struct prefix##_head *h, \
65 return (type *)prefix ## _const_find(h, item); \
68 #define TYPESAFE_FIND_CMP(prefix, type) \
69 macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \
72 return (type *)prefix ## _const_find_lt(h, item); \
74 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \
77 return (type *)prefix ## _const_find_gteq(h, item); \
82 /* single-linked list, unsorted/arbitrary.
83 * can be used as queue with add_tail / pop
86 /* don't use these structs directly */
88 struct slist_item
*next
;
92 struct slist_item
*first
, **last_next
;
96 static inline void typesafe_list_add(struct slist_head
*head
,
97 struct slist_item
**pos
, struct slist_item
*item
)
101 if (pos
== head
->last_next
)
102 head
->last_next
= &item
->next
;
108 * PREDECL_LIST(namelist)
110 * struct namelist_item nlitem;
112 * DECLARE_LIST(namelist, struct name, nlitem)
114 #define PREDECL_LIST(prefix) \
115 struct prefix ## _head { struct slist_head sh; }; \
116 struct prefix ## _item { struct slist_item si; };
118 #define INIT_LIST(var) { .sh = { .last_next = &var.sh.first, }, }
120 #define DECLARE_LIST(prefix, type, field) \
122 macro_inline void prefix ## _init(struct prefix##_head *h) \
124 memset(h, 0, sizeof(*h)); \
125 h->sh.last_next = &h->sh.first; \
127 macro_inline void prefix ## _fini(struct prefix##_head *h) \
129 memset(h, 0, sizeof(*h)); \
131 macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
133 typesafe_list_add(&h->sh, &h->sh.first, &item->field.si); \
135 macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
137 typesafe_list_add(&h->sh, h->sh.last_next, &item->field.si); \
139 macro_inline void prefix ## _add_after(struct prefix##_head *h, \
140 type *after, type *item) \
142 struct slist_item **nextp; \
143 nextp = after ? &after->field.si.next : &h->sh.first; \
144 typesafe_list_add(&h->sh, nextp, &item->field.si); \
146 /* TODO: del_hint */ \
147 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
149 struct slist_item **iter = &h->sh.first; \
150 while (*iter && *iter != &item->field.si) \
151 iter = &(*iter)->next; \
155 *iter = item->field.si.next; \
156 if (!item->field.si.next) \
157 h->sh.last_next = iter; \
160 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
162 struct slist_item *sitem = h->sh.first; \
166 h->sh.first = sitem->next; \
167 if (h->sh.first == NULL) \
168 h->sh.last_next = &h->sh.first; \
169 return container_of(sitem, type, field.si); \
171 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
173 return container_of_null(h->sh.first, type, field.si); \
175 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
178 const struct slist_item *sitem = &item->field.si; \
179 return container_of_null(sitem->next, type, field.si); \
181 TYPESAFE_FIRST_NEXT(prefix, type) \
182 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
184 struct slist_item *sitem; \
187 sitem = &item->field.si; \
188 return container_of_null(sitem->next, type, field.si); \
190 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
192 return h->sh.count; \
196 /* don't use these structs directly */
198 struct dlist_item
*next
;
199 struct dlist_item
*prev
;
203 struct dlist_item hitem
;
207 static inline void typesafe_dlist_add(struct dlist_head
*head
,
208 struct dlist_item
*prev
, struct dlist_item
*item
)
210 item
->next
= prev
->next
;
211 item
->next
->prev
= item
;
217 /* double-linked list, for fast item deletion
219 #define PREDECL_DLIST(prefix) \
220 struct prefix ## _head { struct dlist_head dh; }; \
221 struct prefix ## _item { struct dlist_item di; };
223 #define INIT_DLIST(var) { .dh = { \
224 .hitem = { &var.dh.hitem, &var.dh.hitem }, }, }
226 #define DECLARE_DLIST(prefix, type, field) \
228 macro_inline void prefix ## _init(struct prefix##_head *h) \
230 memset(h, 0, sizeof(*h)); \
231 h->dh.hitem.prev = &h->dh.hitem; \
232 h->dh.hitem.next = &h->dh.hitem; \
234 macro_inline void prefix ## _fini(struct prefix##_head *h) \
236 memset(h, 0, sizeof(*h)); \
238 macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
240 typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di); \
242 macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
244 typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di); \
246 macro_inline void prefix ## _add_after(struct prefix##_head *h, \
247 type *after, type *item) \
249 struct dlist_item *prev; \
250 prev = after ? &after->field.di : &h->dh.hitem; \
251 typesafe_dlist_add(&h->dh, prev, &item->field.di); \
253 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
255 struct dlist_item *ditem = &item->field.di; \
256 ditem->prev->next = ditem->next; \
257 ditem->next->prev = ditem->prev; \
259 ditem->prev = ditem->next = NULL; \
262 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
264 struct dlist_item *ditem = h->dh.hitem.next; \
265 if (ditem == &h->dh.hitem) \
267 ditem->prev->next = ditem->next; \
268 ditem->next->prev = ditem->prev; \
270 return container_of(ditem, type, field.di); \
272 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
274 const struct dlist_item *ditem = h->dh.hitem.next; \
275 if (ditem == &h->dh.hitem) \
277 return container_of(ditem, type, field.di); \
279 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
282 const struct dlist_item *ditem = &item->field.di; \
283 if (ditem->next == &h->dh.hitem) \
285 return container_of(ditem->next, type, field.di); \
287 TYPESAFE_FIRST_NEXT(prefix, type) \
288 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
292 return prefix ## _next(h, item); \
294 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
296 return h->dh.count; \
300 /* note: heap currently caps out at 4G items */
303 typedef uint32_t heap_index_i
;
310 struct heap_item
**array
;
311 uint32_t arraysz
, count
;
314 #define HEAP_RESIZE_TRESH_UP(h) \
315 (h->hh.count + 1 >= h->hh.arraysz)
316 #define HEAP_RESIZE_TRESH_DN(h) \
317 (h->hh.count == 0 || \
318 h->hh.arraysz - h->hh.count > (h->hh.count + 1024) / 2)
320 #define PREDECL_HEAP(prefix) \
321 struct prefix ## _head { struct heap_head hh; }; \
322 struct prefix ## _item { struct heap_item hi; };
324 #define INIT_HEAP(var) { }
326 #define DECLARE_HEAP(prefix, type, field, cmpfn) \
328 macro_inline void prefix ## _init(struct prefix##_head *h) \
330 memset(h, 0, sizeof(*h)); \
332 macro_inline void prefix ## _fini(struct prefix##_head *h) \
334 assert(h->hh.count == 0); \
335 memset(h, 0, sizeof(*h)); \
337 macro_inline int prefix ## __cmp(const struct heap_item *a, \
338 const struct heap_item *b) \
340 return cmpfn(container_of(a, type, field.hi), \
341 container_of(b, type, field.hi)); \
343 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
345 if (HEAP_RESIZE_TRESH_UP(h)) \
346 typesafe_heap_resize(&h->hh, true); \
347 typesafe_heap_pullup(&h->hh, h->hh.count, &item->field.hi, \
352 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
354 struct heap_item *other; \
355 uint32_t index = item->field.hi.index; \
356 assert(h->hh.array[index] == &item->field.hi); \
358 other = h->hh.array[h->hh.count]; \
359 if (cmpfn(container_of(other, type, field.hi), item) < 0) \
360 typesafe_heap_pullup(&h->hh, index, other, prefix ## __cmp); \
362 typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \
363 if (HEAP_RESIZE_TRESH_DN(h)) \
364 typesafe_heap_resize(&h->hh, false); \
367 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
369 struct heap_item *hitem, *other; \
370 if (h->hh.count == 0) \
372 hitem = h->hh.array[0]; \
374 other = h->hh.array[h->hh.count]; \
375 typesafe_heap_pushdown(&h->hh, 0, other, prefix ## __cmp); \
376 if (HEAP_RESIZE_TRESH_DN(h)) \
377 typesafe_heap_resize(&h->hh, false); \
378 return container_of(hitem, type, field.hi); \
380 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
382 if (h->hh.count == 0) \
384 return container_of(h->hh.array[0], type, field.hi); \
386 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
389 uint32_t idx = item->field.hi.index + 1; \
390 if (idx >= h->hh.count) \
392 return container_of(h->hh.array[idx], type, field.hi); \
394 TYPESAFE_FIRST_NEXT(prefix, type) \
395 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
399 return prefix ## _next(h, item); \
401 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
403 return h->hh.count; \
407 extern void typesafe_heap_resize(struct heap_head
*head
, bool grow
);
408 extern void typesafe_heap_pushdown(struct heap_head
*head
, uint32_t index
,
409 struct heap_item
*item
,
410 int (*cmpfn
)(const struct heap_item
*a
,
411 const struct heap_item
*b
));
412 extern void typesafe_heap_pullup(struct heap_head
*head
, uint32_t index
,
413 struct heap_item
*item
,
414 int (*cmpfn
)(const struct heap_item
*a
,
415 const struct heap_item
*b
));
417 /* single-linked list, sorted.
418 * can be used as priority queue with add / pop
421 /* don't use these structs directly */
423 struct ssort_item
*next
;
427 struct ssort_item
*first
;
433 * PREDECL_SORTLIST(namelist)
435 * struct namelist_item nlitem;
437 * DECLARE_SORTLIST(namelist, struct name, nlitem)
439 #define _PREDECL_SORTLIST(prefix) \
440 struct prefix ## _head { struct ssort_head sh; }; \
441 struct prefix ## _item { struct ssort_item si; };
443 #define INIT_SORTLIST_UNIQ(var) { }
444 #define INIT_SORTLIST_NONUNIQ(var) { }
446 #define PREDECL_SORTLIST_UNIQ(prefix) \
447 _PREDECL_SORTLIST(prefix)
448 #define PREDECL_SORTLIST_NONUNIQ(prefix) \
449 _PREDECL_SORTLIST(prefix)
451 #define _DECLARE_SORTLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
453 macro_inline void prefix ## _init(struct prefix##_head *h) \
455 memset(h, 0, sizeof(*h)); \
457 macro_inline void prefix ## _fini(struct prefix##_head *h) \
459 memset(h, 0, sizeof(*h)); \
461 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
463 struct ssort_item **np = &h->sh.first; \
465 while (*np && (c = cmpfn_uq( \
466 container_of(*np, type, field.si), item)) < 0) \
469 return container_of(*np, type, field.si); \
470 item->field.si.next = *np; \
471 *np = &item->field.si; \
475 macro_inline const type *prefix ## _const_find_gteq( \
476 const struct prefix##_head *h, const type *item) \
478 const struct ssort_item *sitem = h->sh.first; \
480 while (sitem && (cmpval = cmpfn_nuq( \
481 container_of(sitem, type, field.si), item)) < 0) \
482 sitem = sitem->next; \
483 return container_of_null(sitem, type, field.si); \
485 macro_inline const type *prefix ## _const_find_lt( \
486 const struct prefix##_head *h, const type *item) \
488 const struct ssort_item *prev = NULL, *sitem = h->sh.first; \
490 while (sitem && (cmpval = cmpfn_nuq( \
491 container_of(sitem, type, field.si), item)) < 0) \
492 sitem = (prev = sitem)->next; \
493 return container_of_null(prev, type, field.si); \
495 TYPESAFE_FIND_CMP(prefix, type) \
496 /* TODO: del_hint */ \
497 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
499 struct ssort_item **iter = &h->sh.first; \
500 while (*iter && *iter != &item->field.si) \
501 iter = &(*iter)->next; \
505 *iter = item->field.si.next; \
508 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
510 struct ssort_item *sitem = h->sh.first; \
514 h->sh.first = sitem->next; \
515 return container_of(sitem, type, field.si); \
517 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
519 return container_of_null(h->sh.first, type, field.si); \
521 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
524 const struct ssort_item *sitem = &item->field.si; \
525 return container_of_null(sitem->next, type, field.si); \
527 TYPESAFE_FIRST_NEXT(prefix, type) \
528 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
530 struct ssort_item *sitem; \
533 sitem = &item->field.si; \
534 return container_of_null(sitem->next, type, field.si); \
536 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
538 return h->sh.count; \
542 #define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \
543 _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn) \
545 macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
548 const struct ssort_item *sitem = h->sh.first; \
550 while (sitem && (cmpval = cmpfn( \
551 container_of(sitem, type, field.si), item)) < 0) \
552 sitem = sitem->next; \
553 if (!sitem || cmpval > 0) \
555 return container_of(sitem, type, field.si); \
557 TYPESAFE_FIND(prefix, type) \
560 #define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \
561 macro_inline int _ ## prefix ## _cmp(const type *a, const type *b) \
563 int cmpval = cmpfn(a, b); \
572 _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp) \
576 /* hash, "sorted" by hash value
579 /* don't use these structs directly */
581 struct thash_item
*next
;
586 struct thash_item
**entries
;
590 uint8_t minshift
, maxshift
;
593 #define _HASH_SIZE(tabshift) \
594 ((1U << (tabshift)) >> 1)
595 #define HASH_SIZE(head) \
596 _HASH_SIZE((head).tabshift)
597 #define _HASH_KEY(tabshift, val) \
598 ((val) >> (33 - (tabshift)))
599 #define HASH_KEY(head, val) \
600 _HASH_KEY((head).tabshift, val)
601 #define HASH_GROW_THRESHOLD(head) \
602 ((head).count >= HASH_SIZE(head))
603 #define HASH_SHRINK_THRESHOLD(head) \
604 ((head).count <= (HASH_SIZE(head) - 1) / 2)
606 extern void typesafe_hash_grow(struct thash_head
*head
);
607 extern void typesafe_hash_shrink(struct thash_head
*head
);
611 * PREDECL_HASH(namelist)
613 * struct namelist_item nlitem;
615 * DECLARE_HASH(namelist, struct name, nlitem, cmpfunc, hashfunc)
617 #define PREDECL_HASH(prefix) \
618 struct prefix ## _head { struct thash_head hh; }; \
619 struct prefix ## _item { struct thash_item hi; };
621 #define INIT_HASH(var) { }
623 #define DECLARE_HASH(prefix, type, field, cmpfn, hashfn) \
625 macro_inline void prefix ## _init(struct prefix##_head *h) \
627 memset(h, 0, sizeof(*h)); \
629 macro_inline void prefix ## _fini(struct prefix##_head *h) \
631 assert(h->hh.count == 0); \
632 h->hh.minshift = 0; \
633 typesafe_hash_shrink(&h->hh); \
634 memset(h, 0, sizeof(*h)); \
636 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
639 if (!h->hh.tabshift || HASH_GROW_THRESHOLD(h->hh)) \
640 typesafe_hash_grow(&h->hh); \
642 uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \
643 item->field.hi.hashval = hval; \
644 struct thash_item **np = &h->hh.entries[hbits]; \
645 while (*np && (*np)->hashval < hval) \
647 if (*np && cmpfn(container_of(*np, type, field.hi), item) == 0) { \
649 return container_of(*np, type, field.hi); \
651 item->field.hi.next = *np; \
652 *np = &item->field.hi; \
655 macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
658 if (!h->hh.tabshift) \
660 uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \
661 const struct thash_item *hitem = h->hh.entries[hbits]; \
662 while (hitem && hitem->hashval < hval) \
663 hitem = hitem->next; \
664 while (hitem && hitem->hashval == hval) { \
665 if (!cmpfn(container_of(hitem, type, field.hi), item)) \
666 return container_of(hitem, type, field.hi); \
667 hitem = hitem->next; \
671 TYPESAFE_FIND(prefix, type) \
672 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
674 if (!h->hh.tabshift) \
676 uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
677 struct thash_item **np = &h->hh.entries[hbits]; \
678 while (*np && (*np)->hashval < hval) \
680 while (*np && *np != &item->field.hi && (*np)->hashval == hval) \
682 if (*np != &item->field.hi) \
684 *np = item->field.hi.next; \
685 item->field.hi.next = NULL; \
687 if (HASH_SHRINK_THRESHOLD(h->hh)) \
688 typesafe_hash_shrink(&h->hh); \
691 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
694 for (i = 0; i < HASH_SIZE(h->hh); i++) \
695 if (h->hh.entries[i]) { \
696 struct thash_item *hitem = h->hh.entries[i]; \
697 h->hh.entries[i] = hitem->next; \
699 hitem->next = NULL; \
700 if (HASH_SHRINK_THRESHOLD(h->hh)) \
701 typesafe_hash_shrink(&h->hh); \
702 return container_of(hitem, type, field.hi); \
706 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
709 for (i = 0; i < HASH_SIZE(h->hh); i++) \
710 if (h->hh.entries[i]) \
711 return container_of(h->hh.entries[i], type, field.hi); \
714 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
717 const struct thash_item *hitem = &item->field.hi; \
719 return container_of(hitem->next, type, field.hi); \
720 uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1; \
721 for (; i < HASH_SIZE(h->hh); i++) \
722 if (h->hh.entries[i]) \
723 return container_of(h->hh.entries[i], type, field.hi); \
726 TYPESAFE_FIRST_NEXT(prefix, type) \
727 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
731 return prefix ## _next(h, item); \
733 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
735 return h->hh.count; \
740 * can be used as priority queue with add / pop
743 /* don't use these structs directly */
744 #define SKIPLIST_MAXDEPTH 16
745 #define SKIPLIST_EMBED 4
746 #define SKIPLIST_OVERFLOW (SKIPLIST_EMBED - 1)
749 struct sskip_item
*next
[SKIPLIST_EMBED
];
752 struct sskip_overflow
{
753 struct sskip_item
*next
[SKIPLIST_MAXDEPTH
- SKIPLIST_OVERFLOW
];
757 struct sskip_item hitem
;
758 struct sskip_item
*overflow
[SKIPLIST_MAXDEPTH
- SKIPLIST_OVERFLOW
];
764 * PREDECL_SKIPLIST(namelist)
766 * struct namelist_item nlitem;
768 * DECLARE_SKIPLIST(namelist, struct name, nlitem, cmpfunc)
770 #define _PREDECL_SKIPLIST(prefix) \
771 struct prefix ## _head { struct sskip_head sh; }; \
772 struct prefix ## _item { struct sskip_item si; };
774 #define INIT_SKIPLIST_UNIQ(var) { }
775 #define INIT_SKIPLIST_NONUNIQ(var) { }
777 #define _DECLARE_SKIPLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
779 macro_inline void prefix ## _init(struct prefix##_head *h) \
781 memset(h, 0, sizeof(*h)); \
782 h->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \
783 ((uintptr_t)h->sh.overflow | 1); \
785 macro_inline void prefix ## _fini(struct prefix##_head *h) \
787 memset(h, 0, sizeof(*h)); \
789 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
791 struct sskip_item *si; \
792 si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq); \
793 return container_of_null(si, type, field.si); \
795 macro_inline const type *prefix ## _const_find_gteq( \
796 const struct prefix##_head *h, const type *item) \
798 const struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \
799 &item->field.si, cmpfn_nuq); \
800 return container_of_null(sitem, type, field.si); \
802 macro_inline const type *prefix ## _const_find_lt( \
803 const struct prefix##_head *h, const type *item) \
805 const struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \
806 &item->field.si, cmpfn_nuq); \
807 return container_of_null(sitem, type, field.si); \
809 TYPESAFE_FIND_CMP(prefix, type) \
810 macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
812 struct sskip_item *sitem = typesafe_skiplist_del(&h->sh, \
813 &item->field.si, cmpfn_uq); \
814 return container_of_null(sitem, type, field.si); \
816 macro_inline type *prefix ## _pop(struct prefix##_head *h) \
818 struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \
819 return container_of_null(sitem, type, field.si); \
821 macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
823 const struct sskip_item *first = h->sh.hitem.next[0]; \
824 return container_of_null(first, type, field.si); \
826 macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
829 const struct sskip_item *next = item->field.si.next[0]; \
830 return container_of_null(next, type, field.si); \
832 TYPESAFE_FIRST_NEXT(prefix, type) \
833 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
835 struct sskip_item *next; \
836 next = item ? item->field.si.next[0] : NULL; \
837 return container_of_null(next, type, field.si); \
839 macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
841 return h->sh.count; \
845 #define PREDECL_SKIPLIST_UNIQ(prefix) \
846 _PREDECL_SKIPLIST(prefix)
847 #define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn) \
849 macro_inline int prefix ## __cmp(const struct sskip_item *a, \
850 const struct sskip_item *b) \
852 return cmpfn(container_of(a, type, field.si), \
853 container_of(b, type, field.si)); \
855 macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
858 const struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \
859 &item->field.si, &prefix ## __cmp); \
860 return container_of_null(sitem, type, field.si); \
862 TYPESAFE_FIND(prefix, type) \
864 _DECLARE_SKIPLIST(prefix, type, field, \
865 prefix ## __cmp, prefix ## __cmp) \
868 #define PREDECL_SKIPLIST_NONUNIQ(prefix) \
869 _PREDECL_SKIPLIST(prefix)
870 #define DECLARE_SKIPLIST_NONUNIQ(prefix, type, field, cmpfn) \
872 macro_inline int prefix ## __cmp(const struct sskip_item *a, \
873 const struct sskip_item *b) \
875 return cmpfn(container_of(a, type, field.si), \
876 container_of(b, type, field.si)); \
878 macro_inline int prefix ## __cmp_uq(const struct sskip_item *a, \
879 const struct sskip_item *b) \
881 int cmpval = cmpfn(container_of(a, type, field.si), \
882 container_of(b, type, field.si)); \
892 _DECLARE_SKIPLIST(prefix, type, field, \
893 prefix ## __cmp, prefix ## __cmp_uq) \
897 extern struct sskip_item
*typesafe_skiplist_add(struct sskip_head
*head
,
898 struct sskip_item
*item
, int (*cmpfn
)(
899 const struct sskip_item
*a
,
900 const struct sskip_item
*b
));
901 extern const struct sskip_item
*typesafe_skiplist_find(
902 const struct sskip_head
*head
,
903 const struct sskip_item
*item
, int (*cmpfn
)(
904 const struct sskip_item
*a
,
905 const struct sskip_item
*b
));
906 extern const struct sskip_item
*typesafe_skiplist_find_gteq(
907 const struct sskip_head
*head
,
908 const struct sskip_item
*item
, int (*cmpfn
)(
909 const struct sskip_item
*a
,
910 const struct sskip_item
*b
));
911 extern const struct sskip_item
*typesafe_skiplist_find_lt(
912 const struct sskip_head
*head
,
913 const struct sskip_item
*item
, int (*cmpfn
)(
914 const struct sskip_item
*a
,
915 const struct sskip_item
*b
));
916 extern struct sskip_item
*typesafe_skiplist_del(
917 struct sskip_head
*head
, struct sskip_item
*item
, int (*cmpfn
)(
918 const struct sskip_item
*a
,
919 const struct sskip_item
*b
));
920 extern struct sskip_item
*typesafe_skiplist_pop(struct sskip_head
*head
);
926 /* this needs to stay at the end because both files include each other.
927 * the resolved order is typesafe.h before typerb.h
931 #endif /* _FRR_TYPESAFE_H */