]> 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 #13108 from opensourcerouting/clippy-string-warn
[mirror_frr.git] / lib / typesafe.h
CommitLineData
acddc0ed 1// SPDX-License-Identifier: ISC
abd71baa
DL		 2/*
3 * Copyright (c) 2016-2019 David Lamparter, for NetDEF, Inc.
abd71baa
DL		 4 */
5
6#ifndef _FRR_TYPESAFE_H
7#define _FRR_TYPESAFE_H
8
9#include <stddef.h>
10#include <stdint.h>
11#include <stdbool.h>
abd71baa
DL		 12#include "compiler.h"
13
eea3c899
RW		 14#ifdef __cplusplus
15extern "C" {
16#endif
17
abd71baa
DL		 18/* generic macros for all list-like types */
19
81fddbe7 20#define frr_each(prefix, head, item) \
abd71baa
DL		 21 for (item = prefix##_first(head); item; \
22 item = prefix##_next(head, item))
81fddbe7 23#define frr_each_safe(prefix, head, item) \
abd71baa
DL		 24 for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe = \
25 prefix##_next_safe(head, \
26 (item = prefix##_first(head))); \
27 item; \
28 item = prefix##_safe, \
29 prefix##_safe = prefix##_next_safe(head, prefix##_safe))
81fddbe7 30#define frr_each_from(prefix, head, item, from) \
abd71baa
DL		 31 for (item = from, from = prefix##_next_safe(head, item); \
32 item; \
33 item = from, from = prefix##_next_safe(head, from))
34
643ea83b
DL		 35/* reverse direction, only supported by a few containers */
36
37#define frr_rev_each(prefix, head, item) \
38 for (item = prefix##_last(head); item; \
39 item = prefix##_prev(head, item))
40#define frr_rev_each_safe(prefix, head, item) \
41 for (typeof(prefix##_prev_safe(head, NULL)) prefix##_safe = \
42 prefix##_prev_safe(head, \
43 (item = prefix##_last(head))); \
44 item; \
45 item = prefix##_safe, \
46 prefix##_safe = prefix##_prev_safe(head, prefix##_safe))
47#define frr_rev_each_from(prefix, head, item, from) \
48 for (item = from, from = prefix##_prev_safe(head, item); \
49 item; \
50 item = from, from = prefix##_prev_safe(head, from))
daf3441d
DL		 51
52/* non-const variants. these wrappers are the same for all the types, so
53 * bundle them together here.
54 */
55#define TYPESAFE_FIRST_NEXT(prefix, type) \
56macro_pure type *prefix ## _first(struct prefix##_head *h) \
57{ \
58 return (type *)prefix ## _const_first(h); \
59} \
60macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \
61{ \
62 return (type *)prefix ## _const_next(h, item); \
63} \
64/* ... */
643ea83b
DL		 65#define TYPESAFE_LAST_PREV(prefix, type) \
66macro_pure type *prefix ## _last(struct prefix##_head *h) \
67{ \
68 return (type *)prefix ## _const_last(h); \
69} \
70macro_pure type *prefix ## _prev(struct prefix##_head *h, type *item) \
71{ \
72 return (type *)prefix ## _const_prev(h, item); \
73} \
74/* ... */
daf3441d
DL		 75#define TYPESAFE_FIND(prefix, type) \
76macro_inline type *prefix ## _find(struct prefix##_head *h, \
77 const type *item) \
78{ \
79 return (type *)prefix ## _const_find(h, item); \
80} \
81/* ... */
82#define TYPESAFE_FIND_CMP(prefix, type) \
83macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \
84 const type *item) \
85{ \
86 return (type *)prefix ## _const_find_lt(h, item); \
87} \
88macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \
89 const type *item) \
90{ \
91 return (type *)prefix ## _const_find_gteq(h, item); \
92} \
93/* ... */
94
f45897e4
DL		 95/* *_member via find - when there is no better membership check than find() */
96#define TYPESAFE_MEMBER_VIA_FIND(prefix, type) \
97macro_inline bool prefix ## _member(struct prefix##_head *h, \
98 const type *item) \
99{ \
100 return item == prefix ## _const_find(h, item); \
101} \
102/* ... */
103
104/* *_member via find_gteq - same for non-unique containers */
105#define TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \
106macro_inline bool prefix ## _member(struct prefix##_head *h, \
107 const type *item) \
108{ \
109 const type *iter; \
110 for (iter = prefix ## _const_find_gteq(h, item); iter; \
111 iter = prefix ## _const_next(h, iter)) { \
112 if (iter == item) \
113 return true; \
114 if (cmpfn(iter, item) > 0) \
115 break; \
116 } \
117 return false; \
118} \
119/* ... */
120
507e0e5d 121/* SWAP_ALL_SIMPLE = for containers where the items don't point back to the
f45897e4 122 * head *AND* the head doesn't point to itself (= everything except LIST,
507e0e5d
DL		 123 * DLIST and SKIPLIST), just switch out the entire head
124 */
125#define TYPESAFE_SWAP_ALL_SIMPLE(prefix) \
126macro_inline void prefix ## _swap_all(struct prefix##_head *a, \
127 struct prefix##_head *b) \
128{ \
129 struct prefix##_head tmp = *a; \
130 *a = *b; \
131 *b = tmp; \
132} \
133/* ... */
daf3441d 134
abd71baa
DL		 135/* single-linked list, unsorted/arbitrary.
136 * can be used as queue with add_tail / pop
137 */
138
139/* don't use these structs directly */
140struct slist_item {
141 struct slist_item *next;
142};
143
144struct slist_head {
145 struct slist_item *first, **last_next;
146 size_t count;
147};
148
d259ca09
DL		 149/* this replaces NULL as the value for ->next on the last item. */
150extern struct slist_item typesafe_slist_sentinel;
151#define _SLIST_LAST &typesafe_slist_sentinel
152
abd71baa
DL		 153static inline void typesafe_list_add(struct slist_head *head,
154 struct slist_item **pos, struct slist_item *item)
155{
156 item->next = *pos;
157 *pos = item;
158 if (pos == head->last_next)
159 head->last_next = &item->next;
160 head->count++;
161}
162
f45897e4
DL		 163extern bool typesafe_list_member(const struct slist_head *head,
164 const struct slist_item *item);
165
abd71baa
DL		 166/* use as:
167 *
960b9a53 168 * PREDECL_LIST(namelist);
abd71baa
DL		 169 * struct name {
170 * struct namelist_item nlitem;
171 * }
960b9a53 172 * DECLARE_LIST(namelist, struct name, nlitem);
abd71baa
DL		 173 */
174#define PREDECL_LIST(prefix) \
175struct prefix ## _head { struct slist_head sh; }; \
960b9a53
DL		 176struct prefix ## _item { struct slist_item si; }; \
177MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 178
179#define INIT_LIST(var) { .sh = { .last_next = &var.sh.first, }, }
180
181#define DECLARE_LIST(prefix, type, field) \
182 \
183macro_inline void prefix ## _init(struct prefix##_head *h) \
184{ \
185 memset(h, 0, sizeof(*h)); \
d259ca09 186 h->sh.first = _SLIST_LAST; \
abd71baa
DL		 187 h->sh.last_next = &h->sh.first; \
188} \
189macro_inline void prefix ## _fini(struct prefix##_head *h) \
190{ \
191 memset(h, 0, sizeof(*h)); \
192} \
193macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
194{ \
195 typesafe_list_add(&h->sh, &h->sh.first, &item->field.si); \
196} \
197macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
198{ \
199 typesafe_list_add(&h->sh, h->sh.last_next, &item->field.si); \
200} \
201macro_inline void prefix ## _add_after(struct prefix##_head *h, \
202 type *after, type *item) \
203{ \
204 struct slist_item **nextp; \
205 nextp = after ? &after->field.si.next : &h->sh.first; \
206 typesafe_list_add(&h->sh, nextp, &item->field.si); \
207} \
208/* TODO: del_hint */ \
da098d78 209macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa
DL		 210{ \
211 struct slist_item **iter = &h->sh.first; \
d259ca09 212 while (*iter != _SLIST_LAST && *iter != &item->field.si) \
abd71baa 213 iter = &(*iter)->next; \
d259ca09 214 if (*iter == _SLIST_LAST) \
da098d78 215 return NULL; \
abd71baa
DL		 216 h->sh.count--; \
217 *iter = item->field.si.next; \
d259ca09 218 if (item->field.si.next == _SLIST_LAST) \
abd71baa 219 h->sh.last_next = iter; \
4a1b3289 220 item->field.si.next = NULL; \
da098d78 221 return item; \
abd71baa
DL		 222} \
223macro_inline type *prefix ## _pop(struct prefix##_head *h) \
224{ \
225 struct slist_item *sitem = h->sh.first; \
d259ca09 226 if (sitem == _SLIST_LAST) \
abd71baa
DL		 227 return NULL; \
228 h->sh.count--; \
229 h->sh.first = sitem->next; \
d259ca09 230 if (h->sh.first == _SLIST_LAST) \
abd71baa 231 h->sh.last_next = &h->sh.first; \
4a1b3289 232 sitem->next = NULL; \
abd71baa
DL		 233 return container_of(sitem, type, field.si); \
234} \
507e0e5d
DL		 235macro_inline void prefix ## _swap_all(struct prefix##_head *a, \
236 struct prefix##_head *b) \
237{ \
238 struct prefix##_head tmp = *a; \
239 *a = *b; \
240 *b = tmp; \
241 if (a->sh.last_next == &b->sh.first) \
242 a->sh.last_next = &a->sh.first; \
243 if (b->sh.last_next == &a->sh.first) \
244 b->sh.last_next = &b->sh.first; \
245} \
daf3441d 246macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
abd71baa 247{ \
d259ca09
DL		 248 if (h->sh.first != _SLIST_LAST) \
249 return container_of(h->sh.first, type, field.si); \
250 return NULL; \
abd71baa 251} \
daf3441d
DL		 252macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
253 const type *item) \
abd71baa 254{ \
daf3441d 255 const struct slist_item *sitem = &item->field.si; \
d259ca09
DL		 256 if (sitem->next != _SLIST_LAST) \
257 return container_of(sitem->next, type, field.si); \
258 return NULL; \
abd71baa 259} \
daf3441d 260TYPESAFE_FIRST_NEXT(prefix, type) \
abd71baa
DL		 261macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
262{ \
263 struct slist_item *sitem; \
264 if (!item) \
265 return NULL; \
266 sitem = &item->field.si; \
d259ca09
DL		 267 if (sitem->next != _SLIST_LAST) \
268 return container_of(sitem->next, type, field.si); \
269 return NULL; \
abd71baa 270} \
0ca16c58 271macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 272{ \
273 return h->sh.count; \
274} \
40ee228d
DL		 275macro_pure bool prefix ## _anywhere(const type *item) \
276{ \
277 return item->field.si.next != NULL; \
278} \
f45897e4
DL		 279macro_pure bool prefix ## _member(const struct prefix##_head *h, \
280 const type *item) \
281{ \
282 return typesafe_list_member(&h->sh, &item->field.si); \
283} \
960b9a53 284MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa 285
fdad523b
DL		 286/* don't use these structs directly */
287struct dlist_item {
288 struct dlist_item *next;
289 struct dlist_item *prev;
290};
291
292struct dlist_head {
293 struct dlist_item hitem;
294 size_t count;
295};
296
297static inline void typesafe_dlist_add(struct dlist_head *head,
298 struct dlist_item *prev, struct dlist_item *item)
299{
255a76a5
DL		 300 /* SA on clang-11 thinks this can happen, but in reality -assuming no
301 * memory corruption- it can't. DLIST uses a "closed" ring, i.e. the
302 * termination at the end of the list is not NULL but rather a pointer
303 * back to the head. (This eliminates special-casing the first or last
304 * item.)
305 *
306 * Sadly, can't use assert() here since the libfrr assert / xref code
307 * uses typesafe lists itself... that said, if an assert tripped here
308 * we'd already be way past some memory corruption, so we might as
309 * well just take the SEGV. (In the presence of corruption, we'd see
310 * random SEGVs from places that make no sense at all anyway, an
311 * assert might actually be a red herring.)
312 *
313 * ("assume()" tells the compiler to produce code as if the condition
314 * will always hold; it doesn't have any actual effect here, it'll
315 * just SEGV out on "item->next->prev = item".)
316 */
317 assume(prev->next != NULL);
318
fdad523b 319 item->next = prev->next;
255a76a5 320 item->next->prev = item;
fdad523b
DL		 321 item->prev = prev;
322 prev->next = item;
323 head->count++;
324}
325
507e0e5d
DL		 326static inline void typesafe_dlist_swap_all(struct dlist_head *a,
327 struct dlist_head *b)
328{
329 struct dlist_head tmp = *a;
330
331 a->count = b->count;
332 if (a->count) {
333 a->hitem.next = b->hitem.next;
334 a->hitem.prev = b->hitem.prev;
335 a->hitem.next->prev = &a->hitem;
336 a->hitem.prev->next = &a->hitem;
337 } else {
338 a->hitem.next = &a->hitem;
339 a->hitem.prev = &a->hitem;
340 }
341
342 b->count = tmp.count;
343 if (b->count) {
344 b->hitem.next = tmp.hitem.next;
345 b->hitem.prev = tmp.hitem.prev;
346 b->hitem.next->prev = &b->hitem;
347 b->hitem.prev->next = &b->hitem;
348 } else {
349 b->hitem.next = &b->hitem;
350 b->hitem.prev = &b->hitem;
351 }
352}
353
f45897e4
DL		 354extern bool typesafe_dlist_member(const struct dlist_head *head,
355 const struct dlist_item *item);
356
fdad523b
DL		 357/* double-linked list, for fast item deletion
358 */
359#define PREDECL_DLIST(prefix) \
360struct prefix ## _head { struct dlist_head dh; }; \
960b9a53
DL		 361struct prefix ## _item { struct dlist_item di; }; \
362MACRO_REQUIRE_SEMICOLON() /* end */
fdad523b
DL		 363
364#define INIT_DLIST(var) { .dh = { \
365 .hitem = { &var.dh.hitem, &var.dh.hitem }, }, }
366
367#define DECLARE_DLIST(prefix, type, field) \
368 \
369macro_inline void prefix ## _init(struct prefix##_head *h) \
370{ \
371 memset(h, 0, sizeof(*h)); \
372 h->dh.hitem.prev = &h->dh.hitem; \
373 h->dh.hitem.next = &h->dh.hitem; \
374} \
375macro_inline void prefix ## _fini(struct prefix##_head *h) \
376{ \
377 memset(h, 0, sizeof(*h)); \
378} \
379macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \
380{ \
381 typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di); \
382} \
383macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \
384{ \
385 typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di); \
386} \
387macro_inline void prefix ## _add_after(struct prefix##_head *h, \
388 type *after, type *item) \
389{ \
390 struct dlist_item *prev; \
391 prev = after ? &after->field.di : &h->dh.hitem; \
392 typesafe_dlist_add(&h->dh, prev, &item->field.di); \
393} \
da098d78 394macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
fdad523b
DL		 395{ \
396 struct dlist_item *ditem = &item->field.di; \
397 ditem->prev->next = ditem->next; \
398 ditem->next->prev = ditem->prev; \
399 h->dh.count--; \
400 ditem->prev = ditem->next = NULL; \
da098d78 401 return item; \
fdad523b
DL		 402} \
403macro_inline type *prefix ## _pop(struct prefix##_head *h) \
404{ \
405 struct dlist_item *ditem = h->dh.hitem.next; \
406 if (ditem == &h->dh.hitem) \
407 return NULL; \
408 ditem->prev->next = ditem->next; \
409 ditem->next->prev = ditem->prev; \
410 h->dh.count--; \
4a1b3289 411 ditem->prev = ditem->next = NULL; \
fdad523b
DL		 412 return container_of(ditem, type, field.di); \
413} \
507e0e5d
DL		 414macro_inline void prefix ## _swap_all(struct prefix##_head *a, \
415 struct prefix##_head *b) \
416{ \
417 typesafe_dlist_swap_all(&a->dh, &b->dh); \
418} \
daf3441d 419macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
fdad523b 420{ \
daf3441d 421 const struct dlist_item *ditem = h->dh.hitem.next; \
fdad523b
DL		 422 if (ditem == &h->dh.hitem) \
423 return NULL; \
424 return container_of(ditem, type, field.di); \
425} \
daf3441d
DL		 426macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
427 const type *item) \
fdad523b 428{ \
daf3441d 429 const struct dlist_item *ditem = &item->field.di; \
fdad523b
DL		 430 if (ditem->next == &h->dh.hitem) \
431 return NULL; \
432 return container_of(ditem->next, type, field.di); \
433} \
daf3441d 434TYPESAFE_FIRST_NEXT(prefix, type) \
643ea83b
DL		 435macro_pure const type *prefix ## _const_last(const struct prefix##_head *h) \
436{ \
437 const struct dlist_item *ditem = h->dh.hitem.prev; \
438 if (ditem == &h->dh.hitem) \
439 return NULL; \
440 return container_of(ditem, type, field.di); \
441} \
442macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h, \
443 const type *item) \
444{ \
445 const struct dlist_item *ditem = &item->field.di; \
446 if (ditem->prev == &h->dh.hitem) \
447 return NULL; \
448 return container_of(ditem->prev, type, field.di); \
449} \
450TYPESAFE_LAST_PREV(prefix, type) \
fdad523b
DL		 451macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
452{ \
453 if (!item) \
454 return NULL; \
455 return prefix ## _next(h, item); \
456} \
643ea83b
DL		 457macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item) \
458{ \
459 if (!item) \
460 return NULL; \
461 return prefix ## _prev(h, item); \
462} \
0ca16c58 463macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
fdad523b
DL		 464{ \
465 return h->dh.count; \
466} \
40ee228d
DL		 467macro_pure bool prefix ## _anywhere(const type *item) \
468{ \
469 const struct dlist_item *ditem = &item->field.di; \
470 return ditem->next && ditem->prev; \
471} \
f45897e4
DL		 472macro_pure bool prefix ## _member(const struct prefix##_head *h, \
473 const type *item) \
474{ \
475 return typesafe_dlist_member(&h->dh, &item->field.di); \
476} \
960b9a53 477MACRO_REQUIRE_SEMICOLON() /* end */
fdad523b 478
5cb4277d
DL		 479/* note: heap currently caps out at 4G items */
480
481#define HEAP_NARY 8U
482typedef uint32_t heap_index_i;
483
484struct heap_item {
485 uint32_t index;
486};
487
488struct heap_head {
489 struct heap_item **array;
490 uint32_t arraysz, count;
491};
492
493#define HEAP_RESIZE_TRESH_UP(h) \
494 (h->hh.count + 1 >= h->hh.arraysz)
495#define HEAP_RESIZE_TRESH_DN(h) \
496 (h->hh.count == 0 || \
497 h->hh.arraysz - h->hh.count > (h->hh.count + 1024) / 2)
498
499#define PREDECL_HEAP(prefix) \
500struct prefix ## _head { struct heap_head hh; }; \
960b9a53
DL		 501struct prefix ## _item { struct heap_item hi; }; \
502MACRO_REQUIRE_SEMICOLON() /* end */
5cb4277d
DL		 503
504#define INIT_HEAP(var) { }
505
506#define DECLARE_HEAP(prefix, type, field, cmpfn) \
507 \
508macro_inline void prefix ## _init(struct prefix##_head *h) \
509{ \
510 memset(h, 0, sizeof(*h)); \
511} \
512macro_inline void prefix ## _fini(struct prefix##_head *h) \
513{ \
514 assert(h->hh.count == 0); \
515 memset(h, 0, sizeof(*h)); \
516} \
517macro_inline int prefix ## __cmp(const struct heap_item *a, \
518 const struct heap_item *b) \
519{ \
520 return cmpfn(container_of(a, type, field.hi), \
521 container_of(b, type, field.hi)); \
522} \
523macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
524{ \
525 if (HEAP_RESIZE_TRESH_UP(h)) \
526 typesafe_heap_resize(&h->hh, true); \
527 typesafe_heap_pullup(&h->hh, h->hh.count, &item->field.hi, \
528 prefix ## __cmp); \
529 h->hh.count++; \
530 return NULL; \
531} \
da098d78 532macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
5cb4277d
DL		 533{ \
534 struct heap_item *other; \
535 uint32_t index = item->field.hi.index; \
536 assert(h->hh.array[index] == &item->field.hi); \
537 h->hh.count--; \
538 other = h->hh.array[h->hh.count]; \
539 if (cmpfn(container_of(other, type, field.hi), item) < 0) \
540 typesafe_heap_pullup(&h->hh, index, other, prefix ## __cmp); \
541 else \
542 typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \
543 if (HEAP_RESIZE_TRESH_DN(h)) \
544 typesafe_heap_resize(&h->hh, false); \
da098d78 545 return item; \
5cb4277d
DL		 546} \
547macro_inline type *prefix ## _pop(struct prefix##_head *h) \
548{ \
549 struct heap_item *hitem, *other; \
550 if (h->hh.count == 0) \
551 return NULL; \
552 hitem = h->hh.array[0]; \
553 h->hh.count--; \
554 other = h->hh.array[h->hh.count]; \
555 typesafe_heap_pushdown(&h->hh, 0, other, prefix ## __cmp); \
556 if (HEAP_RESIZE_TRESH_DN(h)) \
557 typesafe_heap_resize(&h->hh, false); \
558 return container_of(hitem, type, field.hi); \
559} \
507e0e5d 560TYPESAFE_SWAP_ALL_SIMPLE(prefix) \
daf3441d 561macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
5cb4277d
DL		 562{ \
563 if (h->hh.count == 0) \
564 return NULL; \
565 return container_of(h->hh.array[0], type, field.hi); \
566} \
daf3441d
DL		 567macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
568 const type *item) \
5cb4277d
DL		 569{ \
570 uint32_t idx = item->field.hi.index + 1; \
571 if (idx >= h->hh.count) \
572 return NULL; \
573 return container_of(h->hh.array[idx], type, field.hi); \
574} \
daf3441d 575TYPESAFE_FIRST_NEXT(prefix, type) \
5cb4277d
DL		 576macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
577{ \
578 if (!item) \
579 return NULL; \
580 return prefix ## _next(h, item); \
581} \
0ca16c58 582macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
5cb4277d
DL		 583{ \
584 return h->hh.count; \
585} \
f45897e4
DL		 586macro_pure bool prefix ## _member(const struct prefix##_head *h, \
587 const type *item) \
588{ \
589 uint32_t idx = item->field.hi.index; \
590 if (idx >= h->hh.count) \
591 return false; \
592 return h->hh.array[idx] == &item->field.hi; \
593} \
960b9a53 594MACRO_REQUIRE_SEMICOLON() /* end */
5cb4277d
DL		 595
596extern void typesafe_heap_resize(struct heap_head *head, bool grow);
597extern void typesafe_heap_pushdown(struct heap_head *head, uint32_t index,
598 struct heap_item *item,
599 int (*cmpfn)(const struct heap_item *a,
600 const struct heap_item *b));
601extern void typesafe_heap_pullup(struct heap_head *head, uint32_t index,
602 struct heap_item *item,
603 int (*cmpfn)(const struct heap_item *a,
604 const struct heap_item *b));
605
abd71baa
DL		 606/* single-linked list, sorted.
607 * can be used as priority queue with add / pop
608 */
609
610/* don't use these structs directly */
611struct ssort_item {
612 struct ssort_item *next;
613};
614
615struct ssort_head {
616 struct ssort_item *first;
617 size_t count;
618};
619
620/* use as:
621 *
622 * PREDECL_SORTLIST(namelist)
623 * struct name {
624 * struct namelist_item nlitem;
625 * }
626 * DECLARE_SORTLIST(namelist, struct name, nlitem)
627 */
628#define _PREDECL_SORTLIST(prefix) \
629struct prefix ## _head { struct ssort_head sh; }; \
960b9a53
DL		 630struct prefix ## _item { struct ssort_item si; }; \
631MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 632
633#define INIT_SORTLIST_UNIQ(var) { }
634#define INIT_SORTLIST_NONUNIQ(var) { }
635
636#define PREDECL_SORTLIST_UNIQ(prefix) \
637 _PREDECL_SORTLIST(prefix)
638#define PREDECL_SORTLIST_NONUNIQ(prefix) \
639 _PREDECL_SORTLIST(prefix)
640
641#define _DECLARE_SORTLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
642 \
643macro_inline void prefix ## _init(struct prefix##_head *h) \
644{ \
645 memset(h, 0, sizeof(*h)); \
646} \
647macro_inline void prefix ## _fini(struct prefix##_head *h) \
648{ \
649 memset(h, 0, sizeof(*h)); \
650} \
651macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
652{ \
653 struct ssort_item **np = &h->sh.first; \
654 int c = 1; \
655 while (*np && (c = cmpfn_uq( \
656 container_of(*np, type, field.si), item)) < 0) \
657 np = &(*np)->next; \
658 if (c == 0) \
659 return container_of(*np, type, field.si); \
660 item->field.si.next = *np; \
661 *np = &item->field.si; \
662 h->sh.count++; \
663 return NULL; \
664} \
daf3441d
DL		 665macro_inline const type *prefix ## _const_find_gteq( \
666 const struct prefix##_head *h, const type *item) \
abd71baa 667{ \
daf3441d 668 const struct ssort_item *sitem = h->sh.first; \
abd71baa
DL		 669 int cmpval = 0; \
670 while (sitem && (cmpval = cmpfn_nuq( \
4d5cf6bc 671 container_of(sitem, type, field.si), item)) < 0) \
abd71baa
DL		 672 sitem = sitem->next; \
673 return container_of_null(sitem, type, field.si); \
674} \
daf3441d
DL		 675macro_inline const type *prefix ## _const_find_lt( \
676 const struct prefix##_head *h, const type *item) \
abd71baa 677{ \
daf3441d 678 const struct ssort_item *prev = NULL, *sitem = h->sh.first; \
abd71baa
DL		 679 int cmpval = 0; \
680 while (sitem && (cmpval = cmpfn_nuq( \
4d5cf6bc 681 container_of(sitem, type, field.si), item)) < 0) \
abd71baa
DL		 682 sitem = (prev = sitem)->next; \
683 return container_of_null(prev, type, field.si); \
684} \
daf3441d 685TYPESAFE_FIND_CMP(prefix, type) \
abd71baa 686/* TODO: del_hint */ \
da098d78 687macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa
DL		 688{ \
689 struct ssort_item **iter = &h->sh.first; \
690 while (*iter && *iter != &item->field.si) \
691 iter = &(*iter)->next; \
692 if (!*iter) \
da098d78 693 return NULL; \
abd71baa
DL		 694 h->sh.count--; \
695 *iter = item->field.si.next; \
4a1b3289 696 item->field.si.next = NULL; \
da098d78 697 return item; \
abd71baa
DL		 698} \
699macro_inline type *prefix ## _pop(struct prefix##_head *h) \
700{ \
701 struct ssort_item *sitem = h->sh.first; \
702 if (!sitem) \
703 return NULL; \
704 h->sh.count--; \
705 h->sh.first = sitem->next; \
706 return container_of(sitem, type, field.si); \
707} \
507e0e5d 708TYPESAFE_SWAP_ALL_SIMPLE(prefix) \
daf3441d 709macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
abd71baa
DL		 710{ \
711 return container_of_null(h->sh.first, type, field.si); \
712} \
daf3441d
DL		 713macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
714 const type *item) \
abd71baa 715{ \
daf3441d 716 const struct ssort_item *sitem = &item->field.si; \
abd71baa
DL		 717 return container_of_null(sitem->next, type, field.si); \
718} \
daf3441d 719TYPESAFE_FIRST_NEXT(prefix, type) \
abd71baa
DL		 720macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
721{ \
722 struct ssort_item *sitem; \
723 if (!item) \
724 return NULL; \
725 sitem = &item->field.si; \
726 return container_of_null(sitem->next, type, field.si); \
727} \
0ca16c58 728macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 729{ \
730 return h->sh.count; \
731} \
960b9a53 732MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 733
734#define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \
960b9a53 735 _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn); \
daf3441d
DL		 736 \
737macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
738 const type *item) \
abd71baa 739{ \
daf3441d 740 const struct ssort_item *sitem = h->sh.first; \
abd71baa
DL		 741 int cmpval = 0; \
742 while (sitem && (cmpval = cmpfn( \
4d5cf6bc 743 container_of(sitem, type, field.si), item)) < 0) \
abd71baa
DL		 744 sitem = sitem->next; \
745 if (!sitem || cmpval > 0) \
746 return NULL; \
747 return container_of(sitem, type, field.si); \
748} \
daf3441d 749TYPESAFE_FIND(prefix, type) \
f45897e4 750TYPESAFE_MEMBER_VIA_FIND(prefix, type) \
960b9a53 751MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 752
753#define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \
754macro_inline int _ ## prefix ## _cmp(const type *a, const type *b) \
755{ \
756 int cmpval = cmpfn(a, b); \
757 if (cmpval) \
758 return cmpval; \
759 if (a < b) \
760 return -1; \
761 if (a > b) \
762 return 1; \
763 return 0; \
764} \
960b9a53 765 _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp); \
f45897e4 766TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \
960b9a53 767MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 768
769
770/* hash, "sorted" by hash value
771 */
772
773/* don't use these structs directly */
774struct thash_item {
775 struct thash_item *next;
776 uint32_t hashval;
777};
778
779struct thash_head {
780 struct thash_item **entries;
781 uint32_t count;
782
783 uint8_t tabshift;
784 uint8_t minshift, maxshift;
785};
786
787#define _HASH_SIZE(tabshift) \
788 ((1U << (tabshift)) >> 1)
789#define HASH_SIZE(head) \
790 _HASH_SIZE((head).tabshift)
791#define _HASH_KEY(tabshift, val) \
792 ((val) >> (33 - (tabshift)))
793#define HASH_KEY(head, val) \
794 _HASH_KEY((head).tabshift, val)
795#define HASH_GROW_THRESHOLD(head) \
796 ((head).count >= HASH_SIZE(head))
797#define HASH_SHRINK_THRESHOLD(head) \
798 ((head).count <= (HASH_SIZE(head) - 1) / 2)
799
800extern void typesafe_hash_grow(struct thash_head *head);
801extern void typesafe_hash_shrink(struct thash_head *head);
802
803/* use as:
804 *
805 * PREDECL_HASH(namelist)
806 * struct name {
807 * struct namelist_item nlitem;
808 * }
809 * DECLARE_HASH(namelist, struct name, nlitem, cmpfunc, hashfunc)
810 */
811#define PREDECL_HASH(prefix) \
812struct prefix ## _head { struct thash_head hh; }; \
960b9a53
DL		 813struct prefix ## _item { struct thash_item hi; }; \
814MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 815
816#define INIT_HASH(var) { }
817
818#define DECLARE_HASH(prefix, type, field, cmpfn, hashfn) \
819 \
820macro_inline void prefix ## _init(struct prefix##_head *h) \
821{ \
822 memset(h, 0, sizeof(*h)); \
823} \
824macro_inline void prefix ## _fini(struct prefix##_head *h) \
825{ \
826 assert(h->hh.count == 0); \
827 h->hh.minshift = 0; \
828 typesafe_hash_shrink(&h->hh); \
829 memset(h, 0, sizeof(*h)); \
830} \
831macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
832{ \
833 h->hh.count++; \
834 if (!h->hh.tabshift || HASH_GROW_THRESHOLD(h->hh)) \
835 typesafe_hash_grow(&h->hh); \
836 \
837 uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \
838 item->field.hi.hashval = hval; \
839 struct thash_item **np = &h->hh.entries[hbits]; \
840 while (*np && (*np)->hashval < hval) \
841 np = &(*np)->next; \
5e0136c9
FD		 842 while (*np && (*np)->hashval == hval) { \
843 if (cmpfn(container_of(*np, type, field.hi), item) == 0) { \
844 h->hh.count--; \
845 return container_of(*np, type, field.hi); \
846 } \
847 np = &(*np)->next; \
abd71baa
DL		 848 } \
849 item->field.hi.next = *np; \
850 *np = &item->field.hi; \
851 return NULL; \
852} \
daf3441d
DL		 853macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
854 const type *item) \
abd71baa
DL		 855{ \
856 if (!h->hh.tabshift) \
857 return NULL; \
858 uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \
daf3441d 859 const struct thash_item *hitem = h->hh.entries[hbits]; \
abd71baa
DL		 860 while (hitem && hitem->hashval < hval) \
861 hitem = hitem->next; \
862 while (hitem && hitem->hashval == hval) { \
863 if (!cmpfn(container_of(hitem, type, field.hi), item)) \
864 return container_of(hitem, type, field.hi); \
865 hitem = hitem->next; \
866 } \
867 return NULL; \
868} \
daf3441d 869TYPESAFE_FIND(prefix, type) \
da098d78 870macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa
DL		 871{ \
872 if (!h->hh.tabshift) \
da098d78 873 return NULL; \
abd71baa
DL		 874 uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
875 struct thash_item **np = &h->hh.entries[hbits]; \
876 while (*np && (*np)->hashval < hval) \
877 np = &(*np)->next; \
878 while (*np && *np != &item->field.hi && (*np)->hashval == hval) \
879 np = &(*np)->next; \
880 if (*np != &item->field.hi) \
da098d78 881 return NULL; \
abd71baa
DL		 882 *np = item->field.hi.next; \
883 item->field.hi.next = NULL; \
884 h->hh.count--; \
885 if (HASH_SHRINK_THRESHOLD(h->hh)) \
886 typesafe_hash_shrink(&h->hh); \
da098d78 887 return item; \
abd71baa
DL		 888} \
889macro_inline type *prefix ## _pop(struct prefix##_head *h) \
890{ \
891 uint32_t i; \
892 for (i = 0; i < HASH_SIZE(h->hh); i++) \
893 if (h->hh.entries[i]) { \
894 struct thash_item *hitem = h->hh.entries[i]; \
895 h->hh.entries[i] = hitem->next; \
896 h->hh.count--; \
897 hitem->next = NULL; \
898 if (HASH_SHRINK_THRESHOLD(h->hh)) \
899 typesafe_hash_shrink(&h->hh); \
900 return container_of(hitem, type, field.hi); \
901 } \
902 return NULL; \
903} \
507e0e5d 904TYPESAFE_SWAP_ALL_SIMPLE(prefix) \
daf3441d 905macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
abd71baa
DL		 906{ \
907 uint32_t i; \
908 for (i = 0; i < HASH_SIZE(h->hh); i++) \
909 if (h->hh.entries[i]) \
910 return container_of(h->hh.entries[i], type, field.hi); \
911 return NULL; \
912} \
daf3441d
DL		 913macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
914 const type *item) \
abd71baa 915{ \
daf3441d 916 const struct thash_item *hitem = &item->field.hi; \
abd71baa
DL		 917 if (hitem->next) \
918 return container_of(hitem->next, type, field.hi); \
919 uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1; \
daf3441d 920 for (; i < HASH_SIZE(h->hh); i++) \
abd71baa
DL		 921 if (h->hh.entries[i]) \
922 return container_of(h->hh.entries[i], type, field.hi); \
923 return NULL; \
924} \
daf3441d 925TYPESAFE_FIRST_NEXT(prefix, type) \
abd71baa
DL		 926macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
927{ \
928 if (!item) \
929 return NULL; \
930 return prefix ## _next(h, item); \
931} \
0ca16c58 932macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 933{ \
934 return h->hh.count; \
935} \
f45897e4
DL		 936macro_pure bool prefix ## _member(const struct prefix##_head *h, \
937 const type *item) \
938{ \
939 uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
940 const struct thash_item *hitem = h->hh.entries[hbits]; \
941 while (hitem && hitem->hashval < hval) \
942 hitem = hitem->next; \
943 for (hitem = h->hh.entries[hbits]; hitem && hitem->hashval <= hval; \
944 hitem = hitem->next) \
945 if (hitem == &item->field.hi) \
946 return true; \
947 return false; \
948} \
960b9a53 949MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 950
951/* skiplist, sorted.
952 * can be used as priority queue with add / pop
953 */
954
955/* don't use these structs directly */
956#define SKIPLIST_MAXDEPTH 16
957#define SKIPLIST_EMBED 4
958#define SKIPLIST_OVERFLOW (SKIPLIST_EMBED - 1)
959
960struct sskip_item {
961 struct sskip_item *next[SKIPLIST_EMBED];
962};
963
964struct sskip_overflow {
965 struct sskip_item *next[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW];
966};
967
968struct sskip_head {
969 struct sskip_item hitem;
970 struct sskip_item *overflow[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW];
971 size_t count;
972};
973
974/* use as:
975 *
976 * PREDECL_SKIPLIST(namelist)
977 * struct name {
978 * struct namelist_item nlitem;
979 * }
980 * DECLARE_SKIPLIST(namelist, struct name, nlitem, cmpfunc)
981 */
982#define _PREDECL_SKIPLIST(prefix) \
983struct prefix ## _head { struct sskip_head sh; }; \
960b9a53
DL		 984struct prefix ## _item { struct sskip_item si; }; \
985MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 986
987#define INIT_SKIPLIST_UNIQ(var) { }
988#define INIT_SKIPLIST_NONUNIQ(var) { }
989
990#define _DECLARE_SKIPLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \
991 \
992macro_inline void prefix ## _init(struct prefix##_head *h) \
993{ \
994 memset(h, 0, sizeof(*h)); \
995 h->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \
996 ((uintptr_t)h->sh.overflow | 1); \
997} \
998macro_inline void prefix ## _fini(struct prefix##_head *h) \
999{ \
1000 memset(h, 0, sizeof(*h)); \
1001} \
1002macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \
1003{ \
1004 struct sskip_item *si; \
1005 si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq); \
1006 return container_of_null(si, type, field.si); \
1007} \
daf3441d
DL		 1008macro_inline const type *prefix ## _const_find_gteq( \
1009 const struct prefix##_head *h, const type *item) \
abd71baa 1010{ \
daf3441d 1011 const struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \
abd71baa
DL		 1012 &item->field.si, cmpfn_nuq); \
1013 return container_of_null(sitem, type, field.si); \
1014} \
daf3441d
DL		 1015macro_inline const type *prefix ## _const_find_lt( \
1016 const struct prefix##_head *h, const type *item) \
abd71baa 1017{ \
daf3441d 1018 const struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \
abd71baa
DL		 1019 &item->field.si, cmpfn_nuq); \
1020 return container_of_null(sitem, type, field.si); \
1021} \
daf3441d 1022TYPESAFE_FIND_CMP(prefix, type) \
da098d78 1023macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \
abd71baa 1024{ \
da098d78
SW		 1025 struct sskip_item *sitem = typesafe_skiplist_del(&h->sh, \
1026 &item->field.si, cmpfn_uq); \
1027 return container_of_null(sitem, type, field.si); \
abd71baa
DL		 1028} \
1029macro_inline type *prefix ## _pop(struct prefix##_head *h) \
1030{ \
01734da3
DL		 1031 struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \
1032 return container_of_null(sitem, type, field.si); \
abd71baa 1033} \
507e0e5d
DL		 1034macro_inline void prefix ## _swap_all(struct prefix##_head *a, \
1035 struct prefix##_head *b) \
1036{ \
1037 struct prefix##_head tmp = *a; \
1038 *a = *b; \
1039 *b = tmp; \
1040 a->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \
1041 ((uintptr_t)a->sh.overflow | 1); \
1042 b->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \
1043 ((uintptr_t)b->sh.overflow | 1); \
1044} \
daf3441d 1045macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \
abd71baa 1046{ \
daf3441d 1047 const struct sskip_item *first = h->sh.hitem.next[0]; \
abd71baa
DL		 1048 return container_of_null(first, type, field.si); \
1049} \
daf3441d
DL		 1050macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \
1051 const type *item) \
abd71baa 1052{ \
daf3441d 1053 const struct sskip_item *next = item->field.si.next[0]; \
abd71baa
DL		 1054 return container_of_null(next, type, field.si); \
1055} \
daf3441d 1056TYPESAFE_FIRST_NEXT(prefix, type) \
abd71baa
DL		 1057macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
1058{ \
1059 struct sskip_item *next; \
1060 next = item ? item->field.si.next[0] : NULL; \
1061 return container_of_null(next, type, field.si); \
1062} \
0ca16c58 1063macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
abd71baa
DL		 1064{ \
1065 return h->sh.count; \
1066} \
960b9a53 1067MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 1068
1069#define PREDECL_SKIPLIST_UNIQ(prefix) \
1070 _PREDECL_SKIPLIST(prefix)
1071#define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn) \
daf3441d 1072 \
abd71baa
DL		 1073macro_inline int prefix ## __cmp(const struct sskip_item *a, \
1074 const struct sskip_item *b) \
1075{ \
1076 return cmpfn(container_of(a, type, field.si), \
1077 container_of(b, type, field.si)); \
1078} \
daf3441d
DL		 1079macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \
1080 const type *item) \
abd71baa 1081{ \
daf3441d 1082 const struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \
abd71baa
DL		 1083 &item->field.si, &prefix ## __cmp); \
1084 return container_of_null(sitem, type, field.si); \
1085} \
daf3441d 1086TYPESAFE_FIND(prefix, type) \
f45897e4 1087TYPESAFE_MEMBER_VIA_FIND(prefix, type) \
abd71baa
DL		 1088 \
1089_DECLARE_SKIPLIST(prefix, type, field, \
960b9a53
DL		 1090 prefix ## __cmp, prefix ## __cmp); \
1091MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 1092
1093#define PREDECL_SKIPLIST_NONUNIQ(prefix) \
1094 _PREDECL_SKIPLIST(prefix)
1095#define DECLARE_SKIPLIST_NONUNIQ(prefix, type, field, cmpfn) \
1096 \
1097macro_inline int prefix ## __cmp(const struct sskip_item *a, \
1098 const struct sskip_item *b) \
1099{ \
1100 return cmpfn(container_of(a, type, field.si), \
1101 container_of(b, type, field.si)); \
1102} \
1103macro_inline int prefix ## __cmp_uq(const struct sskip_item *a, \
1104 const struct sskip_item *b) \
1105{ \
1106 int cmpval = cmpfn(container_of(a, type, field.si), \
1107 container_of(b, type, field.si)); \
1108 if (cmpval) \
1109 return cmpval; \
1110 if (a < b) \
1111 return -1; \
1112 if (a > b) \
1113 return 1; \
1114 return 0; \
1115} \
1116 \
1117_DECLARE_SKIPLIST(prefix, type, field, \
960b9a53 1118 prefix ## __cmp, prefix ## __cmp_uq); \
f45897e4 1119TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \
960b9a53 1120MACRO_REQUIRE_SEMICOLON() /* end */
abd71baa
DL		 1121
1122
1123extern struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
1124 struct sskip_item *item, int (*cmpfn)(
1125 const struct sskip_item *a,
1126 const struct sskip_item *b));
daf3441d
DL		 1127extern const struct sskip_item *typesafe_skiplist_find(
1128 const struct sskip_head *head,
abd71baa
DL		 1129 const struct sskip_item *item, int (*cmpfn)(
1130 const struct sskip_item *a,
1131 const struct sskip_item *b));
daf3441d
DL		 1132extern const struct sskip_item *typesafe_skiplist_find_gteq(
1133 const struct sskip_head *head,
abd71baa
DL		 1134 const struct sskip_item *item, int (*cmpfn)(
1135 const struct sskip_item *a,
1136 const struct sskip_item *b));
daf3441d
DL		 1137extern const struct sskip_item *typesafe_skiplist_find_lt(
1138 const struct sskip_head *head,
abd71baa
DL		 1139 const struct sskip_item *item, int (*cmpfn)(
1140 const struct sskip_item *a,
1141 const struct sskip_item *b));
da098d78
SW		 1142extern struct sskip_item *typesafe_skiplist_del(
1143 struct sskip_head *head, struct sskip_item *item, int (*cmpfn)(
abd71baa
DL		 1144 const struct sskip_item *a,
1145 const struct sskip_item *b));
01734da3 1146extern struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head);
abd71baa 1147
eea3c899
RW		 1148#ifdef __cplusplus
1149}
1150#endif
1151
80911bc2
DL		 1152/* this needs to stay at the end because both files include each other.
1153 * the resolved order is typesafe.h before typerb.h
1154 */
1155#include "typerb.h"
1156
abd71baa 1157#endif /* _FRR_TYPESAFE_H */
FRRouting mirror