diff options
| -rw-r--r-- | LICENSE | 20 | ||||
| -rw-r--r-- | server/mpm/eventopt/config3.m4 | 2 | ||||
| -rw-r--r-- | server/mpm/eventopt/eventopt.c | 86 | ||||
| -rw-r--r-- | server/mpm/eventopt/skiplist.c | 690 | ||||
| -rw-r--r-- | server/mpm/eventopt/skiplist.h | 119 |
5 files changed, 872 insertions, 45 deletions
@@ -544,4 +544,24 @@ 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/mpm/eventopt/skiplist.? 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/server/mpm/eventopt/config3.m4 b/server/mpm/eventopt/config3.m4 index 868d4b984d..061bcbad7f 100644 --- a/server/mpm/eventopt/config3.m4 +++ b/server/mpm/eventopt/config3.m4 @@ -8,7 +8,7 @@ if test "$ac_cv_serf" = yes ; then fi APACHE_SUBST(MOD_MPM_EVENTOPT_LDADD) -APACHE_MPM_MODULE(eventopt, $enable_mpm_eventopt, eventopt.lo fdqueue.lo equeue.lo,[ +APACHE_MPM_MODULE(eventopt, $enable_mpm_eventopt, eventopt.lo fdqueue.lo equeue.lo skiplist.lo,[ AC_CHECK_FUNCS(pthread_kill) ], , [\$(MOD_MPM_EVENTOPT_LDADD)]) diff --git a/server/mpm/eventopt/eventopt.c b/server/mpm/eventopt/eventopt.c index 2c7891e65e..795dba3115 100644 --- a/server/mpm/eventopt/eventopt.c +++ b/server/mpm/eventopt/eventopt.c @@ -97,6 +97,7 @@ #include "equeue.h" +#include "skiplist.h" #if HAVE_SERF #include "mod_serf.h" @@ -1266,34 +1267,44 @@ static void get_worker(int *have_idle_worker_p, int blocking, int *all_busy) } } -/* XXXXXX: Convert to skiplist or other better data structure - * (yes, this is VERY VERY VERY VERY BAD) - */ - /* Structures to reuse */ static APR_RING_HEAD(timer_free_ring_t, timer_event_t) timer_free_ring; -/* Active timers */ -static APR_RING_HEAD(timer_ring_t, timer_event_t) timer_ring; -static apr_thread_mutex_t *g_timer_ring_mtx; +static Skiplist *timer_skiplist; + +static int indexing_comp(void *a, void *b) +{ + apr_time_t t1 = (apr_time_t) (((timer_event_t *) a)->when); + apr_time_t t2 = (apr_time_t) (((timer_event_t *) b)->when); + AP_DEBUG_ASSERT(t1); + AP_DEBUG_ASSERT(t2); + return ((t1 < t2) ? -1 : ((t1 > t2) ? 1 : 0)); +} + +static int indexing_compk(void *ac, void *b) +{ + apr_time_t *t1 = (apr_time_t *) ac; + apr_time_t t2 = (apr_time_t) (((timer_event_t *) b)->when); + AP_DEBUG_ASSERT(t2); + return ((*t1 < t2) ? -1 : ((*t1 > t2) ? 1 : 0)); +} + +static apr_thread_mutex_t *g_timer_skiplist_mtx; static apr_status_t event_register_timed_callback(apr_time_t t, ap_mpm_callback_fn_t *cbfn, void *baton) { - int inserted = 0; - timer_event_t *ep; timer_event_t *te; /* oh yeah, and make locking smarter/fine grained. */ - apr_thread_mutex_lock(g_timer_ring_mtx); + apr_thread_mutex_lock(g_timer_skiplist_mtx); if (!APR_RING_EMPTY(&timer_free_ring, timer_event_t, link)) { te = APR_RING_FIRST(&timer_free_ring); APR_RING_REMOVE(te, link); } else { - /* XXXXX: lol, pool allocation without a context from any thread.Yeah. Right. MPMs Suck. */ - te = ap_malloc(sizeof(timer_event_t)); + te = skiplist_alloc(timer_skiplist, sizeof(timer_event_t)); APR_RING_ELEM_INIT(te, link); } @@ -1303,23 +1314,9 @@ static apr_status_t event_register_timed_callback(apr_time_t t, te->when = t + apr_time_now(); /* Okay, insert sorted by when.. */ - for (ep = APR_RING_FIRST(&timer_ring); - ep != APR_RING_SENTINEL(&timer_ring, - timer_event_t, link); - ep = APR_RING_NEXT(ep, link)) - { - if (ep->when > te->when) { - inserted = 1; - APR_RING_INSERT_BEFORE(ep, te, link); - break; - } - } - - if (!inserted) { - APR_RING_INSERT_TAIL(&timer_ring, te, timer_event_t, link); - } + skiplist_insert(timer_skiplist, (void *)te); - apr_thread_mutex_unlock(g_timer_ring_mtx); + apr_thread_mutex_unlock(g_timer_skiplist_mtx); return APR_SUCCESS; } @@ -1478,9 +1475,9 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) } } - apr_thread_mutex_lock(g_timer_ring_mtx); - if (!APR_RING_EMPTY(&timer_ring, timer_event_t, link)) { - te = APR_RING_FIRST(&timer_ring); + apr_thread_mutex_lock(g_timer_skiplist_mtx); + te = skiplist_peek(timer_skiplist); + if (te) { if (te->when > now) { timeout_interval = te->when - now; } @@ -1491,7 +1488,7 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) else { timeout_interval = apr_time_from_msec(100); } - apr_thread_mutex_unlock(g_timer_ring_mtx); + apr_thread_mutex_unlock(g_timer_skiplist_mtx); #if HAVE_SERF rc = serf_context_prerun(g_serf); @@ -1517,21 +1514,19 @@ static void * APR_THREAD_FUNC listener_thread(apr_thread_t * thd, void *dummy) } now = apr_time_now(); - apr_thread_mutex_lock(g_timer_ring_mtx); - for (ep = APR_RING_FIRST(&timer_ring); - ep != APR_RING_SENTINEL(&timer_ring, - timer_event_t, link); - ep = APR_RING_FIRST(&timer_ring)) - { + apr_thread_mutex_lock(g_timer_skiplist_mtx); + ep = skiplist_peek(timer_skiplist); + while (ep) { if (ep->when < now + EVENT_FUDGE_FACTOR) { - APR_RING_REMOVE(ep, link); + skiplist_pop(timer_skiplist, NULL); push_timer2worker(ep); } else { break; } + ep = skiplist_peek(timer_skiplist); } - apr_thread_mutex_unlock(g_timer_ring_mtx); + apr_thread_mutex_unlock(g_timer_skiplist_mtx); while (num) { pt = (listener_poll_type *) out_pfd->client_data; @@ -1857,9 +1852,9 @@ static void *APR_THREAD_FUNC worker_thread(apr_thread_t * thd, void *dummy) te->cbfunc(te->baton); { - apr_thread_mutex_lock(g_timer_ring_mtx); + apr_thread_mutex_lock(g_timer_skiplist_mtx); APR_RING_INSERT_TAIL(&timer_free_ring, te, timer_event_t, link); - apr_thread_mutex_unlock(g_timer_ring_mtx); + apr_thread_mutex_unlock(g_timer_skiplist_mtx); } } else { @@ -2184,9 +2179,10 @@ static void child_main(int child_num_arg) clean_child_exit(APEXIT_CHILDFATAL); } - apr_thread_mutex_create(&g_timer_ring_mtx, APR_THREAD_MUTEX_DEFAULT, pchild); + apr_thread_mutex_create(&g_timer_skiplist_mtx, APR_THREAD_MUTEX_DEFAULT, pchild); APR_RING_INIT(&timer_free_ring, timer_event_t, link); - APR_RING_INIT(&timer_ring, timer_event_t, link); + skiplist_init(&timer_skiplist, pchild); + skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk); ap_run_child_init(pchild, ap_server_conf); /* done with init critical section */ @@ -2889,6 +2885,8 @@ static int event_open_logs(apr_pool_t * p, apr_pool_t * plog, return DONE; } } + /* for skiplist */ + srand((unsigned int)apr_time_now()); return OK; } diff --git a/server/mpm/eventopt/skiplist.c b/server/mpm/eventopt/skiplist.c new file mode 100644 index 0000000000..7d60b66f55 --- /dev/null +++ b/server/mpm/eventopt/skiplist.c @@ -0,0 +1,690 @@ +/* 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 "skiplist.h" + +#ifndef MIN +#define MIN(a,b) ((a<b)?(a):(b)) +#endif + +static int get_b_rand(void) +{ + static int ph = 32; /* More bits than we will ever use */ + static apr_uint32_t randseq; + if (ph > 31) { /* Num bits in return of rand() */ + ph = 0; + randseq = (apr_uint32_t) rand(); + } + ph++; + return ((randseq & (1 << (ph - 1))) >> (ph - 1)); +} + +void *skiplist_alloc(Skiplist *sl, size_t size) +{ + if (sl->pool) { + return apr_palloc(sl->pool, size); + } + else { + return ap_malloc(size); + } +} + +void skiplist_free(Skiplist *sl, void *mem) +{ + if (!sl->pool) { + free(mem); + } +} + +static apr_status_t skiplisti_init(Skiplist **s, apr_pool_t *p) +{ + Skiplist *sl; + if (p) { + sl = apr_palloc(p, sizeof(Skiplist)); + } + else { + sl = ap_malloc(sizeof(Skiplist)); + } + sl->compare = (SkiplistComparator) NULL; + sl->comparek = (SkiplistComparator) NULL; + sl->height = 0; + sl->preheight = 0; + sl->size = 0; + sl->top = NULL; + sl->bottom = NULL; + sl->index = NULL; + sl->pool = p; + *s = sl; + return APR_SUCCESS; +} + +static int indexing_comp(void *a, void *b) +{ + void *ac = (void *) (((Skiplist *) a)->compare); + void *bc = (void *) (((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 *) (((Skiplist *) b)->compare); + AP_DEBUG_ASSERT(b); + return ((ac < bc) ? -1 : ((ac > bc) ? 1 : 0)); +} + +apr_status_t skiplist_init(Skiplist **s, apr_pool_t *p) +{ + Skiplist *sl; + skiplisti_init(s, p); + sl = *s; + skiplisti_init(&(sl->index), p); + skiplist_set_compare(sl->index, indexing_comp, indexing_compk); + return APR_SUCCESS; +} + +void skiplist_set_compare(Skiplist *sl, + SkiplistComparator comp, + SkiplistComparator compk) +{ + if (sl->compare && sl->comparek) { + skiplist_add_index(sl, comp, compk); + } + else { + sl->compare = comp; + sl->comparek = compk; + } +} + +void skiplist_add_index(Skiplist *sl, + SkiplistComparator comp, + SkiplistComparator compk) +{ + skiplistnode *m; + Skiplist *ni; + int icount = 0; + skiplist_find(sl->index, (void *)comp, &m); + if (m) { + return; /* Index already there! */ + } + skiplisti_init(&ni, sl->pool); + skiplist_set_compare(ni, comp, compk); + /* Build the new index... This can be expensive! */ + m = skiplist_insert(sl->index, ni); + while (m->prev) { + m = m->prev; + icount++; + } + for (m = skiplist_getlist(sl); m; skiplist_next(sl, &m)) { + int j = icount - 1; + skiplistnode *nsln; + nsln = 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; + } +} + +skiplistnode *skiplist_getlist(Skiplist *sl) +{ + if (!sl->bottom) { + return NULL; + } + return sl->bottom->next; +} + +void *skiplist_find(Skiplist *sl, void *data, skiplistnode **iter) +{ + void *ret; + skiplistnode *aiter; + if (!sl->compare) { + return 0; + } + if (iter) { + ret = skiplist_find_compare(sl, data, iter, sl->compare); + } + else { + ret = skiplist_find_compare(sl, data, &aiter, sl->compare); + } + return ret; +} + +static int skiplisti_find_compare(Skiplist *sl, void *data, + skiplistnode **ret, + SkiplistComparator comp) +{ + skiplistnode *m = NULL; + int count = 0; + m = sl->top; + while (m) { + int compared; + if (m->next) { + compared = comp(data, m->next->data); + } + 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; +} + +void *skiplist_find_compare(Skiplist *sli, void *data, + skiplistnode **iter, + SkiplistComparator comp) +{ + skiplistnode *m = NULL; + Skiplist *sl; + if (comp == sli->compare || !sli->index) { + sl = sli; + } + else { + skiplist_find(sli->index, (void *)comp, &m); + AP_DEBUG_ASSERT(m); + sl = (Skiplist *) m->data; + } + skiplisti_find_compare(sl, data, iter, sl->comparek); + return (*iter) ? ((*iter)->data) : (*iter); +} + + +void *skiplist_next(Skiplist *sl, skiplistnode **iter) +{ + if (!*iter) { + return NULL; + } + *iter = (*iter)->next; + return (*iter) ? ((*iter)->data) : NULL; +} + +void *skiplist_previous(Skiplist *sl, skiplistnode **iter) +{ + if (!*iter) { + return NULL; + } + *iter = (*iter)->prev; + return (*iter) ? ((*iter)->data) : NULL; +} + +skiplistnode *skiplist_insert(Skiplist *sl, void *data) +{ + if (!sl->compare) { + return 0; + } + return skiplist_insert_compare(sl, data, sl->compare); +} + +skiplistnode *skiplist_insert_compare(Skiplist *sl, void *data, + SkiplistComparator comp) +{ + skiplistnode *m, *p, *tmp, *ret, **stack; + int nh = 1, ch, stacki; + if (!sl->top) { + sl->height = 1; + sl->topend = sl->bottomend = sl->top = sl->bottom = + (skiplistnode *)skiplist_alloc(sl, sizeof(skiplistnode)); + AP_DEBUG_ASSERT(sl->top); + sl->top->next = (skiplistnode *)NULL; + sl->top->data = (skiplistnode *)NULL; + sl->top->prev = (skiplistnode *)NULL; + sl->top->up = (skiplistnode *)NULL; + sl->top->down = (skiplistnode *)NULL; + sl->top->nextindex = (skiplistnode *)NULL; + sl->top->previndex = (skiplistnode *)NULL; + 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 = + (skiplistnode *)skiplist_alloc(sl, sizeof(skiplistnode)); + AP_DEBUG_ASSERT(sl->top->up); + sl->top->up->down = sl->top; + sl->top = sl->topend = sl->top->up; + sl->top->prev = sl->top->next = sl->top->nextindex = + sl->top->previndex = sl->top->up = NULL; + sl->top->data = NULL; + 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 = (skiplistnode **)ap_malloc(sizeof(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 = (skiplistnode *)skiplist_alloc(sl, sizeof(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 + */ + skiplistnode *p, *ni, *li; + li = ret; + for (p = skiplist_getlist(sl->index); p; skiplist_next(sl->index, &p)) { + ni = skiplist_insert((Skiplist *) p->data, ret->data); + AP_DEBUG_ASSERT(ni); + li->nextindex = ni; + ni->previndex = li; + li = ni; + } + } + else { + /* sl->size++; */ + } + return ret; +} + +/* + * There are reports of skiplist_append() being buggy. + * Use at own risk + */ +skiplistnode *skiplist_append(Skiplist *sl, void *data) +{ + int nh = 1, ch, compared; + skiplistnode *lastnode, *nodeago; + if (sl->bottomend != sl->bottom) { + compared = sl->compare(data, sl->bottomend->prev->data); + /* If it doesn't belong at the end, then fail */ + if (compared <= 0) + return NULL; + } + 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) + */ + lastnode = sl->bottomend; + nodeago = NULL; + + if (!lastnode) { + return skiplist_insert(sl, data); + } + + for (; sl->height < nh; sl->height++) { + sl->top->up = (skiplistnode *)skiplist_alloc(sl, sizeof(skiplistnode)); + AP_DEBUG_ASSERT(sl->top); + sl->top->up->down = sl->top; + sl->top = sl->top->up; + sl->top->prev = sl->top->next = sl->top->nextindex = + sl->top->previndex = NULL; + sl->top->data = NULL; + sl->top->sl = sl; + } + ch = sl->height; + while (nh) { + skiplistnode *anode; + anode = (skiplistnode *)skiplist_alloc(sl, sizeof(skiplistnode)); + anode->next = lastnode; + anode->prev = lastnode->prev; + anode->up = NULL; + anode->down = nodeago; + if (lastnode->prev) { + if (lastnode == sl->bottom) + sl->bottom = anode; + else if (lastnode == sl->top) + sl->top = anode; + } + nodeago = anode; + lastnode = lastnode->up; + nh--; + } + sl->size++; + return sl->bottomend; +} + +/* + * There are reports of skiplist_concat() being buggy. + * Use at own risk + */ +Skiplist *skiplist_concat(Skiplist *sl1, Skiplist *sl2) +{ + /* Check integrity! */ + int compared, eheight; + Skiplist temp; + skiplistnode *lbottom, *lbottomend, *b1, *e1, *b2, *e2; + if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { + 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) { + skiplist_remove_all(sl2, NULL); + return sl1; + } + compared = sl1->compare(sl1->bottomend->prev->data, sl2->bottom->data); + /* If it doesn't belong at the end, then fail */ + if (compared <= 0) { + return NULL; + } + + /* OK now append sl2 onto sl1 */ + lbottom = lbottomend = NULL; + eheight = MIN(sl1->height, sl2->height); + b1 = sl1->bottom; + e1 = sl1->bottomend; + b2 = sl2->bottom; + e2 = sl2->bottomend; + while (eheight) { + e1->prev->next = b2; + b2->prev = e1->prev->next; + e2->prev->next = e1; + e1->prev = e2->prev; + e2->prev = NULL; + b2 = e2; + b1->down = lbottom; + e1->down = lbottomend; + if (lbottom) { + lbottom->up = b1; + } + if (lbottomend) { + lbottomend->up = e1; + } + + lbottom = b1; + lbottomend = e1; + } + /* Take the top of the longer one (if it is sl2) and make it sl1's */ + if (sl2->height > sl1->height) { + b1->up = b2->up; + e1->up = e2->up; + b1->up->down = b1; + e1->up->down = e1; + sl1->height = sl2->height; + sl1->top = sl2->top; + sl1->topend = sl2->topend; + } + + /* move the top pointer to here if it isn't there already */ + sl2->top = sl2->topend = b2; + sl2->top->up = NULL; /* If it isn't already */ + sl1->size += sl2->size; + skiplist_remove_all(sl2, NULL); + return sl1; +} + +int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree) +{ + if (!sl->compare) { + return 0; + } + return skiplist_remove_compare(sl, data, myfree, sl->comparek); +} + +#if 0 +void skiplist_print_struct(Skiplist * sl, char *prefix) +{ + 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(Skiplist *sl, skiplistnode *m, FreeFunc myfree) +{ + skiplistnode *p; + if (!m) { + return 0; + } + if (m->nextindex) { + skiplisti_remove(m->nextindex->sl, m->nextindex, NULL); + } + else { + sl->size--; + } + + 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(sl, p); + } + 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(sl, p); + sl->height--; + } + if (!sl->top) { + sl->bottom = NULL; + } + AP_DEBUG_ASSERT(sl->height >= 0); + return sl->height; +} + +int skiplist_remove_compare(Skiplist *sli, + void *data, + FreeFunc myfree, SkiplistComparator comp) +{ + skiplistnode *m; + Skiplist *sl; + if (comp == sli->comparek || !sli->index) { + sl = sli; + } + else { + skiplist_find(sli->index, (void *)comp, &m); + AP_DEBUG_ASSERT(m); + sl = (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); +} + +void skiplist_remove_all(Skiplist *sl, 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 + */ + skiplistnode *m, *p, *u; + m = sl->bottom; + while (m) { + p = m->next; + if (myfree && p->data) + myfree(p->data); + while (m) { + u = m->up; + skiplist_free(sl, p); + m = u; + } + m = p; + } + sl->top = sl->bottom = NULL; + sl->height = 0; + sl->size = 0; +} + +void *skiplist_pop(Skiplist *a, FreeFunc myfree) +{ + skiplistnode *sln; + void *data = NULL; + sln = skiplist_getlist(a); + if (sln) { + data = sln->data; + skiplisti_remove(a, sln, myfree); + } + return data; +} + +void *skiplist_peek(Skiplist *a) +{ + skiplistnode *sln; + void *data = NULL; + sln = skiplist_getlist(a); + return data; +} + +Skiplist *skiplist_merge(Skiplist *sl1, Skiplist *sl2) +{ + /* Check integrity! */ + Skiplist temp; + struct skiplistnode *b2; + if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) { + 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) { + skiplist_remove_all(sl2, NULL); + return sl1; + } + /* This is what makes it brute force... Just insert :/ */ + b2 = skiplist_getlist(sl2); + while (b2) { + skiplist_insert(sl1, b2->data); + skiplist_next(sl2, &b2); + } + skiplist_remove_all(sl2, NULL); + return sl1; +} + diff --git a/server/mpm/eventopt/skiplist.h b/server/mpm/eventopt/skiplist.h new file mode 100644 index 0000000000..f704cbcd4f --- /dev/null +++ b/server/mpm/eventopt/skiplist.h @@ -0,0 +1,119 @@ +/* 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 _SKIPLIST_P_H +#define _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 (*SkiplistComparator) (void *, void *); +typedef void (*FreeFunc) (void *); + +typedef struct skiplistnode skiplistnode; +typedef struct Skiplist Skiplist; + +struct Skiplist { + SkiplistComparator compare; + SkiplistComparator comparek; + int height; + int preheight; + int size; + skiplistnode *top; + skiplistnode *bottom; + /* These two are needed for appending */ + skiplistnode *topend; + skiplistnode *bottomend; + Skiplist *index; + apr_pool_t *pool; +}; + +struct skiplistnode { + void *data; + skiplistnode *next; + skiplistnode *prev; + skiplistnode *down; + skiplistnode *up; + skiplistnode *previndex; + skiplistnode *nextindex; + Skiplist *sl; +}; + +void *skiplist_alloc(Skiplist *sl, size_t size); + +void skiplist_free(Skiplist *sl, void *mem); + +apr_status_t skiplist_init(Skiplist **sl, apr_pool_t *p); + +void skiplist_set_compare(Skiplist *sl, SkiplistComparator, + SkiplistComparator); + +void skiplist_add_index(Skiplist *sl, SkiplistComparator, + SkiplistComparator); + +skiplistnode *skiplist_getlist(Skiplist *sl); + +void *skiplist_find_compare(Skiplist *sl, + void *data, + skiplistnode **iter, + SkiplistComparator func); + +void *skiplist_find(Skiplist *sl, void *data, skiplistnode **iter); + +void *skiplist_next(Skiplist *sl, skiplistnode **iter); + +void *skiplist_previous(Skiplist *sl, skiplistnode **iter); + + +skiplistnode *skiplist_insert_compare(Skiplist *sl, + void *data, SkiplistComparator comp); + +skiplistnode *skiplist_insert(Skiplist* sl, void *data); + +skiplistnode *skiplist_append(Skiplist *sl, void *data); + +int skiplist_remove_compare(Skiplist *sl, void *data, + FreeFunc myfree, SkiplistComparator comp); + +int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree); + +#if 0 +int skiplisti_remove(Skiplist *sl, skiplistnode *m, FreeFunc myfree); +#endif + +void skiplist_remove_all(Skiplist *sl, FreeFunc myfree); + +#if 0 +int skiplisti_find_compare(Skiplist *sl, + void *data, + skiplistnode **ret, + SkiplistComparator comp); + +#endif + +void *skiplist_pop(Skiplist *a, FreeFunc myfree); + +void *skiplist_peek(Skiplist *a); + +Skiplist *skiplist_concat(Skiplist *sl1, Skiplist *sl2); + +Skiplist *skiplist_merge(Skiplist *sl1, Skiplist *sl2); + +#endif |