summaryrefslogtreecommitdiffstats
path: root/lib/typesafe.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--lib/typesafe.h1165
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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-18 13:22:15 +0000