lib/skiplist.c

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