diff options
Diffstat (limited to 'tables/apr_skiplist.c')
| -rw-r--r-- | tables/apr_skiplist.c | 864 |
1 files changed, 864 insertions, 0 deletions
diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c new file mode 100644 index 0000000..8013ed7 --- /dev/null +++ b/tables/apr_skiplist.c @@ -0,0 +1,864 @@ +/* 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 unsigned int get_b_rand(void) +{ + static unsigned int ph = 32; /* More bits than we will ever use */ + static unsigned int randseq; + if (ph > 31) { /* Num bits in return of rand() */ + ph = 0; + randseq = rand(); + } + return randseq & (1U << 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 && q->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_put_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_status_t rv; + apr_skiplist *sl; + rv = skiplisti_init(&sl, p); + if (rv != APR_SUCCESS) { + *s = NULL; + return rv; + } + rv = skiplisti_init(&sl->index, p); + if (rv != APR_SUCCESS) { + *s = NULL; + return rv; + } + apr_skiplist_set_compare(sl->index, indexing_comp, indexing_compk); + *s = sl; + 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! */ + } + if (skiplisti_init(&ni, sl->pool) != APR_SUCCESS) { + abort(); + return; + } + 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 last) +{ + int count = 0; + apr_skiplistnode *m, *found = NULL; + for (m = sl->top; m; count++) { + if (m->next) { + int compared = comp(data, m->next->data); + if (compared == 0) { + found = m = m->next; + if (!last) { + break; + } + continue; + } + if (compared > 0) { + m = m->next; + continue; + } + } + m = m->down; + } + if (found) { + while (found->down) { + found = found->down; + } + *ret = found; + } + else { + *ret = NULL; + } + return count; +} + +static void *find_compare(apr_skiplist *sli, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp, + int last) +{ + 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, last); + if (iter) { + *iter = m; + } + return (m) ? m->data : NULL; +} + +APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp) +{ + return find_compare(sl, data, iter, comp, 0); +} + +APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter) +{ + return find_compare(sl, data, iter, sl->compare, 0); +} + +APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp) +{ + return find_compare(sl, data, iter, comp, 1); +} + +APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data, + apr_skiplistnode **iter) +{ + return find_compare(sl, data, iter, sl->compare, 1); +} + + +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; +} + +APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter) +{ + return (iter) ? iter->data : NULL; +} + +/* forward declared */ +static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, + apr_skiplist_freefunc myfree); + +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; +} + +static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data, + apr_skiplist_compare comp, int add, + apr_skiplist_freefunc myfree) +{ + apr_skiplistnode *m, *p, *tmp, *ret = NULL; + int ch, top_nh, nh = 1; + + ch = skiplist_height(sl); + if (sl->preheight) { + while (nh < sl->preheight && get_b_rand()) { + nh++; + } + } + else { + while (nh <= ch && get_b_rand()) { + nh++; + } + } + top_nh = 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) { + /* + * To maintain stability, dups (compared == 0) must be added + * AFTER each other. + */ + if (m->next) { + int compared = comp(data, m->next->data); + if (compared == 0) { + if (!add) { + /* Keep the existing element(s) */ + skiplist_qclear(&sl->stack_q); + return NULL; + } + if (add < 0) { + /* Remove this element and continue with the next node + * or the new top if the current one is also removed. + */ + apr_skiplistnode *top = sl->top; + skiplisti_remove(sl, m->next, myfree); + if (top != sl->top) { + m = sl->top; + skiplist_qclear(&sl->stack_q); + ch = skiplist_height(sl); + nh = top_nh; + } + continue; + } + } + 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 = insert_compare(sli, ret->data, sli->compare, 1, NULL); + li->nextindex = ni; + ni->previndex = li; + li = ni; + } + } + sl->size++; + return ret; +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data, + apr_skiplist_compare comp) +{ + if (!comp) { + return NULL; + } + return insert_compare(sl, data, comp, 0, NULL); +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data) +{ + return apr_skiplist_insert_compare(sl, data, sl->compare); +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void *data, + apr_skiplist_compare comp) +{ + if (!comp) { + return NULL; + } + return insert_compare(sl, data, comp, 1, NULL); +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data) +{ + return apr_skiplist_add_compare(sl, data, sl->compare); +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl, + void *data, apr_skiplist_freefunc myfree, + apr_skiplist_compare comp) +{ + if (!comp) { + return NULL; + } + return insert_compare(sl, data, comp, -1, myfree); +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl, + void *data, apr_skiplist_freefunc myfree) +{ + return apr_skiplist_replace_compare(sl, data, myfree, 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; + } + do { + p = m; + /* take me out of the list */ + p->prev->next = p->next; + if (p->next) { + p->next->prev = p->prev; + } + m = m->down; + /* This only frees the actual data in the bottom one */ + if (!m && myfree && p->data) { + myfree(p->data); + } + skiplist_put_node(sl, p); + } while (m); + 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_put_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_node(apr_skiplist *sl, + apr_skiplistnode *iter, + apr_skiplist_freefunc myfree) +{ + apr_skiplistnode *m = iter; + if (!m) { + return 0; + } + while (m->down) { + m = m->down; + } + while (m->previndex) { + m = m->previndex; + } + return skiplisti_remove(sl, m, myfree); +} + +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, 0); + 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_put_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; +} + +APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl) +{ + return sl->size; +} + +APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl) +{ + return skiplist_height(sl); +} + +APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl) +{ + return sl->preheight; +} + +APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to) +{ + sl->preheight = (to > 0) ? to : 0; +} + +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; +} |