+// SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
/*
* 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.
+ * 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
#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, "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 *))
+#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;
-#if 1
+#ifdef SKIPLIST_DEBUG
#define CHECKLAST(sl) \
do { \
if ((sl)->header->forward[0] && !(sl)->last) \
new->level = 0;
new->count = 0;
new->header = newNodeOfLevel(MaxNumberOfLevels);
- new->stats = newNodeOfLevel(MaxNumberOfLevels);
+ new->level_stats = newStatsOfLevel(MaxNumberOfLevels);
new->flags = flags;
if (cmp)
p = q;
} while (p);
- XFREE(MTYPE_SKIP_LIST_NODE, l->stats);
+ XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats);
XFREE(MTYPE_SKIP_LIST, l);
}
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;
q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
#endif
- ++(l->stats->forward[k]);
+ ++(l->level_stats[k]);
#ifdef 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 level_stats @%p:%d, now %d", __func__, l, k,
+ l->level_stats[k]);
#endif
do {
k++) {
p->forward[k] = q->forward[k];
}
- --(l->stats->forward[k - 1]);
+ --(l->level_stats[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);
+ 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);
l->last = NULL;
}
- --(l->stats->forward[nodelevel]);
+ --(l->level_stats[nodelevel]);
#ifdef 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 level_stats @%p:%d, now %d", __func__, l,
+ nodelevel, l->level_stats[nodelevel]);
#endif
if (l->del)
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));
+ vty_out(vty, " @%d: %d\n", i, l->level_stats[i]);
}
static void *scramble(int i)