summaryrefslogtreecommitdiff
path: root/lib/skiplist.c
diff options
context:
space:
mode:
Diffstat (limited to 'lib/skiplist.c')
-rw-r--r--lib/skiplist.c883
1 files changed, 431 insertions, 452 deletions
diff --git a/lib/skiplist.c b/lib/skiplist.c
index 05f489c905..db8e035070 100644
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -1,5 +1,5 @@
/*
- * Copyright 1990 William Pugh
+ * Copyright 1990 William Pugh
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted.
@@ -23,34 +23,34 @@
/*
* 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
+ * 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.
+ * as currently set.
*/
@@ -61,7 +61,7 @@
#include "vty.h"
#include "skiplist.h"
-DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List")
+DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List")
DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node")
#define BitsInRandom 31
@@ -72,256 +72,251 @@ DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node")
static int randomsLeft;
static int randomBits;
-static struct skiplist *skiplist_last_created; /* debugging hack */
+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)
+#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()
+static int randomLevel()
{
- register int level = 0;
- register int b;
+ register int level = 0;
+ register int b;
- do {
- if (randomsLeft <= 0) {
- randomBits = random();
- randomsLeft = BitsInRandom/2;
- }
- b = randomBits&3;
- randomBits>>=2;
- --randomsLeft;
-
- if (!b) {
- level++;
- if (level >= MaxLevel)
- return MaxLevel;
- }
- } while (!b);
-
- return level;
+ do {
+ if (randomsLeft <= 0) {
+ randomBits = 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(void *key1, void *key2)
+static int default_cmp(void *key1, void *key2)
{
- if (key1 < key2)
- return -1;
- if (key1 > key2)
- return 1;
- return 0;
+ if (key1 < key2)
+ return -1;
+ if (key1 > key2)
+ return 1;
+ return 0;
}
-unsigned int
-skiplist_count(struct skiplist *l)
+unsigned int skiplist_count(struct skiplist *l)
{
- return l->count;
+ return l->count;
}
-struct skiplist *
-skiplist_new(
- int flags,
- int (*cmp) (void *key1, void *key2),
- void (*del) (void *val))
+struct skiplist *skiplist_new(int flags, int (*cmp)(void *key1, void *key2),
+ void (*del)(void *val))
{
- struct skiplist *new;
+ struct skiplist *new;
- new = XCALLOC (MTYPE_SKIP_LIST, sizeof (struct skiplist));
- assert(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->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;
+ new->flags = flags;
+ if (cmp)
+ new->cmp = cmp;
+ else
+ new->cmp = default_cmp;
- if (del)
- new->del = del;
+ if (del)
+ new->del = del;
- skiplist_last_created = new; /* debug */
+ skiplist_last_created = new; /* debug */
- return new;
+ return new;
}
-void
-skiplist_free(struct skiplist *l)
+void skiplist_free(struct skiplist *l)
{
- register struct skiplistnode *p, *q;
+ register struct skiplistnode *p, *q;
- p = l->header;
+ 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);
+ 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);
+ 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)
+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) {
- zlog_err("%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();
- if (k>l->level) {
- k = ++l->level;
- update[k] = l->header;
- }
-
- q = newNodeOfLevel(k);
- q->key = key;
- q->value = value;
+ register int k;
+ struct skiplistnode *update[MaxNumberOfLevels];
+ register struct skiplistnode *p, *q;
+
+ CHECKLAST(l);
+
+ /* DEBUG */
+ if (!key) {
+ zlog_err("%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();
+ if (k > l->level) {
+ k = ++l->level;
+ update[k] = l->header;
+ }
+
+ q = newNodeOfLevel(k);
+ q->key = key;
+ q->value = value;
#if SKIPLIST_0TIMER_DEBUG
- q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
+ q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
#endif
- ++(l->stats->forward[k]);
+ ++(l->stats->forward[k]);
#if SKIPLIST_DEBUG
- zlog_debug("%s: incremented stats @%p:%d, now %ld", __func__, l, k,
- l->stats->forward[k] - (struct skiplistnode *)NULL);
+ 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);
+ 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;
- }
+ /*
+ * If this is the last item in the list, update the "last" pointer
+ */
+ if (!q->forward[0]) {
+ l->last = q;
+ }
- ++(l->count);
+ ++(l->count);
- CHECKLAST(l);
+ CHECKLAST(l);
- return 0;
+ return 0;
}
-int
-skiplist_delete(
- register struct skiplist *l,
- register void *key,
- register void *value) /* used only if duplicates allowed */
+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];
+ 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)) {
+ if (q && (*l->cmp)(q->key, key) == 0) {
+ if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)
+ || (q->value == value)) {
- /*
- * found node to delete
- */
+/*
+ * found node to delete
+ */
#if SKIPLIST_0TIMER_DEBUG
- q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
+ 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]);
+ /*
+ * 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]);
#if SKIPLIST_DEBUG
- zlog_debug("%s: decremented stats @%p:%d, now %ld",
- __func__, l, k-1,
- l->stats->forward[k-1] - (struct skiplistnode *)NULL);
+ 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;
+ 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;
+ CHECKLAST(l);
+ return -1;
}
/*
@@ -330,44 +325,39 @@ skiplist_delete(
*
* Also set a cursor for use with skiplist_next_value.
*/
-int
-skiplist_first_value(
- register struct skiplist *l, /* in */
- register void *key, /* in */
- void **valuePointer, /* out */
- void **cursor) /* out */
+int skiplist_first_value(register struct skiplist *l, /* in */
+ register void *key, /* in */
+ void **valuePointer, /* out */
+ void **cursor) /* out */
{
- register int k;
- register struct skiplistnode *p, *q;
+ register int k;
+ register struct skiplistnode *p, *q;
- p = l->header;
- k = l->level;
+ p = l->header;
+ k = l->level;
- do {
- while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
- p = q;
+ do {
+ while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
+ p = q;
- } while (--k >= 0);
+ } while (--k >= 0);
- if (!q || (*l->cmp)(q->key, key))
- return -1;
+ if (!q || (*l->cmp)(q->key, key))
+ return -1;
- if (valuePointer)
- *valuePointer = q->value;
+ if (valuePointer)
+ *valuePointer = q->value;
- if (cursor)
- *cursor = q;
+ if (cursor)
+ *cursor = q;
- return 0;
+ return 0;
}
-int
-skiplist_search(
- register struct skiplist *l,
- register void *key,
- void **valuePointer)
+int skiplist_search(register struct skiplist *l, register void *key,
+ void **valuePointer)
{
- return skiplist_first_value(l, key, valuePointer, NULL);
+ return skiplist_first_value(l, key, valuePointer, NULL);
}
@@ -380,307 +370,296 @@ skiplist_search(
* 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 void *key, /* in */
- void **valuePointer, /* in/out */
- void **cursor) /* in/out */
+int skiplist_next_value(register struct skiplist *l, /* in */
+ register void *key, /* in */
+ void **valuePointer, /* in/out */
+ void **cursor) /* in/out */
{
- register int k,m;
- register struct skiplistnode *p, *q;
+ register int k, m;
+ register struct skiplistnode *p, *q;
- CHECKLAST(l);
+ CHECKLAST(l);
- if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {
- return -1;
- }
+ if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {
+ return -1;
+ }
- if (!cursor || !*cursor) {
- p = l->header;
- k = m = l->level;
+ if (!cursor || !*cursor) {
+ p = l->header;
+ k = m = 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;
+ }
/*
- * Find matching key
+ * Advance cursor
*/
- do {
- while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
- p = q;
- } while(--k>=0);
+ q = q->forward[0];
- /*
- * Find matching value
+ /*
+ * If we reached end-of-list or if the key is no longer the same,
+ * then return error
*/
- 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;
+ if (!q || ((*l->cmp)(q->key, key) != 0))
+ return -1;
- *valuePointer = q->value;
- if (cursor)
- *cursor = q;
- CHECKLAST(l);
- return 0;
+ *valuePointer = q->value;
+ if (cursor)
+ *cursor = q;
+ CHECKLAST(l);
+ return 0;
}
-int
-skiplist_first(
- register struct skiplist *l,
- void **keyPointer,
- void **valuePointer)
+int skiplist_first(register struct skiplist *l, void **keyPointer,
+ void **valuePointer)
{
- register struct skiplistnode *p;
+ register struct skiplistnode *p;
- CHECKLAST(l);
- p = l->header->forward[0];
- if (!p)
- return -1;
+ CHECKLAST(l);
+ p = l->header->forward[0];
+ if (!p)
+ return -1;
- if (keyPointer)
- *keyPointer = p->key;
+ if (keyPointer)
+ *keyPointer = p->key;
- if (valuePointer)
- *valuePointer = p->value;
+ if (valuePointer)
+ *valuePointer = p->value;
- CHECKLAST(l);
+ CHECKLAST(l);
- return 0;
+ return 0;
}
-int
-skiplist_last(
- register struct skiplist *l,
- void **keyPointer,
- void **valuePointer)
+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;
+ 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)
+int skiplist_empty(register struct skiplist *l)
{
- CHECKLAST(l);
- if (l->last)
- return 0;
- return 1;
+ 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 */
+int skiplist_next(register struct skiplist *l, /* in */
+ void **keyPointer, /* out */
+ void **valuePointer, /* out */
+ void **cursor) /* in/out */
{
- struct skiplistnode *p;
+ struct skiplistnode *p;
- if (!cursor)
- return -1;
+ if (!cursor)
+ return -1;
- CHECKLAST(l);
+ CHECKLAST(l);
- if (!*cursor) {
- p = l->header->forward[0];
- } else {
- p = *cursor;
- p = p->forward[0];
- }
- *cursor = p;
+ if (!*cursor) {
+ p = l->header->forward[0];
+ } else {
+ p = *cursor;
+ p = p->forward[0];
+ }
+ *cursor = p;
- if (!p)
- return -1;
+ if (!p)
+ return -1;
- if (keyPointer)
- *keyPointer = p->key;
+ if (keyPointer)
+ *keyPointer = p->key;
- if (valuePointer)
- *valuePointer = p->value;
+ if (valuePointer)
+ *valuePointer = p->value;
- CHECKLAST(l);
+ CHECKLAST(l);
- return 0;
+ return 0;
}
-int
-skiplist_delete_first(
- register struct skiplist *l)
+int skiplist_delete_first(register struct skiplist *l)
{
- register int k;
- register struct skiplistnode *p, *q;
- int nodelevel = 0;
-
- CHECKLAST(l);
+ register int k;
+ register struct skiplistnode *p, *q;
+ int nodelevel = 0;
- p = l->header;
- q = l->header->forward[0];
+ CHECKLAST(l);
- 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;
+ 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;
+ }
}
- }
#if SKIPLIST_0TIMER_DEBUG
- q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
+ 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]);
+ /*
+ * 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]);
#if SKIPLIST_DEBUG
- zlog_debug("%s: decremented stats @%p:%d, now %ld", __func__, l, nodelevel,
- l->stats->forward[nodelevel] - (struct skiplistnode *)NULL);
+ 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);
+ if (l->del)
+ (*l->del)(q->value);
- XFREE(MTYPE_SKIP_LIST_NODE, q);
+ XFREE(MTYPE_SKIP_LIST_NODE, q);
- CHECKLAST(l);
+ CHECKLAST(l);
- --(l->count);
+ --(l->count);
- return 0;
+ return 0;
}
-void
-skiplist_debug(struct vty *vty, struct skiplist *l)
+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%s", l, l->level, VTY_NEWLINE);
- for (i = l->level; i >= 0; --i)
- vty_out(vty, " @%d: %ld%s",
- i, (long)((l->stats->forward[i]) - (struct skiplistnode *)NULL),
- VTY_NEWLINE);
+ int i;
+
+ if (!l)
+ l = skiplist_last_created;
+ vty_out(vty, "Skiplist %p has max level %d%s", l, l->level,
+ VTY_NEWLINE);
+ for (i = l->level; i >= 0; --i)
+ vty_out(vty, " @%d: %ld%s", i,
+ (long)((l->stats->forward[i])
+ - (struct skiplistnode *)NULL),
+ VTY_NEWLINE);
}
-static void *
-scramble(int i)
+static void *scramble(int i)
{
- uintptr_t result;
+ uintptr_t result;
- result = (i & 0xff) << 24;
- result |= (i >> 8);
+ result = (i & 0xff) << 24;
+ result |= (i >> 8);
- return (void *)result;
+ return (void *)result;
}
#define sampleSize 65536
-void
-skiplist_test(struct vty *vty) {
- struct skiplist *l;
- register int i,k;
- void *keys[sampleSize];
- void *v;
-
- zlog_debug("%s: entry", __func__);
+void skiplist_test(struct vty *vty)
+{
+ struct skiplist *l;
+ register int i, k;
+ void *keys[sampleSize];
+ void *v;
- l= skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
+ zlog_debug("%s: entry", __func__);
- zlog_debug("%s: skiplist_new returned %p", __func__, l);
+ l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
- for (i=0; i < 4; i++) {
+ zlog_debug("%s: skiplist_new returned %p", __func__, l);
- for (k=0; k < sampleSize; k++) {
- if (!(k%1000)) {
- zlog_debug("%s: (%d:%d)", __func__, i, k);
- }
- //keys[k] = (void *)random();
- keys[k] = (void *)scramble(k);
- if (skiplist_insert(l, keys[k], keys[k]))
- zlog_debug("error in insert #%d,#%d",i,k);
- }
+ for (i = 0; i < 4; i++) {
- zlog_debug("%s: inserts done", __func__);
+ for (k = 0; k < sampleSize; k++) {
+ if (!(k % 1000)) {
+ zlog_debug("%s: (%d:%d)", __func__, i, k);
+ }
+ // keys[k] = (void *)random();
+ keys[k] = (void *)scramble(k);
+ if (skiplist_insert(l, keys[k], keys[k]))
+ zlog_debug("error in insert #%d,#%d", i, k);
+ }
- for (k=0; k < sampleSize; k++) {
+ zlog_debug("%s: inserts done", __func__);
- 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);
+ for (k = 0; k < sampleSize; k++) {
- if (v != keys[k])
- zlog_debug("search returned wrong value");
- }
+ 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++) {
+ 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] = (void *)scramble(k ^ 0xf0f0f0f0);
- if (skiplist_insert(l, keys[k], keys[k]))
- zlog_debug("error in insert #%d,#%d",i,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] = (void *)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++) {
+ 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");
+ if (!(k % 1000))
+ zlog_debug("{%d:%d}", i, k);
+ if (skiplist_delete_first(l))
+ zlog_debug("error in delete_first");
+ }
}
- }
- skiplist_free(l);
+ skiplist_free(l);
}
-