xref: /freebsd-10-stable/contrib/apr/tables/apr_skiplist.c

/* Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

/*
 * Modified to use APR and APR pools.
 *  TODO: Is malloc() better? Will long running skiplists grow too much?
 *  Keep the skiplist_alloc() and skiplist_free() until we know
 *  Yeah, if using pools it means some bogus cycles for checks
 *  (and an useless function call for skiplist_free) which we
 *  can removed if/when needed.
 */

#include "apr_skiplist.h"

typedef struct {
    apr_skiplistnode **data;
    size_t size, pos;
    apr_pool_t *p;
} apr_skiplist_q;

struct apr_skiplist {
    apr_skiplist_compare compare;
    apr_skiplist_compare comparek;
    int height;
    int preheight;
    size_t size;
    apr_skiplistnode *top;
    apr_skiplistnode *bottom;
    /* These two are needed for appending */
    apr_skiplistnode *topend;
    apr_skiplistnode *bottomend;
    apr_skiplist *index;
    apr_array_header_t *memlist;
    apr_skiplist_q nodes_q,
                   stack_q;
    apr_pool_t *pool;
};

struct apr_skiplistnode {
    void *data;
    apr_skiplistnode *next;
    apr_skiplistnode *prev;
    apr_skiplistnode *down;
    apr_skiplistnode *up;
    apr_skiplistnode *previndex;
    apr_skiplistnode *nextindex;
    apr_skiplist *sl;
};

static int get_b_rand(void)
{
    static int ph = 32;         /* More bits than we will ever use */
    static int randseq;
    if (ph > 31) {              /* Num bits in return of rand() */
        ph = 0;
        randseq = rand();
    }
    return randseq & (1 << ph++);
}

typedef struct {
    size_t size;
    apr_array_header_t *list;
} memlist_t;

typedef struct {
    void *ptr;
    char inuse;
} chunk_t;

APR_DECLARE(void *) apr_skiplist_alloc(apr_skiplist *sl, size_t size)
{
    if (sl->pool) {
        void *ptr;
        int found_size = 0;
        int i;
        chunk_t *newchunk;
        memlist_t *memlist = (memlist_t *)sl->memlist->elts;
        for (i = 0; i < sl->memlist->nelts; i++) {
            if (memlist->size == size) {
                int j;
                chunk_t *chunk = (chunk_t *)memlist->list->elts;
                found_size = 1;
                for (j = 0; j < memlist->list->nelts; j++) {
                    if (!chunk->inuse) {
                        chunk->inuse = 1;
                        return chunk->ptr;
                    }
                    chunk++;
                }
                break; /* no free of this size; punt */
            }
            memlist++;
        }
        /* no free chunks */
        ptr = apr_palloc(sl->pool, size);
        if (!ptr) {
            return ptr;
        }
        /*
         * is this a new sized chunk? If so, we need to create a new
         * array of them. Otherwise, re-use what we already have.
         */
        if (!found_size) {
            memlist = apr_array_push(sl->memlist);
            memlist->size = size;
            memlist->list = apr_array_make(sl->pool, 20, sizeof(chunk_t));
        }
        newchunk = apr_array_push(memlist->list);
        newchunk->ptr = ptr;
        newchunk->inuse = 1;
        return ptr;
    }
    else {
        return malloc(size);
    }
}

APR_DECLARE(void) apr_skiplist_free(apr_skiplist *sl, void *mem)
{
    if (!sl->pool) {
        free(mem);
    }
    else {
        int i;
        memlist_t *memlist = (memlist_t *)sl->memlist->elts;
        for (i = 0; i < sl->memlist->nelts; i++) {
            int j;
            chunk_t *chunk = (chunk_t *)memlist->list->elts;
            for (j = 0; j < memlist->list->nelts; j++) {
                if (chunk->ptr == mem) {
                    chunk->inuse = 0;
                    return;
                }
                chunk++;
            }
            memlist++;
        }
    }
}

static apr_status_t skiplist_qpush(apr_skiplist_q *q, apr_skiplistnode *m)
{
    if (q->pos >= q->size) {
        apr_skiplistnode **data;
        size_t size = (q->pos) ? q->pos * 2 : 32;
        if (q->p) {
            data = apr_palloc(q->p, size * sizeof(*data));
            if (data) {
                memcpy(data, q->data, q->pos * sizeof(*data));
            }
        }
        else {
            data = realloc(q->data, size * sizeof(*data));
        }
        if (!data) {
            return APR_ENOMEM;
        }
        q->data = data;
        q->size = size;
    }
    q->data[q->pos++] = m;
    return APR_SUCCESS;
}

static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
{
    return (q->pos > 0) ? q->data[--q->pos] : NULL;
}

static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
{
    q->pos = 0;
}

static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl)
{
    apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q);
    if (!m) {
        if (sl->pool) {
            m = apr_palloc(sl->pool, sizeof *m);
        }
        else {
            m = malloc(sizeof *m);
        }
    }
    return m;
}

static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m)
{
    return skiplist_qpush(&sl->nodes_q, m);
}

static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
{
    apr_skiplist *sl;
    if (p) {
        sl = apr_pcalloc(p, sizeof(apr_skiplist));
        sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
        sl->pool = sl->nodes_q.p = sl->stack_q.p = p;
    }
    else {
        sl = calloc(1, sizeof(apr_skiplist));
        if (!sl) {
            return APR_ENOMEM;
        }
    }
    *s = sl;
    return APR_SUCCESS;
}

static int indexing_comp(void *a, void *b)
{
    void *ac = (void *) (((apr_skiplist *) a)->compare);
    void *bc = (void *) (((apr_skiplist *) b)->compare);
    return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
}

static int indexing_compk(void *ac, void *b)
{
    void *bc = (void *) (((apr_skiplist *) b)->compare);
    return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0));
}

APR_DECLARE(apr_status_t) apr_skiplist_init(apr_skiplist **s, apr_pool_t *p)
{
    apr_skiplist *sl;
    skiplisti_init(s, p);
    sl = *s;
    skiplisti_init(&(sl->index), p);
    apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
    return APR_SUCCESS;
}

APR_DECLARE(void) apr_skiplist_set_compare(apr_skiplist *sl,
                          apr_skiplist_compare comp,
                          apr_skiplist_compare compk)
{
    if (sl->compare && sl->comparek) {
        apr_skiplist_add_index(sl, comp, compk);
    }
    else {
        sl->compare = comp;
        sl->comparek = compk;
    }
}

APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl,
                        apr_skiplist_compare comp,
                        apr_skiplist_compare compk)
{
    apr_skiplistnode *m;
    apr_skiplist *ni;
    int icount = 0;
    apr_skiplist_find(sl->index, (void *)comp, &m);
    if (m) {
        return;                 /* Index already there! */
    }
    skiplisti_init(&ni, sl->pool);
    apr_skiplist_set_compare(ni, comp, compk);
    /* Build the new index... This can be expensive! */
    m = apr_skiplist_insert(sl->index, ni);
    while (m->prev) {
        m = m->prev;
        icount++;
    }
    for (m = apr_skiplist_getlist(sl); m; apr_skiplist_next(sl, &m)) {
        int j = icount - 1;
        apr_skiplistnode *nsln;
        nsln = apr_skiplist_insert(ni, m->data);
        /* skip from main index down list */
        while (j > 0) {
            m = m->nextindex;
            j--;
        }
        /* insert this node in the indexlist after m */
        nsln->nextindex = m->nextindex;
        if (m->nextindex) {
            m->nextindex->previndex = nsln;
        }
        nsln->previndex = m;
        m->nextindex = nsln;
    }
}

static int skiplisti_find_compare(apr_skiplist *sl, void *data,
                           apr_skiplistnode **ret,
                           apr_skiplist_compare comp)
{
    int count = 0;
    apr_skiplistnode *m;
    m = sl->top;
    while (m) {
        if (m->next) {
            int compared = comp(data, m->next->data);
            if (compared == 0) {
                m = m->next;
                while (m->down) {
                    m = m->down;
                }
                *ret = m;
                return count;
            }
            if (compared > 0) {
                m = m->next;
                count++;
                continue;
            }
        }
        m = m->down;
        count++;
    }
    *ret = NULL;
    return count;
}

APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
                               apr_skiplistnode **iter,
                               apr_skiplist_compare comp)
{
    apr_skiplistnode *m;
    apr_skiplist *sl;
    if (!comp) {
        if (iter) {
            *iter = NULL;
        }
        return NULL;
    }
    if (comp == sli->compare || !sli->index) {
        sl = sli;
    }
    else {
        apr_skiplist_find(sli->index, (void *)comp, &m);
        if (!m) {
            if (iter) {
                *iter = NULL;
            }
            return NULL;
        }
        sl = (apr_skiplist *) m->data;
    }
    skiplisti_find_compare(sl, data, &m, sl->comparek);
    if (iter) {
        *iter = m;
    }
    return (m) ? m->data : NULL;
}

APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
{
    return apr_skiplist_find_compare(sl, data, iter, sl->compare);
}


APR_DECLARE(apr_skiplistnode *) apr_skiplist_getlist(apr_skiplist *sl)
{
    if (!sl->bottom) {
        return NULL;
    }
    return sl->bottom->next;
}

APR_DECLARE(void *) apr_skiplist_next(apr_skiplist *sl, apr_skiplistnode **iter)
{
    if (!*iter) {
        return NULL;
    }
    *iter = (*iter)->next;
    return (*iter) ? ((*iter)->data) : NULL;
}

APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter)
{
    if (!*iter) {
        return NULL;
    }
    *iter = (*iter)->prev;
    return (*iter) ? ((*iter)->data) : NULL;
}

static APR_INLINE int skiplist_height(const apr_skiplist *sl)
{
    /* Skiplists (even empty) always have a top node, although this
     * implementation defers its creation until the first insert, or
     * deletes it with the last remove. We want the real height here.
     */
    return sl->height ? sl->height : 1;
}

APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
                                      apr_skiplist_compare comp)
{
    apr_skiplistnode *m, *p, *tmp, *ret = NULL;
    int ch, nh = 1;

    if (!comp) {
        return NULL;
    }

    ch = skiplist_height(sl);
    if (sl->preheight) {
        while (nh < sl->preheight && get_b_rand()) {
            nh++;
        }
    }
    else {
        while (nh <= ch && get_b_rand()) {
            nh++;
        }
    }

    /* Now we have in nh the height at which we wish to insert our new node,
     * and in ch the current height: don't create skip paths to the inserted
     * element until the walk down through the tree (which decrements ch)
     * reaches nh. From there, any walk down pushes the current node on a
     * stack (the node(s) after which we would insert) to pop back through
     * for insertion later.
     */
    m = sl->top;
    while (m) {
        if (m->next) {
            int compared = comp(data, m->next->data);
            if (compared == 0) {
                /* Keep the existing element(s) */
                skiplist_qclear(&sl->stack_q);
                return NULL;
            }
            if (compared > 0) {
                m = m->next;
                continue;
            }
        }
        if (ch <= nh) {
            /* push on stack */
            skiplist_qpush(&sl->stack_q, m);
        }
        m = m->down;
        ch--;
    }
    /* Pop the stack and insert nodes */
    p = NULL;
    while ((m = skiplist_qpop(&sl->stack_q))) {
        tmp = skiplist_new_node(sl);
        tmp->next = m->next;
        if (m->next) {
            m->next->prev = tmp;
        }
        m->next = tmp;
        tmp->prev = m;
        tmp->up = NULL;
        tmp->nextindex = tmp->previndex = NULL;
        tmp->down = p;
        if (p) {
            p->up = tmp;
        }
        else {
            /* This sets ret to the bottom-most node we are inserting */
            ret = tmp;
        }
        tmp->data = data;
        tmp->sl = sl;
        p = tmp;
    }

    /* Now we are sure the node is inserted, grow our tree to 'nh' tall */
    for (; sl->height < nh; sl->height++) {
        m = skiplist_new_node(sl);
        tmp = skiplist_new_node(sl);
        m->up = m->prev = m->nextindex = m->previndex = NULL;
        m->next = tmp;
        m->down = sl->top;
        m->data = NULL;
        m->sl = sl;
        if (sl->top) {
            sl->top->up = m;
        }
        else {
            sl->bottom = sl->bottomend = m;
        }
        sl->top = sl->topend = tmp->prev = m;
        tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
        tmp->down = p;
        tmp->data = data;
        tmp->sl = sl;
        if (p) {
            p->up = tmp;
        }
        else {
            /* This sets ret to the bottom-most node we are inserting */
            ret = tmp;
        }
        p = tmp;
    }
    if (sl->index != NULL) {
        /*
         * this is a external insertion, we must insert into each index as
         * well
         */
        apr_skiplistnode *ni, *li;
        li = ret;
        for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
            apr_skiplist *sli = (apr_skiplist *)p->data;
            ni = apr_skiplist_insert_compare(sli, ret->data, sli->compare);
            li->nextindex = ni;
            ni->previndex = li;
            li = ni;
        }
    }
    sl->size++;
    return ret;
}

APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
{
    return apr_skiplist_insert_compare(sl, data, sl->compare);
}

#if 0
void skiplist_print_struct(apr_skiplist * sl, char *prefix)
{
    apr_skiplistnode *p, *q;
    fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
    p = sl->bottom;
    while (p) {
        q = p;
        fprintf(stderr, prefix);
        while (q) {
            fprintf(stderr, "%p ", q->data);
            q = q->up;
        }
        fprintf(stderr, "\n");
        p = p->next;
    }
}
#endif

static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree)
{
    apr_skiplistnode *p;
    if (!m) {
        return 0;
    }
    if (m->nextindex) {
        skiplisti_remove(m->nextindex->sl, m->nextindex, NULL);
    }
    while (m->up) {
        m = m->up;
    }
    while (m) {
        p = m;
        p->prev->next = p->next;/* take me out of the list */
        if (p->next) {
            p->next->prev = p->prev;    /* take me out of the list */
        }
        m = m->down;
        /* This only frees the actual data in the bottom one */
        if (!m && myfree && p->data) {
            myfree(p->data);
        }
        skiplist_free_node(sl, p);
    }
    sl->size--;
    while (sl->top && sl->top->next == NULL) {
        /* While the row is empty and we are not on the bottom row */
        p = sl->top;
        sl->top = sl->top->down;/* Move top down one */
        if (sl->top) {
            sl->top->up = NULL; /* Make it think its the top */
        }
        skiplist_free_node(sl, p);
        sl->height--;
    }
    if (!sl->top) {
        sl->bottom = sl->bottomend = NULL;
        sl->topend = NULL;
    }
    return skiplist_height(sl);
}

APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
                            void *data,
                            apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
{
    apr_skiplistnode *m;
    apr_skiplist *sl;
    if (!comp) {
        return 0;
    }
    if (comp == sli->comparek || !sli->index) {
        sl = sli;
    }
    else {
        apr_skiplist_find(sli->index, (void *)comp, &m);
        if (!m) {
            return 0;
        }
        sl = (apr_skiplist *) m->data;
    }
    skiplisti_find_compare(sl, data, &m, comp);
    if (!m) {
        return 0;
    }
    while (m->previndex) {
        m = m->previndex;
    }
    return skiplisti_remove(sl, m, myfree);
}

APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
{
    return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
}

APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
{
    /*
     * This must remove even the place holder nodes (bottom though top)
     * because we specify in the API that one can free the Skiplist after
     * making this call without memory leaks
     */
    apr_skiplistnode *m, *p, *u;
    m = sl->bottom;
    while (m) {
        p = m->next;
        if (myfree && p && p->data) {
            myfree(p->data);
        }
        do {
            u = m->up;
            skiplist_free_node(sl, m);
            m = u;
        } while (m);
        m = p;
    }
    sl->top = sl->bottom = NULL;
    sl->topend = sl->bottomend = NULL;
    sl->height = 0;
    sl->size = 0;
}

APR_DECLARE(void *) apr_skiplist_pop(apr_skiplist *a, apr_skiplist_freefunc myfree)
{
    apr_skiplistnode *sln;
    void *data = NULL;
    sln = apr_skiplist_getlist(a);
    if (sln) {
        data = sln->data;
        skiplisti_remove(a, sln, myfree);
    }
    return data;
}

APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *a)
{
    apr_skiplistnode *sln;
    sln = apr_skiplist_getlist(a);
    if (sln) {
        return sln->data;
    }
    return NULL;
}

static void skiplisti_destroy(void *vsl)
{
    apr_skiplist_destroy(vsl, NULL);
}

APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
{
    while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
        ;
    apr_skiplist_remove_all(sl, myfree);
    if (!sl->pool) {
        while (sl->nodes_q.pos)
            free(sl->nodes_q.data[--sl->nodes_q.pos]);
        free(sl->nodes_q.data);
        free(sl->stack_q.data);
        free(sl);
    }
}

APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
{
    /* Check integrity! */
    apr_skiplist temp;
    struct apr_skiplistnode *b2;
    if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
        apr_skiplist_remove_all(sl1, NULL);
        temp = *sl1;
        *sl1 = *sl2;
        *sl2 = temp;
        /* swap them so that sl2 can be freed normally upon return. */
        return sl1;
    }
    if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
        apr_skiplist_remove_all(sl2, NULL);
        return sl1;
    }
    /* This is what makes it brute force... Just insert :/ */
    b2 = apr_skiplist_getlist(sl2);
    while (b2) {
        apr_skiplist_insert(sl1, b2->data);
        apr_skiplist_next(sl2, &b2);
    }
    apr_skiplist_remove_all(sl2, NULL);
    return sl1;
}