diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:53:30 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-28 09:53:30 +0000 |
commit | 2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 (patch) | |
tree | c05dc0f8e6aa3accc84e3e5cffc933ed94941383 /lib/typesafe.h | |
parent | Initial commit. (diff) | |
download | frr-upstream/8.4.4.tar.xz frr-upstream/8.4.4.zip |
Adding upstream version 8.4.4.upstream/8.4.4upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | lib/typesafe.h | 1165 |
1 files changed, 1165 insertions, 0 deletions
diff --git a/lib/typesafe.h b/lib/typesafe.h new file mode 100644 index 0000000..50c410a --- /dev/null +++ b/lib/typesafe.h @@ -0,0 +1,1165 @@ +/* + * Copyright (c) 2016-2019 David Lamparter, for NetDEF, Inc. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef _FRR_TYPESAFE_H +#define _FRR_TYPESAFE_H + +#include <stddef.h> +#include <stdint.h> +#include <stdbool.h> +#include "compiler.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/* generic macros for all list-like types */ + +#define frr_each(prefix, head, item) \ + for (item = prefix##_first(head); item; \ + item = prefix##_next(head, item)) +#define frr_each_safe(prefix, head, item) \ + for (typeof(prefix##_next_safe(head, NULL)) prefix##_safe = \ + prefix##_next_safe(head, \ + (item = prefix##_first(head))); \ + item; \ + item = prefix##_safe, \ + prefix##_safe = prefix##_next_safe(head, prefix##_safe)) +#define frr_each_from(prefix, head, item, from) \ + for (item = from, from = prefix##_next_safe(head, item); \ + item; \ + item = from, from = prefix##_next_safe(head, from)) + +/* reverse direction, only supported by a few containers */ + +#define frr_rev_each(prefix, head, item) \ + for (item = prefix##_last(head); item; \ + item = prefix##_prev(head, item)) +#define frr_rev_each_safe(prefix, head, item) \ + for (typeof(prefix##_prev_safe(head, NULL)) prefix##_safe = \ + prefix##_prev_safe(head, \ + (item = prefix##_last(head))); \ + item; \ + item = prefix##_safe, \ + prefix##_safe = prefix##_prev_safe(head, prefix##_safe)) +#define frr_rev_each_from(prefix, head, item, from) \ + for (item = from, from = prefix##_prev_safe(head, item); \ + item; \ + item = from, from = prefix##_prev_safe(head, from)) + +/* non-const variants. these wrappers are the same for all the types, so + * bundle them together here. + */ +#define TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _first(struct prefix##_head *h) \ +{ \ + return (type *)prefix ## _const_first(h); \ +} \ +macro_pure type *prefix ## _next(struct prefix##_head *h, type *item) \ +{ \ + return (type *)prefix ## _const_next(h, item); \ +} \ +/* ... */ +#define TYPESAFE_LAST_PREV(prefix, type) \ +macro_pure type *prefix ## _last(struct prefix##_head *h) \ +{ \ + return (type *)prefix ## _const_last(h); \ +} \ +macro_pure type *prefix ## _prev(struct prefix##_head *h, type *item) \ +{ \ + return (type *)prefix ## _const_prev(h, item); \ +} \ +/* ... */ +#define TYPESAFE_FIND(prefix, type) \ +macro_inline type *prefix ## _find(struct prefix##_head *h, \ + const type *item) \ +{ \ + return (type *)prefix ## _const_find(h, item); \ +} \ +/* ... */ +#define TYPESAFE_FIND_CMP(prefix, type) \ +macro_inline type *prefix ## _find_lt(struct prefix##_head *h, \ + const type *item) \ +{ \ + return (type *)prefix ## _const_find_lt(h, item); \ +} \ +macro_inline type *prefix ## _find_gteq(struct prefix##_head *h, \ + const type *item) \ +{ \ + return (type *)prefix ## _const_find_gteq(h, item); \ +} \ +/* ... */ + +/* *_member via find - when there is no better membership check than find() */ +#define TYPESAFE_MEMBER_VIA_FIND(prefix, type) \ +macro_inline bool prefix ## _member(struct prefix##_head *h, \ + const type *item) \ +{ \ + return item == prefix ## _const_find(h, item); \ +} \ +/* ... */ + +/* *_member via find_gteq - same for non-unique containers */ +#define TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \ +macro_inline bool prefix ## _member(struct prefix##_head *h, \ + const type *item) \ +{ \ + const type *iter; \ + for (iter = prefix ## _const_find_gteq(h, item); iter; \ + iter = prefix ## _const_next(h, iter)) { \ + if (iter == item) \ + return true; \ + if (cmpfn(iter, item) > 0) \ + break; \ + } \ + return false; \ +} \ +/* ... */ + +/* SWAP_ALL_SIMPLE = for containers where the items don't point back to the + * head *AND* the head doesn't point to itself (= everything except LIST, + * DLIST and SKIPLIST), just switch out the entire head + */ +#define TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + struct prefix##_head tmp = *a; \ + *a = *b; \ + *b = tmp; \ +} \ +/* ... */ + +/* single-linked list, unsorted/arbitrary. + * can be used as queue with add_tail / pop + */ + +/* don't use these structs directly */ +struct slist_item { + struct slist_item *next; +}; + +struct slist_head { + struct slist_item *first, **last_next; + size_t count; +}; + +/* this replaces NULL as the value for ->next on the last item. */ +extern struct slist_item typesafe_slist_sentinel; +#define _SLIST_LAST &typesafe_slist_sentinel + +static inline void typesafe_list_add(struct slist_head *head, + struct slist_item **pos, struct slist_item *item) +{ + item->next = *pos; + *pos = item; + if (pos == head->last_next) + head->last_next = &item->next; + head->count++; +} + +extern bool typesafe_list_member(const struct slist_head *head, + const struct slist_item *item); + +/* use as: + * + * PREDECL_LIST(namelist); + * struct name { + * struct namelist_item nlitem; + * } + * DECLARE_LIST(namelist, struct name, nlitem); + */ +#define PREDECL_LIST(prefix) \ +struct prefix ## _head { struct slist_head sh; }; \ +struct prefix ## _item { struct slist_item si; }; \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define INIT_LIST(var) { .sh = { .last_next = &var.sh.first, }, } + +#define DECLARE_LIST(prefix, type, field) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ + h->sh.first = _SLIST_LAST; \ + h->sh.last_next = &h->sh.first; \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \ +{ \ + typesafe_list_add(&h->sh, &h->sh.first, &item->field.si); \ +} \ +macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \ +{ \ + typesafe_list_add(&h->sh, h->sh.last_next, &item->field.si); \ +} \ +macro_inline void prefix ## _add_after(struct prefix##_head *h, \ + type *after, type *item) \ +{ \ + struct slist_item **nextp; \ + nextp = after ? &after->field.si.next : &h->sh.first; \ + typesafe_list_add(&h->sh, nextp, &item->field.si); \ +} \ +/* TODO: del_hint */ \ +macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct slist_item **iter = &h->sh.first; \ + while (*iter != _SLIST_LAST && *iter != &item->field.si) \ + iter = &(*iter)->next; \ + if (*iter == _SLIST_LAST) \ + return NULL; \ + h->sh.count--; \ + *iter = item->field.si.next; \ + if (item->field.si.next == _SLIST_LAST) \ + h->sh.last_next = iter; \ + item->field.si.next = NULL; \ + return item; \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct slist_item *sitem = h->sh.first; \ + if (sitem == _SLIST_LAST) \ + return NULL; \ + h->sh.count--; \ + h->sh.first = sitem->next; \ + if (h->sh.first == _SLIST_LAST) \ + h->sh.last_next = &h->sh.first; \ + sitem->next = NULL; \ + return container_of(sitem, type, field.si); \ +} \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + struct prefix##_head tmp = *a; \ + *a = *b; \ + *b = tmp; \ + if (a->sh.last_next == &b->sh.first) \ + a->sh.last_next = &a->sh.first; \ + if (b->sh.last_next == &a->sh.first) \ + b->sh.last_next = &b->sh.first; \ +} \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ +{ \ + if (h->sh.first != _SLIST_LAST) \ + return container_of(h->sh.first, type, field.si); \ + return NULL; \ +} \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct slist_item *sitem = &item->field.si; \ + if (sitem->next != _SLIST_LAST) \ + return container_of(sitem->next, type, field.si); \ + return NULL; \ +} \ +TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + struct slist_item *sitem; \ + if (!item) \ + return NULL; \ + sitem = &item->field.si; \ + if (sitem->next != _SLIST_LAST) \ + return container_of(sitem->next, type, field.si); \ + return NULL; \ +} \ +macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ +{ \ + return h->sh.count; \ +} \ +macro_pure bool prefix ## _anywhere(const type *item) \ +{ \ + return item->field.si.next != NULL; \ +} \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + return typesafe_list_member(&h->sh, &item->field.si); \ +} \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +/* don't use these structs directly */ +struct dlist_item { + struct dlist_item *next; + struct dlist_item *prev; +}; + +struct dlist_head { + struct dlist_item hitem; + size_t count; +}; + +static inline void typesafe_dlist_add(struct dlist_head *head, + struct dlist_item *prev, struct dlist_item *item) +{ + /* SA on clang-11 thinks this can happen, but in reality -assuming no + * memory corruption- it can't. DLIST uses a "closed" ring, i.e. the + * termination at the end of the list is not NULL but rather a pointer + * back to the head. (This eliminates special-casing the first or last + * item.) + * + * Sadly, can't use assert() here since the libfrr assert / xref code + * uses typesafe lists itself... that said, if an assert tripped here + * we'd already be way past some memory corruption, so we might as + * well just take the SEGV. (In the presence of corruption, we'd see + * random SEGVs from places that make no sense at all anyway, an + * assert might actually be a red herring.) + * + * ("assume()" tells the compiler to produce code as if the condition + * will always hold; it doesn't have any actual effect here, it'll + * just SEGV out on "item->next->prev = item".) + */ + assume(prev->next != NULL); + + item->next = prev->next; + item->next->prev = item; + item->prev = prev; + prev->next = item; + head->count++; +} + +static inline void typesafe_dlist_swap_all(struct dlist_head *a, + struct dlist_head *b) +{ + struct dlist_head tmp = *a; + + a->count = b->count; + if (a->count) { + a->hitem.next = b->hitem.next; + a->hitem.prev = b->hitem.prev; + a->hitem.next->prev = &a->hitem; + a->hitem.prev->next = &a->hitem; + } else { + a->hitem.next = &a->hitem; + a->hitem.prev = &a->hitem; + } + + b->count = tmp.count; + if (b->count) { + b->hitem.next = tmp.hitem.next; + b->hitem.prev = tmp.hitem.prev; + b->hitem.next->prev = &b->hitem; + b->hitem.prev->next = &b->hitem; + } else { + b->hitem.next = &b->hitem; + b->hitem.prev = &b->hitem; + } +} + +extern bool typesafe_dlist_member(const struct dlist_head *head, + const struct dlist_item *item); + +/* double-linked list, for fast item deletion + */ +#define PREDECL_DLIST(prefix) \ +struct prefix ## _head { struct dlist_head dh; }; \ +struct prefix ## _item { struct dlist_item di; }; \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define INIT_DLIST(var) { .dh = { \ + .hitem = { &var.dh.hitem, &var.dh.hitem }, }, } + +#define DECLARE_DLIST(prefix, type, field) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ + h->dh.hitem.prev = &h->dh.hitem; \ + h->dh.hitem.next = &h->dh.hitem; \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _add_head(struct prefix##_head *h, type *item) \ +{ \ + typesafe_dlist_add(&h->dh, &h->dh.hitem, &item->field.di); \ +} \ +macro_inline void prefix ## _add_tail(struct prefix##_head *h, type *item) \ +{ \ + typesafe_dlist_add(&h->dh, h->dh.hitem.prev, &item->field.di); \ +} \ +macro_inline void prefix ## _add_after(struct prefix##_head *h, \ + type *after, type *item) \ +{ \ + struct dlist_item *prev; \ + prev = after ? &after->field.di : &h->dh.hitem; \ + typesafe_dlist_add(&h->dh, prev, &item->field.di); \ +} \ +macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct dlist_item *ditem = &item->field.di; \ + ditem->prev->next = ditem->next; \ + ditem->next->prev = ditem->prev; \ + h->dh.count--; \ + ditem->prev = ditem->next = NULL; \ + return item; \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct dlist_item *ditem = h->dh.hitem.next; \ + if (ditem == &h->dh.hitem) \ + return NULL; \ + ditem->prev->next = ditem->next; \ + ditem->next->prev = ditem->prev; \ + h->dh.count--; \ + ditem->prev = ditem->next = NULL; \ + return container_of(ditem, type, field.di); \ +} \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + typesafe_dlist_swap_all(&a->dh, &b->dh); \ +} \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ +{ \ + const struct dlist_item *ditem = h->dh.hitem.next; \ + if (ditem == &h->dh.hitem) \ + return NULL; \ + return container_of(ditem, type, field.di); \ +} \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct dlist_item *ditem = &item->field.di; \ + if (ditem->next == &h->dh.hitem) \ + return NULL; \ + return container_of(ditem->next, type, field.di); \ +} \ +TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure const type *prefix ## _const_last(const struct prefix##_head *h) \ +{ \ + const struct dlist_item *ditem = h->dh.hitem.prev; \ + if (ditem == &h->dh.hitem) \ + return NULL; \ + return container_of(ditem, type, field.di); \ +} \ +macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct dlist_item *ditem = &item->field.di; \ + if (ditem->prev == &h->dh.hitem) \ + return NULL; \ + return container_of(ditem->prev, type, field.di); \ +} \ +TYPESAFE_LAST_PREV(prefix, type) \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + if (!item) \ + return NULL; \ + return prefix ## _next(h, item); \ +} \ +macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item) \ +{ \ + if (!item) \ + return NULL; \ + return prefix ## _prev(h, item); \ +} \ +macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ +{ \ + return h->dh.count; \ +} \ +macro_pure bool prefix ## _anywhere(const type *item) \ +{ \ + const struct dlist_item *ditem = &item->field.di; \ + return ditem->next && ditem->prev; \ +} \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + return typesafe_dlist_member(&h->dh, &item->field.di); \ +} \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +/* note: heap currently caps out at 4G items */ + +#define HEAP_NARY 8U +typedef uint32_t heap_index_i; + +struct heap_item { + uint32_t index; +}; + +struct heap_head { + struct heap_item **array; + uint32_t arraysz, count; +}; + +#define HEAP_RESIZE_TRESH_UP(h) \ + (h->hh.count + 1 >= h->hh.arraysz) +#define HEAP_RESIZE_TRESH_DN(h) \ + (h->hh.count == 0 || \ + h->hh.arraysz - h->hh.count > (h->hh.count + 1024) / 2) + +#define PREDECL_HEAP(prefix) \ +struct prefix ## _head { struct heap_head hh; }; \ +struct prefix ## _item { struct heap_item hi; }; \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define INIT_HEAP(var) { } + +#define DECLARE_HEAP(prefix, type, field, cmpfn) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + assert(h->hh.count == 0); \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline int prefix ## __cmp(const struct heap_item *a, \ + const struct heap_item *b) \ +{ \ + return cmpfn(container_of(a, type, field.hi), \ + container_of(b, type, field.hi)); \ +} \ +macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ +{ \ + if (HEAP_RESIZE_TRESH_UP(h)) \ + typesafe_heap_resize(&h->hh, true); \ + typesafe_heap_pullup(&h->hh, h->hh.count, &item->field.hi, \ + prefix ## __cmp); \ + h->hh.count++; \ + return NULL; \ +} \ +macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct heap_item *other; \ + uint32_t index = item->field.hi.index; \ + assert(h->hh.array[index] == &item->field.hi); \ + h->hh.count--; \ + other = h->hh.array[h->hh.count]; \ + if (cmpfn(container_of(other, type, field.hi), item) < 0) \ + typesafe_heap_pullup(&h->hh, index, other, prefix ## __cmp); \ + else \ + typesafe_heap_pushdown(&h->hh, index, other, prefix ## __cmp); \ + if (HEAP_RESIZE_TRESH_DN(h)) \ + typesafe_heap_resize(&h->hh, false); \ + return item; \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct heap_item *hitem, *other; \ + if (h->hh.count == 0) \ + return NULL; \ + hitem = h->hh.array[0]; \ + h->hh.count--; \ + other = h->hh.array[h->hh.count]; \ + typesafe_heap_pushdown(&h->hh, 0, other, prefix ## __cmp); \ + if (HEAP_RESIZE_TRESH_DN(h)) \ + typesafe_heap_resize(&h->hh, false); \ + return container_of(hitem, type, field.hi); \ +} \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ +{ \ + if (h->hh.count == 0) \ + return NULL; \ + return container_of(h->hh.array[0], type, field.hi); \ +} \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ +{ \ + uint32_t idx = item->field.hi.index + 1; \ + if (idx >= h->hh.count) \ + return NULL; \ + return container_of(h->hh.array[idx], type, field.hi); \ +} \ +TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + if (!item) \ + return NULL; \ + return prefix ## _next(h, item); \ +} \ +macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ +{ \ + return h->hh.count; \ +} \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + uint32_t idx = item->field.hi.index; \ + if (idx >= h->hh.count) \ + return false; \ + return h->hh.array[idx] == &item->field.hi; \ +} \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +extern void typesafe_heap_resize(struct heap_head *head, bool grow); +extern void typesafe_heap_pushdown(struct heap_head *head, uint32_t index, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)); +extern void typesafe_heap_pullup(struct heap_head *head, uint32_t index, + struct heap_item *item, + int (*cmpfn)(const struct heap_item *a, + const struct heap_item *b)); + +/* single-linked list, sorted. + * can be used as priority queue with add / pop + */ + +/* don't use these structs directly */ +struct ssort_item { + struct ssort_item *next; +}; + +struct ssort_head { + struct ssort_item *first; + size_t count; +}; + +/* use as: + * + * PREDECL_SORTLIST(namelist) + * struct name { + * struct namelist_item nlitem; + * } + * DECLARE_SORTLIST(namelist, struct name, nlitem) + */ +#define _PREDECL_SORTLIST(prefix) \ +struct prefix ## _head { struct ssort_head sh; }; \ +struct prefix ## _item { struct ssort_item si; }; \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define INIT_SORTLIST_UNIQ(var) { } +#define INIT_SORTLIST_NONUNIQ(var) { } + +#define PREDECL_SORTLIST_UNIQ(prefix) \ + _PREDECL_SORTLIST(prefix) +#define PREDECL_SORTLIST_NONUNIQ(prefix) \ + _PREDECL_SORTLIST(prefix) + +#define _DECLARE_SORTLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ +{ \ + struct ssort_item **np = &h->sh.first; \ + int c = 1; \ + while (*np && (c = cmpfn_uq( \ + container_of(*np, type, field.si), item)) < 0) \ + np = &(*np)->next; \ + if (c == 0) \ + return container_of(*np, type, field.si); \ + item->field.si.next = *np; \ + *np = &item->field.si; \ + h->sh.count++; \ + return NULL; \ +} \ +macro_inline const type *prefix ## _const_find_gteq( \ + const struct prefix##_head *h, const type *item) \ +{ \ + const struct ssort_item *sitem = h->sh.first; \ + int cmpval = 0; \ + while (sitem && (cmpval = cmpfn_nuq( \ + container_of(sitem, type, field.si), item)) < 0) \ + sitem = sitem->next; \ + return container_of_null(sitem, type, field.si); \ +} \ +macro_inline const type *prefix ## _const_find_lt( \ + const struct prefix##_head *h, const type *item) \ +{ \ + const struct ssort_item *prev = NULL, *sitem = h->sh.first; \ + int cmpval = 0; \ + while (sitem && (cmpval = cmpfn_nuq( \ + container_of(sitem, type, field.si), item)) < 0) \ + sitem = (prev = sitem)->next; \ + return container_of_null(prev, type, field.si); \ +} \ +TYPESAFE_FIND_CMP(prefix, type) \ +/* TODO: del_hint */ \ +macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct ssort_item **iter = &h->sh.first; \ + while (*iter && *iter != &item->field.si) \ + iter = &(*iter)->next; \ + if (!*iter) \ + return NULL; \ + h->sh.count--; \ + *iter = item->field.si.next; \ + item->field.si.next = NULL; \ + return item; \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct ssort_item *sitem = h->sh.first; \ + if (!sitem) \ + return NULL; \ + h->sh.count--; \ + h->sh.first = sitem->next; \ + return container_of(sitem, type, field.si); \ +} \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ +{ \ + return container_of_null(h->sh.first, type, field.si); \ +} \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct ssort_item *sitem = &item->field.si; \ + return container_of_null(sitem->next, type, field.si); \ +} \ +TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + struct ssort_item *sitem; \ + if (!item) \ + return NULL; \ + sitem = &item->field.si; \ + return container_of_null(sitem->next, type, field.si); \ +} \ +macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ +{ \ + return h->sh.count; \ +} \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define DECLARE_SORTLIST_UNIQ(prefix, type, field, cmpfn) \ + _DECLARE_SORTLIST(prefix, type, field, cmpfn, cmpfn); \ + \ +macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct ssort_item *sitem = h->sh.first; \ + int cmpval = 0; \ + while (sitem && (cmpval = cmpfn( \ + container_of(sitem, type, field.si), item)) < 0) \ + sitem = sitem->next; \ + if (!sitem || cmpval > 0) \ + return NULL; \ + return container_of(sitem, type, field.si); \ +} \ +TYPESAFE_FIND(prefix, type) \ +TYPESAFE_MEMBER_VIA_FIND(prefix, type) \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define DECLARE_SORTLIST_NONUNIQ(prefix, type, field, cmpfn) \ +macro_inline int _ ## prefix ## _cmp(const type *a, const type *b) \ +{ \ + int cmpval = cmpfn(a, b); \ + if (cmpval) \ + return cmpval; \ + if (a < b) \ + return -1; \ + if (a > b) \ + return 1; \ + return 0; \ +} \ + _DECLARE_SORTLIST(prefix, type, field, cmpfn, _ ## prefix ## _cmp); \ +TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \ +MACRO_REQUIRE_SEMICOLON() /* end */ + + +/* hash, "sorted" by hash value + */ + +/* don't use these structs directly */ +struct thash_item { + struct thash_item *next; + uint32_t hashval; +}; + +struct thash_head { + struct thash_item **entries; + uint32_t count; + + uint8_t tabshift; + uint8_t minshift, maxshift; +}; + +#define _HASH_SIZE(tabshift) \ + ((1U << (tabshift)) >> 1) +#define HASH_SIZE(head) \ + _HASH_SIZE((head).tabshift) +#define _HASH_KEY(tabshift, val) \ + ((val) >> (33 - (tabshift))) +#define HASH_KEY(head, val) \ + _HASH_KEY((head).tabshift, val) +#define HASH_GROW_THRESHOLD(head) \ + ((head).count >= HASH_SIZE(head)) +#define HASH_SHRINK_THRESHOLD(head) \ + ((head).count <= (HASH_SIZE(head) - 1) / 2) + +extern void typesafe_hash_grow(struct thash_head *head); +extern void typesafe_hash_shrink(struct thash_head *head); + +/* use as: + * + * PREDECL_HASH(namelist) + * struct name { + * struct namelist_item nlitem; + * } + * DECLARE_HASH(namelist, struct name, nlitem, cmpfunc, hashfunc) + */ +#define PREDECL_HASH(prefix) \ +struct prefix ## _head { struct thash_head hh; }; \ +struct prefix ## _item { struct thash_item hi; }; \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define INIT_HASH(var) { } + +#define DECLARE_HASH(prefix, type, field, cmpfn, hashfn) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + assert(h->hh.count == 0); \ + h->hh.minshift = 0; \ + typesafe_hash_shrink(&h->hh); \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ +{ \ + h->hh.count++; \ + if (!h->hh.tabshift || HASH_GROW_THRESHOLD(h->hh)) \ + typesafe_hash_grow(&h->hh); \ + \ + uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \ + item->field.hi.hashval = hval; \ + struct thash_item **np = &h->hh.entries[hbits]; \ + while (*np && (*np)->hashval < hval) \ + np = &(*np)->next; \ + if (*np && cmpfn(container_of(*np, type, field.hi), item) == 0) { \ + h->hh.count--; \ + return container_of(*np, type, field.hi); \ + } \ + item->field.hi.next = *np; \ + *np = &item->field.hi; \ + return NULL; \ +} \ +macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ + const type *item) \ +{ \ + if (!h->hh.tabshift) \ + return NULL; \ + uint32_t hval = hashfn(item), hbits = HASH_KEY(h->hh, hval); \ + const struct thash_item *hitem = h->hh.entries[hbits]; \ + while (hitem && hitem->hashval < hval) \ + hitem = hitem->next; \ + while (hitem && hitem->hashval == hval) { \ + if (!cmpfn(container_of(hitem, type, field.hi), item)) \ + return container_of(hitem, type, field.hi); \ + hitem = hitem->next; \ + } \ + return NULL; \ +} \ +TYPESAFE_FIND(prefix, type) \ +macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + if (!h->hh.tabshift) \ + return NULL; \ + uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \ + struct thash_item **np = &h->hh.entries[hbits]; \ + while (*np && (*np)->hashval < hval) \ + np = &(*np)->next; \ + while (*np && *np != &item->field.hi && (*np)->hashval == hval) \ + np = &(*np)->next; \ + if (*np != &item->field.hi) \ + return NULL; \ + *np = item->field.hi.next; \ + item->field.hi.next = NULL; \ + h->hh.count--; \ + if (HASH_SHRINK_THRESHOLD(h->hh)) \ + typesafe_hash_shrink(&h->hh); \ + return item; \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + uint32_t i; \ + for (i = 0; i < HASH_SIZE(h->hh); i++) \ + if (h->hh.entries[i]) { \ + struct thash_item *hitem = h->hh.entries[i]; \ + h->hh.entries[i] = hitem->next; \ + h->hh.count--; \ + hitem->next = NULL; \ + if (HASH_SHRINK_THRESHOLD(h->hh)) \ + typesafe_hash_shrink(&h->hh); \ + return container_of(hitem, type, field.hi); \ + } \ + return NULL; \ +} \ +TYPESAFE_SWAP_ALL_SIMPLE(prefix) \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ +{ \ + uint32_t i; \ + for (i = 0; i < HASH_SIZE(h->hh); i++) \ + if (h->hh.entries[i]) \ + return container_of(h->hh.entries[i], type, field.hi); \ + return NULL; \ +} \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct thash_item *hitem = &item->field.hi; \ + if (hitem->next) \ + return container_of(hitem->next, type, field.hi); \ + uint32_t i = HASH_KEY(h->hh, hitem->hashval) + 1; \ + for (; i < HASH_SIZE(h->hh); i++) \ + if (h->hh.entries[i]) \ + return container_of(h->hh.entries[i], type, field.hi); \ + return NULL; \ +} \ +TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + if (!item) \ + return NULL; \ + return prefix ## _next(h, item); \ +} \ +macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ +{ \ + return h->hh.count; \ +} \ +macro_pure bool prefix ## _member(const struct prefix##_head *h, \ + const type *item) \ +{ \ + uint32_t hval = item->field.hi.hashval, hbits = HASH_KEY(h->hh, hval); \ + const struct thash_item *hitem = h->hh.entries[hbits]; \ + while (hitem && hitem->hashval < hval) \ + hitem = hitem->next; \ + for (hitem = h->hh.entries[hbits]; hitem && hitem->hashval <= hval; \ + hitem = hitem->next) \ + if (hitem == &item->field.hi) \ + return true; \ + return false; \ +} \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +/* skiplist, sorted. + * can be used as priority queue with add / pop + */ + +/* don't use these structs directly */ +#define SKIPLIST_MAXDEPTH 16 +#define SKIPLIST_EMBED 4 +#define SKIPLIST_OVERFLOW (SKIPLIST_EMBED - 1) + +struct sskip_item { + struct sskip_item *next[SKIPLIST_EMBED]; +}; + +struct sskip_overflow { + struct sskip_item *next[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW]; +}; + +struct sskip_head { + struct sskip_item hitem; + struct sskip_item *overflow[SKIPLIST_MAXDEPTH - SKIPLIST_OVERFLOW]; + size_t count; +}; + +/* use as: + * + * PREDECL_SKIPLIST(namelist) + * struct name { + * struct namelist_item nlitem; + * } + * DECLARE_SKIPLIST(namelist, struct name, nlitem, cmpfunc) + */ +#define _PREDECL_SKIPLIST(prefix) \ +struct prefix ## _head { struct sskip_head sh; }; \ +struct prefix ## _item { struct sskip_item si; }; \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define INIT_SKIPLIST_UNIQ(var) { } +#define INIT_SKIPLIST_NONUNIQ(var) { } + +#define _DECLARE_SKIPLIST(prefix, type, field, cmpfn_nuq, cmpfn_uq) \ + \ +macro_inline void prefix ## _init(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ + h->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \ + ((uintptr_t)h->sh.overflow | 1); \ +} \ +macro_inline void prefix ## _fini(struct prefix##_head *h) \ +{ \ + memset(h, 0, sizeof(*h)); \ +} \ +macro_inline type *prefix ## _add(struct prefix##_head *h, type *item) \ +{ \ + struct sskip_item *si; \ + si = typesafe_skiplist_add(&h->sh, &item->field.si, cmpfn_uq); \ + return container_of_null(si, type, field.si); \ +} \ +macro_inline const type *prefix ## _const_find_gteq( \ + const struct prefix##_head *h, const type *item) \ +{ \ + const struct sskip_item *sitem = typesafe_skiplist_find_gteq(&h->sh, \ + &item->field.si, cmpfn_nuq); \ + return container_of_null(sitem, type, field.si); \ +} \ +macro_inline const type *prefix ## _const_find_lt( \ + const struct prefix##_head *h, const type *item) \ +{ \ + const struct sskip_item *sitem = typesafe_skiplist_find_lt(&h->sh, \ + &item->field.si, cmpfn_nuq); \ + return container_of_null(sitem, type, field.si); \ +} \ +TYPESAFE_FIND_CMP(prefix, type) \ +macro_inline type *prefix ## _del(struct prefix##_head *h, type *item) \ +{ \ + struct sskip_item *sitem = typesafe_skiplist_del(&h->sh, \ + &item->field.si, cmpfn_uq); \ + return container_of_null(sitem, type, field.si); \ +} \ +macro_inline type *prefix ## _pop(struct prefix##_head *h) \ +{ \ + struct sskip_item *sitem = typesafe_skiplist_pop(&h->sh); \ + return container_of_null(sitem, type, field.si); \ +} \ +macro_inline void prefix ## _swap_all(struct prefix##_head *a, \ + struct prefix##_head *b) \ +{ \ + struct prefix##_head tmp = *a; \ + *a = *b; \ + *b = tmp; \ + a->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \ + ((uintptr_t)a->sh.overflow | 1); \ + b->sh.hitem.next[SKIPLIST_OVERFLOW] = (struct sskip_item *) \ + ((uintptr_t)b->sh.overflow | 1); \ +} \ +macro_pure const type *prefix ## _const_first(const struct prefix##_head *h) \ +{ \ + const struct sskip_item *first = h->sh.hitem.next[0]; \ + return container_of_null(first, type, field.si); \ +} \ +macro_pure const type *prefix ## _const_next(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct sskip_item *next = item->field.si.next[0]; \ + return container_of_null(next, type, field.si); \ +} \ +TYPESAFE_FIRST_NEXT(prefix, type) \ +macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \ +{ \ + struct sskip_item *next; \ + next = item ? item->field.si.next[0] : NULL; \ + return container_of_null(next, type, field.si); \ +} \ +macro_pure size_t prefix ## _count(const struct prefix##_head *h) \ +{ \ + return h->sh.count; \ +} \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define PREDECL_SKIPLIST_UNIQ(prefix) \ + _PREDECL_SKIPLIST(prefix) +#define DECLARE_SKIPLIST_UNIQ(prefix, type, field, cmpfn) \ + \ +macro_inline int prefix ## __cmp(const struct sskip_item *a, \ + const struct sskip_item *b) \ +{ \ + return cmpfn(container_of(a, type, field.si), \ + container_of(b, type, field.si)); \ +} \ +macro_inline const type *prefix ## _const_find(const struct prefix##_head *h, \ + const type *item) \ +{ \ + const struct sskip_item *sitem = typesafe_skiplist_find(&h->sh, \ + &item->field.si, &prefix ## __cmp); \ + return container_of_null(sitem, type, field.si); \ +} \ +TYPESAFE_FIND(prefix, type) \ +TYPESAFE_MEMBER_VIA_FIND(prefix, type) \ + \ +_DECLARE_SKIPLIST(prefix, type, field, \ + prefix ## __cmp, prefix ## __cmp); \ +MACRO_REQUIRE_SEMICOLON() /* end */ + +#define PREDECL_SKIPLIST_NONUNIQ(prefix) \ + _PREDECL_SKIPLIST(prefix) +#define DECLARE_SKIPLIST_NONUNIQ(prefix, type, field, cmpfn) \ + \ +macro_inline int prefix ## __cmp(const struct sskip_item *a, \ + const struct sskip_item *b) \ +{ \ + return cmpfn(container_of(a, type, field.si), \ + container_of(b, type, field.si)); \ +} \ +macro_inline int prefix ## __cmp_uq(const struct sskip_item *a, \ + const struct sskip_item *b) \ +{ \ + int cmpval = cmpfn(container_of(a, type, field.si), \ + container_of(b, type, field.si)); \ + if (cmpval) \ + return cmpval; \ + if (a < b) \ + return -1; \ + if (a > b) \ + return 1; \ + return 0; \ +} \ + \ +_DECLARE_SKIPLIST(prefix, type, field, \ + prefix ## __cmp, prefix ## __cmp_uq); \ +TYPESAFE_MEMBER_VIA_FIND_GTEQ(prefix, type, cmpfn) \ +MACRO_REQUIRE_SEMICOLON() /* end */ + + +extern struct sskip_item *typesafe_skiplist_add(struct sskip_head *head, + struct sskip_item *item, int (*cmpfn)( + const struct sskip_item *a, + const struct sskip_item *b)); +extern const struct sskip_item *typesafe_skiplist_find( + const struct sskip_head *head, + const struct sskip_item *item, int (*cmpfn)( + const struct sskip_item *a, + const struct sskip_item *b)); +extern const struct sskip_item *typesafe_skiplist_find_gteq( + const struct sskip_head *head, + const struct sskip_item *item, int (*cmpfn)( + const struct sskip_item *a, + const struct sskip_item *b)); +extern const struct sskip_item *typesafe_skiplist_find_lt( + const struct sskip_head *head, + const struct sskip_item *item, int (*cmpfn)( + const struct sskip_item *a, + const struct sskip_item *b)); +extern struct sskip_item *typesafe_skiplist_del( + struct sskip_head *head, struct sskip_item *item, int (*cmpfn)( + const struct sskip_item *a, + const struct sskip_item *b)); +extern struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head); + +#ifdef __cplusplus +} +#endif + +/* this needs to stay at the end because both files include each other. + * the resolved order is typesafe.h before typerb.h + */ +#include "typerb.h" + +#endif /* _FRR_TYPESAFE_H */ |