[mirror_frr.git] / lib / typesafe.c

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

#ifdef HAVE_CONFIG_H
#include "config.h"
#endif

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "typesafe.h"
#include "memory.h"
#include "network.h"

DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket");
DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow");
DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array");

struct slist_item typesafe_slist_sentinel = { NULL };

bool typesafe_list_member(const struct slist_head *head,
			  const struct slist_item *item)
{
	struct slist_item *fromhead = head->first;
	struct slist_item **fromnext = (struct slist_item **)&item->next;

	while (fromhead != _SLIST_LAST) {
		if (fromhead == item || fromnext == head->last_next)
			return true;

		fromhead = fromhead->next;
		if (!*fromnext || *fromnext == _SLIST_LAST)
			break;
		fromnext = &(*fromnext)->next;
	}

	return false;
}

bool typesafe_dlist_member(const struct dlist_head *head,
			   const struct dlist_item *item)
{
	const struct dlist_item *fromhead = head->hitem.next;
	const struct dlist_item *fromitem = item->next;

	if (!item->prev || !item->next)
		return false;

	while (fromhead != &head->hitem && fromitem != item) {
		if (fromitem == &head->hitem || fromhead == item)
			return true;
		fromhead = fromhead->next;
		fromitem = fromitem->next;
	}

	return false;
}

#if 0
static void hash_consistency_check(struct thash_head *head)
{
	uint32_t i;
	struct thash_item *item, *prev;

	for (i = 0; i < HASH_SIZE(*head); i++) {
		item = head->entries[i];
		prev = NULL;
		while (item) {
			assert(HASH_KEY(*head, item->hashval) == i);
			assert(!prev || item->hashval >= prev->hashval);
			prev = item;
			item = item->next;
		}
	}
}
#else
#define hash_consistency_check(x)
#endif

void typesafe_hash_grow(struct thash_head *head)
{
	uint32_t newsize = head->count, i, j;
	uint8_t newshift, delta;

	/* note hash_grow is called after head->count++, so newsize is
	 * guaranteed to be >= 1.  So the minimum argument to builtin_ctz
	 * below is 2, which returns 1, and that makes newshift >= 2.
	 *
	 * Calling hash_grow with a zero head->count would result in a
	 * malformed hash table that has tabshift == 1.
	 */
	assert(head->count > 0);

	hash_consistency_check(head);

	newsize |= newsize >> 1;
	newsize |= newsize >> 2;
	newsize |= newsize >> 4;
	newsize |= newsize >> 8;
	newsize |= newsize >> 16;
	newsize++;
	newshift = __builtin_ctz(newsize) + 1;

	if (head->maxshift && newshift > head->maxshift)
		newshift = head->maxshift;
	if (newshift == head->tabshift)
		return;
	newsize = _HASH_SIZE(newshift);

	head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
			sizeof(head->entries[0]) * newsize);
	memset(head->entries + HASH_SIZE(*head), 0,
			sizeof(head->entries[0]) *
				(newsize - HASH_SIZE(*head)));

	delta = newshift - head->tabshift;

	i = HASH_SIZE(*head);
	if (i == 0)
		goto out;
	do {
		struct thash_item **apos, *item;

		i--;
		apos = &head->entries[i];

		for (j = 0; j < (1U << delta); j++) {
			item = *apos;
			*apos = NULL;

			head->entries[(i << delta) + j] = item;
			apos = &head->entries[(i << delta) + j];

			while ((item = *apos)) {
				uint32_t midbits;
				midbits = _HASH_KEY(newshift, item->hashval);
				midbits &= (1 << delta) - 1;
				if (midbits > j)
					break;
				apos = &item->next;
			}
		}
	} while (i > 0);

out:
	head->tabshift = newshift;
	hash_consistency_check(head);
}

void typesafe_hash_shrink(struct thash_head *head)
{
	uint32_t newsize = head->count, i, j;
	uint8_t newshift, delta;

	hash_consistency_check(head);

	if (!head->count) {
		XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries);
		head->tabshift = 0;
		return;
	}

	newsize |= newsize >> 1;
	newsize |= newsize >> 2;
	newsize |= newsize >> 4;
	newsize |= newsize >> 8;
	newsize |= newsize >> 16;
	newsize++;
	newshift = __builtin_ctz(newsize) + 1;

	if (head->minshift && newshift < head->minshift)
		newshift = head->minshift;
	if (newshift == head->tabshift)
		return;
	newsize = _HASH_SIZE(newshift);

	delta = head->tabshift - newshift;

	for (i = 0; i < newsize; i++) {
		struct thash_item **apos = &head->entries[i];

		for (j = 0; j < (1U << delta); j++) {
			*apos = head->entries[(i << delta) + j];
			while (*apos)
				apos = &(*apos)->next;
		}
	}
	head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
			sizeof(head->entries[0]) * newsize);
	head->tabshift = newshift;

	hash_consistency_check(head);
}

/* skiplist */

static inline struct sskip_item *sl_level_get(const struct sskip_item *item,
			size_t level)
{
	if (level < SKIPLIST_OVERFLOW)
		return item->next[level];
	if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
		return item->next[level];

	uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
	ptrval &= UINTPTR_MAX - 3;
	struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
	return oflow->next[level - SKIPLIST_OVERFLOW];
}

static inline void sl_level_set(struct sskip_item *item, size_t level,
		struct sskip_item *value)
{
	if (level < SKIPLIST_OVERFLOW)
		item->next[level] = value;
	else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
		item->next[level] = value;
	else {
		uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
		ptrval &= UINTPTR_MAX - 3;
		struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
		oflow->next[level - SKIPLIST_OVERFLOW] = value;
	}
}

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))
{
	size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel;
	struct sskip_item *prev = &head->hitem, *next, *auxprev, *auxnext;
	int cmpval;

	/* level / newlevel are 1-counted here */
	newlevel = __builtin_ctz(frr_weak_random()) + 1;
	if (newlevel > SKIPLIST_MAXDEPTH)
		newlevel = SKIPLIST_MAXDEPTH;

	next = NULL;
	while (level >= newlevel) {
		next = sl_level_get(prev, level - 1);
		if (!next) {
			level--;
			continue;
		}
		cmpval = cmpfn(next, item);
		if (cmpval < 0) {
			prev = next;
			continue;
		} else if (cmpval == 0) {
			return next;
		}
		level--;
	}

	/* check for duplicate item - could be removed if code doesn't rely
	 * on it, but not really work the complication. */
	auxlevel = level;
	auxprev = prev;
	while (auxlevel) {
		auxlevel--;
		auxnext = sl_level_get(auxprev, auxlevel);
		cmpval = 1;
		while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) {
			auxprev = auxnext;
			auxnext = sl_level_get(auxprev, auxlevel);
		}
		if (cmpval == 0)
			return auxnext;
	};

	head->count++;
	memset(item, 0, sizeof(*item));
	if (newlevel > SKIPLIST_EMBED) {
		struct sskip_overflow *oflow;
		oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *)
				* (newlevel - SKIPLIST_OVERFLOW));
		item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *)
				((uintptr_t)oflow | 1);
	}

	sl_level_set(item, level, next);
	sl_level_set(prev, level, item);
	/* level is now 0-counted and < newlevel*/
	while (level) {
		level--;
		next = sl_level_get(prev, level);
		while (next && cmpfn(next, item) < 0) {
			prev = next;
			next = sl_level_get(prev, level);
		}

		sl_level_set(item, level, next);
		sl_level_set(prev, level, item);
	};
	return NULL;
}

/* NOTE: level counting below is 1-based since that makes the code simpler! */

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))
{
	size_t level = SKIPLIST_MAXDEPTH;
	const struct sskip_item *prev = &head->hitem, *next;
	int cmpval;

	while (level) {
		next = sl_level_get(prev, level - 1);
		if (!next) {
			level--;
			continue;
		}
		cmpval = cmpfn(next, item);
		if (cmpval < 0) {
			prev = next;
			continue;
		}
		if (cmpval == 0)
			return next;
		level--;
	}
	return NULL;
}

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))
{
	size_t level = SKIPLIST_MAXDEPTH;
	const struct sskip_item *prev = &head->hitem, *next;
	int cmpval;

	while (level) {
		next = sl_level_get(prev, level - 1);
		if (!next) {
			level--;
			continue;
		}
		cmpval = cmpfn(next, item);
		if (cmpval < 0) {
			prev = next;
			continue;
		}
		if (cmpval == 0)
			return next;
		level--;
	}
	return next;
}

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))
{
	size_t level = SKIPLIST_MAXDEPTH;
	const struct sskip_item *prev = &head->hitem, *next, *best = NULL;
	int cmpval;

	while (level) {
		next = sl_level_get(prev, level - 1);
		if (!next) {
			level--;
			continue;
		}
		cmpval = cmpfn(next, item);
		if (cmpval < 0) {
			best = prev = next;
			continue;
		}
		level--;
	}
	return best;
}

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))
{
	size_t level = SKIPLIST_MAXDEPTH;
	struct sskip_item *prev = &head->hitem, *next;
	int cmpval;
	bool found = false;

	while (level) {
		next = sl_level_get(prev, level - 1);
		if (!next) {
			level--;
			continue;
		}
		if (next == item) {
			sl_level_set(prev, level - 1,
				sl_level_get(item, level - 1));
			level--;
			found = true;
			continue;
		}
		cmpval = cmpfn(next, item);
		if (cmpval < 0) {
			prev = next;
			continue;
		}
		level--;
	}

	if (!found)
		return NULL;

	/* TBD: assert when trying to remove non-existing item? */
	head->count--;

	if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
		uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
		ptrval &= UINTPTR_MAX - 3;
		struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
		XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
	}
	memset(item, 0, sizeof(*item));

	return item;
}

struct sskip_item *typesafe_skiplist_pop(struct sskip_head *head)
{
	size_t level = SKIPLIST_MAXDEPTH;
	struct sskip_item *prev = &head->hitem, *next, *item;

	item = sl_level_get(prev, 0);
	if (!item)
		return NULL;

	do {
		level--;

		next = sl_level_get(prev, level);
		if (next != item)
			continue;

		sl_level_set(prev, level, sl_level_get(item, level));
	} while (level);

	head->count--;

	if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
		uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
		ptrval &= UINTPTR_MAX - 3;
		struct sskip_overflow *oflow = (struct sskip_overflow *)ptrval;
		XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
	}
	memset(item, 0, sizeof(*item));

	return item;
}

/* heap */

#if 0
static void heap_consistency_check(struct heap_head *head,
				   int (*cmpfn)(const struct heap_item *a,
						const struct heap_item *b),
				   uint32_t pos)
{
	uint32_t rghtpos = pos + 1;
	uint32_t downpos = HEAP_NARY * (pos + 1);

	if (pos + 1 > ~0U / HEAP_NARY)
		downpos = ~0U;

	if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) {
		assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0);
		heap_consistency_check(head, cmpfn, rghtpos);
	}
	if (downpos < head->count) {
		assert(cmpfn(head->array[downpos], head->array[pos]) >= 0);
		heap_consistency_check(head, cmpfn, downpos);
	}
}
#else
#define heap_consistency_check(head, cmpfn, pos)
#endif

void typesafe_heap_resize(struct heap_head *head, bool grow)
{
	uint32_t newsize;

	if (grow) {
		newsize = head->arraysz;
		if (newsize <= 36)
			newsize = 72;
		else if (newsize < 262144)
			newsize += newsize / 2;
		else if (newsize < 0xaaaa0000)
			newsize += newsize / 3;
		else
			assert(!newsize);
	} else if (head->count > 0) {
		newsize = head->count;
	} else {
		XFREE(MTYPE_HEAP_ARRAY, head->array);
		head->arraysz = 0;
		return;
	}

	newsize += HEAP_NARY - 1;
	newsize &= ~(HEAP_NARY - 1);
	if (newsize == head->arraysz)
		return;

	head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array,
			       newsize * sizeof(struct heap_item *));
	head->arraysz = newsize;
}

void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos,
		struct heap_item *item,
		int (*cmpfn)(const struct heap_item *a,
			     const struct heap_item *b))
{
	uint32_t rghtpos, downpos, moveto;

	while (1) {
		/* rghtpos: neighbor to the "right", inside block of NARY.
		 *          may be invalid if last in block, check nary_last()
		 * downpos: first neighbor in the "downwards" block further
		 *          away from the root
		 */
		rghtpos = pos + 1;

		/* make sure we can use the full 4G items */
		downpos = HEAP_NARY * (pos + 1);
		if (pos + 1 > ~0U / HEAP_NARY)
			/* multiplication overflowed.  ~0U is guaranteed
			 * to be an invalid index; size limit is enforced in
			 * resize()
			 */
			downpos = ~0U;

		/* only used on break */
		moveto = pos;

#define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
		if (downpos >= head->count
		    || cmpfn(head->array[downpos], item) >= 0) {
			/* not moving down; either at end or down is >= item */
			if (nary_last(pos) || rghtpos >= head->count
			    || cmpfn(head->array[rghtpos], item) >= 0)
				/* not moving right either - got our spot */
				break;

			moveto = rghtpos;

		/* else: downpos is valid and < item.  choose between down
		 * or right (if the latter is an option) */
		} else if (nary_last(pos) || cmpfn(head->array[rghtpos],
						   head->array[downpos]) >= 0)
			moveto = downpos;
		else
			moveto = rghtpos;
#undef nary_last

		head->array[pos] = head->array[moveto];
		head->array[pos]->index = pos;
		pos = moveto;
	}

	head->array[moveto] = item;
	item->index = moveto;

	heap_consistency_check(head, cmpfn, 0);
}

void typesafe_heap_pullup(struct heap_head *head, uint32_t pos,
		struct heap_item *item,
		int (*cmpfn)(const struct heap_item *a,
			     const struct heap_item *b))
{
	uint32_t moveto;

	while (pos != 0) {
		if ((pos & (HEAP_NARY - 1)) == 0)
			moveto = pos / HEAP_NARY - 1;
		else
			moveto = pos - 1;

		if (cmpfn(head->array[moveto], item) <= 0)
			break;

		head->array[pos] = head->array[moveto];
		head->array[pos]->index = pos;

		pos = moveto;
	}

	head->array[pos] = item;
	item->index = pos;

	heap_consistency_check(head, cmpfn, 0);
}
Commit	Line	Data
acddc0ed	1	// SPDX-License-Identifier: ISC
abd71baa DL	2	/*
abd71baa DL	3	* Copyright (c) 2019 David Lamparter, for NetDEF, Inc.
abd71baa DL	4	*/
abd71baa DL	5
2618a52e DL	6	#ifdef HAVE_CONFIG_H
	7	#include "config.h"
	8	#endif
	9
abd71baa DL	10	#include <stdlib.h>
abd71baa DL	11	#include <string.h>
8d4e934b	12	#include <assert.h>
abd71baa DL	13
	14	#include "typesafe.h"
	15	#include "memory.h"
5920b3eb	16	#include "network.h"
abd71baa	17
bf8d3d6a DL	18	DEFINE_MTYPE_STATIC(LIB, TYPEDHASH_BUCKET, "Typed-hash bucket");
	19	DEFINE_MTYPE_STATIC(LIB, SKIPLIST_OFLOW, "Skiplist overflow");
	20	DEFINE_MTYPE_STATIC(LIB, HEAP_ARRAY, "Typed-heap array");
abd71baa	21
d259ca09 DL	22	struct slist_item typesafe_slist_sentinel = { NULL };
d259ca09 DL	23
f45897e4 DL	24	bool typesafe_list_member(const struct slist_head *head,
	25	const struct slist_item *item)
	26	{
	27	struct slist_item *fromhead = head->first;
	28	struct slist_item fromnext = (struct slist_item )&item->next;
	29
d259ca09	30	while (fromhead != _SLIST_LAST) {
f45897e4 DL	31	if (fromhead == item \|\| fromnext == head->last_next)
	32	return true;
	33
	34	fromhead = fromhead->next;
d259ca09	35	if (!fromnext \|\| fromnext == _SLIST_LAST)
f45897e4 DL	36	break;
	37	fromnext = &(*fromnext)->next;
	38	}
	39
	40	return false;
	41	}
	42
	43	bool typesafe_dlist_member(const struct dlist_head *head,
	44	const struct dlist_item *item)
	45	{
	46	const struct dlist_item *fromhead = head->hitem.next;
	47	const struct dlist_item *fromitem = item->next;
	48
	49	if (!item->prev \|\| !item->next)
	50	return false;
	51
	52	while (fromhead != &head->hitem && fromitem != item) {
	53	if (fromitem == &head->hitem \|\| fromhead == item)
	54	return true;
	55	fromhead = fromhead->next;
	56	fromitem = fromitem->next;
	57	}
	58
	59	return false;
	60	}
	61
abd71baa DL	62	#if 0
	63	static void hash_consistency_check(struct thash_head *head)
	64	{
	65	uint32_t i;
	66	struct thash_item item, prev;
	67
	68	for (i = 0; i < HASH_SIZE(*head); i++) {
	69	item = head->entries[i];
	70	prev = NULL;
	71	while (item) {
	72	assert(HASH_KEY(*head, item->hashval) == i);
	73	assert(!prev \|\| item->hashval >= prev->hashval);
	74	prev = item;
	75	item = item->next;
	76	}
	77	}
	78	}
	79	#else
	80	#define hash_consistency_check(x)
	81	#endif
	82
	83	void typesafe_hash_grow(struct thash_head *head)
	84	{
	85	uint32_t newsize = head->count, i, j;
	86	uint8_t newshift, delta;
	87
ae19023b DL	88	/* note hash_grow is called after head->count++, so newsize is
	89	* guaranteed to be >= 1. So the minimum argument to builtin_ctz
	90	* below is 2, which returns 1, and that makes newshift >= 2.
	91	*
	92	* Calling hash_grow with a zero head->count would result in a
	93	* malformed hash table that has tabshift == 1.
	94	*/
	95	assert(head->count > 0);
	96
abd71baa DL	97	hash_consistency_check(head);
	98
	99	newsize \|= newsize >> 1;
	100	newsize \|= newsize >> 2;
	101	newsize \|= newsize >> 4;
	102	newsize \|= newsize >> 8;
	103	newsize \|= newsize >> 16;
	104	newsize++;
	105	newshift = __builtin_ctz(newsize) + 1;
	106
	107	if (head->maxshift && newshift > head->maxshift)
	108	newshift = head->maxshift;
	109	if (newshift == head->tabshift)
	110	return;
	111	newsize = _HASH_SIZE(newshift);
	112
	113	head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
	114	sizeof(head->entries[0]) * newsize);
	115	memset(head->entries + HASH_SIZE(*head), 0,
	116	sizeof(head->entries[0]) *
	117	(newsize - HASH_SIZE(*head)));
	118
	119	delta = newshift - head->tabshift;
	120
	121	i = HASH_SIZE(*head);
	122	if (i == 0)
	123	goto out;
	124	do {
	125	struct thash_item *apos, item;
	126
	127	i--;
	128	apos = &head->entries[i];
	129
	130	for (j = 0; j < (1U << delta); j++) {
	131	item = *apos;
	132	*apos = NULL;
	133
	134	head->entries[(i << delta) + j] = item;
	135	apos = &head->entries[(i << delta) + j];
	136
	137	while ((item = *apos)) {
	138	uint32_t midbits;
	139	midbits = _HASH_KEY(newshift, item->hashval);
	140	midbits &= (1 << delta) - 1;
	141	if (midbits > j)
	142	break;
	143	apos = &item->next;
	144	}
	145	}
	146	} while (i > 0);
	147
	148	out:
	149	head->tabshift = newshift;
	150	hash_consistency_check(head);
	151	}
	152
	153	void typesafe_hash_shrink(struct thash_head *head)
	154	{
	155	uint32_t newsize = head->count, i, j;
	156	uint8_t newshift, delta;
	157
	158	hash_consistency_check(head);
	159
	160	if (!head->count) {
161	XFREE(MTYPE_TYPEDHASH_BUCKET, head->entries);
162	head->tabshift = 0;
163	return;
164	}
165
166	newsize \|= newsize >> 1;
167	newsize \|= newsize >> 2;
168	newsize \|= newsize >> 4;
169	newsize \|= newsize >> 8;
170	newsize \|= newsize >> 16;
171	newsize++;
172	newshift = __builtin_ctz(newsize) + 1;
173
174	if (head->minshift && newshift < head->minshift)
175	newshift = head->minshift;
176	if (newshift == head->tabshift)
177	return;
178	newsize = _HASH_SIZE(newshift);
179
180	delta = head->tabshift - newshift;
181
182	for (i = 0; i < newsize; i++) {
183	struct thash_item **apos = &head->entries[i];
184
185	for (j = 0; j < (1U << delta); j++) {
186	*apos = head->entries[(i << delta) + j];
187	while (*apos)
188	apos = &(*apos)->next;
189	}
190	}
191	head->entries = XREALLOC(MTYPE_TYPEDHASH_BUCKET, head->entries,
192	sizeof(head->entries[0]) * newsize);
193	head->tabshift = newshift;
194
195	hash_consistency_check(head);
196	}
197
198	/* skiplist */
199
daf3441d	200	static inline struct sskip_item sl_level_get(const struct sskip_item item,
abd71baa DL	201	size_t level)
	202	{
	203	if (level < SKIPLIST_OVERFLOW)
	204	return item->next[level];
	205	if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
	206	return item->next[level];
	207
	208	uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
	209	ptrval &= UINTPTR_MAX - 3;
	210	struct sskip_overflow oflow = (struct sskip_overflow )ptrval;
	211	return oflow->next[level - SKIPLIST_OVERFLOW];
	212	}
	213
	214	static inline void sl_level_set(struct sskip_item *item, size_t level,
	215	struct sskip_item *value)
	216	{
	217	if (level < SKIPLIST_OVERFLOW)
	218	item->next[level] = value;
	219	else if (level == SKIPLIST_OVERFLOW && !((uintptr_t)item->next[level] & 1))
	220	item->next[level] = value;
	221	else {
	222	uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
	223	ptrval &= UINTPTR_MAX - 3;
	224	struct sskip_overflow oflow = (struct sskip_overflow )ptrval;
	225	oflow->next[level - SKIPLIST_OVERFLOW] = value;
	226	}
	227	}
	228
	229	struct sskip_item typesafe_skiplist_add(struct sskip_head head,
	230	struct sskip_item *item,
	231	int (cmpfn)(const struct sskip_item a,
	232	const struct sskip_item *b))
	233	{
	234	size_t level = SKIPLIST_MAXDEPTH, newlevel, auxlevel;
	235	struct sskip_item prev = &head->hitem, next, auxprev, auxnext;
	236	int cmpval;
	237
	238	/* level / newlevel are 1-counted here */
5920b3eb	239	newlevel = __builtin_ctz(frr_weak_random()) + 1;
abd71baa DL	240	if (newlevel > SKIPLIST_MAXDEPTH)
	241	newlevel = SKIPLIST_MAXDEPTH;
	242
	243	next = NULL;
	244	while (level >= newlevel) {
	245	next = sl_level_get(prev, level - 1);
	246	if (!next) {
	247	level--;
	248	continue;
	249	}
	250	cmpval = cmpfn(next, item);
	251	if (cmpval < 0) {
	252	prev = next;
	253	continue;
	254	} else if (cmpval == 0) {
	255	return next;
	256	}
	257	level--;
	258	}
	259
	260	/* check for duplicate item - could be removed if code doesn't rely
	261	* on it, but not really work the complication. */
	262	auxlevel = level;
	263	auxprev = prev;
	264	while (auxlevel) {
	265	auxlevel--;
	266	auxnext = sl_level_get(auxprev, auxlevel);
	267	cmpval = 1;
	268	while (auxnext && (cmpval = cmpfn(auxnext, item)) < 0) {
	269	auxprev = auxnext;
	270	auxnext = sl_level_get(auxprev, auxlevel);
	271	}
	272	if (cmpval == 0)
	273	return auxnext;
	274	};
	275
	276	head->count++;
	277	memset(item, 0, sizeof(*item));
	278	if (newlevel > SKIPLIST_EMBED) {
	279	struct sskip_overflow *oflow;
	280	oflow = XMALLOC(MTYPE_SKIPLIST_OFLOW, sizeof(void *)
	281	* (newlevel - SKIPLIST_OVERFLOW));
	282	item->next[SKIPLIST_OVERFLOW] = (struct sskip_item *)
	283	((uintptr_t)oflow \| 1);
	284	}
	285
	286	sl_level_set(item, level, next);
	287	sl_level_set(prev, level, item);
	288	/* level is now 0-counted and < newlevel*/
	289	while (level) {
	290	level--;
	291	next = sl_level_get(prev, level);
	292	while (next && cmpfn(next, item) < 0) {
	293	prev = next;
	294	next = sl_level_get(prev, level);
	295	}
	296
	297	sl_level_set(item, level, next);
	298	sl_level_set(prev, level, item);
	299	};
	300	return NULL;
	301	}
	302
	303	/* NOTE: level counting below is 1-based since that makes the code simpler! */
304
daf3441d DL	305	const struct sskip_item *typesafe_skiplist_find(
daf3441d DL	306	const struct sskip_head *head,
abd71baa DL	307	const struct sskip_item item, int (cmpfn)(
	308	const struct sskip_item *a,
	309	const struct sskip_item *b))
	310	{
	311	size_t level = SKIPLIST_MAXDEPTH;
daf3441d	312	const struct sskip_item prev = &head->hitem, next;
abd71baa DL	313	int cmpval;
	314
	315	while (level) {
	316	next = sl_level_get(prev, level - 1);
	317	if (!next) {
	318	level--;
	319	continue;
	320	}
	321	cmpval = cmpfn(next, item);
	322	if (cmpval < 0) {
	323	prev = next;
	324	continue;
	325	}
	326	if (cmpval == 0)
	327	return next;
	328	level--;
	329	}
	330	return NULL;
	331	}
	332
daf3441d DL	333	const struct sskip_item *typesafe_skiplist_find_gteq(
daf3441d DL	334	const struct sskip_head *head,
abd71baa DL	335	const struct sskip_item item, int (cmpfn)(
	336	const struct sskip_item *a,
	337	const struct sskip_item *b))
	338	{
	339	size_t level = SKIPLIST_MAXDEPTH;
daf3441d	340	const struct sskip_item prev = &head->hitem, next;
abd71baa DL	341	int cmpval;
	342
	343	while (level) {
	344	next = sl_level_get(prev, level - 1);
	345	if (!next) {
	346	level--;
	347	continue;
	348	}
	349	cmpval = cmpfn(next, item);
	350	if (cmpval < 0) {
	351	prev = next;
	352	continue;
	353	}
	354	if (cmpval == 0)
	355	return next;
	356	level--;
	357	}
	358	return next;
	359	}
	360
daf3441d DL	361	const struct sskip_item *typesafe_skiplist_find_lt(
daf3441d DL	362	const struct sskip_head *head,
abd71baa DL	363	const struct sskip_item item, int (cmpfn)(
	364	const struct sskip_item *a,
	365	const struct sskip_item *b))
	366	{
	367	size_t level = SKIPLIST_MAXDEPTH;
daf3441d	368	const struct sskip_item prev = &head->hitem, next, *best = NULL;
abd71baa DL	369	int cmpval;
	370
	371	while (level) {
	372	next = sl_level_get(prev, level - 1);
	373	if (!next) {
	374	level--;
	375	continue;
	376	}
	377	cmpval = cmpfn(next, item);
	378	if (cmpval < 0) {
	379	best = prev = next;
	380	continue;
	381	}
	382	level--;
	383	}
	384	return best;
	385	}
	386
da098d78 SW	387	struct sskip_item *typesafe_skiplist_del(
	388	struct sskip_head head, struct sskip_item item,
	389	int (cmpfn)(const struct sskip_item a, const struct sskip_item *b))
abd71baa DL	390	{
	391	size_t level = SKIPLIST_MAXDEPTH;
	392	struct sskip_item prev = &head->hitem, next;
	393	int cmpval;
da098d78	394	bool found = false;
abd71baa DL	395
	396	while (level) {
	397	next = sl_level_get(prev, level - 1);
	398	if (!next) {
	399	level--;
	400	continue;
	401	}
	402	if (next == item) {
	403	sl_level_set(prev, level - 1,
	404	sl_level_get(item, level - 1));
	405	level--;
da098d78	406	found = true;
abd71baa DL	407	continue;
	408	}
	409	cmpval = cmpfn(next, item);
	410	if (cmpval < 0) {
	411	prev = next;
	412	continue;
	413	}
	414	level--;
	415	}
	416
da098d78 SW	417	if (!found)
	418	return NULL;
	419
abd71baa DL	420	/* TBD: assert when trying to remove non-existing item? */
	421	head->count--;
	422
	423	if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
	424	uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
	425	ptrval &= UINTPTR_MAX - 3;
	426	struct sskip_overflow oflow = (struct sskip_overflow )ptrval;
	427	XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
	428	}
	429	memset(item, 0, sizeof(*item));
da098d78 SW	430
da098d78 SW	431	return item;
abd71baa	432	}
01734da3 DL	433
	434	struct sskip_item typesafe_skiplist_pop(struct sskip_head head)
	435	{
	436	size_t level = SKIPLIST_MAXDEPTH;
	437	struct sskip_item prev = &head->hitem, next, *item;
	438
	439	item = sl_level_get(prev, 0);
	440	if (!item)
	441	return NULL;
	442
	443	do {
	444	level--;
	445
	446	next = sl_level_get(prev, level);
	447	if (next != item)
	448	continue;
	449
	450	sl_level_set(prev, level, sl_level_get(item, level));
	451	} while (level);
	452
	453	head->count--;
	454
	455	if ((uintptr_t)item->next[SKIPLIST_OVERFLOW] & 1) {
	456	uintptr_t ptrval = (uintptr_t)item->next[SKIPLIST_OVERFLOW];
	457	ptrval &= UINTPTR_MAX - 3;
	458	struct sskip_overflow oflow = (struct sskip_overflow )ptrval;
	459	XFREE(MTYPE_SKIPLIST_OFLOW, oflow);
	460	}
	461	memset(item, 0, sizeof(*item));
	462
	463	return item;
	464	}
5cb4277d DL	465
	466	/* heap */
	467
	468	#if 0
	469	static void heap_consistency_check(struct heap_head *head,
	470	int (cmpfn)(const struct heap_item a,
	471	const struct heap_item *b),
	472	uint32_t pos)
	473	{
	474	uint32_t rghtpos = pos + 1;
	475	uint32_t downpos = HEAP_NARY * (pos + 1);
	476
	477	if (pos + 1 > ~0U / HEAP_NARY)
	478	downpos = ~0U;
	479
	480	if ((pos & (HEAP_NARY - 1)) != HEAP_NARY - 1 && rghtpos < head->count) {
	481	assert(cmpfn(head->array[rghtpos], head->array[pos]) >= 0);
	482	heap_consistency_check(head, cmpfn, rghtpos);
	483	}
	484	if (downpos < head->count) {
	485	assert(cmpfn(head->array[downpos], head->array[pos]) >= 0);
	486	heap_consistency_check(head, cmpfn, downpos);
	487	}
	488	}
	489	#else
	490	#define heap_consistency_check(head, cmpfn, pos)
	491	#endif
	492
	493	void typesafe_heap_resize(struct heap_head *head, bool grow)
	494	{
	495	uint32_t newsize;
	496
	497	if (grow) {
	498	newsize = head->arraysz;
	499	if (newsize <= 36)
	500	newsize = 72;
	501	else if (newsize < 262144)
	502	newsize += newsize / 2;
	503	else if (newsize < 0xaaaa0000)
	504	newsize += newsize / 3;
	505	else
	506	assert(!newsize);
	507	} else if (head->count > 0) {
	508	newsize = head->count;
	509	} else {
	510	XFREE(MTYPE_HEAP_ARRAY, head->array);
	511	head->arraysz = 0;
	512	return;
	513	}
	514
	515	newsize += HEAP_NARY - 1;
	516	newsize &= ~(HEAP_NARY - 1);
	517	if (newsize == head->arraysz)
	518	return;
c258527b	519
5cb4277d DL	520	head->array = XREALLOC(MTYPE_HEAP_ARRAY, head->array,
	521	newsize * sizeof(struct heap_item *));
	522	head->arraysz = newsize;
	523	}
	524
	525	void typesafe_heap_pushdown(struct heap_head *head, uint32_t pos,
	526	struct heap_item *item,
	527	int (cmpfn)(const struct heap_item a,
	528	const struct heap_item *b))
	529	{
	530	uint32_t rghtpos, downpos, moveto;
	531
	532	while (1) {
	533	/* rghtpos: neighbor to the "right", inside block of NARY.
	534	* may be invalid if last in block, check nary_last()
	535	* downpos: first neighbor in the "downwards" block further
	536	* away from the root
	537	*/
	538	rghtpos = pos + 1;
	539
	540	/* make sure we can use the full 4G items */
	541	downpos = HEAP_NARY * (pos + 1);
	542	if (pos + 1 > ~0U / HEAP_NARY)
	543	/* multiplication overflowed. ~0U is guaranteed
	544	* to be an invalid index; size limit is enforced in
	545	* resize()
	546	*/
	547	downpos = ~0U;
	548
	549	/* only used on break */
	550	moveto = pos;
	551
	552	#define nary_last(x) (((x) & (HEAP_NARY - 1)) == HEAP_NARY - 1)
	553	if (downpos >= head->count
	554	\|\| cmpfn(head->array[downpos], item) >= 0) {
	555	/* not moving down; either at end or down is >= item */
	556	if (nary_last(pos) \|\| rghtpos >= head->count
	557	\|\| cmpfn(head->array[rghtpos], item) >= 0)
	558	/* not moving right either - got our spot */
	559	break;
	560
	561	moveto = rghtpos;
	562
	563	/* else: downpos is valid and < item. choose between down
	564	* or right (if the latter is an option) */
	565	} else if (nary_last(pos) \|\| cmpfn(head->array[rghtpos],
	566	head->array[downpos]) >= 0)
	567	moveto = downpos;
	568	else
	569	moveto = rghtpos;
	570	#undef nary_last
	571
	572	head->array[pos] = head->array[moveto];
	573	head->array[pos]->index = pos;
	574	pos = moveto;
	575	}
	576
	577	head->array[moveto] = item;
	578	item->index = moveto;
	579
	580	heap_consistency_check(head, cmpfn, 0);
	581	}
	582
	583	void typesafe_heap_pullup(struct heap_head *head, uint32_t pos,
584	struct heap_item *item,
585	int (cmpfn)(const struct heap_item a,
586	const struct heap_item *b))
587	{
588	uint32_t moveto;
589
590	while (pos != 0) {
591	if ((pos & (HEAP_NARY - 1)) == 0)
592	moveto = pos / HEAP_NARY - 1;
593	else
594	moveto = pos - 1;
595
596	if (cmpfn(head->array[moveto], item) <= 0)
597	break;
598
599	head->array[pos] = head->array[moveto];
600	head->array[pos]->index = pos;
601
602	pos = moveto;
603	}
604
605	head->array[pos] = item;
606	item->index = pos;
607
608	heap_consistency_check(head, cmpfn, 0);
609	}