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