Merge pull request #12798 from donaldsharp/rib_match_multicast

[mirror_frr.git] / lib / skiplist.c

diff --git a/lib/skiplist.c b/lib/skiplist.c
index fc42857418ef1f20e445f4110a0f9938f602320f..fb8cb72e8d082d6591afde33cea9534d6c64b9db 100644 (file)
--- a/lib/skiplist.c
+++ b/lib/skiplist.c
@@ -1,27 +1,12 @@
+// 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
@@ -65,17 +50,25 @@
 
 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)                   \
@@ -138,7 +131,7 @@ struct skiplist *skiplist_new(int flags,
        new->level = 0;
        new->count = 0;
        new->header = newNodeOfLevel(MaxNumberOfLevels);
-       new->stats = newNodeOfLevel(MaxNumberOfLevels);
+       new->level_stats = newStatsOfLevel(MaxNumberOfLevels);
 
        new->flags = flags;
        if (cmp)
@@ -166,7 +159,7 @@ void skiplist_free(struct skiplist *l)
                p = q;
        } while (p);
 
-       XFREE(MTYPE_SKIP_LIST_NODE, l->stats);
+       XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats);
        XFREE(MTYPE_SKIP_LIST, l);
 }
 
@@ -180,11 +173,13 @@ int skiplist_insert(register struct skiplist *l, register void *key,
 
        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;
@@ -214,10 +209,10 @@ int skiplist_insert(register struct skiplist *l, register void *key,
        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 {
@@ -298,12 +293,10 @@ int skiplist_delete(register struct skiplist *l, register void *key,
                             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);
@@ -559,11 +552,10 @@ int skiplist_delete_first(register struct skiplist *l)
                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)
@@ -587,9 +579,7 @@ void skiplist_debug(struct vty *vty, struct skiplist *l)
 
        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)