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     *cursor = q;
 443     CHECKLAST(l);
 444     return 0;
 445 }
 446
 447 int
 448 skiplist_first(
 449     register struct skiplist     *l,
 450     void                        **keyPointer,
 451     void                        **valuePointer)
 452 {
 453     register struct skiplistnode *p;
 454
 455     CHECKLAST(l);
 456     p = l->header->forward[0];
 457     if (!p)
 458         return -1;
 459
 460     if (keyPointer)
 461         *keyPointer = p->key;
 462
 463     if (valuePointer)
 464         *valuePointer = p->value;
 465
 466     CHECKLAST(l);
 467
 468     return 0;
 469 }
 470
 471 int
 472 skiplist_last(
 473     register struct skiplist     *l,
 474     void                        **keyPointer,
 475     void                        **valuePointer)
 476 {
 477     CHECKLAST(l);
 478     if (l->last) {
 479         if (keyPointer)
 480             *keyPointer = l->last->key;
 481         if (valuePointer)
 482             *valuePointer = l->last->value;
 483         return 0;
 484     }
 485     return -1;
 486 }
 487
 488 /*
 489  * true = empty
 490  */
 491 int
 492 skiplist_empty(
 493     register struct skiplist     *l)
 494 {
 495     CHECKLAST(l);
 496     if (l->last)
 497         return 0;
 498     return 1;
 499 }
 500
 501 /*
 502  * Use this to walk the list. Caller sets *cursor to NULL to obtain
 503  * first element. Return value of 0 indicates valid cursor/element
 504  * returned, otherwise NULL cursor arg or EOL.
 505  */
 506 int
 507 skiplist_next(
 508     register struct skiplist     *l,                    /* in */
 509     void                        **keyPointer,           /* out */
 510     void                        **valuePointer,         /* out */
 511     void                        **cursor)               /* in/out */
 512 {
 513     struct skiplistnode *p;
 514
 515     if (!cursor)
 516         return -1;
 517
 518     CHECKLAST(l);
 519
 520     if (!*cursor) {
 521         p = l->header->forward[0];
 522     } else {
 523         p = *cursor;
 524         p = p->forward[0];
 525     }
 526     *cursor = p;
 527
 528     if (!p)
 529         return -1;
 530
 531     if (keyPointer)
 532         *keyPointer = p->key;
 533
 534     if (valuePointer)
 535         *valuePointer = p->value;
 536
 537     CHECKLAST(l);
 538
 539     return 0;
 540 }
 541
 542 int
 543 skiplist_delete_first(
 544     register struct skiplist     *l)
 545 {
 546     register int                k;
 547     register struct skiplistnode *p, *q;
 548     int nodelevel = 0;
 549
 550     CHECKLAST(l);
 551
 552     p = l->header;
 553     q = l->header->forward[0];
 554
 555     if (!q)
 556         return -1;
 557
 558     for (k = l->level; k >= 0; --k) {
 559         if (p->forward[k] == q) {
 560             p->forward[k] = q->forward[k];
 561             if ((k == l->level) && (p->forward[k] == NULL) && (l->level > 0))
 562                 --(l->level);
 563             if (!nodelevel)
 564                 nodelevel = k;
 565         }
 566     }
 567
 568 #if SKIPLIST_0TIMER_DEBUG
 569     q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED;
 570 #endif
 571     /*
 572      * If we are deleting the last element of the list,
 573      * update the list's "last" pointer.
 574      */
 575     if (l->last == q) {
 576         l->last = NULL;
 577     }
 578
 579     --(l->stats->forward[nodelevel]);
 580 #if SKIPLIST_DEBUG
 581     zlog_debug("%s: decremented stats @%p:%d, now %ld", __func__, l, nodelevel,
 582         l->stats->forward[nodelevel] - (struct skiplistnode *)NULL);
 583 #endif
 584
 585     if (l->del)
 586         (*l->del)(q->value);
 587
 588     XFREE(MTYPE_SKIP_LIST_NODE, q);
 589
 590     CHECKLAST(l);
 591
 592     --(l->count);
 593
 594     return 0;
 595 }
 596
 597 void
 598 skiplist_debug(struct vty *vty, struct skiplist *l)
 599 {
 600     int i;
 601
 602     if (!l)
 603         l = skiplist_last_created;
 604     vty_out(vty, "Skiplist %p has max level %d%s", l, l->level, VTY_NEWLINE);
 605     for (i = l->level; i >= 0; --i)
 606         vty_out(vty, "  @%d: %ld%s",
 607             i, (long)((l->stats->forward[i]) - (struct skiplistnode *)NULL),
 608             VTY_NEWLINE);
 609 }
 610
 611 static void *
 612 scramble(int i)
 613 {
 614     uintptr_t   result;
 615
 616     result = (i & 0xff) << 24;
 617     result |= (i >> 8);
 618
 619     return (void *)result;
 620 }
 621
 622 #define sampleSize 65536
 623 void
 624 skiplist_test(struct vty *vty) {
 625     struct skiplist *l;
 626     register int i,k;
 627     void *keys[sampleSize];
 628     void *v;
 629
 630     zlog_debug("%s: entry", __func__);
 631
 632     l= skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
 633
 634     zlog_debug("%s: skiplist_new returned %p", __func__, l);
 635
 636     for (i=0; i < 4; i++) {
 637
 638         for (k=0; k < sampleSize; k++) {
 639             if (!(k%1000)) {
 640                 zlog_debug("%s: (%d:%d)", __func__, i, k);
 641             }
 642             //keys[k] = (void *)random();
 643             keys[k] = (void *)scramble(k);
 644             if (skiplist_insert(l, keys[k], keys[k]))
 645                 zlog_debug("error in insert #%d,#%d",i,k);
 646         }
 647
 648         zlog_debug("%s: inserts done", __func__);
 649
 650         for (k=0; k < sampleSize; k++) {
 651
 652             if (!(k % 1000))
 653                 zlog_debug("[%d:%d]", i, k);
 654             if (skiplist_search(l, keys[k], &v))
 655                 zlog_debug("error in search #%d,#%d",i,k);
 656
 657             if (v != keys[k])
 658                 zlog_debug("search returned wrong value");
 659         }
 660
 661
 662
 663         for (k=0; k < sampleSize; k++) {
 664
 665             if (!(k % 1000))
 666                 zlog_debug("<%d:%d>", i, k);
 667             if (skiplist_delete(l, keys[k], keys[k]))
 668                 zlog_debug("error in delete");
 669             keys[k] = (void *)scramble(k ^ 0xf0f0f0f0);
 670             if (skiplist_insert(l, keys[k], keys[k]))
 671                 zlog_debug("error in insert #%d,#%d",i,k);
 672         }
 673
 674         for (k=0; k < sampleSize; k++) {
 675
 676             if (!(k % 1000))
 677                 zlog_debug("{%d:%d}", i, k);
 678             if (skiplist_delete_first(l))
 679                 zlog_debug("error in delete_first");
 680         }
 681     }
 682
 683     skiplist_free(l);
 684 }
 685