]>
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 | /* | |
214d8a60 | 24 | * Skip List implementation based on code from William Pugh. |
520d2512 | 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" |
5920b3eb | 64 | #include "network.h" |
520d2512 | 65 | |
bf8d3d6a DL |
66 | DEFINE_MTYPE_STATIC(LIB, SKIP_LIST, "Skip List"); |
67 | DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_NODE, "Skip Node"); | |
c324b10f | 68 | DEFINE_MTYPE_STATIC(LIB, SKIP_LIST_STATS, "Skiplist Counters"); |
520d2512 LB |
69 | |
70 | #define BitsInRandom 31 | |
71 | ||
72 | #define MaxNumberOfLevels 16 | |
73 | #define MaxLevel (MaxNumberOfLevels-1) | |
c324b10f PZ |
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)) | |
520d2512 LB |
82 | |
83 | static int randomsLeft; | |
84 | static int randomBits; | |
520d2512 | 85 | |
c324b10f | 86 | #ifdef SKIPLIST_DEBUG |
d62a17ae | 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) | |
520d2512 LB |
94 | #else |
95 | #define CHECKLAST(sl) | |
96 | #endif | |
97 | ||
98 | ||
4d762f26 | 99 | static int randomLevel(void) |
520d2512 | 100 | { |
d62a17ae | 101 | register int level = 0; |
102 | register int b; | |
520d2512 | 103 | |
d62a17ae | 104 | do { |
105 | if (randomsLeft <= 0) { | |
5920b3eb | 106 | randomBits = frr_weak_random(); |
d62a17ae | 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; | |
520d2512 LB |
121 | } |
122 | ||
1a4189d4 | 123 | static int default_cmp(const void *key1, const void *key2) |
520d2512 | 124 | { |
d62a17ae | 125 | if (key1 < key2) |
126 | return -1; | |
127 | if (key1 > key2) | |
128 | return 1; | |
129 | return 0; | |
520d2512 LB |
130 | } |
131 | ||
d62a17ae | 132 | unsigned int skiplist_count(struct skiplist *l) |
520d2512 | 133 | { |
d62a17ae | 134 | return l->count; |
520d2512 LB |
135 | } |
136 | ||
1a4189d4 DS |
137 | struct skiplist *skiplist_new(int flags, |
138 | int (*cmp)(const void *key1, const void *key2), | |
d62a17ae | 139 | void (*del)(void *val)) |
520d2512 | 140 | { |
d62a17ae | 141 | struct skiplist *new; |
520d2512 | 142 | |
d62a17ae | 143 | new = XCALLOC(MTYPE_SKIP_LIST, sizeof(struct skiplist)); |
144 | assert(new); | |
520d2512 | 145 | |
d62a17ae | 146 | new->level = 0; |
147 | new->count = 0; | |
148 | new->header = newNodeOfLevel(MaxNumberOfLevels); | |
c324b10f | 149 | new->level_stats = newStatsOfLevel(MaxNumberOfLevels); |
520d2512 | 150 | |
d62a17ae | 151 | new->flags = flags; |
152 | if (cmp) | |
153 | new->cmp = cmp; | |
154 | else | |
155 | new->cmp = default_cmp; | |
520d2512 | 156 | |
d62a17ae | 157 | if (del) |
158 | new->del = del; | |
520d2512 | 159 | |
d62a17ae | 160 | return new; |
520d2512 LB |
161 | } |
162 | ||
d62a17ae | 163 | void skiplist_free(struct skiplist *l) |
520d2512 | 164 | { |
d62a17ae | 165 | register struct skiplistnode *p, *q; |
520d2512 | 166 | |
d62a17ae | 167 | p = l->header; |
520d2512 | 168 | |
d62a17ae | 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); | |
520d2512 | 176 | |
c324b10f | 177 | XFREE(MTYPE_SKIP_LIST_STATS, l->level_stats); |
d62a17ae | 178 | XFREE(MTYPE_SKIP_LIST, l); |
520d2512 LB |
179 | } |
180 | ||
181 | ||
d62a17ae | 182 | int skiplist_insert(register struct skiplist *l, register void *key, |
183 | register void *value) | |
520d2512 | 184 | { |
d62a17ae | 185 | register int k; |
186 | struct skiplistnode *update[MaxNumberOfLevels]; | |
187 | register struct skiplistnode *p, *q; | |
188 | ||
189 | CHECKLAST(l); | |
190 | ||
c324b10f | 191 | #ifdef SKIPLIST_DEBUG |
d62a17ae | 192 | /* DEBUG */ |
193 | if (!key) { | |
450971aa | 194 | flog_err(EC_LIB_DEVELOPMENT, "%s: key is 0, value is %p", |
1c50c1c0 | 195 | __func__, value); |
d62a17ae | 196 | } |
c324b10f | 197 | #endif |
d62a17ae | 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(); | |
f70247fe | 214 | assert(k >= 0); |
d62a17ae | 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; | |
1e20238a | 223 | #ifdef SKIPLIST_0TIMER_DEBUG |
d62a17ae | 224 | q->flags = SKIPLIST_NODE_FLAG_INSERTED; /* debug */ |
520d2512 LB |
225 | #endif |
226 | ||
c324b10f | 227 | ++(l->level_stats[k]); |
1e20238a | 228 | #ifdef SKIPLIST_DEBUG |
c324b10f PZ |
229 | zlog_debug("%s: incremented level_stats @%p:%d, now %d", __func__, l, k, |
230 | l->level_stats[k]); | |
520d2512 LB |
231 | #endif |
232 | ||
d62a17ae | 233 | do { |
234 | p = update[k]; | |
235 | q->forward[k] = p->forward[k]; | |
236 | p->forward[k] = q; | |
237 | } while (--k >= 0); | |
520d2512 | 238 | |
d62a17ae | 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 | } | |
520d2512 | 245 | |
d62a17ae | 246 | ++(l->count); |
520d2512 | 247 | |
d62a17ae | 248 | CHECKLAST(l); |
520d2512 | 249 | |
d62a17ae | 250 | return 0; |
520d2512 LB |
251 | } |
252 | ||
d62a17ae | 253 | int skiplist_delete(register struct skiplist *l, register void *key, |
254 | register void *value) /* used only if duplicates allowed */ | |
520d2512 | 255 | { |
d62a17ae | 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 | } | |
520d2512 | 284 | } |
520d2512 | 285 | |
d62a17ae | 286 | if (q && (*l->cmp)(q->key, key) == 0) { |
287 | if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES) | |
288 | || (q->value == value)) { | |
520d2512 | 289 | |
d62a17ae | 290 | /* |
291 | * found node to delete | |
292 | */ | |
1e20238a | 293 | #ifdef SKIPLIST_0TIMER_DEBUG |
d62a17ae | 294 | q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED; |
520d2512 | 295 | #endif |
d62a17ae | 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 | } | |
c324b10f | 311 | --(l->level_stats[k - 1]); |
1e20238a | 312 | #ifdef SKIPLIST_DEBUG |
c324b10f PZ |
313 | zlog_debug("%s: decremented level_stats @%p:%d, now %d", |
314 | __func__, l, k - 1, l->level_stats[k - 1]); | |
520d2512 | 315 | #endif |
d62a17ae | 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 | } | |
520d2512 | 326 | } |
520d2512 | 327 | |
d62a17ae | 328 | CHECKLAST(l); |
329 | return -1; | |
520d2512 LB |
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 | */ | |
d62a17ae | 338 | int skiplist_first_value(register struct skiplist *l, /* in */ |
1a4189d4 DS |
339 | register const void *key, /* in */ |
340 | void **valuePointer, /* out */ | |
d62a17ae | 341 | void **cursor) /* out */ |
520d2512 | 342 | { |
d62a17ae | 343 | register int k; |
344 | register struct skiplistnode *p, *q; | |
520d2512 | 345 | |
d62a17ae | 346 | p = l->header; |
347 | k = l->level; | |
520d2512 | 348 | |
d62a17ae | 349 | do { |
350 | while (q = p->forward[k], q && (*l->cmp)(q->key, key) < 0) | |
351 | p = q; | |
520d2512 | 352 | |
d62a17ae | 353 | } while (--k >= 0); |
520d2512 | 354 | |
d62a17ae | 355 | if (!q || (*l->cmp)(q->key, key)) |
356 | return -1; | |
520d2512 | 357 | |
d62a17ae | 358 | if (valuePointer) |
359 | *valuePointer = q->value; | |
520d2512 | 360 | |
d62a17ae | 361 | if (cursor) |
362 | *cursor = q; | |
520d2512 | 363 | |
d62a17ae | 364 | return 0; |
520d2512 LB |
365 | } |
366 | ||
d62a17ae | 367 | int skiplist_search(register struct skiplist *l, register void *key, |
368 | void **valuePointer) | |
520d2512 | 369 | { |
d62a17ae | 370 | return skiplist_first_value(l, key, valuePointer, NULL); |
520d2512 LB |
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 | */ | |
d62a17ae | 383 | int skiplist_next_value(register struct skiplist *l, /* in */ |
1a4189d4 | 384 | register const void *key, /* in */ |
d62a17ae | 385 | void **valuePointer, /* in/out */ |
386 | void **cursor) /* in/out */ | |
520d2512 | 387 | { |
5037cc3e | 388 | register int k; |
d62a17ae | 389 | register struct skiplistnode *p, *q; |
520d2512 | 390 | |
d62a17ae | 391 | CHECKLAST(l); |
520d2512 | 392 | |
d62a17ae | 393 | if (!(l->flags & SKIPLIST_FLAG_ALLOW_DUPLICATES)) { |
394 | return -1; | |
395 | } | |
520d2512 | 396 | |
d62a17ae | 397 | if (!cursor || !*cursor) { |
398 | p = l->header; | |
5037cc3e | 399 | k = l->level; |
d62a17ae | 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 | } | |
520d2512 LB |
429 | |
430 | /* | |
d62a17ae | 431 | * Advance cursor |
520d2512 | 432 | */ |
d62a17ae | 433 | q = q->forward[0]; |
520d2512 | 434 | |
d62a17ae | 435 | /* |
436 | * If we reached end-of-list or if the key is no longer the same, | |
437 | * then return error | |
520d2512 | 438 | */ |
d62a17ae | 439 | if (!q || ((*l->cmp)(q->key, key) != 0)) |
440 | return -1; | |
520d2512 | 441 | |
d62a17ae | 442 | *valuePointer = q->value; |
443 | if (cursor) | |
444 | *cursor = q; | |
445 | CHECKLAST(l); | |
446 | return 0; | |
520d2512 LB |
447 | } |
448 | ||
d62a17ae | 449 | int skiplist_first(register struct skiplist *l, void **keyPointer, |
450 | void **valuePointer) | |
520d2512 | 451 | { |
d62a17ae | 452 | register struct skiplistnode *p; |
520d2512 | 453 | |
d62a17ae | 454 | CHECKLAST(l); |
455 | p = l->header->forward[0]; | |
456 | if (!p) | |
457 | return -1; | |
520d2512 | 458 | |
d62a17ae | 459 | if (keyPointer) |
460 | *keyPointer = p->key; | |
520d2512 | 461 | |
d62a17ae | 462 | if (valuePointer) |
463 | *valuePointer = p->value; | |
520d2512 | 464 | |
d62a17ae | 465 | CHECKLAST(l); |
520d2512 | 466 | |
d62a17ae | 467 | return 0; |
520d2512 LB |
468 | } |
469 | ||
d62a17ae | 470 | int skiplist_last(register struct skiplist *l, void **keyPointer, |
471 | void **valuePointer) | |
520d2512 | 472 | { |
d62a17ae | 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; | |
520d2512 LB |
482 | } |
483 | ||
484 | /* | |
485 | * true = empty | |
486 | */ | |
d62a17ae | 487 | int skiplist_empty(register struct skiplist *l) |
520d2512 | 488 | { |
d62a17ae | 489 | CHECKLAST(l); |
490 | if (l->last) | |
491 | return 0; | |
492 | return 1; | |
520d2512 LB |
493 | } |
494 | ||
d62a17ae | 495 | /* |
520d2512 LB |
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 | */ | |
d62a17ae | 500 | int skiplist_next(register struct skiplist *l, /* in */ |
501 | void **keyPointer, /* out */ | |
502 | void **valuePointer, /* out */ | |
503 | void **cursor) /* in/out */ | |
520d2512 | 504 | { |
d62a17ae | 505 | struct skiplistnode *p; |
520d2512 | 506 | |
d62a17ae | 507 | if (!cursor) |
508 | return -1; | |
520d2512 | 509 | |
d62a17ae | 510 | CHECKLAST(l); |
520d2512 | 511 | |
d62a17ae | 512 | if (!*cursor) { |
513 | p = l->header->forward[0]; | |
514 | } else { | |
515 | p = *cursor; | |
516 | p = p->forward[0]; | |
517 | } | |
518 | *cursor = p; | |
520d2512 | 519 | |
d62a17ae | 520 | if (!p) |
521 | return -1; | |
520d2512 | 522 | |
d62a17ae | 523 | if (keyPointer) |
524 | *keyPointer = p->key; | |
520d2512 | 525 | |
d62a17ae | 526 | if (valuePointer) |
527 | *valuePointer = p->value; | |
520d2512 | 528 | |
d62a17ae | 529 | CHECKLAST(l); |
520d2512 | 530 | |
d62a17ae | 531 | return 0; |
520d2512 LB |
532 | } |
533 | ||
d62a17ae | 534 | int skiplist_delete_first(register struct skiplist *l) |
520d2512 | 535 | { |
d62a17ae | 536 | register int k; |
537 | register struct skiplistnode *p, *q; | |
538 | int nodelevel = 0; | |
520d2512 | 539 | |
d62a17ae | 540 | CHECKLAST(l); |
520d2512 | 541 | |
d62a17ae | 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 | } | |
520d2512 | 557 | } |
520d2512 | 558 | |
1e20238a | 559 | #ifdef SKIPLIST_0TIMER_DEBUG |
d62a17ae | 560 | q->flags &= ~SKIPLIST_NODE_FLAG_INSERTED; |
520d2512 | 561 | #endif |
d62a17ae | 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 | ||
c324b10f | 570 | --(l->level_stats[nodelevel]); |
1e20238a | 571 | #ifdef SKIPLIST_DEBUG |
c324b10f PZ |
572 | zlog_debug("%s: decremented level_stats @%p:%d, now %d", __func__, l, |
573 | nodelevel, l->level_stats[nodelevel]); | |
520d2512 LB |
574 | #endif |
575 | ||
d62a17ae | 576 | if (l->del) |
577 | (*l->del)(q->value); | |
520d2512 | 578 | |
d62a17ae | 579 | XFREE(MTYPE_SKIP_LIST_NODE, q); |
520d2512 | 580 | |
d62a17ae | 581 | CHECKLAST(l); |
520d2512 | 582 | |
d62a17ae | 583 | --(l->count); |
520d2512 | 584 | |
d62a17ae | 585 | return 0; |
520d2512 LB |
586 | } |
587 | ||
d62a17ae | 588 | void skiplist_debug(struct vty *vty, struct skiplist *l) |
520d2512 | 589 | { |
d62a17ae | 590 | int i; |
591 | ||
592 | if (!l) | |
bcbc2aa7 EB |
593 | return; |
594 | ||
d62a17ae | 595 | vty_out(vty, "Skiplist %p has max level %d\n", l, l->level); |
596 | for (i = l->level; i >= 0; --i) | |
c324b10f | 597 | vty_out(vty, " @%d: %d\n", i, l->level_stats[i]); |
520d2512 LB |
598 | } |
599 | ||
d62a17ae | 600 | static void *scramble(int i) |
520d2512 | 601 | { |
d62a17ae | 602 | uintptr_t result; |
520d2512 | 603 | |
937652c6 DL |
604 | result = (unsigned)(i & 0xff) << 24; |
605 | result |= (unsigned)i >> 8; | |
520d2512 | 606 | |
d62a17ae | 607 | return (void *)result; |
520d2512 LB |
608 | } |
609 | ||
610 | #define sampleSize 65536 | |
d62a17ae | 611 | void skiplist_test(struct vty *vty) |
612 | { | |
613 | struct skiplist *l; | |
614 | register int i, k; | |
615 | void *keys[sampleSize]; | |
6ce59f0b | 616 | void *v = NULL; |
520d2512 | 617 | |
d62a17ae | 618 | zlog_debug("%s: entry", __func__); |
520d2512 | 619 | |
d62a17ae | 620 | l = skiplist_new(SKIPLIST_FLAG_ALLOW_DUPLICATES, NULL, NULL); |
520d2512 | 621 | |
d62a17ae | 622 | zlog_debug("%s: skiplist_new returned %p", __func__, l); |
520d2512 | 623 | |
d62a17ae | 624 | for (i = 0; i < 4; i++) { |
520d2512 | 625 | |
d62a17ae | 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(); | |
c4efd0f4 | 631 | keys[k] = scramble(k); |
d62a17ae | 632 | if (skiplist_insert(l, keys[k], keys[k])) |
633 | zlog_debug("error in insert #%d,#%d", i, k); | |
634 | } | |
520d2512 | 635 | |
d62a17ae | 636 | zlog_debug("%s: inserts done", __func__); |
520d2512 | 637 | |
d62a17ae | 638 | for (k = 0; k < sampleSize; k++) { |
520d2512 | 639 | |
d62a17ae | 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); | |
520d2512 | 644 | |
d62a17ae | 645 | if (v != keys[k]) |
646 | zlog_debug("search returned wrong value"); | |
647 | } | |
520d2512 LB |
648 | |
649 | ||
d62a17ae | 650 | for (k = 0; k < sampleSize; k++) { |
520d2512 | 651 | |
d62a17ae | 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"); | |
c4efd0f4 | 656 | keys[k] = scramble(k ^ 0xf0f0f0f0); |
d62a17ae | 657 | if (skiplist_insert(l, keys[k], keys[k])) |
658 | zlog_debug("error in insert #%d,#%d", i, k); | |
659 | } | |
520d2512 | 660 | |
d62a17ae | 661 | for (k = 0; k < sampleSize; k++) { |
520d2512 | 662 | |
d62a17ae | 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 | } | |
520d2512 | 668 | } |
520d2512 | 669 | |
d62a17ae | 670 | skiplist_free(l); |
520d2512 | 671 | } |