path: root/lib/typesafe.h

// SPDX-License-Identifier: ISC
/*
 * Copyright (c) 2016-2019  David Lamparter, for NetDEF, Inc.
 */

#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 */

/* to iterate using the const variants of the functions, append "_const" to
 * the name of the container, e.g. "frr_each (my_list, head, item)" becomes
 * "frr_each (my_list_const, head, item)"
 */

#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;

	/* tabshift can be 0 if the hash table is empty and entries is NULL.
	 * otherwise it will always be 2 or larger because it contains
	 * the shift value *plus 1*.  This is a trick to make HASH_SIZE return
	 * the correct value (with the >> 1) for tabshift == 0, without needing
	 * a conditional branch.
	 */
	uint8_t tabshift;
	uint8_t minshift, maxshift;
};

#define _HASH_SIZE(tabshift)                                                   \
	({                                                                     \
		assume((tabshift) <= 31);                                      \
		(1U << (tabshift)) >> 1;                                       \
	})
#define HASH_SIZE(head) \
	_HASH_SIZE((head).tabshift)
#define _HASH_KEY(tabshift, val)                                               \
	({                                                                     \
		assume((tabshift) >= 2 && (tabshift) <= 31);                   \
		(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;                                             \
	while (*np && (*np)->hashval == hval) {                                \
		if (cmpfn(container_of(*np, type, field.hi), item) == 0) {     \
			h->hh.count--;                                         \
			return container_of(*np, type, field.hi);              \
		}                                                              \
		np = &(*np)->next;                                             \
	}                                                                      \
	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)                            \
{                                                                              \
	if (!h->hh.tabshift)                                                   \
		return NULL;                                                   \
	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 */