2 * Copyright 1990 William Pugh
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted.
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
20 * Permission to include in quagga provide on March 31, 2016
24 * Skip List impementation based on code from William Pugh.
25 * ftp://ftp.cs.umd.edu/pub/skipLists/
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.
31 * This file contains source code to implement a dictionary using
32 * skip lists and a test driver to test the routines.
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.
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.
43 * Levels start at zero and go up to MaxLevel (which is equal to
44 * (MaxNumberOfLevels-1).
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.
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
63 #include "lib_errors.h"
65 DEFINE_MTYPE_STATIC(LIB
, SKIP_LIST
, "Skip List")
66 DEFINE_MTYPE_STATIC(LIB
, SKIP_LIST_NODE
, "Skip Node")
68 #define BitsInRandom 31
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 *))
74 static int randomsLeft
;
75 static int randomBits
;
76 static struct skiplist
*skiplist_last_created
; /* debugging hack */
79 #define CHECKLAST(sl) \
81 if ((sl)->header->forward[0] && !(sl)->last) \
83 if (!(sl)->header->forward[0] && (sl)->last) \
91 static int randomLevel(void)
93 register int level
= 0;
97 if (randomsLeft
<= 0) {
98 randomBits
= random();
99 randomsLeft
= BitsInRandom
/ 2;
107 if (level
>= MaxLevel
)
115 static int default_cmp(const void *key1
, const void *key2
)
124 unsigned int skiplist_count(struct skiplist
*l
)
129 struct skiplist
*skiplist_new(int flags
,
130 int (*cmp
)(const void *key1
, const void *key2
),
131 void (*del
)(void *val
))
133 struct skiplist
*new;
135 new = XCALLOC(MTYPE_SKIP_LIST
, sizeof(struct skiplist
));
140 new->header
= newNodeOfLevel(MaxNumberOfLevels
);
141 new->stats
= newNodeOfLevel(MaxNumberOfLevels
);
147 new->cmp
= default_cmp
;
152 skiplist_last_created
= new; /* debug */
157 void skiplist_free(struct skiplist
*l
)
159 register struct skiplistnode
*p
, *q
;
165 if (l
->del
&& p
!= l
->header
)
167 XFREE(MTYPE_SKIP_LIST_NODE
, p
);
171 XFREE(MTYPE_SKIP_LIST_NODE
, l
->stats
);
172 XFREE(MTYPE_SKIP_LIST
, l
);
176 int skiplist_insert(register struct skiplist
*l
, register void *key
,
177 register void *value
)
180 struct skiplistnode
*update
[MaxNumberOfLevels
];
181 register struct skiplistnode
*p
, *q
;
187 flog_err(EC_LIB_DEVELOPMENT
, "%s: key is 0, value is %p",
194 while (q
= p
->forward
[k
], q
&& (*l
->cmp
)(q
->key
, key
) < 0)
199 if (!(l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
) && q
200 && ((*l
->cmp
)(q
->key
, key
) == 0)) {
209 update
[k
] = l
->header
;
212 q
= newNodeOfLevel(k
);
215 #ifdef SKIPLIST_0TIMER_DEBUG
216 q
->flags
= SKIPLIST_NODE_FLAG_INSERTED
; /* debug */
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
);
227 q
->forward
[k
] = p
->forward
[k
];
232 * If this is the last item in the list, update the "last" pointer
234 if (!q
->forward
[0]) {
245 int skiplist_delete(register struct skiplist
*l
, register void *key
,
246 register void *value
) /* used only if duplicates allowed */
249 struct skiplistnode
*update
[MaxNumberOfLevels
];
250 register struct skiplistnode
*p
, *q
;
254 /* to make debugging easier */
255 for (k
= 0; k
< MaxNumberOfLevels
; ++k
)
261 while (q
= p
->forward
[k
], q
&& (*l
->cmp
)(q
->key
, key
) < 0)
266 if (l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
) {
267 while (q
&& ((*l
->cmp
)(q
->key
, key
) == 0)
268 && (q
->value
!= value
)) {
270 for (i
= 0; i
<= l
->level
; ++i
) {
271 if (update
[i
]->forward
[i
] == q
)
278 if (q
&& (*l
->cmp
)(q
->key
, key
) == 0) {
279 if (!(l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
)
280 || (q
->value
== value
)) {
283 * found node to delete
285 #ifdef SKIPLIST_0TIMER_DEBUG
286 q
->flags
&= ~SKIPLIST_NODE_FLAG_INSERTED
;
289 * If we are deleting the last element of the list,
290 * update the list's "last" pointer.
293 if (update
[0] == l
->header
)
299 for (k
= 0; k
<= m
&& (p
= update
[k
])->forward
[k
] == q
;
301 p
->forward
[k
] = q
->forward
[k
];
303 --(l
->stats
->forward
[k
- 1]);
304 #ifdef SKIPLIST_DEBUG
305 zlog_debug("%s: decremented stats @%p:%d, now %ld",
307 l
->stats
->forward
[k
- 1]
308 - (struct skiplistnode
*)NULL
);
312 XFREE(MTYPE_SKIP_LIST_NODE
, q
);
313 while (l
->header
->forward
[m
] == NULL
&& m
> 0)
327 * Obtain first value matching "key". Unless SKIPLIST_FLAG_ALLOW_DUPLICATES
328 * is set, this will also be the only value matching "key".
330 * Also set a cursor for use with skiplist_next_value.
332 int skiplist_first_value(register struct skiplist
*l
, /* in */
333 register const void *key
, /* in */
334 void **valuePointer
, /* out */
335 void **cursor
) /* out */
338 register struct skiplistnode
*p
, *q
;
344 while (q
= p
->forward
[k
], q
&& (*l
->cmp
)(q
->key
, key
) < 0)
349 if (!q
|| (*l
->cmp
)(q
->key
, key
))
353 *valuePointer
= q
->value
;
361 int skiplist_search(register struct skiplist
*l
, register void *key
,
364 return skiplist_first_value(l
, key
, valuePointer
, NULL
);
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).
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.
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 */
383 register struct skiplistnode
*p
, *q
;
387 if (!(l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
)) {
391 if (!cursor
|| !*cursor
) {
399 while (q
= p
->forward
[k
],
400 q
&& (*l
->cmp
)(q
->key
, key
) < 0)
405 * Find matching value
407 while (q
&& ((*l
->cmp
)(q
->key
, key
) == 0)
408 && (q
->value
!= *valuePointer
)) {
412 if (!q
|| ((*l
->cmp
)(q
->key
, key
) != 0)
413 || (q
->value
!= *valuePointer
)) {
421 q
= (struct skiplistnode
*)*cursor
;
430 * If we reached end-of-list or if the key is no longer the same,
433 if (!q
|| ((*l
->cmp
)(q
->key
, key
) != 0))
436 *valuePointer
= q
->value
;
443 int skiplist_first(register struct skiplist
*l
, void **keyPointer
,
446 register struct skiplistnode
*p
;
449 p
= l
->header
->forward
[0];
454 *keyPointer
= p
->key
;
457 *valuePointer
= p
->value
;
464 int skiplist_last(register struct skiplist
*l
, void **keyPointer
,
470 *keyPointer
= l
->last
->key
;
472 *valuePointer
= l
->last
->value
;
481 int skiplist_empty(register struct skiplist
*l
)
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.
494 int skiplist_next(register struct skiplist
*l
, /* in */
495 void **keyPointer
, /* out */
496 void **valuePointer
, /* out */
497 void **cursor
) /* in/out */
499 struct skiplistnode
*p
;
507 p
= l
->header
->forward
[0];
518 *keyPointer
= p
->key
;
521 *valuePointer
= p
->value
;
528 int skiplist_delete_first(register struct skiplist
*l
)
531 register struct skiplistnode
*p
, *q
;
537 q
= l
->header
->forward
[0];
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
)
553 #ifdef SKIPLIST_0TIMER_DEBUG
554 q
->flags
&= ~SKIPLIST_NODE_FLAG_INSERTED
;
557 * If we are deleting the last element of the list,
558 * update the list's "last" pointer.
564 --(l
->stats
->forward
[nodelevel
]);
565 #ifdef SKIPLIST_DEBUG
566 zlog_debug("%s: decremented stats @%p:%d, now %ld", __func__
, l
,
568 l
->stats
->forward
[nodelevel
] - (struct skiplistnode
*)NULL
);
574 XFREE(MTYPE_SKIP_LIST_NODE
, q
);
583 void skiplist_debug(struct vty
*vty
, struct skiplist
*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
));
596 static void *scramble(int i
)
600 result
= (unsigned)(i
& 0xff) << 24;
601 result
|= (unsigned)i
>> 8;
603 return (void *)result
;
606 #define sampleSize 65536
607 void skiplist_test(struct vty
*vty
)
611 void *keys
[sampleSize
];
614 zlog_debug("%s: entry", __func__
);
616 l
= skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES
, NULL
, NULL
);
618 zlog_debug("%s: skiplist_new returned %p", __func__
, l
);
620 for (i
= 0; i
< 4; i
++) {
622 for (k
= 0; k
< sampleSize
; k
++) {
624 zlog_debug("%s: (%d:%d)", __func__
, i
, k
);
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
);
632 zlog_debug("%s: inserts done", __func__
);
634 for (k
= 0; k
< sampleSize
; k
++) {
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
);
642 zlog_debug("search returned wrong value");
646 for (k
= 0; k
< sampleSize
; k
++) {
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
);
657 for (k
= 0; k
< sampleSize
; k
++) {
660 zlog_debug("{%d:%d}", i
, k
);
661 if (skiplist_delete_first(l
))
662 zlog_debug("error in delete_first");