1 // SPDX-License-Identifier: LicenseRef-Skiplist-BSD-0-Clause
3 * Copyright 1990 William Pugh
5 * Permission to include in quagga provide on March 31, 2016
9 * Skip List implementation based on code from William Pugh.
10 * ftp://ftp.cs.umd.edu/pub/skipLists/
12 * Skip Lists are a probabilistic alternative to balanced trees, as
13 * described in the June 1990 issue of CACM and were invented by
14 * William Pugh in 1987.
16 * This file contains source code to implement a dictionary using
17 * skip lists and a test driver to test the routines.
19 * A couple of comments about this implementation:
20 * The routine randomLevel has been hard-coded to generate random
21 * levels using p=0.25. It can be easily changed.
23 * The insertion routine has been implemented so as to use the
24 * dirty hack described in the CACM paper: if a random level is
25 * generated that is more than the current maximum level, the
26 * current maximum level plus one is used instead.
28 * Levels start at zero and go up to MaxLevel (which is equal to
29 * (MaxNumberOfLevels-1).
31 * The run-time flag SKIPLIST_FLAG_ALLOW_DUPLICATES determines whether or
32 * not duplicates are allowed for a given list. If set, duplicates are
33 * allowed and act in a FIFO manner. If not set, an insertion of a value
34 * already in the list updates the previously existing binding.
36 * BitsInRandom is defined to be the number of bits returned by a call to
37 * random(). For most all machines with 32-bit integers, this is 31 bits
48 #include "lib_errors.h"
51 DEFINE_MTYPE_STATIC(LIB
, SKIP_LIST
, "Skip List");
52 DEFINE_MTYPE_STATIC(LIB
, SKIP_LIST_NODE
, "Skip Node");
53 DEFINE_MTYPE_STATIC(LIB
, SKIP_LIST_STATS
, "Skiplist Counters");
55 #define BitsInRandom 31
57 #define MaxNumberOfLevels 16
58 #define MaxLevel (MaxNumberOfLevels-1)
59 #define newNodeOfLevel(l) \
60 XCALLOC(MTYPE_SKIP_LIST_NODE, \
61 sizeof(struct skiplistnode) \
62 + (l) * sizeof(struct skiplistnode *))
64 /* XXX must match type of (struct skiplist).level_stats */
65 #define newStatsOfLevel(l) \
66 XCALLOC(MTYPE_SKIP_LIST_STATS, ((l) + 1) * sizeof(int))
68 static int randomsLeft
;
69 static int randomBits
;
72 #define CHECKLAST(sl) \
74 if ((sl)->header->forward[0] && !(sl)->last) \
76 if (!(sl)->header->forward[0] && (sl)->last) \
84 static int randomLevel(void)
86 register int level
= 0;
90 if (randomsLeft
<= 0) {
91 randomBits
= frr_weak_random();
92 randomsLeft
= BitsInRandom
/ 2;
100 if (level
>= MaxLevel
)
108 static int default_cmp(const void *key1
, const void *key2
)
117 unsigned int skiplist_count(struct skiplist
*l
)
122 struct skiplist
*skiplist_new(int flags
,
123 int (*cmp
)(const void *key1
, const void *key2
),
124 void (*del
)(void *val
))
126 struct skiplist
*new;
128 new = XCALLOC(MTYPE_SKIP_LIST
, sizeof(struct skiplist
));
133 new->header
= newNodeOfLevel(MaxNumberOfLevels
);
134 new->level_stats
= newStatsOfLevel(MaxNumberOfLevels
);
140 new->cmp
= default_cmp
;
148 void skiplist_free(struct skiplist
*l
)
150 register struct skiplistnode
*p
, *q
;
156 if (l
->del
&& p
!= l
->header
)
158 XFREE(MTYPE_SKIP_LIST_NODE
, p
);
162 XFREE(MTYPE_SKIP_LIST_STATS
, l
->level_stats
);
163 XFREE(MTYPE_SKIP_LIST
, l
);
167 int skiplist_insert(register struct skiplist
*l
, register void *key
,
168 register void *value
)
171 struct skiplistnode
*update
[MaxNumberOfLevels
];
172 register struct skiplistnode
*p
, *q
;
176 #ifdef SKIPLIST_DEBUG
179 flog_err(EC_LIB_DEVELOPMENT
, "%s: key is 0, value is %p",
187 while (q
= p
->forward
[k
], q
&& (*l
->cmp
)(q
->key
, key
) < 0)
192 if (!(l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
) && q
193 && ((*l
->cmp
)(q
->key
, key
) == 0)) {
202 update
[k
] = l
->header
;
205 q
= newNodeOfLevel(k
);
208 #ifdef SKIPLIST_0TIMER_DEBUG
209 q
->flags
= SKIPLIST_NODE_FLAG_INSERTED
; /* debug */
212 ++(l
->level_stats
[k
]);
213 #ifdef SKIPLIST_DEBUG
214 zlog_debug("%s: incremented level_stats @%p:%d, now %d", __func__
, l
, k
,
220 q
->forward
[k
] = p
->forward
[k
];
225 * If this is the last item in the list, update the "last" pointer
227 if (!q
->forward
[0]) {
238 int skiplist_delete(register struct skiplist
*l
, register void *key
,
239 register void *value
) /* used only if duplicates allowed */
242 struct skiplistnode
*update
[MaxNumberOfLevels
];
243 register struct skiplistnode
*p
, *q
;
247 /* to make debugging easier */
248 for (k
= 0; k
< MaxNumberOfLevels
; ++k
)
254 while (q
= p
->forward
[k
], q
&& (*l
->cmp
)(q
->key
, key
) < 0)
259 if (l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
) {
260 while (q
&& ((*l
->cmp
)(q
->key
, key
) == 0)
261 && (q
->value
!= value
)) {
263 for (i
= 0; i
<= l
->level
; ++i
) {
264 if (update
[i
]->forward
[i
] == q
)
271 if (q
&& (*l
->cmp
)(q
->key
, key
) == 0) {
272 if (!(l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
)
273 || (q
->value
== value
)) {
276 * found node to delete
278 #ifdef SKIPLIST_0TIMER_DEBUG
279 q
->flags
&= ~SKIPLIST_NODE_FLAG_INSERTED
;
282 * If we are deleting the last element of the list,
283 * update the list's "last" pointer.
286 if (update
[0] == l
->header
)
292 for (k
= 0; k
<= m
&& (p
= update
[k
])->forward
[k
] == q
;
294 p
->forward
[k
] = q
->forward
[k
];
296 --(l
->level_stats
[k
- 1]);
297 #ifdef SKIPLIST_DEBUG
298 zlog_debug("%s: decremented level_stats @%p:%d, now %d",
299 __func__
, l
, k
- 1, l
->level_stats
[k
- 1]);
303 XFREE(MTYPE_SKIP_LIST_NODE
, q
);
304 while (l
->header
->forward
[m
] == NULL
&& m
> 0)
318 * Obtain first value matching "key". Unless SKIPLIST_FLAG_ALLOW_DUPLICATES
319 * is set, this will also be the only value matching "key".
321 * Also set a cursor for use with skiplist_next_value.
323 int skiplist_first_value(register struct skiplist
*l
, /* in */
324 register const void *key
, /* in */
325 void **valuePointer
, /* out */
326 void **cursor
) /* out */
329 register struct skiplistnode
*p
, *q
;
335 while (q
= p
->forward
[k
], q
&& (*l
->cmp
)(q
->key
, key
) < 0)
340 if (!q
|| (*l
->cmp
)(q
->key
, key
))
344 *valuePointer
= q
->value
;
352 int skiplist_search(register struct skiplist
*l
, register void *key
,
355 return skiplist_first_value(l
, key
, valuePointer
, NULL
);
360 * Caller supplies key and value of an existing item in the list.
361 * Function returns the value of the next list item that has the
362 * same key (useful when SKIPLIST_FLAG_ALLOW_DUPLICATES is set).
364 * Returns 0 on success. If the caller-supplied key and value
365 * do not correspond to a list element, or if they specify the
366 * last element with the given key, -1 is returned.
368 int skiplist_next_value(register struct skiplist
*l
, /* in */
369 register const void *key
, /* in */
370 void **valuePointer
, /* in/out */
371 void **cursor
) /* in/out */
374 register struct skiplistnode
*p
, *q
;
378 if (!(l
->flags
& SKIPLIST_FLAG_ALLOW_DUPLICATES
)) {
382 if (!cursor
|| !*cursor
) {
390 while (q
= p
->forward
[k
],
391 q
&& (*l
->cmp
)(q
->key
, key
) < 0)
396 * Find matching value
398 while (q
&& ((*l
->cmp
)(q
->key
, key
) == 0)
399 && (q
->value
!= *valuePointer
)) {
403 if (!q
|| ((*l
->cmp
)(q
->key
, key
) != 0)
404 || (q
->value
!= *valuePointer
)) {
412 q
= (struct skiplistnode
*)*cursor
;
421 * If we reached end-of-list or if the key is no longer the same,
424 if (!q
|| ((*l
->cmp
)(q
->key
, key
) != 0))
427 *valuePointer
= q
->value
;
434 int skiplist_first(register struct skiplist
*l
, void **keyPointer
,
437 register struct skiplistnode
*p
;
440 p
= l
->header
->forward
[0];
445 *keyPointer
= p
->key
;
448 *valuePointer
= p
->value
;
455 int skiplist_last(register struct skiplist
*l
, void **keyPointer
,
461 *keyPointer
= l
->last
->key
;
463 *valuePointer
= l
->last
->value
;
472 int skiplist_empty(register struct skiplist
*l
)
481 * Use this to walk the list. Caller sets *cursor to NULL to obtain
482 * first element. Return value of 0 indicates valid cursor/element
483 * returned, otherwise NULL cursor arg or EOL.
485 int skiplist_next(register struct skiplist
*l
, /* in */
486 void **keyPointer
, /* out */
487 void **valuePointer
, /* out */
488 void **cursor
) /* in/out */
490 struct skiplistnode
*p
;
498 p
= l
->header
->forward
[0];
509 *keyPointer
= p
->key
;
512 *valuePointer
= p
->value
;
519 int skiplist_delete_first(register struct skiplist
*l
)
522 register struct skiplistnode
*p
, *q
;
528 q
= l
->header
->forward
[0];
533 for (k
= l
->level
; k
>= 0; --k
) {
534 if (p
->forward
[k
] == q
) {
535 p
->forward
[k
] = q
->forward
[k
];
536 if ((k
== l
->level
) && (p
->forward
[k
] == NULL
)
544 #ifdef SKIPLIST_0TIMER_DEBUG
545 q
->flags
&= ~SKIPLIST_NODE_FLAG_INSERTED
;
548 * If we are deleting the last element of the list,
549 * update the list's "last" pointer.
555 --(l
->level_stats
[nodelevel
]);
556 #ifdef SKIPLIST_DEBUG
557 zlog_debug("%s: decremented level_stats @%p:%d, now %d", __func__
, l
,
558 nodelevel
, l
->level_stats
[nodelevel
]);
564 XFREE(MTYPE_SKIP_LIST_NODE
, q
);
573 void skiplist_debug(struct vty
*vty
, struct skiplist
*l
)
580 vty_out(vty
, "Skiplist %p has max level %d\n", l
, l
->level
);
581 for (i
= l
->level
; i
>= 0; --i
)
582 vty_out(vty
, " @%d: %d\n", i
, l
->level_stats
[i
]);
585 static void *scramble(int i
)
589 result
= (unsigned)(i
& 0xff) << 24;
590 result
|= (unsigned)i
>> 8;
592 return (void *)result
;
595 #define sampleSize 65536
596 void skiplist_test(struct vty
*vty
)
600 void *keys
[sampleSize
];
603 zlog_debug("%s: entry", __func__
);
605 l
= skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES
, NULL
, NULL
);
607 zlog_debug("%s: skiplist_new returned %p", __func__
, l
);
609 for (i
= 0; i
< 4; i
++) {
611 for (k
= 0; k
< sampleSize
; k
++) {
613 zlog_debug("%s: (%d:%d)", __func__
, i
, k
);
615 // keys[k] = (void *)random();
616 keys
[k
] = scramble(k
);
617 if (skiplist_insert(l
, keys
[k
], keys
[k
]))
618 zlog_debug("error in insert #%d,#%d", i
, k
);
621 zlog_debug("%s: inserts done", __func__
);
623 for (k
= 0; k
< sampleSize
; k
++) {
626 zlog_debug("[%d:%d]", i
, k
);
627 if (skiplist_search(l
, keys
[k
], &v
))
628 zlog_debug("error in search #%d,#%d", i
, k
);
631 zlog_debug("search returned wrong value");
635 for (k
= 0; k
< sampleSize
; k
++) {
638 zlog_debug("<%d:%d>", i
, k
);
639 if (skiplist_delete(l
, keys
[k
], keys
[k
]))
640 zlog_debug("error in delete");
641 keys
[k
] = scramble(k
^ 0xf0f0f0f0);
642 if (skiplist_insert(l
, keys
[k
], keys
[k
]))
643 zlog_debug("error in insert #%d,#%d", i
, k
);
646 for (k
= 0; k
< sampleSize
; k
++) {
649 zlog_debug("{%d:%d}", i
, k
);
650 if (skiplist_delete_first(l
))
651 zlog_debug("error in delete_first");