1 /* Licensed to the Apache Software Foundation (ASF) under one or more
2 * contributor license agreements. See the NOTICE file distributed with
3 * this work for additional information regarding copyright ownership.
4 * The ASF licenses this file to You under the Apache License, Version 2.0
5 * (the "License"); you may not use this file except in compliance with
6 * the License. You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /*
18 * Modified to use APR and APR pools.
19 * TODO: Is malloc() better? Will long running skiplists grow too much?
20 * Keep the skiplist_alloc() and skiplist_free() until we know
21 * Yeah, if using pools it means some bogus cycles for checks
22 * (and an useless function call for skiplist_free) which we
23 * can removed if/when needed.
24 */
25
26 #include "apr_skiplist.h"
27
28 typedef struct {
29 apr_skiplistnode **data;
30 size_t size, pos;
31 apr_pool_t *p;
32 } apr_skiplist_q;
33
34 struct apr_skiplist {
35 apr_skiplist_compare compare;
36 apr_skiplist_compare comparek;
37 int height;
38 int preheight;
39 size_t size;
40 apr_skiplistnode *top;
41 apr_skiplistnode *bottom;
42 /* These two are needed for appending */
43 apr_skiplistnode *topend;
44 apr_skiplistnode *bottomend;
45 apr_skiplist *index;
46 apr_array_header_t *memlist;
47 apr_skiplist_q nodes_q,
48 stack_q;
49 apr_pool_t *pool;
50 };
51
52 struct apr_skiplistnode {
53 void *data;
54 apr_skiplistnode *next;
55 apr_skiplistnode *prev;
56 apr_skiplistnode *down;
57 apr_skiplistnode *up;
58 apr_skiplistnode *previndex;
59 apr_skiplistnode *nextindex;
60 apr_skiplist *sl;
61 };
62
get_b_rand(void)63 static int get_b_rand(void)
64 {
65 static int ph = 32; /* More bits than we will ever use */
66 static int randseq;
67 if (ph > 31) { /* Num bits in return of rand() */
68 ph = 0;
69 randseq = rand();
70 }
71 return randseq & (1 << ph++);
72 }
73
74 typedef struct {
75 size_t size;
76 apr_array_header_t *list;
77 } memlist_t;
78
79 typedef struct {
80 void *ptr;
81 char inuse;
82 } chunk_t;
83
apr_skiplist_alloc(apr_skiplist * sl,size_t size)84 APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size)
85 {
86 if (sl->pool) {
87 void *ptr;
88 int found_size = 0;
89 int i;
90 chunk_t *newchunk;
91 memlist_t *memlist = (memlist_t *)sl->memlist->elts;
92 for (i = 0; i < sl->memlist->nelts; i++) {
93 if (memlist->size == size) {
94 int j;
95 chunk_t *chunk = (chunk_t *)memlist->list->elts;
96 found_size = 1;
97 for (j = 0; j < memlist->list->nelts; j++) {
98 if (!chunk->inuse) {
99 chunk->inuse = 1;
100 return chunk->ptr;
101 }
102 chunk++;
103 }
104 break; /* no free of this size; punt */
105 }
106 memlist++;
107 }
108 /* no free chunks */
109 ptr = apr_palloc(sl->pool, size);
110 if (!ptr) {
111 return ptr;
112 }
113 /*
114 * is this a new sized chunk? If so, we need to create a new
115 * array of them. Otherwise, re-use what we already have.
116 */
117 if (!found_size) {
118 memlist = apr_array_push(sl->memlist);
119 memlist->size = size;
120 memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t));
121 }
122 newchunk = apr_array_push(memlist->list);
123 newchunk->ptr = ptr;
124 newchunk->inuse = 1;
125 return ptr;
126 }
127 else {
128 return malloc(size);
129 }
130 }
131
apr_skiplist_free(apr_skiplist * sl,void * mem)132 APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem)
133 {
134 if (!sl->pool) {
135 free(mem);
136 }
137 else {
138 int i;
139 memlist_t *memlist = (memlist_t *)sl->memlist->elts;
140 for (i = 0; i < sl->memlist->nelts; i++) {
141 int j;
142 chunk_t *chunk = (chunk_t *)memlist->list->elts;
143 for (j = 0; j < memlist->list->nelts; j++) {
144 if (chunk->ptr == mem) {
145 chunk->inuse = 0;
146 return;
147 }
148 chunk++;
149 }
150 memlist++;
151 }
152 }
153 }
154
skiplist_qpush(apr_skiplist_q * q,apr_skiplistnode * m)155 static apr_status_t skiplist_qpush(apr_skiplist_q *q, apr_skiplistnode *m)
156 {
157 if (q->pos >= q->size) {
158 apr_skiplistnode **data;
159 size_t size = (q->pos) ? q->pos * 2 : 32;
160 if (q->p) {
161 data = apr_palloc(q->p, size * sizeof(*data));
162 if (data) {
163 memcpy(data, q->data, q->pos * sizeof(*data));
164 }
165 }
166 else {
167 data = realloc(q->data, size * sizeof(*data));
168 }
169 if (!data) {
170 return APR_ENOMEM;
171 }
172 q->data = data;
173 q->size = size;
174 }
175 q->data[q->pos++] = m;
176 return APR_SUCCESS;
177 }
178
skiplist_qpop(apr_skiplist_q * q)179 static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
180 {
181 return (q->pos > 0) ? q->data[--q->pos] : NULL;
182 }
183
skiplist_qclear(apr_skiplist_q * q)184 static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
185 {
186 q->pos = 0;
187 }
188
skiplist_new_node(apr_skiplist * sl)189 static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl)
190 {
191 apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q);
192 if (!m) {
193 if (sl->pool) {
194 m = apr_palloc(sl->pool, sizeof *m);
195 }
196 else {
197 m = malloc(sizeof *m);
198 }
199 }
200 return m;
201 }
202
skiplist_put_node(apr_skiplist * sl,apr_skiplistnode * m)203 static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m)
204 {
205 return skiplist_qpush(&sl->nodes_q, m);
206 }
207
skiplisti_init(apr_skiplist ** s,apr_pool_t * p)208 static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
209 {
210 apr_skiplist *sl;
211 if (p) {
212 sl = apr_pcalloc(p, sizeof(apr_skiplist));
213 sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
214 sl->pool = sl->nodes_q.p = sl->stack_q.p = p;
215 }
216 else {
217 sl = calloc(1, sizeof(apr_skiplist));
218 if (!sl) {
219 return APR_ENOMEM;
220 }
221 }
222 *s = sl;
223 return APR_SUCCESS;
224 }
225
indexing_comp(void * a,void * b)226 static int indexing_comp(void *a, void *b)
227 {
228 void *ac = (void *) (((apr_skiplist *) a)->compare);
229 void *bc = (void *) (((apr_skiplist *) b)->compare);
230 return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
231 }
232
indexing_compk(void * ac,void * b)233 static int indexing_compk(void *ac, void *b)
234 {
235 void *bc = (void *) (((apr_skiplist *) b)->compare);
236 return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
237 }
238
apr_skiplist_init(apr_skiplist ** s,apr_pool_t * p)239 APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
240 {
241 apr_skiplist *sl;
242 skiplisti_init(s, p);
243 sl = *s;
244 skiplisti_init(&(sl->index), p);
245 apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
246 return APR_SUCCESS;
247 }
248
apr_skiplist_set_compare(apr_skiplist * sl,apr_skiplist_compare comp,apr_skiplist_compare compk)249 APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl,
250 apr_skiplist_compare comp,
251 apr_skiplist_compare compk)
252 {
253 if (sl->compare && sl->comparek) {
254 apr_skiplist_add_index(sl, comp, compk);
255 }
256 else {
257 sl->compare = comp;
258 sl->comparek = compk;
259 }
260 }
261
apr_skiplist_add_index(apr_skiplist * sl,apr_skiplist_compare comp,apr_skiplist_compare compk)262 APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl,
263 apr_skiplist_compare comp,
264 apr_skiplist_compare compk)
265 {
266 apr_skiplistnode *m;
267 apr_skiplist *ni;
268 int icount = 0;
269 apr_skiplist_find(sl->index, (void *)comp, &m);
270 if (m) {
271 return; /* Index already there! */
272 }
273 skiplisti_init(&ni, sl->pool);
274 apr_skiplist_set_compare(ni, comp, compk);
275 /* Build the new index... This can be expensive! */
276 m = apr_skiplist_insert(sl->index, ni);
277 while (m->prev) {
278 m = m->prev;
279 icount++;
280 }
281 for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) {
282 int j = icount - 1;
283 apr_skiplistnode *nsln;
284 nsln = apr_skiplist_insert(ni, m->data);
285 /* skip from main index down list */
286 while (j > 0) {
287 m = m->nextindex;
288 j--;
289 }
290 /* insert this node in the indexlist after m */
291 nsln->nextindex = m->nextindex;
292 if (m->nextindex) {
293 m->nextindex->previndex = nsln;
294 }
295 nsln->previndex = m;
296 m->nextindex = nsln;
297 }
298 }
299
skiplisti_find_compare(apr_skiplist * sl,void * data,apr_skiplistnode ** ret,apr_skiplist_compare comp,int last)300 static int skiplisti_find_compare(apr_skiplist *sl, void *data,
301 apr_skiplistnode **ret,
302 apr_skiplist_compare comp,
303 int last)
304 {
305 int count = 0;
306 apr_skiplistnode *m, *found = NULL;
307 for (m = sl->top; m; count++) {
308 if (m->next) {
309 int compared = comp(data, m->next->data);
310 if (compared == 0) {
311 found = m = m->next;
312 if (!last) {
313 break;
314 }
315 continue;
316 }
317 if (compared > 0) {
318 m = m->next;
319 continue;
320 }
321 }
322 m = m->down;
323 }
324 if (found) {
325 while (found->down) {
326 found = found->down;
327 }
328 *ret = found;
329 }
330 else {
331 *ret = NULL;
332 }
333 return count;
334 }
335
find_compare(apr_skiplist * sli,void * data,apr_skiplistnode ** iter,apr_skiplist_compare comp,int last)336 static void *find_compare(apr_skiplist *sli, void *data,
337 apr_skiplistnode **iter,
338 apr_skiplist_compare comp,
339 int last)
340 {
341 apr_skiplistnode *m;
342 apr_skiplist *sl;
343 if (!comp) {
344 if (iter) {
345 *iter = NULL;
346 }
347 return NULL;
348 }
349 if (comp == sli->compare || !sli->index) {
350 sl = sli;
351 }
352 else {
353 apr_skiplist_find(sli->index, (void *)comp, &m);
354 if (!m) {
355 if (iter) {
356 *iter = NULL;
357 }
358 return NULL;
359 }
360 sl = (apr_skiplist *) m->data;
361 }
362 skiplisti_find_compare(sl, data, &m, sl->comparek, last);
363 if (iter) {
364 *iter = m;
365 }
366 return (m) ? m->data : NULL;
367 }
368
apr_skiplist_find_compare(apr_skiplist * sl,void * data,apr_skiplistnode ** iter,apr_skiplist_compare comp)369 APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, void *data,
370 apr_skiplistnode **iter,
371 apr_skiplist_compare comp)
372 {
373 return find_compare(sl, data, iter, comp, 0);
374 }
375
apr_skiplist_find(apr_skiplist * sl,void * data,apr_skiplistnode ** iter)376 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
377 {
378 return find_compare(sl, data, iter, sl->compare, 0);
379 }
380
apr_skiplist_last_compare(apr_skiplist * sl,void * data,apr_skiplistnode ** iter,apr_skiplist_compare comp)381 APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data,
382 apr_skiplistnode **iter,
383 apr_skiplist_compare comp)
384 {
385 return find_compare(sl, data, iter, comp, 1);
386 }
387
apr_skiplist_last(apr_skiplist * sl,void * data,apr_skiplistnode ** iter)388 APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data,
389 apr_skiplistnode **iter)
390 {
391 return find_compare(sl, data, iter, sl->compare, 1);
392 }
393
394
apr_skiplist_getlist(apr_skiplist * sl)395 APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
396 {
397 if (!sl->bottom) {
398 return NULL;
399 }
400 return sl->bottom->next;
401 }
402
apr_skiplist_next(apr_skiplist * sl,apr_skiplistnode ** iter)403 APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
404 {
405 if (!*iter) {
406 return NULL;
407 }
408 *iter = (*iter)->next;
409 return (*iter) ? ((*iter)->data) : NULL;
410 }
411
apr_skiplist_previous(apr_skiplist * sl,apr_skiplistnode ** iter)412 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
413 {
414 if (!*iter) {
415 return NULL;
416 }
417 *iter = (*iter)->prev;
418 return (*iter) ? ((*iter)->data) : NULL;
419 }
420
apr_skiplist_element(apr_skiplistnode * iter)421 APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter)
422 {
423 return (iter) ? iter->data : NULL;
424 }
425
426 /* forward declared */
427 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
428 apr_skiplist_freefunc myfree);
429
skiplist_height(const apr_skiplist * sl)430 static APR_INLINE int skiplist_height(const apr_skiplist *sl)
431 {
432 /* Skiplists (even empty) always have a top node, although this
433 * implementation defers its creation until the first insert, or
434 * deletes it with the last remove. We want the real height here.
435 */
436 return sl->height ? sl->height : 1;
437 }
438
insert_compare(apr_skiplist * sl,void * data,apr_skiplist_compare comp,int add,apr_skiplist_freefunc myfree)439 static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
440 apr_skiplist_compare comp, int add,
441 apr_skiplist_freefunc myfree)
442 {
443 apr_skiplistnode *m, *p, *tmp, *ret = NULL;
444 int ch, top_nh, nh = 1;
445
446 ch = skiplist_height(sl);
447 if (sl->preheight) {
448 while (nh < sl->preheight && get_b_rand()) {
449 nh++;
450 }
451 }
452 else {
453 while (nh <= ch && get_b_rand()) {
454 nh++;
455 }
456 }
457 top_nh = nh;
458
459 /* Now we have in nh the height at which we wish to insert our new node,
460 * and in ch the current height: don't create skip paths to the inserted
461 * element until the walk down through the tree (which decrements ch)
462 * reaches nh. From there, any walk down pushes the current node on a
463 * stack (the node(s) after which we would insert) to pop back through
464 * for insertion later.
465 */
466 m = sl->top;
467 while (m) {
468 /*
469 * To maintain stability, dups (compared == 0) must be added
470 * AFTER each other.
471 */
472 if (m->next) {
473 int compared = comp(data, m->next->data);
474 if (compared == 0) {
475 if (!add) {
476 /* Keep the existing element(s) */
477 skiplist_qclear(&sl->stack_q);
478 return NULL;
479 }
480 if (add < 0) {
481 /* Remove this element and continue with the next node
482 * or the new top if the current one is also removed.
483 */
484 apr_skiplistnode *top = sl->top;
485 skiplisti_remove(sl, m->next, myfree);
486 if (top != sl->top) {
487 m = sl->top;
488 skiplist_qclear(&sl->stack_q);
489 ch = skiplist_height(sl);
490 nh = top_nh;
491 }
492 continue;
493 }
494 }
495 if (compared >= 0) {
496 m = m->next;
497 continue;
498 }
499 }
500 if (ch <= nh) {
501 /* push on stack */
502 skiplist_qpush(&sl->stack_q, m);
503 }
504 m = m->down;
505 ch--;
506 }
507 /* Pop the stack and insert nodes */
508 p = NULL;
509 while ((m = skiplist_qpop(&sl->stack_q))) {
510 tmp = skiplist_new_node(sl);
511 tmp->next = m->next;
512 if (m->next) {
513 m->next->prev = tmp;
514 }
515 m->next = tmp;
516 tmp->prev = m;
517 tmp->up = NULL;
518 tmp->nextindex = tmp->previndex = NULL;
519 tmp->down = p;
520 if (p) {
521 p->up = tmp;
522 }
523 else {
524 /* This sets ret to the bottom-most node we are inserting */
525 ret = tmp;
526 }
527 tmp->data = data;
528 tmp->sl = sl;
529 p = tmp;
530 }
531
532 /* Now we are sure the node is inserted, grow our tree to 'nh' tall */
533 for (; sl->height < nh; sl->height++) {
534 m = skiplist_new_node(sl);
535 tmp = skiplist_new_node(sl);
536 m->up = m->prev = m->nextindex = m->previndex = NULL;
537 m->next = tmp;
538 m->down = sl->top;
539 m->data = NULL;
540 m->sl = sl;
541 if (sl->top) {
542 sl->top->up = m;
543 }
544 else {
545 sl->bottom = sl->bottomend = m;
546 }
547 sl->top = sl->topend = tmp->prev = m;
548 tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
549 tmp->down = p;
550 tmp->data = data;
551 tmp->sl = sl;
552 if (p) {
553 p->up = tmp;
554 }
555 else {
556 /* This sets ret to the bottom-most node we are inserting */
557 ret = tmp;
558 }
559 p = tmp;
560 }
561 if (sl->index != NULL) {
562 /*
563 * this is a external insertion, we must insert into each index as
564 * well
565 */
566 apr_skiplistnode *ni, *li;
567 li = ret;
568 for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
569 apr_skiplist *sli = (apr_skiplist *)p->data;
570 ni = insert_compare(sli, ret->data, sli->compare, 1, NULL);
571 li->nextindex = ni;
572 ni->previndex = li;
573 li = ni;
574 }
575 }
576 sl->size++;
577 return ret;
578 }
579
apr_skiplist_insert_compare(apr_skiplist * sl,void * data,apr_skiplist_compare comp)580 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
581 apr_skiplist_compare comp)
582 {
583 if (!comp) {
584 return NULL;
585 }
586 return insert_compare(sl, data, comp, 0, NULL);
587 }
588
apr_skiplist_insert(apr_skiplist * sl,void * data)589 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
590 {
591 return apr_skiplist_insert_compare(sl, data, sl->compare);
592 }
593
apr_skiplist_add_compare(apr_skiplist * sl,void * data,apr_skiplist_compare comp)594 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void *data,
595 apr_skiplist_compare comp)
596 {
597 if (!comp) {
598 return NULL;
599 }
600 return insert_compare(sl, data, comp, 1, NULL);
601 }
602
apr_skiplist_add(apr_skiplist * sl,void * data)603 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
604 {
605 return apr_skiplist_add_compare(sl, data, sl->compare);
606 }
607
apr_skiplist_replace_compare(apr_skiplist * sl,void * data,apr_skiplist_freefunc myfree,apr_skiplist_compare comp)608 APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
609 void *data, apr_skiplist_freefunc myfree,
610 apr_skiplist_compare comp)
611 {
612 if (!comp) {
613 return NULL;
614 }
615 return insert_compare(sl, data, comp, -1, myfree);
616 }
617
apr_skiplist_replace(apr_skiplist * sl,void * data,apr_skiplist_freefunc myfree)618 APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
619 void *data, apr_skiplist_freefunc myfree)
620 {
621 return apr_skiplist_replace_compare(sl, data, myfree, sl->compare);
622 }
623
624 #if 0
625 void skiplist_print_struct(apr_skiplist * sl, char *prefix)
626 {
627 apr_skiplistnode *p, *q;
628 fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
629 p = sl->bottom;
630 while (p) {
631 q = p;
632 fprintf(stderr, prefix);
633 while (q) {
634 fprintf(stderr, "%p ", q->data);
635 q = q->up;
636 }
637 fprintf(stderr, "\n");
638 p = p->next;
639 }
640 }
641 #endif
642
skiplisti_remove(apr_skiplist * sl,apr_skiplistnode * m,apr_skiplist_freefunc myfree)643 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
644 apr_skiplist_freefunc myfree)
645 {
646 apr_skiplistnode *p;
647 if (!m) {
648 return 0;
649 }
650 if (m->nextindex) {
651 skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
652 }
653 while (m->up) {
654 m = m->up;
655 }
656 do {
657 p = m;
658 /* take me out of the list */
659 p->prev->next = p->next;
660 if (p->next) {
661 p->next->prev = p->prev;
662 }
663 m = m->down;
664 /* This only frees the actual data in the bottom one */
665 if (!m && myfree && p->data) {
666 myfree(p->data);
667 }
668 skiplist_put_node(sl, p);
669 } while (m);
670 sl->size--;
671 while (sl->top && sl->top->next == NULL) {
672 /* While the row is empty and we are not on the bottom row */
673 p = sl->top;
674 sl->top = sl->top->down;/* Move top down one */
675 if (sl->top) {
676 sl->top->up = NULL; /* Make it think its the top */
677 }
678 skiplist_put_node(sl, p);
679 sl->height--;
680 }
681 if (!sl->top) {
682 sl->bottom = sl->bottomend = NULL;
683 sl->topend = NULL;
684 }
685 return skiplist_height(sl);
686 }
687
apr_skiplist_remove_node(apr_skiplist * sl,apr_skiplistnode * iter,apr_skiplist_freefunc myfree)688 APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
689 apr_skiplistnode *iter,
690 apr_skiplist_freefunc myfree)
691 {
692 apr_skiplistnode *m = iter;
693 if (!m) {
694 return 0;
695 }
696 while (m->down) {
697 m = m->down;
698 }
699 while (m->previndex) {
700 m = m->previndex;
701 }
702 return skiplisti_remove(sl, m, myfree);
703 }
704
apr_skiplist_remove_compare(apr_skiplist * sli,void * data,apr_skiplist_freefunc myfree,apr_skiplist_compare comp)705 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
706 void *data,
707 apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
708 {
709 apr_skiplistnode *m;
710 apr_skiplist *sl;
711 if (!comp) {
712 return 0;
713 }
714 if (comp == sli->comparek || !sli->index) {
715 sl = sli;
716 }
717 else {
718 apr_skiplist_find(sli->index, (void *)comp, &m);
719 if (!m) {
720 return 0;
721 }
722 sl = (apr_skiplist *) m->data;
723 }
724 skiplisti_find_compare(sl, data, &m, comp, 0);
725 if (!m) {
726 return 0;
727 }
728 while (m->previndex) {
729 m = m->previndex;
730 }
731 return skiplisti_remove(sl, m, myfree);
732 }
733
apr_skiplist_remove(apr_skiplist * sl,void * data,apr_skiplist_freefunc myfree)734 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
735 {
736 return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
737 }
738
apr_skiplist_remove_all(apr_skiplist * sl,apr_skiplist_freefunc myfree)739 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
740 {
741 /*
742 * This must remove even the place holder nodes (bottom though top)
743 * because we specify in the API that one can free the Skiplist after
744 * making this call without memory leaks
745 */
746 apr_skiplistnode *m, *p, *u;
747 m = sl->bottom;
748 while (m) {
749 p = m->next;
750 if (myfree && p && p->data) {
751 myfree(p->data);
752 }
753 do {
754 u = m->up;
755 skiplist_put_node(sl, m);
756 m = u;
757 } while (m);
758 m = p;
759 }
760 sl->top = sl->bottom = NULL;
761 sl->topend = sl->bottomend = NULL;
762 sl->height = 0;
763 sl->size = 0;
764 }
765
apr_skiplist_pop(apr_skiplist * a,apr_skiplist_freefunc myfree)766 APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
767 {
768 apr_skiplistnode *sln;
769 void *data = NULL;
770 sln = apr_skiplist_getlist(a);
771 if (sln) {
772 data = sln->data;
773 skiplisti_remove(a, sln, myfree);
774 }
775 return data;
776 }
777
apr_skiplist_peek(apr_skiplist * a)778 APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
779 {
780 apr_skiplistnode *sln;
781 sln = apr_skiplist_getlist(a);
782 if (sln) {
783 return sln->data;
784 }
785 return NULL;
786 }
787
apr_skiplist_size(const apr_skiplist * sl)788 APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
789 {
790 return sl->size;
791 }
792
apr_skiplist_height(const apr_skiplist * sl)793 APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
794 {
795 return skiplist_height(sl);
796 }
797
apr_skiplist_preheight(const apr_skiplist * sl)798 APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
799 {
800 return sl->preheight;
801 }
802
apr_skiplist_set_preheight(apr_skiplist * sl,int to)803 APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to)
804 {
805 sl->preheight = (to > 0) ? to : 0;
806 }
807
skiplisti_destroy(void * vsl)808 static void skiplisti_destroy(void *vsl)
809 {
810 apr_skiplist_destroy(vsl, NULL);
811 }
812
apr_skiplist_destroy(apr_skiplist * sl,apr_skiplist_freefunc myfree)813 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
814 {
815 while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
816 ;
817 apr_skiplist_remove_all(sl, myfree);
818 if (!sl->pool) {
819 while (sl->nodes_q.pos)
820 free(sl->nodes_q.data[--sl->nodes_q.pos]);
821 free(sl->nodes_q.data);
822 free(sl->stack_q.data);
823 free(sl);
824 }
825 }
826
apr_skiplist_merge(apr_skiplist * sl1,apr_skiplist * sl2)827 APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
828 {
829 /* Check integrity! */
830 apr_skiplist temp;
831 struct apr_skiplistnode *b2;
832 if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
833 apr_skiplist_remove_all(sl1, NULL);
834 temp = *sl1;
835 *sl1 = *sl2;
836 *sl2 = temp;
837 /* swap them so that sl2 can be freed normally upon return. */
838 return sl1;
839 }
840 if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
841 apr_skiplist_remove_all(sl2, NULL);
842 return sl1;
843 }
844 /* This is what makes it brute force... Just insert :/ */
845 b2 = apr_skiplist_getlist(sl2);
846 while (b2) {
847 apr_skiplist_insert(sl1, b2->data);
848 apr_skiplist_next(sl2, &b2);
849 }
850 apr_skiplist_remove_all(sl2, NULL);
851 return sl1;
852 }
853