[mirror_frr.git] / lib / skiplist.c

/*
 * Copyright 1990 William Pugh
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 * Permission to include in quagga provide on March 31, 2016
 */

/*
 * Skip List impementation based on code from William Pugh.
 * ftp://ftp.cs.umd.edu/pub/skipLists/
 *
 * Skip Lists are a probabilistic alternative to balanced trees, as
 * described in the June 1990 issue of CACM and were invented by
 * William Pugh in 1987.
 *
 * This file contains source code to implement a dictionary using
 * skip lists and a test driver to test the routines.
 *
 * A couple of comments about this implementation:
 *   The routine randomLevel has been hard-coded to generate random
 *   levels using p=0.25. It can be easily changed.
 *
 *   The insertion routine has been implemented so as to use the
 *   dirty hack described in the CACM paper: if a random level is
 *   generated that is more than the current maximum level, the
 *   current maximum level plus one is used instead.
 *
 *   Levels start at zero and go up to MaxLevel (which is equal to
 * 	(MaxNumberOfLevels-1).
 *
 * The run-time flag SKIPLIST_FLAG_ALLOW_DUPLICATES determines whether or
 * not duplicates are allowed for a given list. If set, duplicates are
 * allowed and act in a FIFO manner. If not set, an insertion of a value
 * already in the list updates the previously existing binding.
 *
 * BitsInRandom is defined to be the number of bits returned by a call to
 * random(). For most all machines with 32-bit integers, this is 31 bits
 * as currently set.
 */


#include <zebra.h>

#include "memory.h"
#include "log.h"
#include "vty.h"
#include "skiplist.h"
#include "lib_errors.h"
#include "network.h"

DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List")
DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node")

#define BitsInRandom 31

#define MaxNumberOfLevels 16
#define MaxLevel (MaxNumberOfLevels-1)
#define newNodeOfLevel(l) XCALLOC(MTYPE_SKIP_LIST_NODE, sizeof(struct skiplistnode)+(l)*sizeof(struct skiplistnode *))

static int randomsLeft;
static int randomBits;
static struct skiplist *skiplist_last_created; /* debugging hack */

#if 1
#define CHECKLAST(sl)                                                          \
	do {                                                                   \
		if ((sl)->header->forward[0] && !(sl)->last)                   \
			assert(0);                                             \
		if (!(sl)->header->forward[0] && (sl)->last)                   \
			assert(0);                                             \
	} while (0)
#else
#define CHECKLAST(sl)
#endif


static int randomLevel(void)
{
	register int level = 0;
	register int b;

	do {
		if (randomsLeft <= 0) {
			randomBits = frr_weak_random();
			randomsLeft = BitsInRandom / 2;
		}
		b = randomBits & 3;
		randomBits >>= 2;
		--randomsLeft;

		if (!b) {
			level++;
			if (level >= MaxLevel)
				return MaxLevel;
		}
	} while (!b);

	return level;
}

static int default_cmp(const void *key1, const void *key2)
{
	if (key1 < key2)
		return -1;
	if (key1 > key2)
		return 1;
	return 0;
}

unsigned int skiplist_count(struct skiplist *l)
{
	return l->count;
}

struct skiplist *skiplist_new(int flags,
			      int (*cmp)(const void *key1, const void *key2),
			      void (*del)(void *val))
{
	struct skiplist *new;

	new = XCALLOC(MTYPE_SKIP_LIST, sizeof(struct skiplist));
	assert(new);

	new->level = 0;
	new->count = 0;
	new->header = newNodeOfLevel(MaxNumberOfLevels);
	new->stats = newNodeOfLevel(MaxNumberOfLevels);

	new->flags = flags;
	if (cmp)
		new->cmp = cmp;
	else
		new->cmp = default_cmp;

	if (del)
		new->del = del;

	skiplist_last_created = new; /* debug */

	return new;
}

void skiplist_free(struct skiplist *l)
{
	register struct skiplistnode *p, *q;

	p = l->header;

	do {
		q = p->forward[0];
		if (l->del && p != l->header)
			(*l->del)(p->value);
		XFREE(MTYPE_SKIP_LIST_NODE, p);
		p = q;
	} while (p);

	XFREE(MTYPE_SKIP_LIST_NODE, l->stats);
	XFREE(MTYPE_SKIP_LIST, l);
}


int skiplist_insert(register struct skiplist *l, register void *key,
		    register void *value)
{
	register int k;
	struct skiplistnode *update[MaxNumberOfLevels];
	register struct skiplistnode *p, *q;

	CHECKLAST(l);

	/* DEBUG */
	if (!key) {
		flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p",
			 __func__, value);
	}

	p = l->header;
	k = l->level;
	do {
		while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
			p = q;
		update[k] = p;
	} while (--k >= 0);

	if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) && q
	    && ((*l->cmp)(q->key, key) == 0)) {

		return -1;
	}

	k = randomLevel();
	assert(k >= 0);
	if (k > l->level) {
		k = ++l->level;
		update[k] = l->header;
	}

	q = newNodeOfLevel(k);
	q->key = key;
	q->value = value;
#ifdef SKIPLIST_0TIMER_DEBUG
	q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
#endif

	++(l->stats->forward[k]);
#ifdef SKIPLIST_DEBUG
	zlog_debug("%s: incremented stats @%p:%d, now %ld", __func__, l, k,
		   l->stats->forward[k] - (struct skiplistnode *)NULL);
#endif

	do {
		p = update[k];
		q->forward[k] = p->forward[k];
		p->forward[k] = q;
	} while (--k >= 0);

	/*
	 * If this is the last item in the list, update the "last" pointer
	 */
	if (!q->forward[0]) {
		l->last = q;
	}

	++(l->count);

	CHECKLAST(l);

	return 0;
}

int skiplist_delete(register struct skiplist *l, register void *key,
		    register void *value) /* used only if duplicates allowed */
{
	register int k, m;
	struct skiplistnode *update[MaxNumberOfLevels];
	register struct skiplistnode *p, *q;

	CHECKLAST(l);

	/* to make debugging easier */
	for (k = 0; k < MaxNumberOfLevels; ++k)
		update[k] = NULL;

	p = l->header;
	k = m = l->level;
	do {
		while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
			p = q;
		update[k] = p;
	} while (--k >= 0);

	if (l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) {
		while (q && ((*l->cmp)(q->key, key) == 0)
		       && (q->value != value)) {
			int i;
			for (i = 0; i <= l->level; ++i) {
				if (update[i]->forward[i] == q)
					update[i] = q;
			}
			q = q->forward[0];
		}
	}

	if (q && (*l->cmp)(q->key, key) == 0) {
		if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)
		    || (q->value == value)) {

/*
 * found node to delete
 */
#ifdef SKIPLIST_0TIMER_DEBUG
			q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
#endif
			/*
			 * If we are deleting the last element of the list,
			 * update the list's "last" pointer.
			 */
			if (l->last == q) {
				if (update[0] == l->header)
					l->last = NULL;
				else
					l->last = update[0];
			}

			for (k = 0; k <= m && (p = update[k])->forward[k] == q;
			     k++) {
				p->forward[k] = q->forward[k];
			}
			--(l->stats->forward[k - 1]);
#ifdef SKIPLIST_DEBUG
			zlog_debug("%s: decremented stats @%p:%d, now %ld",
				   __func__, l, k - 1,
				   l->stats->forward[k - 1]
					   - (struct skiplistnode *)NULL);
#endif
			if (l->del)
				(*l->del)(q->value);
			XFREE(MTYPE_SKIP_LIST_NODE, q);
			while (l->header->forward[m] == NULL && m > 0)
				m--;
			l->level = m;
			CHECKLAST(l);
			--(l->count);
			return 0;
		}
	}

	CHECKLAST(l);
	return -1;
}

/*
 * Obtain first value matching "key". Unless SKIPLIST_FLAG_ALLOW_DUPLICATES
 * is set, this will also be the only value matching "key".
 *
 * Also set a cursor for use with skiplist_next_value.
 */
int skiplist_first_value(register struct skiplist *l, /* in */
			 register const void *key,    /* in */
			 void **valuePointer,	      /* out */
			 void **cursor)		      /* out */
{
	register int k;
	register struct skiplistnode *p, *q;

	p = l->header;
	k = l->level;

	do {
		while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
			p = q;

	} while (--k >= 0);

	if (!q || (*l->cmp)(q->key, key))
		return -1;

	if (valuePointer)
		*valuePointer = q->value;

	if (cursor)
		*cursor = q;

	return 0;
}

int skiplist_search(register struct skiplist *l, register void *key,
		    void **valuePointer)
{
	return skiplist_first_value(l, key, valuePointer, NULL);
}


/*
 * Caller supplies key and value of an existing item in the list.
 * Function returns the value of the next list item that has the
 * same key (useful when SKIPLIST_FLAG_ALLOW_DUPLICATES is set).
 *
 * Returns 0 on success. If the caller-supplied key and value
 * do not correspond to a list element, or if they specify the
 * last element with the given key, -1 is returned.
 */
int skiplist_next_value(register struct skiplist *l, /* in */
			register const void *key,	  /* in */
			void **valuePointer,	 /* in/out */
			void **cursor)		     /* in/out */
{
	register int k;
	register struct skiplistnode *p, *q;

	CHECKLAST(l);

	if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {
		return -1;
	}

	if (!cursor || !*cursor) {
		p = l->header;
		k = l->level;

		/*
		 * Find matching key
		 */
		do {
			while (q = p->forward[k],
			       q && (*l->cmp)(q->key, key) < 0)
				p = q;
		} while (--k >= 0);

		/*
		 * Find matching value
		 */
		while (q && ((*l->cmp)(q->key, key) == 0)
		       && (q->value != *valuePointer)) {
			q = q->forward[0];
		}

		if (!q || ((*l->cmp)(q->key, key) != 0)
		    || (q->value != *valuePointer)) {
			/*
			 * No matching value
			 */
			CHECKLAST(l);
			return -1;
		}
	} else {
		q = (struct skiplistnode *)*cursor;
	}

	/*
	 * Advance cursor
	 */
	q = q->forward[0];

	/*
	 * If we reached end-of-list or if the key is no longer the same,
	 * then return error
	 */
	if (!q || ((*l->cmp)(q->key, key) != 0))
		return -1;

	*valuePointer = q->value;
	if (cursor)
		*cursor = q;
	CHECKLAST(l);
	return 0;
}

int skiplist_first(register struct skiplist *l, void **keyPointer,
		   void **valuePointer)
{
	register struct skiplistnode *p;

	CHECKLAST(l);
	p = l->header->forward[0];
	if (!p)
		return -1;

	if (keyPointer)
		*keyPointer = p->key;

	if (valuePointer)
		*valuePointer = p->value;

	CHECKLAST(l);

	return 0;
}

int skiplist_last(register struct skiplist *l, void **keyPointer,
		  void **valuePointer)
{
	CHECKLAST(l);
	if (l->last) {
		if (keyPointer)
			*keyPointer = l->last->key;
		if (valuePointer)
			*valuePointer = l->last->value;
		return 0;
	}
	return -1;
}

/*
 * true = empty
 */
int skiplist_empty(register struct skiplist *l)
{
	CHECKLAST(l);
	if (l->last)
		return 0;
	return 1;
}

/*
 * Use this to walk the list. Caller sets *cursor to NULL to obtain
 * first element. Return value of 0 indicates valid cursor/element
 * returned, otherwise NULL cursor arg or EOL.
 */
int skiplist_next(register struct skiplist *l, /* in */
		  void **keyPointer,	   /* out */
		  void **valuePointer,	 /* out */
		  void **cursor)	       /* in/out */
{
	struct skiplistnode *p;

	if (!cursor)
		return -1;

	CHECKLAST(l);

	if (!*cursor) {
		p = l->header->forward[0];
	} else {
		p = *cursor;
		p = p->forward[0];
	}
	*cursor = p;

	if (!p)
		return -1;

	if (keyPointer)
		*keyPointer = p->key;

	if (valuePointer)
		*valuePointer = p->value;

	CHECKLAST(l);

	return 0;
}

int skiplist_delete_first(register struct skiplist *l)
{
	register int k;
	register struct skiplistnode *p, *q;
	int nodelevel = 0;

	CHECKLAST(l);

	p = l->header;
	q = l->header->forward[0];

	if (!q)
		return -1;

	for (k = l->level; k >= 0; --k) {
		if (p->forward[k] == q) {
			p->forward[k] = q->forward[k];
			if ((k == l->level) && (p->forward[k] == NULL)
			    && (l->level > 0))
				--(l->level);
			if (!nodelevel)
				nodelevel = k;
		}
	}

#ifdef SKIPLIST_0TIMER_DEBUG
	q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
#endif
	/*
	 * If we are deleting the last element of the list,
	 * update the list's "last" pointer.
	 */
	if (l->last == q) {
		l->last = NULL;
	}

	--(l->stats->forward[nodelevel]);
#ifdef SKIPLIST_DEBUG
	zlog_debug("%s: decremented stats @%p:%d, now %ld", __func__, l,
		   nodelevel,
		   l->stats->forward[nodelevel] - (struct skiplistnode *)NULL);
#endif

	if (l->del)
		(*l->del)(q->value);

	XFREE(MTYPE_SKIP_LIST_NODE, q);

	CHECKLAST(l);

	--(l->count);

	return 0;
}

void skiplist_debug(struct vty *vty, struct skiplist *l)
{
	int i;

	if (!l)
		l = skiplist_last_created;
	vty_out(vty, "Skiplist %p has max level %d\n", l, l->level);
	for (i = l->level; i >= 0; --i)
		vty_out(vty, "  @%d: %ld\n", i,
			(long)((l->stats->forward[i])
			       - (struct skiplistnode *)NULL));
}

static void *scramble(int i)
{
	uintptr_t result;

	result = (unsigned)(i & 0xff) << 24;
	result |= (unsigned)i >> 8;

	return (void *)result;
}

#define sampleSize 65536
void skiplist_test(struct vty *vty)
{
	struct skiplist *l;
	register int i, k;
	void *keys[sampleSize];
	void *v = NULL;

	zlog_debug("%s: entry", __func__);

	l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);

	zlog_debug("%s: skiplist_new returned %p", __func__, l);

	for (i = 0; i < 4; i++) {

		for (k = 0; k < sampleSize; k++) {
			if (!(k % 1000)) {
				zlog_debug("%s: (%d:%d)", __func__, i, k);
			}
			// keys[k] = (void *)random();
			keys[k] = scramble(k);
			if (skiplist_insert(l, keys[k], keys[k]))
				zlog_debug("error in insert #%d,#%d", i, k);
		}

		zlog_debug("%s: inserts done", __func__);

		for (k = 0; k < sampleSize; k++) {

			if (!(k % 1000))
				zlog_debug("[%d:%d]", i, k);
			if (skiplist_search(l, keys[k], &v))
				zlog_debug("error in search #%d,#%d", i, k);

			if (v != keys[k])
				zlog_debug("search returned wrong value");
		}


		for (k = 0; k < sampleSize; k++) {

			if (!(k % 1000))
				zlog_debug("<%d:%d>", i, k);
			if (skiplist_delete(l, keys[k], keys[k]))
				zlog_debug("error in delete");
			keys[k] = scramble(k ^ 0xf0f0f0f0);
			if (skiplist_insert(l, keys[k], keys[k]))
				zlog_debug("error in insert #%d,#%d", i, k);
		}

		for (k = 0; k < sampleSize; k++) {

			if (!(k % 1000))
				zlog_debug("{%d:%d}", i, k);
			if (skiplist_delete_first(l))
				zlog_debug("error in delete_first");
		}
	}

	skiplist_free(l);
}
Commit	Line	Data
520d2512	1	/*
d62a17ae	2	* Copyright 1990 William Pugh
520d2512 LB	3	*
	4	* Redistribution and use in source and binary forms, with or without
	5	* modification, are permitted.
	6	*
	7	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS''
	8	* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
	9	* TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
	10	* PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR
	11	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	12	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
	13	* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
	14	* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
	15	* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
	16	* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
	17	* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	18	* SUCH DAMAGE.
	19	*
	20	* Permission to include in quagga provide on March 31, 2016
	21	*/
	22
	23	/*
	24	* Skip List impementation based on code from William Pugh.
	25	* ftp://ftp.cs.umd.edu/pub/skipLists/
d62a17ae	26	*
520d2512	27	* Skip Lists are a probabilistic alternative to balanced trees, as
d62a17ae	28	* described in the June 1990 issue of CACM and were invented by
	29	* William Pugh in 1987.
	30	*
	31	* This file contains source code to implement a dictionary using
520d2512	32	* skip lists and a test driver to test the routines.
d62a17ae	33	*
520d2512 LB	34	* A couple of comments about this implementation:
	35	* The routine randomLevel has been hard-coded to generate random
	36	* levels using p=0.25. It can be easily changed.
d62a17ae	37	*
520d2512 LB	38	* The insertion routine has been implemented so as to use the
	39	* dirty hack described in the CACM paper: if a random level is
	40	* generated that is more than the current maximum level, the
	41	* current maximum level plus one is used instead.
d62a17ae	42	*
520d2512 LB	43	* Levels start at zero and go up to MaxLevel (which is equal to
520d2512 LB	44	* (MaxNumberOfLevels-1).
d62a17ae	45	*
520d2512 LB	46	* The run-time flag SKIPLIST_FLAG_ALLOW_DUPLICATES determines whether or
	47	* not duplicates are allowed for a given list. If set, duplicates are
	48	* allowed and act in a FIFO manner. If not set, an insertion of a value
	49	* already in the list updates the previously existing binding.
d62a17ae	50	*
520d2512 LB	51	* BitsInRandom is defined to be the number of bits returned by a call to
520d2512 LB	52	* random(). For most all machines with 32-bit integers, this is 31 bits
d62a17ae	53	* as currently set.
520d2512 LB	54	*/
	55
	56
	57	#include <zebra.h>
	58
	59	#include "memory.h"
	60	#include "log.h"
	61	#include "vty.h"
	62	#include "skiplist.h"
472878dc	63	#include "lib_errors.h"
5920b3eb	64	#include "network.h"
520d2512	65
d62a17ae	66	DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List")
520d2512 LB	67	DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node")
	68
	69	#define BitsInRandom 31
	70
	71	#define MaxNumberOfLevels 16
	72	#define MaxLevel (MaxNumberOfLevels-1)
	73	#define newNodeOfLevel(l) XCALLOC(MTYPE_SKIP_LIST_NODE, sizeof(struct skiplistnode)+(l)sizeof(struct skiplistnode ))
	74
	75	static int randomsLeft;
	76	static int randomBits;
d62a17ae	77	static struct skiplist skiplist_last_created; / debugging hack */
520d2512 LB	78
520d2512 LB	79	#if 1
d62a17ae	80	#define CHECKLAST(sl) \
	81	do { \
	82	if ((sl)->header->forward[0] && !(sl)->last) \
	83	assert(0); \
	84	if (!(sl)->header->forward[0] && (sl)->last) \
	85	assert(0); \
	86	} while (0)
520d2512 LB	87	#else
	88	#define CHECKLAST(sl)
	89	#endif
	90
	91
4d762f26	92	static int randomLevel(void)
520d2512	93	{
d62a17ae	94	register int level = 0;
d62a17ae	95	register int b;
520d2512	96
d62a17ae	97	do {
d62a17ae	98	if (randomsLeft <= 0) {
5920b3eb	99	randomBits = frr_weak_random();
d62a17ae	100	randomsLeft = BitsInRandom / 2;
	101	}
	102	b = randomBits & 3;
	103	randomBits >>= 2;
	104	--randomsLeft;
	105
	106	if (!b) {
	107	level++;
	108	if (level >= MaxLevel)
	109	return MaxLevel;
	110	}
	111	} while (!b);
	112
	113	return level;
520d2512 LB	114	}
520d2512 LB	115
1a4189d4	116	static int default_cmp(const void key1, const void key2)
520d2512	117	{
d62a17ae	118	if (key1 < key2)
	119	return -1;
	120	if (key1 > key2)
	121	return 1;
	122	return 0;
520d2512 LB	123	}
520d2512 LB	124
d62a17ae	125	unsigned int skiplist_count(struct skiplist *l)
520d2512	126	{
d62a17ae	127	return l->count;
520d2512 LB	128	}
520d2512 LB	129
1a4189d4 DS	130	struct skiplist *skiplist_new(int flags,
1a4189d4 DS	131	int (cmp)(const void key1, const void *key2),
d62a17ae	132	void (del)(void val))
520d2512	133	{
d62a17ae	134	struct skiplist *new;
520d2512	135
d62a17ae	136	new = XCALLOC(MTYPE_SKIP_LIST, sizeof(struct skiplist));
d62a17ae	137	assert(new);
520d2512	138
d62a17ae	139	new->level = 0;
	140	new->count = 0;
	141	new->header = newNodeOfLevel(MaxNumberOfLevels);
	142	new->stats = newNodeOfLevel(MaxNumberOfLevels);
520d2512	143
d62a17ae	144	new->flags = flags;
	145	if (cmp)
	146	new->cmp = cmp;
	147	else
	148	new->cmp = default_cmp;
520d2512	149
d62a17ae	150	if (del)
d62a17ae	151	new->del = del;
520d2512	152
d62a17ae	153	skiplist_last_created = new; /* debug */
520d2512	154
d62a17ae	155	return new;
520d2512 LB	156	}
520d2512 LB	157
d62a17ae	158	void skiplist_free(struct skiplist *l)
520d2512	159	{
d62a17ae	160	register struct skiplistnode p, q;
520d2512	161
d62a17ae	162	p = l->header;
520d2512	163
d62a17ae	164	do {
	165	q = p->forward[0];
	166	if (l->del && p != l->header)
	167	(*l->del)(p->value);
	168	XFREE(MTYPE_SKIP_LIST_NODE, p);
	169	p = q;
	170	} while (p);
520d2512	171
d62a17ae	172	XFREE(MTYPE_SKIP_LIST_NODE, l->stats);
d62a17ae	173	XFREE(MTYPE_SKIP_LIST, l);
520d2512 LB	174	}
	175
	176
d62a17ae	177	int skiplist_insert(register struct skiplist l, register void key,
d62a17ae	178	register void *value)
520d2512	179	{
d62a17ae	180	register int k;
	181	struct skiplistnode *update[MaxNumberOfLevels];
	182	register struct skiplistnode p, q;
	183
	184	CHECKLAST(l);
	185
	186	/* DEBUG */
	187	if (!key) {
450971aa	188	flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p",
1c50c1c0	189	__func__, value);
d62a17ae	190	}
	191
	192	p = l->header;
	193	k = l->level;
	194	do {
	195	while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
	196	p = q;
	197	update[k] = p;
	198	} while (--k >= 0);
	199
	200	if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) && q
	201	&& ((*l->cmp)(q->key, key) == 0)) {
	202
	203	return -1;
	204	}
	205
	206	k = randomLevel();
f70247fe	207	assert(k >= 0);
d62a17ae	208	if (k > l->level) {
	209	k = ++l->level;
	210	update[k] = l->header;
	211	}
	212
	213	q = newNodeOfLevel(k);
	214	q->key = key;
	215	q->value = value;
1e20238a	216	#ifdef SKIPLIST_0TIMER_DEBUG
d62a17ae	217	q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
520d2512 LB	218	#endif
520d2512 LB	219
d62a17ae	220	++(l->stats->forward[k]);
1e20238a	221	#ifdef SKIPLIST_DEBUG
d62a17ae	222	zlog_debug("%s: incremented stats @%p:%d, now %ld", __func__, l, k,
d62a17ae	223	l->stats->forward[k] - (struct skiplistnode *)NULL);
520d2512 LB	224	#endif
520d2512 LB	225
d62a17ae	226	do {
	227	p = update[k];
	228	q->forward[k] = p->forward[k];
	229	p->forward[k] = q;
	230	} while (--k >= 0);
520d2512	231
d62a17ae	232	/*
	233	* If this is the last item in the list, update the "last" pointer
	234	*/
	235	if (!q->forward[0]) {
	236	l->last = q;
	237	}
520d2512	238
d62a17ae	239	++(l->count);
520d2512	240
d62a17ae	241	CHECKLAST(l);
520d2512	242
d62a17ae	243	return 0;
520d2512 LB	244	}
520d2512 LB	245
d62a17ae	246	int skiplist_delete(register struct skiplist l, register void key,
d62a17ae	247	register void value) / used only if duplicates allowed */
520d2512	248	{
d62a17ae	249	register int k, m;
	250	struct skiplistnode *update[MaxNumberOfLevels];
	251	register struct skiplistnode p, q;
	252
	253	CHECKLAST(l);
	254
	255	/* to make debugging easier */
	256	for (k = 0; k < MaxNumberOfLevels; ++k)
	257	update[k] = NULL;
	258
	259	p = l->header;
	260	k = m = l->level;
	261	do {
	262	while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
	263	p = q;
	264	update[k] = p;
	265	} while (--k >= 0);
	266
	267	if (l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) {
	268	while (q && ((*l->cmp)(q->key, key) == 0)
	269	&& (q->value != value)) {
	270	int i;
	271	for (i = 0; i <= l->level; ++i) {
	272	if (update[i]->forward[i] == q)
	273	update[i] = q;
	274	}
	275	q = q->forward[0];
	276	}
520d2512	277	}
520d2512	278
d62a17ae	279	if (q && (*l->cmp)(q->key, key) == 0) {
	280	if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)
	281	\|\| (q->value == value)) {
520d2512	282
d62a17ae	283	/*
	284	* found node to delete
	285	*/
1e20238a	286	#ifdef SKIPLIST_0TIMER_DEBUG
d62a17ae	287	q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
520d2512	288	#endif
d62a17ae	289	/*
	290	* If we are deleting the last element of the list,
	291	* update the list's "last" pointer.
	292	*/
	293	if (l->last == q) {
	294	if (update[0] == l->header)
	295	l->last = NULL;
	296	else
	297	l->last = update[0];
	298	}
	299
	300	for (k = 0; k <= m && (p = update[k])->forward[k] == q;
	301	k++) {
	302	p->forward[k] = q->forward[k];
	303	}
	304	--(l->stats->forward[k - 1]);
1e20238a	305	#ifdef SKIPLIST_DEBUG
d62a17ae	306	zlog_debug("%s: decremented stats @%p:%d, now %ld",
	307	__func__, l, k - 1,
	308	l->stats->forward[k - 1]
	309	- (struct skiplistnode *)NULL);
520d2512	310	#endif
d62a17ae	311	if (l->del)
	312	(*l->del)(q->value);
	313	XFREE(MTYPE_SKIP_LIST_NODE, q);
	314	while (l->header->forward[m] == NULL && m > 0)
	315	m--;
	316	l->level = m;
	317	CHECKLAST(l);
	318	--(l->count);
	319	return 0;
	320	}
520d2512	321	}
520d2512	322
d62a17ae	323	CHECKLAST(l);
d62a17ae	324	return -1;
520d2512 LB	325	}
	326
	327	/*
	328	* Obtain first value matching "key". Unless SKIPLIST_FLAG_ALLOW_DUPLICATES
	329	* is set, this will also be the only value matching "key".
	330	*
	331	* Also set a cursor for use with skiplist_next_value.
	332	*/
d62a17ae	333	int skiplist_first_value(register struct skiplist l, / in */
1a4189d4 DS	334	register const void key, / in */
1a4189d4 DS	335	void *valuePointer, / out */
d62a17ae	336	void *cursor) / out */
520d2512	337	{
d62a17ae	338	register int k;
d62a17ae	339	register struct skiplistnode p, q;
520d2512	340
d62a17ae	341	p = l->header;
d62a17ae	342	k = l->level;
520d2512	343
d62a17ae	344	do {
	345	while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
	346	p = q;
520d2512	347
d62a17ae	348	} while (--k >= 0);
520d2512	349
d62a17ae	350	if (!q \|\| (*l->cmp)(q->key, key))
d62a17ae	351	return -1;
520d2512	352
d62a17ae	353	if (valuePointer)
d62a17ae	354	*valuePointer = q->value;
520d2512	355
d62a17ae	356	if (cursor)
d62a17ae	357	*cursor = q;
520d2512	358
d62a17ae	359	return 0;
520d2512 LB	360	}
520d2512 LB	361
d62a17ae	362	int skiplist_search(register struct skiplist l, register void key,
d62a17ae	363	void **valuePointer)
520d2512	364	{
d62a17ae	365	return skiplist_first_value(l, key, valuePointer, NULL);
520d2512 LB	366	}
	367
	368
	369	/*
	370	* Caller supplies key and value of an existing item in the list.
	371	* Function returns the value of the next list item that has the
	372	* same key (useful when SKIPLIST_FLAG_ALLOW_DUPLICATES is set).
	373	*
	374	* Returns 0 on success. If the caller-supplied key and value
	375	* do not correspond to a list element, or if they specify the
	376	* last element with the given key, -1 is returned.
	377	*/
d62a17ae	378	int skiplist_next_value(register struct skiplist l, / in */
1a4189d4	379	register const void key, / in */
d62a17ae	380	void *valuePointer, / in/out */
d62a17ae	381	void *cursor) / in/out */
520d2512	382	{
5037cc3e	383	register int k;
d62a17ae	384	register struct skiplistnode p, q;
520d2512	385
d62a17ae	386	CHECKLAST(l);
520d2512	387
d62a17ae	388	if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {
	389	return -1;
	390	}
520d2512	391
d62a17ae	392	if (!cursor \|\| !*cursor) {
d62a17ae	393	p = l->header;
5037cc3e	394	k = l->level;
d62a17ae	395
	396	/*
	397	* Find matching key
	398	*/
	399	do {
	400	while (q = p->forward[k],
	401	q && (*l->cmp)(q->key, key) < 0)
	402	p = q;
	403	} while (--k >= 0);
	404
	405	/*
	406	* Find matching value
	407	*/
	408	while (q && ((*l->cmp)(q->key, key) == 0)
	409	&& (q->value != *valuePointer)) {
	410	q = q->forward[0];
	411	}
	412
	413	if (!q \|\| ((*l->cmp)(q->key, key) != 0)
	414	\|\| (q->value != *valuePointer)) {
	415	/*
	416	* No matching value
	417	*/
	418	CHECKLAST(l);
	419	return -1;
	420	}
	421	} else {
	422	q = (struct skiplistnode )cursor;
	423	}
520d2512 LB	424
520d2512 LB	425	/*
d62a17ae	426	* Advance cursor
520d2512	427	*/
d62a17ae	428	q = q->forward[0];
520d2512	429
d62a17ae	430	/*
	431	* If we reached end-of-list or if the key is no longer the same,
	432	* then return error
520d2512	433	*/
d62a17ae	434	if (!q \|\| ((*l->cmp)(q->key, key) != 0))
d62a17ae	435	return -1;
520d2512	436
d62a17ae	437	*valuePointer = q->value;
	438	if (cursor)
	439	*cursor = q;
	440	CHECKLAST(l);
	441	return 0;
520d2512 LB	442	}
520d2512 LB	443
d62a17ae	444	int skiplist_first(register struct skiplist l, void *keyPointer,
d62a17ae	445	void **valuePointer)
520d2512	446	{
d62a17ae	447	register struct skiplistnode *p;
520d2512	448
d62a17ae	449	CHECKLAST(l);
	450	p = l->header->forward[0];
	451	if (!p)
	452	return -1;
520d2512	453
d62a17ae	454	if (keyPointer)
d62a17ae	455	*keyPointer = p->key;
520d2512	456
d62a17ae	457	if (valuePointer)
d62a17ae	458	*valuePointer = p->value;
520d2512	459
d62a17ae	460	CHECKLAST(l);
520d2512	461
d62a17ae	462	return 0;
520d2512 LB	463	}
520d2512 LB	464
d62a17ae	465	int skiplist_last(register struct skiplist l, void *keyPointer,
d62a17ae	466	void **valuePointer)
520d2512	467	{
d62a17ae	468	CHECKLAST(l);
	469	if (l->last) {
	470	if (keyPointer)
	471	*keyPointer = l->last->key;
	472	if (valuePointer)
	473	*valuePointer = l->last->value;
	474	return 0;
	475	}
	476	return -1;
520d2512 LB	477	}
	478
	479	/*
	480	* true = empty
	481	*/
d62a17ae	482	int skiplist_empty(register struct skiplist *l)
520d2512	483	{
d62a17ae	484	CHECKLAST(l);
	485	if (l->last)
	486	return 0;
	487	return 1;
520d2512 LB	488	}
520d2512 LB	489
d62a17ae	490	/*
520d2512 LB	491	* Use this to walk the list. Caller sets *cursor to NULL to obtain
	492	* first element. Return value of 0 indicates valid cursor/element
	493	* returned, otherwise NULL cursor arg or EOL.
	494	*/
d62a17ae	495	int skiplist_next(register struct skiplist l, / in */
	496	void *keyPointer, / out */
	497	void *valuePointer, / out */
	498	void *cursor) / in/out */
520d2512	499	{
d62a17ae	500	struct skiplistnode *p;
520d2512	501
d62a17ae	502	if (!cursor)
d62a17ae	503	return -1;
520d2512	504
d62a17ae	505	CHECKLAST(l);
520d2512	506
d62a17ae	507	if (!*cursor) {
	508	p = l->header->forward[0];
	509	} else {
	510	p = *cursor;
	511	p = p->forward[0];
	512	}
	513	*cursor = p;
520d2512	514
d62a17ae	515	if (!p)
d62a17ae	516	return -1;
520d2512	517
d62a17ae	518	if (keyPointer)
d62a17ae	519	*keyPointer = p->key;
520d2512	520
d62a17ae	521	if (valuePointer)
d62a17ae	522	*valuePointer = p->value;
520d2512	523
d62a17ae	524	CHECKLAST(l);
520d2512	525
d62a17ae	526	return 0;
520d2512 LB	527	}
520d2512 LB	528
d62a17ae	529	int skiplist_delete_first(register struct skiplist *l)
520d2512	530	{
d62a17ae	531	register int k;
	532	register struct skiplistnode p, q;
	533	int nodelevel = 0;
520d2512	534
d62a17ae	535	CHECKLAST(l);
520d2512	536
d62a17ae	537	p = l->header;
	538	q = l->header->forward[0];
	539
	540	if (!q)
	541	return -1;
	542
	543	for (k = l->level; k >= 0; --k) {
	544	if (p->forward[k] == q) {
	545	p->forward[k] = q->forward[k];
	546	if ((k == l->level) && (p->forward[k] == NULL)
	547	&& (l->level > 0))
	548	--(l->level);
	549	if (!nodelevel)
	550	nodelevel = k;
	551	}
520d2512	552	}
520d2512	553
1e20238a	554	#ifdef SKIPLIST_0TIMER_DEBUG
d62a17ae	555	q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
520d2512	556	#endif
d62a17ae	557	/*
	558	* If we are deleting the last element of the list,
	559	* update the list's "last" pointer.
	560	*/
	561	if (l->last == q) {
	562	l->last = NULL;
	563	}
	564
	565	--(l->stats->forward[nodelevel]);
1e20238a	566	#ifdef SKIPLIST_DEBUG
d62a17ae	567	zlog_debug("%s: decremented stats @%p:%d, now %ld", __func__, l,
	568	nodelevel,
	569	l->stats->forward[nodelevel] - (struct skiplistnode *)NULL);
520d2512 LB	570	#endif
520d2512 LB	571
d62a17ae	572	if (l->del)
d62a17ae	573	(*l->del)(q->value);
520d2512	574
d62a17ae	575	XFREE(MTYPE_SKIP_LIST_NODE, q);
520d2512	576
d62a17ae	577	CHECKLAST(l);
520d2512	578
d62a17ae	579	--(l->count);
520d2512	580
d62a17ae	581	return 0;
520d2512 LB	582	}
520d2512 LB	583
d62a17ae	584	void skiplist_debug(struct vty vty, struct skiplist l)
520d2512	585	{
d62a17ae	586	int i;
	587
	588	if (!l)
	589	l = skiplist_last_created;
	590	vty_out(vty, "Skiplist %p has max level %d\n", l, l->level);
	591	for (i = l->level; i >= 0; --i)
	592	vty_out(vty, " @%d: %ld\n", i,
	593	(long)((l->stats->forward[i])
	594	- (struct skiplistnode *)NULL));
520d2512 LB	595	}
520d2512 LB	596
d62a17ae	597	static void *scramble(int i)
520d2512	598	{
d62a17ae	599	uintptr_t result;
520d2512	600
937652c6 DL	601	result = (unsigned)(i & 0xff) << 24;
937652c6 DL	602	result \|= (unsigned)i >> 8;
520d2512	603
d62a17ae	604	return (void *)result;
520d2512 LB	605	}
	606
	607	#define sampleSize 65536
d62a17ae	608	void skiplist_test(struct vty *vty)
	609	{
	610	struct skiplist *l;
	611	register int i, k;
	612	void *keys[sampleSize];
6ce59f0b	613	void *v = NULL;
520d2512	614
d62a17ae	615	zlog_debug("%s: entry", __func__);
520d2512	616
d62a17ae	617	l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
520d2512	618
d62a17ae	619	zlog_debug("%s: skiplist_new returned %p", __func__, l);
520d2512	620
d62a17ae	621	for (i = 0; i < 4; i++) {
520d2512	622
d62a17ae	623	for (k = 0; k < sampleSize; k++) {
	624	if (!(k % 1000)) {
	625	zlog_debug("%s: (%d:%d)", __func__, i, k);
	626	}
	627	// keys[k] = (void *)random();
c4efd0f4	628	keys[k] = scramble(k);
d62a17ae	629	if (skiplist_insert(l, keys[k], keys[k]))
	630	zlog_debug("error in insert #%d,#%d", i, k);
	631	}
520d2512	632
d62a17ae	633	zlog_debug("%s: inserts done", __func__);
520d2512	634
d62a17ae	635	for (k = 0; k < sampleSize; k++) {
520d2512	636
d62a17ae	637	if (!(k % 1000))
	638	zlog_debug("[%d:%d]", i, k);
	639	if (skiplist_search(l, keys[k], &v))
	640	zlog_debug("error in search #%d,#%d", i, k);
520d2512	641
d62a17ae	642	if (v != keys[k])
	643	zlog_debug("search returned wrong value");
	644	}
520d2512 LB	645
520d2512 LB	646
d62a17ae	647	for (k = 0; k < sampleSize; k++) {
520d2512	648
d62a17ae	649	if (!(k % 1000))
	650	zlog_debug("<%d:%d>", i, k);
	651	if (skiplist_delete(l, keys[k], keys[k]))
	652	zlog_debug("error in delete");
c4efd0f4	653	keys[k] = scramble(k ^ 0xf0f0f0f0);
d62a17ae	654	if (skiplist_insert(l, keys[k], keys[k]))
	655	zlog_debug("error in insert #%d,#%d", i, k);
	656	}
520d2512	657
d62a17ae	658	for (k = 0; k < sampleSize; k++) {
520d2512	659
d62a17ae	660	if (!(k % 1000))
	661	zlog_debug("{%d:%d}", i, k);
	662	if (skiplist_delete_first(l))
	663	zlog_debug("error in delete_first");
	664	}
520d2512	665	}
520d2512	666
d62a17ae	667	skiplist_free(l);
520d2512	668	}