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