httpd-cvs mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From j..@apache.org
Subject svn commit: r1411190 - in /httpd/httpd/trunk: LICENSE server/mpm/eventopt/config3.m4 server/mpm/eventopt/eventopt.c server/mpm/eventopt/skiplist.c server/mpm/eventopt/skiplist.h
Date Mon, 19 Nov 2012 14:11:39 GMT
Author: jim
Date: Mon Nov 19 14:11:38 2012
New Revision: 1411190

URL: http://svn.apache.org/viewvc?rev=1411190&view=rev
Log:
Merge branch 'skiplist'

Added:
    httpd/httpd/trunk/server/mpm/eventopt/skiplist.c   (with props)
    httpd/httpd/trunk/server/mpm/eventopt/skiplist.h   (with props)
Modified:
    httpd/httpd/trunk/LICENSE
    httpd/httpd/trunk/server/mpm/eventopt/config3.m4
    httpd/httpd/trunk/server/mpm/eventopt/eventopt.c

Modified: httpd/httpd/trunk/LICENSE
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/LICENSE?rev=1411190&r1=1411189&r2=1411190&view=diff
==============================================================================
--- httpd/httpd/trunk/LICENSE (original)
+++ httpd/httpd/trunk/LICENSE Mon Nov 19 14:11:38 2012
@@ -544,4 +544,24 @@ CLAIM, DAMAGES OR OTHER LIABILITY, WHETH
 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.
+ *
+ * ======================================================================
+ */
+
+
 ====================================================================

Modified: httpd/httpd/trunk/server/mpm/eventopt/config3.m4
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/config3.m4?rev=1411190&r1=1411189&r2=1411190&view=diff
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/config3.m4 (original)
+++ httpd/httpd/trunk/server/mpm/eventopt/config3.m4 Mon Nov 19 14:11:38 2012
@@ -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)])
 

Modified: httpd/httpd/trunk/server/mpm/eventopt/eventopt.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/eventopt.c?rev=1411190&r1=1411189&r2=1411190&view=diff
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/eventopt.c (original)
+++ httpd/httpd/trunk/server/mpm/eventopt/eventopt.c Mon Nov 19 14:11:38 2012
@@ -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_wo
     }
 }
 
-/* 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
     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_t
             }
         }
 
-        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_t
         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_t
         }
 
         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_thre
             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 * 
             return DONE;
         }
     }
+    /* for skiplist */
+    srand((unsigned int)apr_time_now());
     return OK;
 }
 

Added: httpd/httpd/trunk/server/mpm/eventopt/skiplist.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/skiplist.c?rev=1411190&view=auto
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/skiplist.c (added)
+++ httpd/httpd/trunk/server/mpm/eventopt/skiplist.c Mon Nov 19 14:11:38 2012
@@ -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;
+}
+

Propchange: httpd/httpd/trunk/server/mpm/eventopt/skiplist.c
------------------------------------------------------------------------------
    svn:eol-style = native

Added: httpd/httpd/trunk/server/mpm/eventopt/skiplist.h
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/skiplist.h?rev=1411190&view=auto
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/skiplist.h (added)
+++ httpd/httpd/trunk/server/mpm/eventopt/skiplist.h Mon Nov 19 14:11:38 2012
@@ -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

Propchange: httpd/httpd/trunk/server/mpm/eventopt/skiplist.h
------------------------------------------------------------------------------
    svn:eol-style = native



Mime
View raw message