Adding upstream version 8.4.4.upstream/8.4.4upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 671 insertions, 0 deletions

diff --git a/lib/skiplist.c b/lib/skiplist.c
new file mode 100644
index 0000000..8140782
--- /dev/null
+++ b/lib/skiplist.c
@@ -0,0 +1,671 @@
+/*
+ * 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 implementation 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_MTYPE_STATIC(LIB, SKIP_LIST_STATS, "Skiplist Counters");
+
+#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 *))
+
+/* XXX must match type of (struct skiplist).level_stats */
+#define newStatsOfLevel(l)                                                     \
+	XCALLOC(MTYPE_SKIP_LIST_STATS, ((l) + 1) * sizeof(int))
+
+static int randomsLeft;
+static int randomBits;
+
+#ifdef SKIPLIST_DEBUG
+#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->level_stats = newStatsOfLevel(MaxNumberOfLevels);
+
+	new->flags = flags;
+	if (cmp)
+		new->cmp = cmp;
+	else
+		new->cmp = default_cmp;
+
+	if (del)
+		new->del = del;
+
+	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_STATS, l->level_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);
+
+#ifdef SKIPLIST_DEBUG
+	/* DEBUG */
+	if (!key) {
+		flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p",
+			 __func__, value);
+	}
+#endif
+
+	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->level_stats[k]);
+#ifdef SKIPLIST_DEBUG
+	zlog_debug("%s: incremented level_stats @%p:%d, now %d", __func__, l, k,
+		   l->level_stats[k]);
+#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->level_stats[k - 1]);
+#ifdef SKIPLIST_DEBUG
+			zlog_debug("%s: decremented level_stats @%p:%d, now %d",
+				   __func__, l, k - 1, l->level_stats[k - 1]);
+#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->level_stats[nodelevel]);
+#ifdef SKIPLIST_DEBUG
+	zlog_debug("%s: decremented level_stats @%p:%d, now %d", __func__, l,
+		   nodelevel, l->level_stats[nodelevel]);
+#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)
+		return;
+
+	vty_out(vty, "Skiplist %p has max level %d\n", l, l->level);
+	for (i = l->level; i >= 0; --i)
+		vty_out(vty, "  @%d: %d\n", i, l->level_stats[i]);
+}
+
+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);
+}