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
28struct apr_skiplist {
29    apr_skiplist_compare compare;
30    apr_skiplist_compare comparek;
31    int height;
32    int preheight;
33    int size;
34    apr_skiplistnode *top;
35    apr_skiplistnode *bottom;
36    /* These two are needed for appending */
37    apr_skiplistnode *topend;
38    apr_skiplistnode *bottomend;
39    apr_skiplist *index;
40    apr_array_header_t *memlist;
41    apr_pool_t *pool;
42};
43
44struct apr_skiplistnode {
45    void *data;
46    apr_skiplistnode *next;
47    apr_skiplistnode *prev;
48    apr_skiplistnode *down;
49    apr_skiplistnode *up;
50    apr_skiplistnode *previndex;
51    apr_skiplistnode *nextindex;
52    apr_skiplist *sl;
53};
54
55#ifndef MIN
56#define MIN(a,b) ((a<b)?(a):(b))
57#endif
58
59static int get_b_rand(void)
60{
61    static int ph = 32;         /* More bits than we will ever use */
62    static apr_uint32_t randseq;
63    if (ph > 31) {              /* Num bits in return of rand() */
64        ph = 0;
65        randseq = (apr_uint32_t) rand();
66    }
67    ph++;
68    return ((randseq & (1 << (ph - 1))) >> (ph - 1));
69}
70
71typedef struct {
72    size_t size;
73    apr_array_header_t *list;
74} memlist_t;
75
76typedef struct {
77    void *ptr;
78    char inuse;
79} chunk_t;
80
81APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size)
82{
83    if (sl->pool) {
84        void *ptr;
85        int found_size = 0;
86        int i;
87        chunk_t *newchunk;
88        memlist_t *memlist = (memlist_t *)sl->memlist->elts;
89        for (i = 0; i < sl->memlist->nelts; i++) {
90            if (memlist->size == size) {
91                int j;
92                chunk_t *chunk = (chunk_t *)memlist->list->elts;
93                found_size = 1;
94                for (j = 0; j < memlist->list->nelts; j++) {
95                    if (!chunk->inuse) {
96                        chunk->inuse = 1;
97                        return chunk->ptr;
98                    }
99                    chunk++;
100                }
101                break; /* no free of this size; punt */
102            }
103            memlist++;
104        }
105        /* no free chunks */
106        ptr = apr_pcalloc(sl->pool, size);
107        if (!ptr) {
108            return ptr;
109        }
110        /*
111         * is this a new sized chunk? If so, we need to create a new
112         * array of them. Otherwise, re-use what we already have.
113         */
114        if (!found_size) {
115            memlist = apr_array_push(sl->memlist);
116            memlist->size = size;
117            memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t));
118        }
119        newchunk = apr_array_push(memlist->list);
120        newchunk->ptr = ptr;
121        newchunk->inuse = 1;
122        return ptr;
123    }
124    else {
125        return calloc(1, size);
126    }
127}
128
129APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem)
130{
131    if (!sl->pool) {
132        free(mem);
133    }
134    else {
135        int i;
136        memlist_t *memlist = (memlist_t *)sl->memlist->elts;
137        for (i = 0; i < sl->memlist->nelts; i++) {
138            int j;
139            chunk_t *chunk = (chunk_t *)memlist->list->elts;
140            for (j = 0; j < memlist->list->nelts; j++) {
141                if (chunk->ptr == mem) {
142                    chunk->inuse = 0;
143                    return;
144                }
145                chunk++;
146            }
147            memlist++;
148        }
149    }
150}
151
152static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
153{
154    apr_skiplist *sl;
155    if (p) {
156        sl = apr_pcalloc(p, sizeof(apr_skiplist));
157        sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
158    }
159    else {
160        sl = calloc(1, sizeof(apr_skiplist));
161    }
162#if 0
163    sl->compare = (apr_skiplist_compare) NULL;
164    sl->comparek = (apr_skiplist_compare) NULL;
165    sl->height = 0;
166    sl->preheight = 0;
167    sl->size = 0;
168    sl->top = NULL;
169    sl->bottom = NULL;
170    sl->index = NULL;
171#endif
172    sl->pool = p;
173    *s = sl;
174    return APR_SUCCESS;
175}
176
177static int indexing_comp(void *a, void *b)
178{
179    void *ac = (void *) (((apr_skiplist *) a)->compare);
180    void *bc = (void *) (((apr_skiplist *) b)->compare);
181    return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
182}
183
184static int indexing_compk(void *ac, void *b)
185{
186    void *bc = (void *) (((apr_skiplist *) b)->compare);
187    return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
188}
189
190APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
191{
192    apr_skiplist *sl;
193    skiplisti_init(s, p);
194    sl = *s;
195    skiplisti_init(&(sl->index), p);
196    apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
197    return APR_SUCCESS;
198}
199
200APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl,
201                          apr_skiplist_compare comp,
202                          apr_skiplist_compare compk)
203{
204    if (sl->compare && sl->comparek) {
205        apr_skiplist_add_index(sl, comp, compk);
206    }
207    else {
208        sl->compare = comp;
209        sl->comparek = compk;
210    }
211}
212
213APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl,
214                        apr_skiplist_compare comp,
215                        apr_skiplist_compare compk)
216{
217    apr_skiplistnode *m;
218    apr_skiplist *ni;
219    int icount = 0;
220    apr_skiplist_find(sl->index, (void *)comp, &m);
221    if (m) {
222        return;                 /* Index already there! */
223    }
224    skiplisti_init(&ni, sl->pool);
225    apr_skiplist_set_compare(ni, comp, compk);
226    /* Build the new index... This can be expensive! */
227    m = apr_skiplist_insert(sl->index, ni);
228    while (m->prev) {
229        m = m->prev;
230        icount++;
231    }
232    for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) {
233        int j = icount - 1;
234        apr_skiplistnode *nsln;
235        nsln = apr_skiplist_insert(ni, m->data);
236        /* skip from main index down list */
237        while (j > 0) {
238            m = m->nextindex;
239            j--;
240        }
241        /* insert this node in the indexlist after m */
242        nsln->nextindex = m->nextindex;
243        if (m->nextindex) {
244            m->nextindex->previndex = nsln;
245        }
246        nsln->previndex = m;
247        m->nextindex = nsln;
248    }
249}
250
251APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
252{
253    if (!sl->bottom) {
254        return NULL;
255    }
256    return sl->bottom->next;
257}
258
259APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
260{
261    void *ret;
262    apr_skiplistnode *aiter;
263    if (!sl->compare) {
264        return 0;
265    }
266    if (iter) {
267        ret = apr_skiplist_find_compare(sl, data, iter, sl->compare);
268    }
269    else {
270        ret = apr_skiplist_find_compare(sl, data, &aiter, sl->compare);
271    }
272    return ret;
273}
274
275static int skiplisti_find_compare(apr_skiplist *sl, void *data,
276                           apr_skiplistnode **ret,
277                           apr_skiplist_compare comp)
278{
279    apr_skiplistnode *m = NULL;
280    int count = 0;
281    m = sl->top;
282    while (m) {
283        int compared;
284        compared = (m->next) ? comp(data, m->next->data) : -1;
285        if (compared == 0) {
286            m = m->next;
287            while (m->down) {
288                m = m->down;
289            }
290            *ret = m;
291            return count;
292        }
293        if ((m->next == NULL) || (compared < 0)) {
294            m = m->down;
295            count++;
296        }
297        else {
298            m = m->next;
299            count++;
300        }
301    }
302    *ret = NULL;
303    return count;
304}
305
306APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
307                               apr_skiplistnode **iter,
308                               apr_skiplist_compare comp)
309{
310    apr_skiplistnode *m = NULL;
311    apr_skiplist *sl;
312    if (comp == sli->compare || !sli->index) {
313        sl = sli;
314    }
315    else {
316        apr_skiplist_find(sli->index, (void *)comp, &m);
317        sl = (apr_skiplist *) m->data;
318    }
319    skiplisti_find_compare(sl, data, iter, sl->comparek);
320    return (iter && *iter) ? ((*iter)->data) : NULL;
321}
322
323
324APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
325{
326    if (!*iter) {
327        return NULL;
328    }
329    *iter = (*iter)->next;
330    return (*iter) ? ((*iter)->data) : NULL;
331}
332
333APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
334{
335    if (!*iter) {
336        return NULL;
337    }
338    *iter = (*iter)->prev;
339    return (*iter) ? ((*iter)->data) : NULL;
340}
341
342APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
343{
344    if (!sl->compare) {
345        return 0;
346    }
347    return apr_skiplist_insert_compare(sl, data, sl->compare);
348}
349
350APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
351                                      apr_skiplist_compare comp)
352{
353    apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack;
354    int nh = 1, ch, stacki;
355    if (!sl->top) {
356        sl->height = 1;
357        sl->topend = sl->bottomend = sl->top = sl->bottom =
358            (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
359#if 0
360        sl->top->next = (apr_skiplistnode *)NULL;
361        sl->top->data = (apr_skiplistnode *)NULL;
362        sl->top->prev = (apr_skiplistnode *)NULL;
363        sl->top->up = (apr_skiplistnode *)NULL;
364        sl->top->down = (apr_skiplistnode *)NULL;
365        sl->top->nextindex = (apr_skiplistnode *)NULL;
366        sl->top->previndex = (apr_skiplistnode *)NULL;
367#endif
368        sl->top->sl = sl;
369    }
370    if (sl->preheight) {
371        while (nh < sl->preheight && get_b_rand()) {
372            nh++;
373        }
374    }
375    else {
376        while (nh <= sl->height && get_b_rand()) {
377            nh++;
378        }
379    }
380    /* Now we have the new height at which we wish to insert our new node */
381    /*
382     * Let us make sure that our tree is a least that tall (grow if
383     * necessary)
384     */
385    for (; sl->height < nh; sl->height++) {
386        sl->top->up =
387            (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
388        sl->top->up->down = sl->top;
389        sl->top = sl->topend = sl->top->up;
390#if 0
391        sl->top->prev = sl->top->next = sl->top->nextindex =
392            sl->top->previndex = sl->top->up = NULL;
393        sl->top->data = NULL;
394#endif
395        sl->top->sl = sl;
396    }
397    ch = sl->height;
398    /* Find the node (or node after which we would insert) */
399    /* Keep a stack to pop back through for insertion */
400    /* malloc() is OK since we free the temp stack */
401    m = sl->top;
402    stack = (apr_skiplistnode **)malloc(sizeof(apr_skiplistnode *) * (nh));
403    stacki = 0;
404    while (m) {
405        int compared = -1;
406        if (m->next) {
407            compared = comp(data, m->next->data);
408        }
409        if (compared == 0) {
410            free(stack);    /* OK. was malloc'ed */
411            return 0;
412        }
413        if ((m->next == NULL) || (compared < 0)) {
414            if (ch <= nh) {
415                /* push on stack */
416                stack[stacki++] = m;
417            }
418            m = m->down;
419            ch--;
420        }
421        else {
422            m = m->next;
423        }
424    }
425    /* Pop the stack and insert nodes */
426    p = NULL;
427    for (; stacki > 0; stacki--) {
428        m = stack[stacki - 1];
429        tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
430        tmp->next = m->next;
431        if (m->next) {
432            m->next->prev = tmp;
433        }
434        tmp->prev = m;
435        tmp->up = NULL;
436        tmp->nextindex = tmp->previndex = NULL;
437        tmp->down = p;
438        if (p) {
439            p->up = tmp;
440        }
441        tmp->data = data;
442        tmp->sl = sl;
443        m->next = tmp;
444        /* This sets ret to the bottom-most node we are inserting */
445        if (!p) {
446            ret = tmp;
447            sl->size++; /* this seems to go here got each element to be counted */
448        }
449        p = tmp;
450    }
451    free(stack); /* OK. was malloc'ed */
452    if (sl->index != NULL) {
453        /*
454         * this is a external insertion, we must insert into each index as
455         * well
456         */
457        apr_skiplistnode *ni, *li;
458        li = ret;
459        for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
460            ni = apr_skiplist_insert((apr_skiplist *) p->data, ret->data);
461            li->nextindex = ni;
462            ni->previndex = li;
463            li = ni;
464        }
465    }
466    else {
467        /* sl->size++; */
468    }
469    sl->size++;
470    return ret;
471}
472
473APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
474{
475    if (!sl->compare) {
476        return 0;
477    }
478    return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
479}
480
481#if 0
482void skiplist_print_struct(apr_skiplist * sl, char *prefix)
483{
484    apr_skiplistnode *p, *q;
485    fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
486    p = sl->bottom;
487    while (p) {
488        q = p;
489        fprintf(stderr, prefix);
490        while (q) {
491            fprintf(stderr, "%p ", q->data);
492            q = q->up;
493        }
494        fprintf(stderr, "\n");
495        p = p->next;
496    }
497}
498#endif
499
500static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree)
501{
502    apr_skiplistnode *p;
503    if (!m) {
504        return 0;
505    }
506    if (m->nextindex) {
507        skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
508    }
509    while (m->up) {
510        m = m->up;
511    }
512    while (m) {
513        p = m;
514        p->prev->next = p->next;/* take me out of the list */
515        if (p->next) {
516            p->next->prev = p->prev;    /* take me out of the list */
517        }
518        m = m->down;
519        /* This only frees the actual data in the bottom one */
520        if (!m && myfree && p->data) {
521            myfree(p->data);
522        }
523        apr_skiplist_free(sl, p);
524    }
525    sl->size--;
526    while (sl->top && sl->top->next == NULL) {
527        /* While the row is empty and we are not on the bottom row */
528        p = sl->top;
529        sl->top = sl->top->down;/* Move top down one */
530        if (sl->top) {
531            sl->top->up = NULL; /* Make it think its the top */
532        }
533        apr_skiplist_free(sl, p);
534        sl->height--;
535    }
536    if (!sl->top) {
537        sl->bottom = NULL;
538    }
539    return sl->height;  /* return 1; ?? */
540}
541
542APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
543                            void *data,
544                            apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
545{
546    apr_skiplistnode *m;
547    apr_skiplist *sl;
548    if (comp == sli->comparek || !sli->index) {
549        sl = sli;
550    }
551    else {
552        apr_skiplist_find(sli->index, (void *)comp, &m);
553        sl = (apr_skiplist *) m->data;
554    }
555    skiplisti_find_compare(sl, data, &m, comp);
556    if (!m) {
557        return 0;
558    }
559    while (m->previndex) {
560        m = m->previndex;
561    }
562    return skiplisti_remove(sl, m, myfree);
563}
564
565APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
566{
567    /*
568     * This must remove even the place holder nodes (bottom though top)
569     * because we specify in the API that one can free the Skiplist after
570     * making this call without memory leaks
571     */
572    apr_skiplistnode *m, *p, *u;
573    m = sl->bottom;
574    while (m) {
575        p = m->next;
576        if (p && myfree && p->data)
577            myfree(p->data);
578        while (m) {
579            u = m->up;
580            apr_skiplist_free(sl, p);
581            m = u;
582        }
583        m = p;
584    }
585    sl->top = sl->bottom = NULL;
586    sl->height = 0;
587    sl->size = 0;
588}
589
590APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
591{
592    apr_skiplistnode *sln;
593    void *data = NULL;
594    sln = apr_skiplist_getlist(a);
595    if (sln) {
596        data = sln->data;
597        skiplisti_remove(a, sln, myfree);
598    }
599    return data;
600}
601
602APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
603{
604    apr_skiplistnode *sln;
605    sln = apr_skiplist_getlist(a);
606    if (sln) {
607        return sln->data;
608    }
609    return NULL;
610}
611
612static void skiplisti_destroy(void *vsl)
613{
614    apr_skiplist_destroy((apr_skiplist *) vsl, NULL);
615    apr_skiplist_free((apr_skiplist *) vsl, vsl);
616}
617
618APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
619{
620    while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
621        ;
622    apr_skiplist_remove_all(sl, myfree);
623}
624
625APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
626{
627    /* Check integrity! */
628    apr_skiplist temp;
629    struct apr_skiplistnode *b2;
630    if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
631        apr_skiplist_remove_all(sl1, NULL);
632        temp = *sl1;
633        *sl1 = *sl2;
634        *sl2 = temp;
635        /* swap them so that sl2 can be freed normally upon return. */
636        return sl1;
637    }
638    if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
639        apr_skiplist_remove_all(sl2, NULL);
640        return sl1;
641    }
642    /* This is what makes it brute force... Just insert :/ */
643    b2 = apr_skiplist_getlist(sl2);
644    while (b2) {
645        apr_skiplist_insert(sl1, b2->data);
646        apr_skiplist_next(sl2, &b2);
647    }
648    apr_skiplist_remove_all(sl2, NULL);
649    return sl1;
650}
651