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