Line data Source code
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 36 : DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List");
67 36 : DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node");
68 36 : 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 0 : static int randomLevel(void)
100 : {
101 0 : register int level = 0;
102 0 : register int b;
103 :
104 0 : do {
105 0 : if (randomsLeft <= 0) {
106 0 : randomBits = frr_weak_random();
107 0 : randomsLeft = BitsInRandom / 2;
108 : }
109 0 : b = randomBits & 3;
110 0 : randomBits >>= 2;
111 0 : --randomsLeft;
112 :
113 0 : if (!b) {
114 0 : level++;
115 0 : if (level >= MaxLevel)
116 : return MaxLevel;
117 : }
118 0 : } while (!b);
119 :
120 : return level;
121 : }
122 :
123 0 : static int default_cmp(const void *key1, const void *key2)
124 : {
125 0 : if (key1 < key2)
126 : return -1;
127 0 : if (key1 > key2)
128 0 : return 1;
129 : return 0;
130 : }
131 :
132 0 : unsigned int skiplist_count(struct skiplist *l)
133 : {
134 0 : return l->count;
135 : }
136 :
137 0 : struct skiplist *skiplist_new(int flags,
138 : int (*cmp)(const void *key1, const void *key2),
139 : void (*del)(void *val))
140 : {
141 0 : struct skiplist *new;
142 :
143 0 : new = XCALLOC(MTYPE_SKIP_LIST, sizeof(struct skiplist));
144 0 : assert(new);
145 :
146 0 : new->level = 0;
147 0 : new->count = 0;
148 0 : new->header = newNodeOfLevel(MaxNumberOfLevels);
149 0 : new->level_stats = newStatsOfLevel(MaxNumberOfLevels);
150 :
151 0 : new->flags = flags;
152 0 : if (cmp)
153 0 : new->cmp = cmp;
154 : else
155 0 : new->cmp = default_cmp;
156 :
157 0 : if (del)
158 0 : new->del = del;
159 :
160 0 : return new;
161 : }
162 :
163 0 : void skiplist_free(struct skiplist *l)
164 : {
165 0 : register struct skiplistnode *p, *q;
166 :
167 0 : p = l->header;
168 :
169 0 : do {
170 0 : q = p->forward[0];
171 0 : if (l->del && p != l->header)
172 0 : (*l->del)(p->value);
173 0 : XFREE(MTYPE_SKIP_LIST_NODE, p);
174 0 : p = q;
175 0 : } while (p);
176 :
177 0 : XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats);
178 0 : XFREE(MTYPE_SKIP_LIST, l);
179 0 : }
180 :
181 :
182 0 : int skiplist_insert(register struct skiplist *l, register void *key,
183 : register void *value)
184 : {
185 0 : register int k;
186 0 : struct skiplistnode *update[MaxNumberOfLevels];
187 0 : register struct skiplistnode *p, *q;
188 :
189 0 : 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 0 : p = l->header;
200 0 : k = l->level;
201 : do {
202 0 : while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
203 : p = q;
204 0 : update[k] = p;
205 0 : } while (--k >= 0);
206 :
207 0 : if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) && q
208 0 : && ((*l->cmp)(q->key, key) == 0)) {
209 :
210 : return -1;
211 : }
212 :
213 0 : k = randomLevel();
214 0 : assert(k >= 0);
215 0 : if (k > l->level) {
216 0 : k = ++l->level;
217 0 : update[k] = l->header;
218 : }
219 :
220 0 : q = newNodeOfLevel(k);
221 0 : q->key = key;
222 0 : q->value = value;
223 : #ifdef SKIPLIST_0TIMER_DEBUG
224 0 : q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */
225 : #endif
226 :
227 0 : ++(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 0 : do {
234 0 : p = update[k];
235 0 : q->forward[k] = p->forward[k];
236 0 : p->forward[k] = q;
237 0 : } while (--k >= 0);
238 :
239 : /*
240 : * If this is the last item in the list, update the "last" pointer
241 : */
242 0 : if (!q->forward[0]) {
243 0 : l->last = q;
244 : }
245 :
246 0 : ++(l->count);
247 :
248 0 : CHECKLAST(l);
249 :
250 0 : return 0;
251 : }
252 :
253 0 : int skiplist_delete(register struct skiplist *l, register void *key,
254 : register void *value) /* used only if duplicates allowed */
255 : {
256 0 : register int k, m;
257 0 : struct skiplistnode *update[MaxNumberOfLevels];
258 0 : register struct skiplistnode *p, *q;
259 :
260 0 : CHECKLAST(l);
261 :
262 : /* to make debugging easier */
263 0 : for (k = 0; k < MaxNumberOfLevels; ++k)
264 0 : update[k] = NULL;
265 :
266 0 : p = l->header;
267 0 : k = m = l->level;
268 : do {
269 0 : while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
270 : p = q;
271 0 : update[k] = p;
272 0 : } while (--k >= 0);
273 :
274 0 : if (l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) {
275 0 : while (q && ((*l->cmp)(q->key, key) == 0)
276 0 : && (q->value != value)) {
277 : int i;
278 0 : for (i = 0; i <= l->level; ++i) {
279 0 : if (update[i]->forward[i] == q)
280 0 : update[i] = q;
281 : }
282 0 : q = q->forward[0];
283 : }
284 : }
285 :
286 0 : if (q && (*l->cmp)(q->key, key) == 0) {
287 0 : if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)
288 0 : || (q->value == value)) {
289 :
290 : /*
291 : * found node to delete
292 : */
293 : #ifdef SKIPLIST_0TIMER_DEBUG
294 0 : 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 0 : if (l->last == q) {
301 0 : if (update[0] == l->header)
302 0 : l->last = NULL;
303 : else
304 0 : l->last = update[0];
305 : }
306 :
307 0 : for (k = 0; k <= m && (p = update[k])->forward[k] == q;
308 0 : k++) {
309 0 : p->forward[k] = q->forward[k];
310 : }
311 0 : --(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 0 : if (l->del)
317 0 : (*l->del)(q->value);
318 0 : XFREE(MTYPE_SKIP_LIST_NODE, q);
319 0 : while (l->header->forward[m] == NULL && m > 0)
320 0 : m--;
321 0 : l->level = m;
322 0 : CHECKLAST(l);
323 0 : --(l->count);
324 0 : 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 0 : 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 0 : register int k;
344 0 : register struct skiplistnode *p, *q;
345 :
346 0 : p = l->header;
347 0 : k = l->level;
348 :
349 : do {
350 0 : while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0)
351 : p = q;
352 :
353 0 : } while (--k >= 0);
354 :
355 0 : if (!q || (*l->cmp)(q->key, key))
356 0 : return -1;
357 :
358 0 : if (valuePointer)
359 0 : *valuePointer = q->value;
360 :
361 0 : if (cursor)
362 0 : *cursor = q;
363 :
364 : return 0;
365 : }
366 :
367 0 : int skiplist_search(register struct skiplist *l, register void *key,
368 : void **valuePointer)
369 : {
370 0 : 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 0 : 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 0 : register int k;
389 0 : register struct skiplistnode *p, *q;
390 :
391 0 : CHECKLAST(l);
392 :
393 0 : if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) {
394 : return -1;
395 : }
396 :
397 0 : if (!cursor || !*cursor) {
398 0 : p = l->header;
399 0 : k = l->level;
400 :
401 : /*
402 : * Find matching key
403 : */
404 : do {
405 0 : while (q = p->forward[k],
406 0 : q && (*l->cmp)(q->key, key) < 0)
407 : p = q;
408 0 : } while (--k >= 0);
409 :
410 : /*
411 : * Find matching value
412 : */
413 0 : while (q && ((*l->cmp)(q->key, key) == 0)
414 0 : && (q->value != *valuePointer)) {
415 0 : q = q->forward[0];
416 : }
417 :
418 0 : if (!q || ((*l->cmp)(q->key, key) != 0)
419 0 : || (q->value != *valuePointer)) {
420 : /*
421 : * No matching value
422 : */
423 0 : CHECKLAST(l);
424 0 : return -1;
425 : }
426 : } else {
427 : q = (struct skiplistnode *)*cursor;
428 : }
429 :
430 : /*
431 : * Advance cursor
432 : */
433 0 : 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 0 : if (!q || ((*l->cmp)(q->key, key) != 0))
440 0 : return -1;
441 :
442 0 : *valuePointer = q->value;
443 0 : if (cursor)
444 0 : *cursor = q;
445 : CHECKLAST(l);
446 : return 0;
447 : }
448 :
449 0 : int skiplist_first(register struct skiplist *l, void **keyPointer,
450 : void **valuePointer)
451 : {
452 0 : register struct skiplistnode *p;
453 :
454 0 : CHECKLAST(l);
455 0 : p = l->header->forward[0];
456 0 : if (!p)
457 : return -1;
458 :
459 0 : if (keyPointer)
460 0 : *keyPointer = p->key;
461 :
462 0 : if (valuePointer)
463 0 : *valuePointer = p->value;
464 :
465 : CHECKLAST(l);
466 :
467 : return 0;
468 : }
469 :
470 0 : int skiplist_last(register struct skiplist *l, void **keyPointer,
471 : void **valuePointer)
472 : {
473 0 : CHECKLAST(l);
474 0 : if (l->last) {
475 0 : if (keyPointer)
476 0 : *keyPointer = l->last->key;
477 0 : if (valuePointer)
478 0 : *valuePointer = l->last->value;
479 0 : return 0;
480 : }
481 : return -1;
482 : }
483 :
484 : /*
485 : * true = empty
486 : */
487 0 : int skiplist_empty(register struct skiplist *l)
488 : {
489 0 : CHECKLAST(l);
490 0 : if (l->last)
491 0 : 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 0 : int skiplist_next(register struct skiplist *l, /* in */
501 : void **keyPointer, /* out */
502 : void **valuePointer, /* out */
503 : void **cursor) /* in/out */
504 : {
505 0 : struct skiplistnode *p;
506 :
507 0 : if (!cursor)
508 : return -1;
509 :
510 0 : CHECKLAST(l);
511 :
512 0 : if (!*cursor) {
513 0 : p = l->header->forward[0];
514 : } else {
515 0 : p = *cursor;
516 0 : p = p->forward[0];
517 : }
518 0 : *cursor = p;
519 :
520 0 : if (!p)
521 : return -1;
522 :
523 0 : if (keyPointer)
524 0 : *keyPointer = p->key;
525 :
526 0 : if (valuePointer)
527 0 : *valuePointer = p->value;
528 :
529 : CHECKLAST(l);
530 :
531 : return 0;
532 : }
533 :
534 0 : int skiplist_delete_first(register struct skiplist *l)
535 : {
536 0 : register int k;
537 0 : register struct skiplistnode *p, *q;
538 0 : int nodelevel = 0;
539 :
540 0 : CHECKLAST(l);
541 :
542 0 : p = l->header;
543 0 : q = l->header->forward[0];
544 :
545 0 : if (!q)
546 : return -1;
547 :
548 0 : for (k = l->level; k >= 0; --k) {
549 0 : if (p->forward[k] == q) {
550 0 : p->forward[k] = q->forward[k];
551 0 : if ((k == l->level) && (p->forward[k] == NULL)
552 0 : && (l->level > 0))
553 0 : --(l->level);
554 0 : if (!nodelevel)
555 0 : nodelevel = k;
556 : }
557 : }
558 :
559 : #ifdef SKIPLIST_0TIMER_DEBUG
560 0 : 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 0 : if (l->last == q) {
567 0 : l->last = NULL;
568 : }
569 :
570 0 : --(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 0 : if (l->del)
577 0 : (*l->del)(q->value);
578 :
579 0 : XFREE(MTYPE_SKIP_LIST_NODE, q);
580 :
581 0 : CHECKLAST(l);
582 :
583 0 : --(l->count);
584 :
585 0 : return 0;
586 : }
587 :
588 0 : void skiplist_debug(struct vty *vty, struct skiplist *l)
589 : {
590 0 : int i;
591 :
592 0 : if (!l)
593 : return;
594 :
595 0 : vty_out(vty, "Skiplist %p has max level %d\n", l, l->level);
596 0 : for (i = l->level; i >= 0; --i)
597 0 : vty_out(vty, " @%d: %d\n", i, l->level_stats[i]);
598 : }
599 :
600 0 : static void *scramble(int i)
601 : {
602 0 : uintptr_t result;
603 :
604 0 : result = (unsigned)(i & 0xff) << 24;
605 0 : result |= (unsigned)i >> 8;
606 :
607 0 : return (void *)result;
608 : }
609 :
610 : #define sampleSize 65536
611 0 : void skiplist_test(struct vty *vty)
612 : {
613 0 : struct skiplist *l;
614 0 : register int i, k;
615 0 : void *keys[sampleSize];
616 0 : void *v = NULL;
617 :
618 0 : zlog_debug("%s: entry", __func__);
619 :
620 0 : l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL);
621 :
622 0 : zlog_debug("%s: skiplist_new returned %p", __func__, l);
623 :
624 0 : for (i = 0; i < 4; i++) {
625 :
626 0 : for (k = 0; k < sampleSize; k++) {
627 0 : if (!(k % 1000)) {
628 0 : zlog_debug("%s: (%d:%d)", __func__, i, k);
629 : }
630 : // keys[k] = (void *)random();
631 0 : keys[k] = scramble(k);
632 0 : if (skiplist_insert(l, keys[k], keys[k]))
633 0 : zlog_debug("error in insert #%d,#%d", i, k);
634 : }
635 :
636 0 : zlog_debug("%s: inserts done", __func__);
637 :
638 0 : for (k = 0; k < sampleSize; k++) {
639 :
640 0 : if (!(k % 1000))
641 0 : zlog_debug("[%d:%d]", i, k);
642 0 : if (skiplist_search(l, keys[k], &v))
643 0 : zlog_debug("error in search #%d,#%d", i, k);
644 :
645 0 : if (v != keys[k])
646 0 : zlog_debug("search returned wrong value");
647 : }
648 :
649 :
650 0 : for (k = 0; k < sampleSize; k++) {
651 :
652 0 : if (!(k % 1000))
653 0 : zlog_debug("<%d:%d>", i, k);
654 0 : if (skiplist_delete(l, keys[k], keys[k]))
655 0 : zlog_debug("error in delete");
656 0 : keys[k] = scramble(k ^ 0xf0f0f0f0);
657 0 : if (skiplist_insert(l, keys[k], keys[k]))
658 0 : zlog_debug("error in insert #%d,#%d", i, k);
659 : }
660 :
661 0 : for (k = 0; k < sampleSize; k++) {
662 :
663 0 : if (!(k % 1000))
664 0 : zlog_debug("{%d:%d}", i, k);
665 0 : if (skiplist_delete_first(l))
666 0 : zlog_debug("error in delete_first");
667 : }
668 : }
669 :
670 0 : skiplist_free(l);
671 0 : }
|
