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