From 2c7cac91ed6e7db0f6937923d2b57f97dbdbc337 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 28 Apr 2024 11:53:30 +0200 Subject: Adding upstream version 8.4.4. Signed-off-by: Daniel Baumann --- lib/skiplist.c | 671 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 671 insertions(+) create mode 100644 lib/skiplist.c (limited to 'lib/skiplist.c') 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 + +#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); +} -- cgit v1.2.3