From 898365fd1d0dbde88531f5ea0ab1c7a88c7bf178 Mon Sep 17 00:00:00 2001 From: Jim Jagielski Date: Wed, 2 Oct 2013 12:12:36 +0000 Subject: [PATCH] skiplist is now in apr 1.5 and above git-svn-id: https://svn.apache.org/repos/asf/httpd/httpd/trunk@1528437 13f79535-47bb-0310-9956-ffa450edef68 --- LICENSE | 19 - include/ap_skiplist.h | 82 ---- server/Makefile.in | 2 +- server/mpm/event/event.c | 22 +- server/mpm/eventopt/eventopt.c | 20 +- server/skiplist.c | 659 --------------------------------- 6 files changed, 22 insertions(+), 782 deletions(-) delete mode 100644 include/ap_skiplist.h delete mode 100644 server/skiplist.c diff --git a/LICENSE b/LICENSE index 1c38a63504..cfe471617e 100644 --- a/LICENSE +++ b/LICENSE @@ -544,24 +544,5 @@ CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. -for the server/skiplist.c component: - -/* ====================================================================== - * Copyright (c) 2000,2006 Theo Schlossnagle - * All rights reserved. - * The following code was written by Theo Schlossnagle for use in the - * Backhand project at The Center for Networking and Distributed Systems - * at The Johns Hopkins University. - * - * This is a skiplist implementation to be used for abstract structures - * and is release under the LGPL license version 2.1 or later. A copy - * of this license can be found file LGPL. - * - * Alternatively, this file may be licensed under the new BSD license. - * A copy of this license can be found file BSD. - * - * ====================================================================== - */ - ==================================================================== diff --git a/include/ap_skiplist.h b/include/ap_skiplist.h deleted file mode 100644 index 18d1bdac59..0000000000 --- a/include/ap_skiplist.h +++ /dev/null @@ -1,82 +0,0 @@ -/* 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. - */ - -#ifndef _AP_SKIPLIST_P_H -#define _AP_SKIPLIST_P_H - -#include "apr.h" -#include "apr_portable.h" -#include "ap_config.h" -#include "httpd.h" - -/* This is the function type that must be implemented per object type - that is used in a skiplist for comparisons to maintain order */ -typedef int (*ap_skiplist_compare) (void *, void *); -typedef void (*ap_skiplist_freefunc) (void *); - -struct ap_skiplist; -struct ap_skiplistnode; - -typedef struct ap_skiplistnode ap_skiplistnode; -typedef struct ap_skiplist ap_skiplist; - -AP_DECLARE(void *) ap_skiplist_alloc(ap_skiplist *sl, size_t size); - -AP_DECLARE(void) ap_skiplist_free(ap_skiplist *sl, void *mem); - -AP_DECLARE(apr_status_t) ap_skiplist_init(ap_skiplist **sl, apr_pool_t *p); - -AP_DECLARE(void) ap_skiplist_set_compare(ap_skiplist *sl, ap_skiplist_compare, - ap_skiplist_compare); - -AP_DECLARE(void) ap_skiplist_add_index(ap_skiplist *sl, ap_skiplist_compare, - ap_skiplist_compare); - -AP_DECLARE(ap_skiplistnode *) ap_skiplist_getlist(ap_skiplist *sl); - -AP_DECLARE(void *) ap_skiplist_find_compare(ap_skiplist *sl, - void *data, - ap_skiplistnode **iter, - ap_skiplist_compare func); - -AP_DECLARE(void *) ap_skiplist_find(ap_skiplist *sl, void *data, ap_skiplistnode **iter); - -AP_DECLARE(void *) ap_skiplist_next(ap_skiplist *sl, ap_skiplistnode **iter); - -AP_DECLARE(void *) ap_skiplist_previous(ap_skiplist *sl, ap_skiplistnode **iter); - - -AP_DECLARE(ap_skiplistnode *) ap_skiplist_insert_compare(ap_skiplist *sl, - void *data, ap_skiplist_compare comp); - -AP_DECLARE(ap_skiplistnode *) ap_skiplist_insert(ap_skiplist* sl, void *data); - -AP_DECLARE(int) ap_skiplist_remove_compare(ap_skiplist *sl, void *data, - ap_skiplist_freefunc myfree, ap_skiplist_compare comp); - -AP_DECLARE(int) ap_skiplist_remove(ap_skiplist *sl, void *data, ap_skiplist_freefunc myfree); - -AP_DECLARE(void) ap_skiplist_remove_all(ap_skiplist *sl, ap_skiplist_freefunc myfree); - -AP_DECLARE(void) ap_skiplist_destroy(ap_skiplist *sl, ap_skiplist_freefunc myfree); - -AP_DECLARE(void *) ap_skiplist_pop(ap_skiplist *a, ap_skiplist_freefunc myfree); - -AP_DECLARE(void *) ap_skiplist_peek(ap_skiplist *a); - -AP_DECLARE(ap_skiplist *) ap_skiplist_merge(ap_skiplist *sl1, ap_skiplist *sl2); - -#endif diff --git a/server/Makefile.in b/server/Makefile.in index 69e5fe09ed..57422e9f6f 100644 --- a/server/Makefile.in +++ b/server/Makefile.in @@ -18,7 +18,7 @@ LTLIBRARY_SOURCES = \ apreq_cookie.c apreq_error.c apreq_module.c \ apreq_module_cgi.c apreq_module_custom.c apreq_param.c \ apreq_parser.c apreq_parser_header.c apreq_parser_multipart.c \ - apreq_parser_urlencoded.c apreq_util.c skiplist.c + apreq_parser_urlencoded.c apreq_util.c LTLIBRARY_DEPENDENCIES = test_char.h diff --git a/server/mpm/event/event.c b/server/mpm/event/event.c index 595425164a..07fa55411e 100644 --- a/server/mpm/event/event.c +++ b/server/mpm/event/event.c @@ -91,7 +91,7 @@ #include "mpm_default.h" #include "http_vhost.h" #include "unixd.h" -#include "ap_skiplist.h" +#include "apr_skiplist.h" #include #include /* for INT_MAX */ @@ -1299,7 +1299,7 @@ static void get_worker(int *have_idle_worker_p, int blocking, int *all_busy) /* Structures to reuse */ static APR_RING_HEAD(timer_free_ring_t, timer_event_t) timer_free_ring; -static ap_skiplist *timer_skiplist; +static apr_skiplist *timer_skiplist; static int indexing_comp(void *a, void *b) { @@ -1333,7 +1333,7 @@ static apr_status_t event_register_timed_callback(apr_time_t t, APR_RING_REMOVE(te, link); } else { - te = ap_skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); + te = apr_skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); APR_RING_ELEM_INIT(te, link); } @@ -1343,7 +1343,7 @@ static apr_status_t event_register_timed_callback(apr_time_t t, te->when = t + apr_time_now(); /* Okay, insert sorted by when.. */ - ap_skiplist_insert(timer_skiplist, (void *)te); + apr_skiplist_insert(timer_skiplist, (void *)te); apr_thread_mutex_unlock(g_timer_skiplist_mtx); @@ -1578,7 +1578,7 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) } apr_thread_mutex_lock(g_timer_skiplist_mtx); - te = ap_skiplist_peek(timer_skiplist); + te = apr_skiplist_peek(timer_skiplist); if (te) { if (te->when > now) { timeout_interval = te->when - now; @@ -1620,16 +1620,16 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) now = apr_time_now(); apr_thread_mutex_lock(g_timer_skiplist_mtx); - ep = ap_skiplist_peek(timer_skiplist); + ep = apr_skiplist_peek(timer_skiplist); while (ep) { if (ep->when < now + EVENT_FUDGE_FACTOR) { - ap_skiplist_pop(timer_skiplist, NULL); + apr_skiplist_pop(timer_skiplist, NULL); push_timer2worker(ep); } else { break; } - ep = ap_skiplist_peek(timer_skiplist); + ep = apr_skiplist_peek(timer_skiplist); } apr_thread_mutex_unlock(g_timer_skiplist_mtx); @@ -1814,7 +1814,7 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) APR_RING_REMOVE(te, link); } else { - te = ap_skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); + te = apr_skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); APR_RING_ELEM_INIT(te, link); } apr_thread_mutex_unlock(g_timer_skiplist_mtx); @@ -2290,8 +2290,8 @@ static void child_main(int child_num_arg) apr_thread_mutex_create(&g_timer_skiplist_mtx, APR_THREAD_MUTEX_DEFAULT, pchild); APR_RING_INIT(&timer_free_ring, timer_event_t, link); - ap_skiplist_init(&timer_skiplist, pchild); - ap_skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk); + apr_skiplist_init(&timer_skiplist, pchild); + apr_skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk); ap_run_child_init(pchild, ap_server_conf); /* done with init critical section */ diff --git a/server/mpm/eventopt/eventopt.c b/server/mpm/eventopt/eventopt.c index 0e6ad4771e..f73c1582f7 100644 --- a/server/mpm/eventopt/eventopt.c +++ b/server/mpm/eventopt/eventopt.c @@ -97,7 +97,7 @@ #include "equeue.h" -#include "ap_skiplist.h" +#include "apr_skiplist.h" #if HAVE_SERF #include "mod_serf.h" @@ -1353,7 +1353,7 @@ static void get_worker(int *have_idle_worker_p, int blocking, int *all_busy) /* Structures to reuse */ static APR_RING_HEAD(timer_free_ring_t, timer_event_t) timer_free_ring; -static ap_skiplist *timer_skiplist; +static apr_skiplist *timer_skiplist; static int indexing_comp(void *a, void *b) { @@ -1387,7 +1387,7 @@ static apr_status_t event_register_timed_callback(apr_time_t t, APR_RING_REMOVE(te, link); } else { - te = ap_skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); + te = apr_skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); APR_RING_ELEM_INIT(te, link); } @@ -1397,7 +1397,7 @@ static apr_status_t event_register_timed_callback(apr_time_t t, te->when = t + apr_time_now(); /* Okay, insert sorted by when.. */ - ap_skiplist_insert(timer_skiplist, (void *)te); + apr_skiplist_insert(timer_skiplist, (void *)te); apr_thread_mutex_unlock(g_timer_skiplist_mtx); @@ -1561,7 +1561,7 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) } apr_thread_mutex_lock(g_timer_skiplist_mtx); - te = ap_skiplist_peek(timer_skiplist); + te = apr_skiplist_peek(timer_skiplist); if (te) { if (te->when > now) { timeout_interval = te->when - now; @@ -1600,16 +1600,16 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) now = apr_time_now() + EVENT_FUDGE_FACTOR; apr_thread_mutex_lock(g_timer_skiplist_mtx); - ep = ap_skiplist_peek(timer_skiplist); + ep = apr_skiplist_peek(timer_skiplist); while (ep) { if (ep->when < now) { - ap_skiplist_pop(timer_skiplist, NULL); + apr_skiplist_pop(timer_skiplist, NULL); push_timer2worker(ep); } else { break; } - ep = ap_skiplist_peek(timer_skiplist); + ep = apr_skiplist_peek(timer_skiplist); } apr_thread_mutex_unlock(g_timer_skiplist_mtx); @@ -2267,8 +2267,8 @@ static void child_main(int child_num_arg) apr_thread_mutex_create(&g_timer_skiplist_mtx, APR_THREAD_MUTEX_DEFAULT, pchild); APR_RING_INIT(&timer_free_ring, timer_event_t, link); apr_pool_create(&pskip, pchild); - ap_skiplist_init(&timer_skiplist, pskip); - ap_skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk); + apr_skiplist_init(&timer_skiplist, pskip); + apr_skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk); ap_run_child_init(pchild, ap_server_conf); /* done with init critical section */ diff --git a/server/skiplist.c b/server/skiplist.c deleted file mode 100644 index a02085f9cf..0000000000 --- a/server/skiplist.c +++ /dev/null @@ -1,659 +0,0 @@ -/* 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 "ap_skiplist.h" - -struct ap_skiplist { - ap_skiplist_compare compare; - ap_skiplist_compare comparek; - int height; - int preheight; - int size; - ap_skiplistnode *top; - ap_skiplistnode *bottom; - /* These two are needed for appending */ - ap_skiplistnode *topend; - ap_skiplistnode *bottomend; - ap_skiplist *index; - apr_array_header_t *memlist; - apr_pool_t *pool; -}; - -struct ap_skiplistnode { - void *data; - ap_skiplistnode *next; - ap_skiplistnode *prev; - ap_skiplistnode *down; - ap_skiplistnode *up; - ap_skiplistnode *previndex; - ap_skiplistnode *nextindex; - ap_skiplist *sl; -}; - -#ifndef MIN -#define MIN(a,b) ((a 31) { /* Num bits in return of rand() */ - ph = 0; - randseq = (apr_uint32_t) rand(); - } - ph++; - return ((randseq & (1 << (ph - 1))) >> (ph - 1)); -} - -typedef struct { - size_t size; - apr_array_header_t *list; -} memlist_t; - -typedef struct { - void *ptr; - char inuse; -} chunk_t; - -AP_DECLARE(void *) ap_skiplist_alloc(ap_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_pcalloc(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 ap_calloc(1, size); - } -} - -AP_DECLARE(void) ap_skiplist_free(ap_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 skiplisti_init(ap_skiplist **s, apr_pool_t *p) -{ - ap_skiplist *sl; - if (p) { - sl = apr_pcalloc(p, sizeof(ap_skiplist)); - sl->memlist = apr_array_make(p, 20, sizeof(memlist_t)); - } - else { - sl = ap_calloc(1, sizeof(ap_skiplist)); - } -#if 0 - sl->compare = (ap_skiplist_compare) NULL; - sl->comparek = (ap_skiplist_compare) NULL; - sl->height = 0; - sl->preheight = 0; - sl->size = 0; - sl->top = NULL; - sl->bottom = NULL; - sl->index = NULL; -#endif - sl->pool = p; - *s = sl; - return APR_SUCCESS; -} - -static int indexing_comp(void *a, void *b) -{ - void *ac = (void *) (((ap_skiplist *) a)->compare); - void *bc = (void *) (((ap_skiplist *) b)->compare); - AP_DEBUG_ASSERT(a); - AP_DEBUG_ASSERT(b); - return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); -} - -static int indexing_compk(void *ac, void *b) -{ - void *bc = (void *) (((ap_skiplist *) b)->compare); - AP_DEBUG_ASSERT(b); - return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); -} - -AP_DECLARE(apr_status_t) ap_skiplist_init(ap_skiplist **s, apr_pool_t *p) -{ - ap_skiplist *sl; - skiplisti_init(s, p); - sl = *s; - skiplisti_init(&(sl->index), p); - ap_skiplist_set_compare(sl->index, indexing_comp, indexing_compk); - return APR_SUCCESS; -} - -AP_DECLARE(void) ap_skiplist_set_compare(ap_skiplist *sl, - ap_skiplist_compare comp, - ap_skiplist_compare compk) -{ - if (sl->compare && sl->comparek) { - ap_skiplist_add_index(sl, comp, compk); - } - else { - sl->compare = comp; - sl->comparek = compk; - } -} - -AP_DECLARE(void) ap_skiplist_add_index(ap_skiplist *sl, - ap_skiplist_compare comp, - ap_skiplist_compare compk) -{ - ap_skiplistnode *m; - ap_skiplist *ni; - int icount = 0; - ap_skiplist_find(sl->index, (void *)comp, &m); - if (m) { - return; /* Index already there! */ - } - skiplisti_init(&ni, sl->pool); - ap_skiplist_set_compare(ni, comp, compk); - /* Build the new index... This can be expensive! */ - m = ap_skiplist_insert(sl->index, ni); - while (m->prev) { - m = m->prev; - icount++; - } - for (m = ap_skiplist_getlist(sl); m; ap_skiplist_next(sl, &m)) { - int j = icount - 1; - ap_skiplistnode *nsln; - nsln = ap_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; - } -} - -AP_DECLARE(ap_skiplistnode *) ap_skiplist_getlist(ap_skiplist *sl) -{ - if (!sl->bottom) { - return NULL; - } - return sl->bottom->next; -} - -AP_DECLARE(void *) ap_skiplist_find(ap_skiplist *sl, void *data, ap_skiplistnode **iter) -{ - void *ret; - ap_skiplistnode *aiter; - if (!sl->compare) { - return 0; - } - if (iter) { - ret = ap_skiplist_find_compare(sl, data, iter, sl->compare); - } - else { - ret = ap_skiplist_find_compare(sl, data, &aiter, sl->compare); - } - return ret; -} - -static int skiplisti_find_compare(ap_skiplist *sl, void *data, - ap_skiplistnode **ret, - ap_skiplist_compare comp) -{ - ap_skiplistnode *m = NULL; - int count = 0; - m = sl->top; - while (m) { - int compared; - compared = (m->next) ? comp(data, m->next->data) : -1; - if (compared == 0) { - m = m->next; - while (m->down) { - m = m->down; - } - *ret = m; - return count; - } - if ((m->next == NULL) || (compared < 0)) { - m = m->down; - count++; - } - else { - m = m->next; - count++; - } - } - *ret = NULL; - return count; -} - -AP_DECLARE(void *) ap_skiplist_find_compare(ap_skiplist *sli, void *data, - ap_skiplistnode **iter, - ap_skiplist_compare comp) -{ - ap_skiplistnode *m = NULL; - ap_skiplist *sl; - if (comp == sli->compare || !sli->index) { - sl = sli; - } - else { - ap_skiplist_find(sli->index, (void *)comp, &m); - AP_DEBUG_ASSERT(m); - sl = (ap_skiplist *) m->data; - } - skiplisti_find_compare(sl, data, iter, sl->comparek); - return (iter && *iter) ? ((*iter)->data) : NULL; -} - - -AP_DECLARE(void *) ap_skiplist_next(ap_skiplist *sl, ap_skiplistnode **iter) -{ - if (!*iter) { - return NULL; - } - *iter = (*iter)->next; - return (*iter) ? ((*iter)->data) : NULL; -} - -AP_DECLARE(void *) ap_skiplist_previous(ap_skiplist *sl, ap_skiplistnode **iter) -{ - if (!*iter) { - return NULL; - } - *iter = (*iter)->prev; - return (*iter) ? ((*iter)->data) : NULL; -} - -AP_DECLARE(ap_skiplistnode *) ap_skiplist_insert(ap_skiplist *sl, void *data) -{ - if (!sl->compare) { - return 0; - } - return ap_skiplist_insert_compare(sl, data, sl->compare); -} - -AP_DECLARE(ap_skiplistnode *) ap_skiplist_insert_compare(ap_skiplist *sl, void *data, - ap_skiplist_compare comp) -{ - ap_skiplistnode *m, *p, *tmp, *ret = NULL, **stack; - int nh = 1, ch, stacki; - if (!sl->top) { - sl->height = 1; - sl->topend = sl->bottomend = sl->top = sl->bottom = - (ap_skiplistnode *)ap_skiplist_alloc(sl, sizeof(ap_skiplistnode)); - AP_DEBUG_ASSERT(sl->top); -#if 0 - sl->top->next = (ap_skiplistnode *)NULL; - sl->top->data = (ap_skiplistnode *)NULL; - sl->top->prev = (ap_skiplistnode *)NULL; - sl->top->up = (ap_skiplistnode *)NULL; - sl->top->down = (ap_skiplistnode *)NULL; - sl->top->nextindex = (ap_skiplistnode *)NULL; - sl->top->previndex = (ap_skiplistnode *)NULL; -#endif - sl->top->sl = sl; - } - if (sl->preheight) { - while (nh < sl->preheight && get_b_rand()) { - nh++; - } - } - else { - while (nh <= sl->height && get_b_rand()) { - nh++; - } - } - /* Now we have the new height at which we wish to insert our new node */ - /* - * Let us make sure that our tree is a least that tall (grow if - * necessary) - */ - for (; sl->height < nh; sl->height++) { - sl->top->up = - (ap_skiplistnode *)ap_skiplist_alloc(sl, sizeof(ap_skiplistnode)); - AP_DEBUG_ASSERT(sl->top->up); - sl->top->up->down = sl->top; - sl->top = sl->topend = sl->top->up; -#if 0 - sl->top->prev = sl->top->next = sl->top->nextindex = - sl->top->previndex = sl->top->up = NULL; - sl->top->data = NULL; -#endif - sl->top->sl = sl; - } - ch = sl->height; - /* Find the node (or node after which we would insert) */ - /* Keep a stack to pop back through for insertion */ - /* malloc() is OK since we free the temp stack */ - m = sl->top; - stack = (ap_skiplistnode **)ap_malloc(sizeof(ap_skiplistnode *) * (nh)); - stacki = 0; - while (m) { - int compared = -1; - if (m->next) { - compared = comp(data, m->next->data); - } - if (compared == 0) { - free(stack); /* OK. was ap_malloc'ed */ - return 0; - } - if ((m->next == NULL) || (compared < 0)) { - if (ch <= nh) { - /* push on stack */ - stack[stacki++] = m; - } - m = m->down; - ch--; - } - else { - m = m->next; - } - } - /* Pop the stack and insert nodes */ - p = NULL; - for (; stacki > 0; stacki--) { - m = stack[stacki - 1]; - tmp = (ap_skiplistnode *)ap_skiplist_alloc(sl, sizeof(ap_skiplistnode)); - tmp->next = m->next; - if (m->next) { - m->next->prev = tmp; - } - tmp->prev = m; - tmp->up = NULL; - tmp->nextindex = tmp->previndex = NULL; - tmp->down = p; - if (p) { - p->up = tmp; - } - tmp->data = data; - tmp->sl = sl; - m->next = tmp; - /* This sets ret to the bottom-most node we are inserting */ - if (!p) { - ret = tmp; - sl->size++; /* this seems to go here got each element to be counted */ - } - p = tmp; - } - free(stack); /* OK. was malloc'ed */ - if (sl->index != NULL) { - /* - * this is a external insertion, we must insert into each index as - * well - */ - ap_skiplistnode *ni, *li; - li = ret; - for (p = ap_skiplist_getlist(sl->index); p; ap_skiplist_next(sl->index, &p)) { - ni = ap_skiplist_insert((ap_skiplist *) p->data, ret->data); - AP_DEBUG_ASSERT(ni); - li->nextindex = ni; - ni->previndex = li; - li = ni; - } - } - else { - /* sl->size++; */ - } - sl->size++; - return ret; -} - -AP_DECLARE(int) ap_skiplist_remove(ap_skiplist *sl, void *data, ap_skiplist_freefunc myfree) -{ - if (!sl->compare) { - return 0; - } - return ap_skiplist_remove_compare(sl, data, myfree, sl->comparek); -} - -#if 0 -void skiplist_print_struct(ap_skiplist * sl, char *prefix) -{ - ap_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(ap_skiplist *sl, ap_skiplistnode *m, ap_skiplist_freefunc myfree) -{ - ap_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); - } - ap_skiplist_free(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 */ - } - ap_skiplist_free(sl, p); - sl->height--; - } - if (!sl->top) { - sl->bottom = NULL; - } - AP_DEBUG_ASSERT(sl->height >= 0); - return sl->height; /* return 1; ?? */ -} - -AP_DECLARE(int) ap_skiplist_remove_compare(ap_skiplist *sli, - void *data, - ap_skiplist_freefunc myfree, ap_skiplist_compare comp) -{ - ap_skiplistnode *m; - ap_skiplist *sl; - if (comp == sli->comparek || !sli->index) { - sl = sli; - } - else { - ap_skiplist_find(sli->index, (void *)comp, &m); - AP_DEBUG_ASSERT(m); - sl = (ap_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); -} - -AP_DECLARE(void) ap_skiplist_remove_all(ap_skiplist *sl, ap_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 - */ - ap_skiplistnode *m, *p, *u; - m = sl->bottom; - while (m) { - p = m->next; - if (p && myfree && p->data) - myfree(p->data); - while (m) { - u = m->up; - ap_skiplist_free(sl, p); - m = u; - } - m = p; - } - sl->top = sl->bottom = NULL; - sl->height = 0; - sl->size = 0; -} - -AP_DECLARE(void *) ap_skiplist_pop(ap_skiplist *a, ap_skiplist_freefunc myfree) -{ - ap_skiplistnode *sln; - void *data = NULL; - sln = ap_skiplist_getlist(a); - if (sln) { - data = sln->data; - skiplisti_remove(a, sln, myfree); - } - return data; -} - -AP_DECLARE(void *) ap_skiplist_peek(ap_skiplist *a) -{ - ap_skiplistnode *sln; - sln = ap_skiplist_getlist(a); - if (sln) { - return sln->data; - } - return NULL; -} - -static void skiplisti_destroy(void *vsl) -{ - ap_skiplist_destroy((ap_skiplist *) vsl, NULL); - ap_skiplist_free((ap_skiplist *) vsl, vsl); -} - -AP_DECLARE(void) ap_skiplist_destroy(ap_skiplist *sl, ap_skiplist_freefunc myfree) -{ - while (ap_skiplist_pop(sl->index, skiplisti_destroy) != NULL) - ; - ap_skiplist_remove_all(sl, myfree); -} - -AP_DECLARE(ap_skiplist *) ap_skiplist_merge(ap_skiplist *sl1, ap_skiplist *sl2) -{ - /* Check integrity! */ - ap_skiplist temp; - struct ap_skiplistnode *b2; - if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { - ap_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) { - ap_skiplist_remove_all(sl2, NULL); - return sl1; - } - /* This is what makes it brute force... Just insert :/ */ - b2 = ap_skiplist_getlist(sl2); - while (b2) { - ap_skiplist_insert(sl1, b2->data); - ap_skiplist_next(sl2, &b2); - } - ap_skiplist_remove_all(sl2, NULL); - return sl1; -} -- 2.40.0