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
28typedef struct {
29    apr_skiplistnode **data;
30    size_t size, pos;
31    apr_pool_t *p;
32} apr_skiplist_q;
33
34struct 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
52struct 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
63static 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
74typedef struct {
75    size_t size;
76    apr_array_header_t *list;
77} memlist_t;
78
79typedef struct {
80    void *ptr;
81    char inuse;
82} chunk_t;
83
84APR_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
132APR_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
155static 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
179static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
180{
181    return (q->pos > 0) ? q->data[--q->pos] : NULL;
182}
183
184static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
185{
186    q->pos = 0;
187}
188
189static 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
203static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m)
204{
205    return skiplist_qpush(&sl->nodes_q, m);
206}
207
208static 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
226static 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
233static 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
239APR_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
249APR_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
262APR_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
300static 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
336static 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
369APR_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
376APR_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
381APR_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
388APR_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
395APR_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
403APR_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
412APR_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
421APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter)
422{
423    return (iter) ? iter->data : NULL;
424}
425
426/* forward declared */
427static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
428                            apr_skiplist_freefunc myfree);
429
430static 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
439static 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
580APR_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
589APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
590{
591    return apr_skiplist_insert_compare(sl, data, sl->compare);
592}
593
594APR_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
603APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
604{
605    return apr_skiplist_add_compare(sl, data, sl->compare);
606}
607
608APR_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
618APR_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
625void 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
643static 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
688APR_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
705APR_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
734APR_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
739APR_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
766APR_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
778APR_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
788APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
789{
790    return sl->size;
791}
792
793APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
794{
795    return skiplist_height(sl);
796}
797
798APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
799{
800    return sl->preheight;
801}
802
803APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to)
804{
805    sl->preheight = (to > 0) ? to : 0;
806}
807
808static void skiplisti_destroy(void *vsl)
809{
810    apr_skiplist_destroy(vsl, NULL);
811}
812
813APR_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
827APR_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