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