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