lib/skiplist.c

   1 // SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
   2 /*
   3  * Copyright 1990 William Pugh
   4  *
   5  * Permission to include in quagga provide on March 31, 2016
   6  */
   7
   8 /*
   9  * Skip List implementation based on code from William Pugh.
  10  * ftp://ftp.cs.umd.edu/pub/skipLists/
  11  *
  12  * Skip Lists are a probabilistic alternative to balanced trees, as
  13  * described in the June 1990 issue of CACM and were invented by
  14  * William Pugh in 1987.
  15  *
  16  * This file contains source code to implement a dictionary using
  17  * skip lists and a test driver to test the routines.
  18  *
  19  * A couple of comments about this implementation:
  20  *   The routine randomLevel has been hard-coded to generate random
  21  *   levels using p=0.25. It can be easily changed.
  22  *
  23  *   The insertion routine has been implemented so as to use the
  24  *   dirty hack described in the CACM paper: if a random level is
  25  *   generated that is more than the current maximum level, the
  26  *   current maximum level plus one is used instead.
  27  *
  28  *   Levels start at zero and go up to MaxLevel (which is equal to
  29  *      (MaxNumberOfLevels-1).
  30  *
  31  * The run-time flag SKIPLIST_FLAG_ALLOW_DUPLICATES determines whether or
  32  * not duplicates are allowed for a given list. If set, duplicates are
  33  * allowed and act in a FIFO manner. If not set, an insertion of a value
  34  * already in the list updates the previously existing binding.
  35  *
  36  * BitsInRandom is defined to be the number of bits returned by a call to
  37  * random(). For most all machines with 32-bit integers, this is 31 bits
  38  * as currently set.
  39  */
  40
  41
  42 #include <zebra.h>
  43
  44 #include "memory.h"
  45 #include "log.h"
  46 #include "vty.h"
  47 #include "skiplist.h"
  48 #include "lib_errors.h"
  49 #include "network.h"
  50
  51 DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List");
  52 DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node");
  53 DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_STATS, "Skiplist Counters");
  54
  55 #define BitsInRandom 31
  56
  57 #define MaxNumberOfLevels 16
  58 #define MaxLevel (MaxNumberOfLevels-1)
  59 #define newNodeOfLevel(l)                                                      \
  60         XCALLOC(MTYPE_SKIP_LIST_NODE,                                          \
  61                 sizeof(struct skiplistnode)                                    \
  62                         + (l) * sizeof(struct skiplistnode *))
  63
  64 /* XXX must match type of (struct skiplist).level_stats */
  65 #define newStatsOfLevel(l)                                                     \
  66         XCALLOC(MTYPE_SKIP_LIST_STATS, ((l) + 1) * sizeof(int))
  67
  68 static int randomsLeft;
  69 static int randomBits;
  70
  71 #ifdef SKIPLIST_DEBUG
  72 #define CHECKLAST(sl)                                                          \
  73         do {                                                                   \
  74                 if ((sl)->header->forward[0] && !(sl)->last)                   \
  75                         assert(0);                                             \
  76                 if (!(sl)->header->forward[0] && (sl)->last)                   \
  77                         assert(0);                                             \
  78         } while (0)
  79 #else
  80 #define CHECKLAST(sl)
  81 #endif
  82
  83
  84 static int randomLevel(void)
  85 {
  86         register int level = 0;
  87         register int b;
  88
  89         do {
  90                 if (randomsLeft <= 0) {
  91                         randomBits = frr_weak_random();
  92                         randomsLeft = BitsInRandom / 2;
  93                 }
  94                 b = randomBits & 3;
  95                 randomBits >>= 2;
  96                 --randomsLeft;
  97
  98                 if (!b) {
  99                         level++;
 100                         if (level >= MaxLevel)
 101                                 return MaxLevel;
 102                 }
 103         } while (!b);
 104
 105         return level;
 106 }
 107
 108 static int default_cmp(const void *key1, const void *key2)
 109 {
 110         if (key1 < key2)
 111                 return -1;
 112         if (key1 > key2)
 113                 return 1;
 114         return 0;
 115 }
 116
 117 unsigned int skiplist_count(struct skiplist *l)
 118 {
 119         return l->count;
 120 }
 121
 122 struct skiplist *skiplist_new(int flags,
 123                               int (*cmp)(const void *key1, const void *key2),
 124                               void (*del)(void *val))
 125 {
 126         struct skiplist *new;
 127
 128         new = XCALLOC(MTYPE_SKIP_LIST, sizeof(struct skiplist));
 129         assert(new);
 130
 131         new->level = 0;
 132         new->count = 0;
 133         new->header = newNodeOfLevel(MaxNumberOfLevels);
 134         new->level_stats = newStatsOfLevel(MaxNumberOfLevels);
 135
 136         new->flags = flags;
 137         if (cmp)
 138                 new->cmp = cmp;
 139         else
 140                 new->cmp = default_cmp;
 141
 142         if (del)
 143                 new->del = del;
 144
 145         return new;
 146 }
 147
 148 void skiplist_free(struct skiplist *l)
 149 {
 150         register struct skiplistnode *p, *q;
 151
 152         p = l->header;
 153
 154         do {
 155                 q = p->forward[0];
 156                 if (l->del && p != l->header)
 157                         (*l->del)(p->value);
 158                 XFREE(MTYPE_SKIP_LIST_NODE, p);
 159                 p = q;
 160         } while (p);
 161
 162         XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats);
 163         XFREE(MTYPE_SKIP_LIST, l);
 164 }
 165
 166
 167 int skiplist_insert(register struct skiplist *l, register void *key,
 168                     register void *value)
 169 {
 170         register int k;
 171         struct skiplistnode *update[MaxNumberOfLevels];
 172         register struct skiplistnode *p, *q;
 173
 174         CHECKLAST(l);
 175
 176 #ifdef SKIPLIST_DEBUG
 177         /* DEBUG */
 178         if (!key) {
 179                 flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p",
 180                          __func__, value);
 181         }
 182 #endif
 183
 184         p = l->header;
 185         k = l->level;
 186         do {
 187                 while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
 188                         p = q;
 189                 update[k] = p;
 190         } while (--k >= 0);
 191
 192         if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) && q
 193             && ((*l->cmp)(q->key, key) == 0)) {
 194
 195                 return -1;
 196         }
 197
 198         k = randomLevel();
 199         assert(k >= 0);
 200         if (k > l->level) {
 201                 k = ++l->level;
 202                 update[k] = l->header;
 203         }
 204
 205         q = newNodeOfLevel(k);
 206         q->key = key;
 207         q->value = value;
 208 #ifdef SKIPLIST_0TIMER_DEBUG
 209         q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
 210 #endif
 211
 212         ++(l->level_stats[k]);
 213 #ifdef SKIPLIST_DEBUG
 214         zlog_debug("%s: incremented level_stats @%p:%d, now %d", __func__, l, k,
 215                    l->level_stats[k]);
 216 #endif
 217
 218         do {
 219                 p = update[k];
 220                 q->forward[k] = p->forward[k];
 221                 p->forward[k] = q;
 222         } while (--k >= 0);
 223
 224         /*
 225          * If this is the last item in the list, update the "last" pointer
 226          */
 227         if (!q->forward[0]) {
 228                 l->last = q;
 229         }
 230
 231         ++(l->count);
 232
 233         CHECKLAST(l);
 234
 235         return 0;
 236 }
 237
 238 int skiplist_delete(register struct skiplist *l, register void *key,
 239                     register void *value) /* used only if duplicates allowed */
 240 {
 241         register int k, m;
 242         struct skiplistnode *update[MaxNumberOfLevels];
 243         register struct skiplistnode *p, *q;
 244
 245         CHECKLAST(l);
 246
 247         /* to make debugging easier */
 248         for (k = 0; k < MaxNumberOfLevels; ++k)
 249                 update[k] = NULL;
 250
 251         p = l->header;
 252         k = m = l->level;
 253         do {
 254                 while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
 255                         p = q;
 256                 update[k] = p;
 257         } while (--k >= 0);
 258
 259         if (l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) {
 260                 while (q && ((*l->cmp)(q->key, key) == 0)
 261                        && (q->value != value)) {
 262                         int i;
 263                         for (i = 0; i <= l->level; ++i) {
 264                                 if (update[i]->forward[i] == q)
 265                                         update[i] = q;
 266                         }
 267                         q = q->forward[0];
 268                 }
 269         }
 270
 271         if (q && (*l->cmp)(q->key, key) == 0) {
 272                 if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)
 273                     || (q->value == value)) {
 274
 275 /*
 276  * found node to delete
 277  */
 278 #ifdef SKIPLIST_0TIMER_DEBUG
 279                         q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
 280 #endif
 281                         /*
 282                          * If we are deleting the last element of the list,
 283                          * update the list's "last" pointer.
 284                          */
 285                         if (l->last == q) {
 286                                 if (update[0] == l->header)
 287                                         l->last = NULL;
 288                                 else
 289                                         l->last = update[0];
 290                         }
 291
 292                         for (k = 0; k <= m && (p = update[k])->forward[k] == q;
 293                              k++) {
 294                                 p->forward[k] = q->forward[k];
 295                         }
 296                         --(l->level_stats[k - 1]);
 297 #ifdef SKIPLIST_DEBUG
 298                         zlog_debug("%s: decremented level_stats @%p:%d, now %d",
 299                                    __func__, l, k - 1, l->level_stats[k - 1]);
 300 #endif
 301                         if (l->del)
 302                                 (*l->del)(q->value);
 303                         XFREE(MTYPE_SKIP_LIST_NODE, q);
 304                         while (l->header->forward[m] == NULL && m > 0)
 305                                 m--;
 306                         l->level = m;
 307                         CHECKLAST(l);
 308                         --(l->count);
 309                         return 0;
 310                 }
 311         }
 312
 313         CHECKLAST(l);
 314         return -1;
 315 }
 316
 317 /*
 318  * Obtain first value matching "key". Unless SKIPLIST_FLAG_ALLOW_DUPLICATES
 319  * is set, this will also be the only value matching "key".
 320  *
 321  * Also set a cursor for use with skiplist_next_value.
 322  */
 323 int skiplist_first_value(register struct skiplist *l, /* in */
 324                          register const void *key,    /* in */
 325                          void **valuePointer,         /* out */
 326                          void **cursor)               /* out */
 327 {
 328         register int k;
 329         register struct skiplistnode *p, *q;
 330
 331         p = l->header;
 332         k = l->level;
 333
 334         do {
 335                 while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
 336                         p = q;
 337
 338         } while (--k >= 0);
 339
 340         if (!q || (*l->cmp)(q->key, key))
 341                 return -1;
 342
 343         if (valuePointer)
 344                 *valuePointer = q->value;
 345
 346         if (cursor)
 347                 *cursor = q;
 348
 349         return 0;
 350 }
 351
 352 int skiplist_search(register struct skiplist *l, register void *key,
 353                     void **valuePointer)
 354 {
 355         return skiplist_first_value(l, key, valuePointer, NULL);
 356 }
 357
 358
 359 /*
 360  * Caller supplies key and value of an existing item in the list.
 361  * Function returns the value of the next list item that has the
 362  * same key (useful when SKIPLIST_FLAG_ALLOW_DUPLICATES is set).
 363  *
 364  * Returns 0 on success. If the caller-supplied key and value
 365  * do not correspond to a list element, or if they specify the
 366  * last element with the given key, -1 is returned.
 367  */
 368 int skiplist_next_value(register struct skiplist *l, /* in */
 369                         register const void *key,         /* in */
 370                         void **valuePointer,     /* in/out */
 371                         void **cursor)               /* in/out */
 372 {
 373         register int k;
 374         register struct skiplistnode *p, *q;
 375
 376         CHECKLAST(l);
 377
 378         if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {
 379                 return -1;
 380         }
 381
 382         if (!cursor || !*cursor) {
 383                 p = l->header;
 384                 k = l->level;
 385
 386                 /*
 387                  * Find matching key
 388                  */
 389                 do {
 390                         while (q = p->forward[k],
 391                                q && (*l->cmp)(q->key, key) < 0)
 392                                 p = q;
 393                 } while (--k >= 0);
 394
 395                 /*
 396                  * Find matching value
 397                  */
 398                 while (q && ((*l->cmp)(q->key, key) == 0)
 399                        && (q->value != *valuePointer)) {
 400                         q = q->forward[0];
 401                 }
 402
 403                 if (!q || ((*l->cmp)(q->key, key) != 0)
 404                     || (q->value != *valuePointer)) {
 405                         /*
 406                          * No matching value
 407                          */
 408                         CHECKLAST(l);
 409                         return -1;
 410                 }
 411         } else {
 412                 q = (struct skiplistnode *)*cursor;
 413         }
 414
 415         /*
 416          * Advance cursor
 417          */
 418         q = q->forward[0];
 419
 420         /*
 421          * If we reached end-of-list or if the key is no longer the same,
 422          * then return error
 423          */
 424         if (!q || ((*l->cmp)(q->key, key) != 0))
 425                 return -1;
 426
 427         *valuePointer = q->value;
 428         if (cursor)
 429                 *cursor = q;
 430         CHECKLAST(l);
 431         return 0;
 432 }
 433
 434 int skiplist_first(register struct skiplist *l, void **keyPointer,
 435                    void **valuePointer)
 436 {
 437         register struct skiplistnode *p;
 438
 439         CHECKLAST(l);
 440         p = l->header->forward[0];
 441         if (!p)
 442                 return -1;
 443
 444         if (keyPointer)
 445                 *keyPointer = p->key;
 446
 447         if (valuePointer)
 448                 *valuePointer = p->value;
 449
 450         CHECKLAST(l);
 451
 452         return 0;
 453 }
 454
 455 int skiplist_last(register struct skiplist *l, void **keyPointer,
 456                   void **valuePointer)
 457 {
 458         CHECKLAST(l);
 459         if (l->last) {
 460                 if (keyPointer)
 461                         *keyPointer = l->last->key;
 462                 if (valuePointer)
 463                         *valuePointer = l->last->value;
 464                 return 0;
 465         }
 466         return -1;
 467 }
 468
 469 /*
 470  * true = empty
 471  */
 472 int skiplist_empty(register struct skiplist *l)
 473 {
 474         CHECKLAST(l);
 475         if (l->last)
 476                 return 0;
 477         return 1;
 478 }
 479
 480 /*
 481  * Use this to walk the list. Caller sets *cursor to NULL to obtain
 482  * first element. Return value of 0 indicates valid cursor/element
 483  * returned, otherwise NULL cursor arg or EOL.
 484  */
 485 int skiplist_next(register struct skiplist *l, /* in */
 486                   void **keyPointer,       /* out */
 487                   void **valuePointer,   /* out */
 488                   void **cursor)               /* in/out */
 489 {
 490         struct skiplistnode *p;
 491
 492         if (!cursor)
 493                 return -1;
 494
 495         CHECKLAST(l);
 496
 497         if (!*cursor) {
 498                 p = l->header->forward[0];
 499         } else {
 500                 p = *cursor;
 501                 p = p->forward[0];
 502         }
 503         *cursor = p;
 504
 505         if (!p)
 506                 return -1;
 507
 508         if (keyPointer)
 509                 *keyPointer = p->key;
 510
 511         if (valuePointer)
 512                 *valuePointer = p->value;
 513
 514         CHECKLAST(l);
 515
 516         return 0;
 517 }
 518
 519 int skiplist_delete_first(register struct skiplist *l)
 520 {
 521         register int k;
 522         register struct skiplistnode *p, *q;
 523         int nodelevel = 0;
 524
 525         CHECKLAST(l);
 526
 527         p = l->header;
 528         q = l->header->forward[0];
 529
 530         if (!q)
 531                 return -1;
 532
 533         for (k = l->level; k >= 0; --k) {
 534                 if (p->forward[k] == q) {
 535                         p->forward[k] = q->forward[k];
 536                         if ((k == l->level) && (p->forward[k] == NULL)
 537                             && (l->level > 0))
 538                                 --(l->level);
 539                         if (!nodelevel)
 540                                 nodelevel = k;
 541                 }
 542         }
 543
 544 #ifdef SKIPLIST_0TIMER_DEBUG
 545         q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
 546 #endif
 547         /*
 548          * If we are deleting the last element of the list,
 549          * update the list's "last" pointer.
 550          */
 551         if (l->last == q) {
 552                 l->last = NULL;
 553         }
 554
 555         --(l->level_stats[nodelevel]);
 556 #ifdef SKIPLIST_DEBUG
 557         zlog_debug("%s: decremented level_stats @%p:%d, now %d", __func__, l,
 558                    nodelevel, l->level_stats[nodelevel]);
 559 #endif
 560
 561         if (l->del)
 562                 (*l->del)(q->value);
 563
 564         XFREE(MTYPE_SKIP_LIST_NODE, q);
 565
 566         CHECKLAST(l);
 567
 568         --(l->count);
 569
 570         return 0;
 571 }
 572
 573 void skiplist_debug(struct vty *vty, struct skiplist *l)
 574 {
 575         int i;
 576
 577         if (!l)
 578                 return;
 579
 580         vty_out(vty, "Skiplist %p has max level %d\n", l, l->level);
 581         for (i = l->level; i >= 0; --i)
 582                 vty_out(vty, "  @%d: %d\n", i, l->level_stats[i]);
 583 }
 584
 585 static void *scramble(int i)
 586 {
 587         uintptr_t result;
 588
 589         result = (unsigned)(i & 0xff) << 24;
 590         result |= (unsigned)i >> 8;
 591
 592         return (void *)result;
 593 }
 594
 595 #define sampleSize 65536
 596 void skiplist_test(struct vty *vty)
 597 {
 598         struct skiplist *l;
 599         register int i, k;
 600         void *keys[sampleSize];
 601         void *v = NULL;
 602
 603         zlog_debug("%s: entry", __func__);
 604
 605         l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
 606
 607         zlog_debug("%s: skiplist_new returned %p", __func__, l);
 608
 609         for (i = 0; i < 4; i++) {
 610
 611                 for (k = 0; k < sampleSize; k++) {
 612                         if (!(k % 1000)) {
 613                                 zlog_debug("%s: (%d:%d)", __func__, i, k);
 614                         }
 615                         // keys[k] = (void *)random();
 616                         keys[k] = scramble(k);
 617                         if (skiplist_insert(l, keys[k], keys[k]))
 618                                 zlog_debug("error in insert #%d,#%d", i, k);
 619                 }
 620
 621                 zlog_debug("%s: inserts done", __func__);
 622
 623                 for (k = 0; k < sampleSize; k++) {
 624
 625                         if (!(k % 1000))
 626                                 zlog_debug("[%d:%d]", i, k);
 627                         if (skiplist_search(l, keys[k], &v))
 628                                 zlog_debug("error in search #%d,#%d", i, k);
 629
 630                         if (v != keys[k])
 631                                 zlog_debug("search returned wrong value");
 632                 }
 633
 634
 635                 for (k = 0; k < sampleSize; k++) {
 636
 637                         if (!(k % 1000))
 638                                 zlog_debug("<%d:%d>", i, k);
 639                         if (skiplist_delete(l, keys[k], keys[k]))
 640                                 zlog_debug("error in delete");
 641                         keys[k] = scramble(k ^ 0xf0f0f0f0);
 642                         if (skiplist_insert(l, keys[k], keys[k]))
 643                                 zlog_debug("error in insert #%d,#%d", i, k);
 644                 }
 645
 646                 for (k = 0; k < sampleSize; k++) {
 647
 648                         if (!(k % 1000))
 649                                 zlog_debug("{%d:%d}", i, k);
 650                         if (skiplist_delete_first(l))
 651                                 zlog_debug("error in delete_first");
 652                 }
 653         }
 654
 655         skiplist_free(l);
 656 }