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