lib/typesafe.h

   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
  26 /* generic macros for all list-like types */
  27
  28 #define for_each(prefix, head, item)                                           \
  29         for (item = prefix##_first(head); item;                                \
  30                         item = prefix##_next(head, item))
  31 #define for_each_safe(prefix, head, item)                                      \
  32         for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe =            \
  33                         prefix##_next_safe(head,                               \
  34                                 (item = prefix##_first(head)));                \
  35                 item;                                                          \
  36                 item = prefix##_safe,                                          \
  37                         prefix##_safe = prefix##_next_safe(head, prefix##_safe))
  38 #define for_each_from(prefix, head, item, from)                                \
  39         for (item = from, from = prefix##_next_safe(head, item);               \
  40                 item;                                                          \
  41                 item = from, from = prefix##_next_safe(head, from))
  42
  43 /* single-linked list, unsorted/arbitrary.
  44  * can be used as queue with add_tail / pop
  45  */
  46
  47 /* don't use these structs directly */
  48 struct slist_item {
  49         struct slist_item *next;
  50 };
  51
  52 struct slist_head {
  53         struct slist_item *first, **last_next;
  54         size_t count;
  55 };
  56
  57 static inline void typesafe_list_add(struct slist_head *head,
  58                 struct slist_item **pos, struct slist_item *item)
  59 {
  60         item->next = *pos;
  61         *pos = item;
  62         if (pos == head->last_next)
  63                 head->last_next = &item->next;
  64         head->count++;
  65 }
  66
  67 /* use as:
  68  *
  69  * PREDECL_LIST(namelist)
  70  * struct name {
  71  *   struct namelist_item nlitem;
  72  * }
  73  * DECLARE_LIST(namelist, struct name, nlitem)
  74  */
  75 #define PREDECL_LIST(prefix)                                                   \
  76 struct prefix ## _head { struct slist_head sh; };                              \
  77 struct prefix ## _item { struct slist_item si; };
  78
  79 #define INIT_LIST(var) { .sh = { .last_next = &var.sh.first, }, }
  80
  81 #define DECLARE_LIST(prefix, type, field)                                      \
  82                                                                                \
  83 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
  84 {                                                                              \
  85         memset(h, 0, sizeof(*h));                                              \
  86         h->sh.last_next = &h->sh.first;                                        \
  87 }                                                                              \
  88 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
  89 {                                                                              \
  90         memset(h, 0, sizeof(*h));                                              \
  91 }                                                                              \
  92 macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item)     \
  93 {                                                                              \
  94         typesafe_list_add(&h->sh, &h->sh.first, &item->field.si);              \
  95 }                                                                              \
  96 macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item)     \
  97 {                                                                              \
  98         typesafe_list_add(&h->sh, h->sh.last_next, &item->field.si);           \
  99 }                                                                              \
 100 macro_inline void prefix ## _add_after(struct prefix##_head *h,                \
 101                 type *after, type *item)                                       \
 102 {                                                                              \
 103         struct slist_item **nextp;                                             \
 104         nextp = after ? &after->field.si.next : &h->sh.first;                  \
 105         typesafe_list_add(&h->sh, nextp, &item->field.si);                     \
 106 }                                                                              \
 107 /* TODO: del_hint */                                                           \
 108 macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 109 {                                                                              \
 110         struct slist_item **iter = &h->sh.first;                               \
 111         while (*iter && *iter != &item->field.si)                              \
 112                 iter = &(*iter)->next;                                         \
 113         if (!*iter)                                                            \
 114                 return;                                                        \
 115         h->sh.count--;                                                         \
 116         *iter = item->field.si.next;                                           \
 117         if (!item->field.si.next)                                              \
 118                 h->sh.last_next = iter;                                        \
 119 }                                                                              \
 120 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 121 {                                                                              \
 122         struct slist_item *sitem = h->sh.first;                                \
 123         if (!sitem)                                                            \
 124                 return NULL;                                                   \
 125         h->sh.count--;                                                         \
 126         h->sh.first = sitem->next;                                             \
 127         if (h->sh.first == NULL)                                               \
 128                 h->sh.last_next = &h->sh.first;                                \
 129         return container_of(sitem, type, field.si);                            \
 130 }                                                                              \
 131 macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
 132 {                                                                              \
 133         return container_of_null(h->sh.first, type, field.si);                 \
 134 }                                                                              \
 135 macro_pure type *prefix ## _next(struct prefix##_head * h, type *item)         \
 136 {                                                                              \
 137         struct slist_item *sitem = &item->field.si;                            \
 138         return container_of_null(sitem->next, type, field.si);                 \
 139 }                                                                              \
 140 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 141 {                                                                              \
 142         struct slist_item *sitem;                                              \
 143         if (!item)                                                             \
 144                 return NULL;                                                   \
 145         sitem = &item->field.si;                                               \
 146         return container_of_null(sitem->next, type, field.si);                 \
 147 }                                                                              \
 148 macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
 149 {                                                                              \
 150         return h->sh.count;                                                    \
 151 }                                                                              \
 152 /* ... */
 153
 154 /* single-linked list, sorted.
 155  * can be used as priority queue with add / pop
 156  */
 157
 158 /* don't use these structs directly */
 159 struct ssort_item {
 160         struct ssort_item *next;
 161 };
 162
 163 struct ssort_head {
 164         struct ssort_item *first;
 165         size_t count;
 166 };
 167
 168 /* use as:
 169  *
 170  * PREDECL_SORTLIST(namelist)
 171  * struct name {
 172  *   struct namelist_item nlitem;
 173  * }
 174  * DECLARE_SORTLIST(namelist, struct name, nlitem)
 175  */
 176 #define _PREDECL_SORTLIST(prefix)                                              \
 177 struct prefix ## _head { struct ssort_head sh; };                              \
 178 struct prefix ## _item { struct ssort_item si; };
 179
 180 #define INIT_SORTLIST_UNIQ(var)         { }
 181 #define INIT_SORTLIST_NONUNIQ(var)      { }
 182
 183 #define PREDECL_SORTLIST_UNIQ(prefix)                                          \
 184         _PREDECL_SORTLIST(prefix)
 185 #define PREDECL_SORTLIST_NONUNIQ(prefix)                                       \
 186         _PREDECL_SORTLIST(prefix)
 187
 188 #define _DECLARE_SORTLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq)            \
 189                                                                                \
 190 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
 191 {                                                                              \
 192         memset(h, 0, sizeof(*h));                                              \
 193 }                                                                              \
 194 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
 195 {                                                                              \
 196         memset(h, 0, sizeof(*h));                                              \
 197 }                                                                              \
 198 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 199 {                                                                              \
 200         struct ssort_item **np = &h->sh.first;                                 \
 201         int c = 1;                                                             \
 202         while (*np && (c = cmpfn_uq(                                           \
 203                         container_of(*np, type, field.si), item)) < 0)         \
 204                 np = &(*np)->next;                                             \
 205         if (c == 0)                                                            \
 206                 return container_of(*np, type, field.si);                      \
 207         item->field.si.next = *np;                                             \
 208         *np = &item->field.si;                                                 \
 209         h->sh.count++;                                                         \
 210         return NULL;                                                           \
 211 }                                                                              \
 212 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
 213                 const type *item)                                              \
 214 {                                                                              \
 215         struct ssort_item *sitem = h->sh.first;                                \
 216         int cmpval = 0;                                                        \
 217         while (sitem && (cmpval = cmpfn_nuq(                                   \
 218                         container_of(sitem, type, field.si), item) < 0))       \
 219                 sitem = sitem->next;                                           \
 220         return container_of_null(sitem, type, field.si);                       \
 221 }                                                                              \
 222 macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 223                 const type *item)                                              \
 224 {                                                                              \
 225         struct ssort_item *prev = NULL, *sitem = h->sh.first;                  \
 226         int cmpval = 0;                                                        \
 227         while (sitem && (cmpval = cmpfn_nuq(                                   \
 228                         container_of(sitem, type, field.si), item) < 0))       \
 229                 sitem = (prev = sitem)->next;                                  \
 230         return container_of_null(prev, type, field.si);                        \
 231 }                                                                              \
 232 /* TODO: del_hint */                                                           \
 233 macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 234 {                                                                              \
 235         struct ssort_item **iter = &h->sh.first;                               \
 236         while (*iter && *iter != &item->field.si)                              \
 237                 iter = &(*iter)->next;                                         \
 238         if (!*iter)                                                            \
 239                 return;                                                        \
 240         h->sh.count--;                                                         \
 241         *iter = item->field.si.next;                                           \
 242 }                                                                              \
 243 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 244 {                                                                              \
 245         struct ssort_item *sitem = h->sh.first;                                \
 246         if (!sitem)                                                            \
 247                 return NULL;                                                   \
 248         h->sh.count--;                                                         \
 249         h->sh.first = sitem->next;                                             \
 250         return container_of(sitem, type, field.si);                            \
 251 }                                                                              \
 252 macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
 253 {                                                                              \
 254         return container_of_null(h->sh.first, type, field.si);                 \
 255 }                                                                              \
 256 macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
 257 {                                                                              \
 258         struct ssort_item *sitem = &item->field.si;                            \
 259         return container_of_null(sitem->next, type, field.si);                 \
 260 }                                                                              \
 261 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 262 {                                                                              \
 263         struct ssort_item *sitem;                                              \
 264         if (!item)                                                             \
 265                 return NULL;                                                   \
 266         sitem = &item->field.si;                                               \
 267         return container_of_null(sitem->next, type, field.si);                 \
 268 }                                                                              \
 269 macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
 270 {                                                                              \
 271         return h->sh.count;                                                    \
 272 }                                                                              \
 273 /* ... */
 274
 275 #define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn)                      \
 276         _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn)                   \
 277                                                                                \
 278 macro_inline type *prefix ## _find(const struct prefix##_head *h, const type *item)  \
 279 {                                                                              \
 280         struct ssort_item *sitem = h->sh.first;                                \
 281         int cmpval = 0;                                                        \
 282         while (sitem && (cmpval = cmpfn(                                       \
 283                         container_of(sitem, type, field.si), item) < 0))       \
 284                 sitem = sitem->next;                                           \
 285         if (!sitem || cmpval > 0)                                              \
 286                 return NULL;                                                   \
 287         return container_of(sitem, type, field.si);                            \
 288 }                                                                              \
 289 /* ... */
 290
 291 #define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn)                   \
 292 macro_inline int _ ## prefix ## _cmp(const type *a, const type *b)             \
 293 {                                                                              \
 294         int cmpval = cmpfn(a, b);                                              \
 295         if (cmpval)                                                            \
 296                 return cmpval;                                                 \
 297         if (a < b)                                                             \
 298                 return -1;                                                     \
 299         if (a > b)                                                             \
 300                 return 1;                                                      \
 301         return 0;                                                              \
 302 }                                                                              \
 303         _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp)     \
 304 /* ... */
 305
 306
 307 /* hash, "sorted" by hash value
 308  */
 309
 310 /* don't use these structs directly */
 311 struct thash_item {
 312         struct thash_item *next;
 313         uint32_t hashval;
 314 };
 315
 316 struct thash_head {
 317         struct thash_item **entries;
 318         uint32_t count;
 319
 320         uint8_t tabshift;
 321         uint8_t minshift, maxshift;
 322 };
 323
 324 #define _HASH_SIZE(tabshift) \
 325         ((1U << (tabshift)) >> 1)
 326 #define HASH_SIZE(head) \
 327         _HASH_SIZE((head).tabshift)
 328 #define _HASH_KEY(tabshift, val) \
 329         ((val) >> (33 - (tabshift)))
 330 #define HASH_KEY(head, val) \
 331         _HASH_KEY((head).tabshift, val)
 332 #define HASH_GROW_THRESHOLD(head) \
 333         ((head).count >= HASH_SIZE(head))
 334 #define HASH_SHRINK_THRESHOLD(head) \
 335         ((head).count <= (HASH_SIZE(head) - 1) / 2)
 336
 337 extern void typesafe_hash_grow(struct thash_head *head);
 338 extern void typesafe_hash_shrink(struct thash_head *head);
 339
 340 /* use as:
 341  *
 342  * PREDECL_HASH(namelist)
 343  * struct name {
 344  *   struct namelist_item nlitem;
 345  * }
 346  * DECLARE_HASH(namelist, struct name, nlitem, cmpfunc, hashfunc)
 347  */
 348 #define PREDECL_HASH(prefix)                                                   \
 349 struct prefix ## _head { struct thash_head hh; };                              \
 350 struct prefix ## _item { struct thash_item hi; };
 351
 352 #define INIT_HASH(var)  { }
 353
 354 #define DECLARE_HASH(prefix, type, field, cmpfn, hashfn)                       \
 355                                                                                \
 356 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
 357 {                                                                              \
 358         memset(h, 0, sizeof(*h));                                              \
 359 }                                                                              \
 360 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
 361 {                                                                              \
 362         assert(h->hh.count == 0);                                              \
 363         h->hh.minshift = 0;                                                    \
 364         typesafe_hash_shrink(&h->hh);                                          \
 365         memset(h, 0, sizeof(*h));                                              \
 366 }                                                                              \
 367 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 368 {                                                                              \
 369         h->hh.count++;                                                         \
 370         if (!h->hh.tabshift || HASH_GROW_THRESHOLD(h->hh))                     \
 371                 typesafe_hash_grow(&h->hh);                                    \
 372                                                                                \
 373         uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval);           \
 374         item->field.hi.hashval = hval;                                         \
 375         struct thash_item **np = &h->hh.entries[hbits];                        \
 376         while (*np && (*np)->hashval < hval)                                   \
 377                 np = &(*np)->next;                                             \
 378         if (*np && cmpfn(container_of(*np, type, field.hi), item) == 0) {      \
 379                 h->hh.count--;                                                 \
 380                 return container_of(*np, type, field.hi);                      \
 381         }                                                                      \
 382         item->field.hi.next = *np;                                             \
 383         *np = &item->field.hi;                                                 \
 384         return NULL;                                                           \
 385 }                                                                              \
 386 macro_inline type *prefix ## _find(const struct prefix##_head *h, const type *item)  \
 387 {                                                                              \
 388         if (!h->hh.tabshift)                                                   \
 389                 return NULL;                                                   \
 390         uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval);           \
 391         struct thash_item *hitem = h->hh.entries[hbits];                       \
 392         while (hitem && hitem->hashval < hval)                                 \
 393                 hitem = hitem->next;                                           \
 394         while (hitem && hitem->hashval == hval) {                              \
 395                 if (!cmpfn(container_of(hitem, type, field.hi), item))         \
 396                         return container_of(hitem, type, field.hi);            \
 397                 hitem = hitem->next;                                           \
 398         }                                                                      \
 399         return NULL;                                                           \
 400 }                                                                              \
 401 macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 402 {                                                                              \
 403         if (!h->hh.tabshift)                                                   \
 404                 return;                                                        \
 405         uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \
 406         struct thash_item **np = &h->hh.entries[hbits];                        \
 407         while (*np && (*np)->hashval < hval)                                   \
 408                 np = &(*np)->next;                                             \
 409         while (*np && *np != &item->field.hi && (*np)->hashval == hval)        \
 410                 np = &(*np)->next;                                             \
 411         if (*np != &item->field.hi)                                            \
 412                 return;                                                        \
 413         *np = item->field.hi.next;                                             \
 414         item->field.hi.next = NULL;                                            \
 415         h->hh.count--;                                                         \
 416         if (HASH_SHRINK_THRESHOLD(h->hh))                                      \
 417                 typesafe_hash_shrink(&h->hh);                                  \
 418 }                                                                              \
 419 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 420 {                                                                              \
 421         uint32_t i;                                                            \
 422         for (i = 0; i < HASH_SIZE(h->hh); i++)                                 \
 423                 if (h->hh.entries[i]) {                                        \
 424                         struct thash_item *hitem = h->hh.entries[i];           \
 425                         h->hh.entries[i] = hitem->next;                        \
 426                         h->hh.count--;                                         \
 427                         hitem->next = NULL;                                    \
 428                         if (HASH_SHRINK_THRESHOLD(h->hh))                      \
 429                                 typesafe_hash_shrink(&h->hh);                  \
 430                         return container_of(hitem, type, field.hi);            \
 431                 }                                                              \
 432         return NULL;                                                           \
 433 }                                                                              \
 434 macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
 435 {                                                                              \
 436         uint32_t i;                                                            \
 437         for (i = 0; i < HASH_SIZE(h->hh); i++)                                 \
 438                 if (h->hh.entries[i])                                          \
 439                         return container_of(h->hh.entries[i], type, field.hi); \
 440         return NULL;                                                           \
 441 }                                                                              \
 442 macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
 443 {                                                                              \
 444         struct thash_item *hitem = &item->field.hi;                            \
 445         if (hitem->next)                                                       \
 446                 return container_of(hitem->next, type, field.hi);              \
 447         uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1;                      \
 448         for (; i < HASH_SIZE(h->hh); i++)                                      \
 449                 if (h->hh.entries[i])                                          \
 450                         return container_of(h->hh.entries[i], type, field.hi); \
 451         return NULL;                                                           \
 452 }                                                                              \
 453 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 454 {                                                                              \
 455         if (!item)                                                             \
 456                 return NULL;                                                   \
 457         return prefix ## _next(h, item);                                       \
 458 }                                                                              \
 459 macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
 460 {                                                                              \
 461         return h->hh.count;                                                    \
 462 }                                                                              \
 463 /* ... */
 464
 465 /* skiplist, sorted.
 466  * can be used as priority queue with add / pop
 467  */
 468
 469 /* don't use these structs directly */
 470 #define SKIPLIST_MAXDEPTH       16
 471 #define SKIPLIST_EMBED          4
 472 #define SKIPLIST_OVERFLOW       (SKIPLIST_EMBED - 1)
 473
 474 struct sskip_item {
 475         struct sskip_item *next[SKIPLIST_EMBED];
 476 };
 477
 478 struct sskip_overflow {
 479         struct sskip_item *next[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW];
 480 };
 481
 482 struct sskip_head {
 483         struct sskip_item hitem;
 484         struct sskip_item *overflow[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW];
 485         size_t count;
 486 };
 487
 488 /* use as:
 489  *
 490  * PREDECL_SKIPLIST(namelist)
 491  * struct name {
 492  *   struct namelist_item nlitem;
 493  * }
 494  * DECLARE_SKIPLIST(namelist, struct name, nlitem, cmpfunc)
 495  */
 496 #define _PREDECL_SKIPLIST(prefix)                                              \
 497 struct prefix ## _head { struct sskip_head sh; };                              \
 498 struct prefix ## _item { struct sskip_item si; };
 499
 500 #define INIT_SKIPLIST_UNIQ(var)         { }
 501 #define INIT_SKIPLIST_NONUNIQ(var)      { }
 502
 503 #define _DECLARE_SKIPLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq)            \
 504                                                                                \
 505 macro_inline void prefix ## _init(struct prefix##_head *h)                     \
 506 {                                                                              \
 507         memset(h, 0, sizeof(*h));                                              \
 508         h->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *)            \
 509                 ((uintptr_t)h->sh.overflow | 1);                               \
 510 }                                                                              \
 511 macro_inline void prefix ## _fini(struct prefix##_head *h)                     \
 512 {                                                                              \
 513         memset(h, 0, sizeof(*h));                                              \
 514 }                                                                              \
 515 macro_inline type *prefix ## _add(struct prefix##_head *h, type *item)         \
 516 {                                                                              \
 517         struct sskip_item *si;                                                 \
 518         si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq);         \
 519         return container_of_null(si, type, field.si);                          \
 520 }                                                                              \
 521 macro_inline type *prefix ## _find_gteq(struct prefix##_head *h,               \
 522                 const type *item)                                              \
 523 {                                                                              \
 524         struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh,         \
 525                         &item->field.si, cmpfn_nuq);                           \
 526         return container_of_null(sitem, type, field.si);                       \
 527 }                                                                              \
 528 macro_inline type *prefix ## _find_lt(struct prefix##_head *h,                 \
 529                 const type *item)                                              \
 530 {                                                                              \
 531         struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh,           \
 532                         &item->field.si, cmpfn_nuq);                           \
 533         return container_of_null(sitem, type, field.si);                       \
 534 }                                                                              \
 535 macro_inline void prefix ## _del(struct prefix##_head *h, type *item)          \
 536 {                                                                              \
 537         typesafe_skiplist_del(&h->sh, &item->field.si, cmpfn_uq);              \
 538 }                                                                              \
 539 macro_inline type *prefix ## _pop(struct prefix##_head *h)                     \
 540 {                                                                              \
 541         struct sskip_item *sitem = h->sh.hitem.next[0];                        \
 542         if (!sitem)                                                            \
 543                 return NULL;                                                   \
 544         typesafe_skiplist_del(&h->sh, sitem, cmpfn_uq);                        \
 545         return container_of(sitem, type, field.si);                            \
 546 }                                                                              \
 547 macro_pure type *prefix ## _first(struct prefix##_head *h)                     \
 548 {                                                                              \
 549         struct sskip_item *first = h->sh.hitem.next[0];                        \
 550         return container_of_null(first, type, field.si);                       \
 551 }                                                                              \
 552 macro_pure type *prefix ## _next(struct prefix##_head *h, type *item)          \
 553 {                                                                              \
 554         struct sskip_item *next = item->field.si.next[0];                      \
 555         return container_of_null(next, type, field.si);                        \
 556 }                                                                              \
 557 macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item)     \
 558 {                                                                              \
 559         struct sskip_item *next;                                               \
 560         next = item ? item->field.si.next[0] : NULL;                           \
 561         return container_of_null(next, type, field.si);                        \
 562 }                                                                              \
 563 macro_pure size_t prefix ## _count(struct prefix##_head *h)                    \
 564 {                                                                              \
 565         return h->sh.count;                                                    \
 566 }                                                                              \
 567 /* ... */
 568
 569 #define PREDECL_SKIPLIST_UNIQ(prefix)                                          \
 570         _PREDECL_SKIPLIST(prefix)
 571 #define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn)                      \
 572                                                                                \
 573 macro_inline int prefix ## __cmp(const struct sskip_item *a,                   \
 574                 const struct sskip_item *b)                                    \
 575 {                                                                              \
 576         return cmpfn(container_of(a, type, field.si),                          \
 577                         container_of(b, type, field.si));                      \
 578 }                                                                              \
 579 macro_inline type *prefix ## _find(const struct prefix##_head *h, const type *item)  \
 580 {                                                                              \
 581         struct sskip_item *sitem = typesafe_skiplist_find(&h->sh,              \
 582                         &item->field.si, &prefix ## __cmp);                    \
 583         return container_of_null(sitem, type, field.si);                       \
 584 }                                                                              \
 585                                                                                \
 586 _DECLARE_SKIPLIST(prefix, type, field,                                         \
 587                 prefix ## __cmp, prefix ## __cmp)                              \
 588 /* ... */
 589
 590 #define PREDECL_SKIPLIST_NONUNIQ(prefix)                                       \
 591         _PREDECL_SKIPLIST(prefix)
 592 #define DECLARE_SKIPLIST_NONUNIQ(prefix, type, field, cmpfn)                   \
 593                                                                                \
 594 macro_inline int prefix ## __cmp(const struct sskip_item *a,                   \
 595                 const struct sskip_item *b)                                    \
 596 {                                                                              \
 597         return cmpfn(container_of(a, type, field.si),                          \
 598                         container_of(b, type, field.si));                      \
 599 }                                                                              \
 600 macro_inline int prefix ## __cmp_uq(const struct sskip_item *a,                \
 601                 const struct sskip_item *b)                                    \
 602 {                                                                              \
 603         int cmpval = cmpfn(container_of(a, type, field.si),                    \
 604                         container_of(b, type, field.si));                      \
 605         if (cmpval)                                                            \
 606                 return cmpval;                                                 \
 607         if (a < b)                                                             \
 608                 return -1;                                                     \
 609         if (a > b)                                                             \
 610                 return 1;                                                      \
 611         return 0;                                                              \
 612 }                                                                              \
 613                                                                                \
 614 _DECLARE_SKIPLIST(prefix, type, field,                                         \
 615                 prefix ## __cmp, prefix ## __cmp_uq)                           \
 616 /* ... */
 617
 618
 619 extern struct sskip_item *typesafe_skiplist_add(struct sskip_head *head,
 620                 struct sskip_item *item, int (*cmpfn)(
 621                         const struct sskip_item *a,
 622                         const struct sskip_item *b));
 623 extern struct sskip_item *typesafe_skiplist_find(struct sskip_head *head,
 624                 const struct sskip_item *item, int (*cmpfn)(
 625                         const struct sskip_item *a,
 626                         const struct sskip_item *b));
 627 extern struct sskip_item *typesafe_skiplist_find_gteq(struct sskip_head *head,
 628                 const struct sskip_item *item, int (*cmpfn)(
 629                         const struct sskip_item *a,
 630                         const struct sskip_item *b));
 631 extern struct sskip_item *typesafe_skiplist_find_lt(struct sskip_head *head,
 632                 const struct sskip_item *item, int (*cmpfn)(
 633                         const struct sskip_item *a,
 634                         const struct sskip_item *b));
 635 extern void typesafe_skiplist_del(struct sskip_head *head,
 636                 struct sskip_item *item, int (*cmpfn)(
 637                         const struct sskip_item *a,
 638                         const struct sskip_item *b));
 639
 640 /* this needs to stay at the end because both files include each other.
 641  * the resolved order is typesafe.h before typerb.h
 642  */
 643 #include "typerb.h"
 644
 645 #endif /* _FRR_TYPESAFE_H */