You are viewing a plain text version of this content. The canonical link for it is here.
Posted to cvs@httpd.apache.org by ji...@apache.org on 2013/03/01 16:24:06 UTC
svn commit: r1451616 - in /httpd/httpd/trunk/server/mpm/eventopt: eventopt.c
skiplist.c skiplist.h
Author: jim
Date: Fri Mar 1 15:24:05 2013
New Revision: 1451616
URL: http://svn.apache.org/r1451616
Log:
1st phase of moving into httpd "core"
Modified:
httpd/httpd/trunk/server/mpm/eventopt/eventopt.c
httpd/httpd/trunk/server/mpm/eventopt/skiplist.c
httpd/httpd/trunk/server/mpm/eventopt/skiplist.h
Modified: httpd/httpd/trunk/server/mpm/eventopt/eventopt.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/eventopt.c?rev=1451616&r1=1451615&r2=1451616&view=diff
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/eventopt.c (original)
+++ httpd/httpd/trunk/server/mpm/eventopt/eventopt.c Fri Mar 1 15:24:05 2013
@@ -1345,7 +1345,7 @@ static void get_worker(int *have_idle_wo
/* Structures to reuse */
static APR_RING_HEAD(timer_free_ring_t, timer_event_t) timer_free_ring;
-static Skiplist *timer_skiplist;
+static ap_skiplist *timer_skiplist;
static int indexing_comp(void *a, void *b)
{
@@ -1379,7 +1379,7 @@ static apr_status_t event_register_timed
APR_RING_REMOVE(te, link);
}
else {
- te = skiplist_alloc(timer_skiplist, sizeof(timer_event_t));
+ te = ap_skiplist_alloc(timer_skiplist, sizeof(timer_event_t));
APR_RING_ELEM_INIT(te, link);
}
@@ -1389,7 +1389,7 @@ static apr_status_t event_register_timed
te->when = t + apr_time_now();
/* Okay, insert sorted by when.. */
- skiplist_insert(timer_skiplist, (void *)te);
+ ap_skiplist_insert(timer_skiplist, (void *)te);
apr_thread_mutex_unlock(g_timer_skiplist_mtx);
@@ -1553,7 +1553,7 @@ static void * APR_THREAD_FUNC listener_t
}
apr_thread_mutex_lock(g_timer_skiplist_mtx);
- te = skiplist_peek(timer_skiplist);
+ te = ap_skiplist_peek(timer_skiplist);
if (te) {
if (te->when > now) {
timeout_interval = te->when - now;
@@ -1592,16 +1592,16 @@ static void * APR_THREAD_FUNC listener_t
now = apr_time_now() + EVENT_FUDGE_FACTOR;
apr_thread_mutex_lock(g_timer_skiplist_mtx);
- ep = skiplist_peek(timer_skiplist);
+ ep = ap_skiplist_peek(timer_skiplist);
while (ep) {
if (ep->when < now) {
- skiplist_pop(timer_skiplist, NULL);
+ ap_skiplist_pop(timer_skiplist, NULL);
push_timer2worker(ep);
}
else {
break;
}
- ep = skiplist_peek(timer_skiplist);
+ ep = ap_skiplist_peek(timer_skiplist);
}
apr_thread_mutex_unlock(g_timer_skiplist_mtx);
@@ -2257,8 +2257,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);
- skiplist_init(&timer_skiplist, pchild);
- skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk);
+ ap_skiplist_init(&timer_skiplist, pchild);
+ ap_skiplist_set_compare(timer_skiplist, indexing_comp, indexing_compk);
ap_run_child_init(pchild, ap_server_conf);
/* done with init critical section */
Modified: httpd/httpd/trunk/server/mpm/eventopt/skiplist.c
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/skiplist.c?rev=1451616&r1=1451615&r2=1451616&view=diff
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/skiplist.c (original)
+++ httpd/httpd/trunk/server/mpm/eventopt/skiplist.c Fri Mar 1 15:24:05 2013
@@ -41,7 +41,7 @@ static int get_b_rand(void)
return ((randseq & (1 << (ph - 1))) >> (ph - 1));
}
-void *skiplist_alloc(Skiplist *sl, size_t size)
+void *ap_skiplist_alloc(ap_skiplist *sl, size_t size)
{
if (sl->pool) {
return apr_pcalloc(sl->pool, size);
@@ -51,25 +51,25 @@ void *skiplist_alloc(Skiplist *sl, size_
}
}
-void skiplist_free(Skiplist *sl, void *mem)
+void ap_skiplist_free(ap_skiplist *sl, void *mem)
{
if (!sl->pool) {
free(mem);
}
}
-static apr_status_t skiplisti_init(Skiplist **s, apr_pool_t *p)
+static apr_status_t skiplisti_init(ap_skiplist **s, apr_pool_t *p)
{
- Skiplist *sl;
+ ap_skiplist *sl;
if (p) {
- sl = apr_pcalloc(p, sizeof(Skiplist));
+ sl = apr_pcalloc(p, sizeof(ap_skiplist));
}
else {
- sl = ap_calloc(1, sizeof(Skiplist));
+ sl = ap_calloc(1, sizeof(ap_skiplist));
}
#if 0
- sl->compare = (SkiplistComparator) NULL;
- sl->comparek = (SkiplistComparator) NULL;
+ sl->compare = (ap_skiplist_compare) NULL;
+ sl->comparek = (ap_skiplist_compare) NULL;
sl->height = 0;
sl->preheight = 0;
sl->size = 0;
@@ -84,8 +84,8 @@ static apr_status_t skiplisti_init(Skipl
static int indexing_comp(void *a, void *b)
{
- void *ac = (void *) (((Skiplist *) a)->compare);
- void *bc = (void *) (((Skiplist *) b)->compare);
+ 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));
@@ -93,27 +93,27 @@ static int indexing_comp(void *a, void *
static int indexing_compk(void *ac, void *b)
{
- void *bc = (void *) (((Skiplist *) b)->compare);
+ void *bc = (void *) (((ap_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)
+apr_status_t ap_skiplist_init(ap_skiplist **s, apr_pool_t *p)
{
- Skiplist *sl;
+ ap_skiplist *sl;
skiplisti_init(s, p);
sl = *s;
skiplisti_init(&(sl->index), p);
- skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
+ ap_skiplist_set_compare(sl->index, indexing_comp, indexing_compk);
return APR_SUCCESS;
}
-void skiplist_set_compare(Skiplist *sl,
- SkiplistComparator comp,
- SkiplistComparator compk)
+void ap_skiplist_set_compare(ap_skiplist *sl,
+ ap_skiplist_compare comp,
+ ap_skiplist_compare compk)
{
if (sl->compare && sl->comparek) {
- skiplist_add_index(sl, comp, compk);
+ ap_skiplist_add_index(sl, comp, compk);
}
else {
sl->compare = comp;
@@ -121,29 +121,29 @@ void skiplist_set_compare(Skiplist *sl,
}
}
-void skiplist_add_index(Skiplist *sl,
- SkiplistComparator comp,
- SkiplistComparator compk)
+void ap_skiplist_add_index(ap_skiplist *sl,
+ ap_skiplist_compare comp,
+ ap_skiplist_compare compk)
{
- skiplistnode *m;
- Skiplist *ni;
+ ap_skiplistnode *m;
+ ap_skiplist *ni;
int icount = 0;
- skiplist_find(sl->index, (void *)comp, &m);
+ ap_skiplist_find(sl->index, (void *)comp, &m);
if (m) {
return; /* Index already there! */
}
skiplisti_init(&ni, sl->pool);
- skiplist_set_compare(ni, comp, compk);
+ ap_skiplist_set_compare(ni, comp, compk);
/* Build the new index... This can be expensive! */
- m = skiplist_insert(sl->index, ni);
+ m = ap_skiplist_insert(sl->index, ni);
while (m->prev) {
m = m->prev;
icount++;
}
- for (m = skiplist_getlist(sl); m; skiplist_next(sl, &m)) {
+ for (m = ap_skiplist_getlist(sl); m; ap_skiplist_next(sl, &m)) {
int j = icount - 1;
- skiplistnode *nsln;
- nsln = skiplist_insert(ni, m->data);
+ ap_skiplistnode *nsln;
+ nsln = ap_skiplist_insert(ni, m->data);
/* skip from main index down list */
while (j > 0) {
m = m->nextindex;
@@ -159,7 +159,7 @@ void skiplist_add_index(Skiplist *sl,
}
}
-skiplistnode *skiplist_getlist(Skiplist *sl)
+ap_skiplistnode *ap_skiplist_getlist(ap_skiplist *sl)
{
if (!sl->bottom) {
return NULL;
@@ -167,27 +167,27 @@ skiplistnode *skiplist_getlist(Skiplist
return sl->bottom->next;
}
-void *skiplist_find(Skiplist *sl, void *data, skiplistnode **iter)
+void *ap_skiplist_find(ap_skiplist *sl, void *data, ap_skiplistnode **iter)
{
void *ret;
- skiplistnode *aiter;
+ ap_skiplistnode *aiter;
if (!sl->compare) {
return 0;
}
if (iter) {
- ret = skiplist_find_compare(sl, data, iter, sl->compare);
+ ret = ap_skiplist_find_compare(sl, data, iter, sl->compare);
}
else {
- ret = skiplist_find_compare(sl, data, &aiter, sl->compare);
+ ret = ap_skiplist_find_compare(sl, data, &aiter, sl->compare);
}
return ret;
}
-static int skiplisti_find_compare(Skiplist *sl, void *data,
- skiplistnode **ret,
- SkiplistComparator comp)
+static int skiplisti_find_compare(ap_skiplist *sl, void *data,
+ ap_skiplistnode **ret,
+ ap_skiplist_compare comp)
{
- skiplistnode *m = NULL;
+ ap_skiplistnode *m = NULL;
int count = 0;
m = sl->top;
while (m) {
@@ -214,26 +214,26 @@ static int skiplisti_find_compare(Skipli
return count;
}
-void *skiplist_find_compare(Skiplist *sli, void *data,
- skiplistnode **iter,
- SkiplistComparator comp)
+void *ap_skiplist_find_compare(ap_skiplist *sli, void *data,
+ ap_skiplistnode **iter,
+ ap_skiplist_compare comp)
{
- skiplistnode *m = NULL;
- Skiplist *sl;
+ ap_skiplistnode *m = NULL;
+ ap_skiplist *sl;
if (comp == sli->compare || !sli->index) {
sl = sli;
}
else {
- skiplist_find(sli->index, (void *)comp, &m);
+ ap_skiplist_find(sli->index, (void *)comp, &m);
AP_DEBUG_ASSERT(m);
- sl = (Skiplist *) m->data;
+ sl = (ap_skiplist *) m->data;
}
skiplisti_find_compare(sl, data, iter, sl->comparek);
return (*iter) ? ((*iter)->data) : (*iter);
}
-void *skiplist_next(Skiplist *sl, skiplistnode **iter)
+void *ap_skiplist_next(ap_skiplist *sl, ap_skiplistnode **iter)
{
if (!*iter) {
return NULL;
@@ -242,7 +242,7 @@ void *skiplist_next(Skiplist *sl, skipli
return (*iter) ? ((*iter)->data) : NULL;
}
-void *skiplist_previous(Skiplist *sl, skiplistnode **iter)
+void *ap_skiplist_previous(ap_skiplist *sl, ap_skiplistnode **iter)
{
if (!*iter) {
return NULL;
@@ -251,32 +251,32 @@ void *skiplist_previous(Skiplist *sl, sk
return (*iter) ? ((*iter)->data) : NULL;
}
-skiplistnode *skiplist_insert(Skiplist *sl, void *data)
+ap_skiplistnode *ap_skiplist_insert(ap_skiplist *sl, void *data)
{
if (!sl->compare) {
return 0;
}
- return skiplist_insert_compare(sl, data, sl->compare);
+ return ap_skiplist_insert_compare(sl, data, sl->compare);
}
-skiplistnode *skiplist_insert_compare(Skiplist *sl, void *data,
- SkiplistComparator comp)
+ap_skiplistnode *ap_skiplist_insert_compare(ap_skiplist *sl, void *data,
+ ap_skiplist_compare comp)
{
- skiplistnode *m, *p, *tmp, *ret, **stack;
+ ap_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_skiplistnode *)ap_skiplist_alloc(sl, sizeof(ap_skiplistnode));
AP_DEBUG_ASSERT(sl->top);
#if 0
- 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->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;
}
@@ -297,7 +297,7 @@ skiplistnode *skiplist_insert_compare(Sk
*/
for (; sl->height < nh; sl->height++) {
sl->top->up =
- (skiplistnode *)skiplist_alloc(sl, sizeof(skiplistnode));
+ (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;
@@ -313,7 +313,7 @@ skiplistnode *skiplist_insert_compare(Sk
/* 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));
+ stack = (ap_skiplistnode **)ap_malloc(sizeof(ap_skiplistnode *) * (nh));
stacki = 0;
while (m) {
int compared = -1;
@@ -340,7 +340,7 @@ skiplistnode *skiplist_insert_compare(Sk
p = NULL;
for (; stacki > 0; stacki--) {
m = stack[stacki - 1];
- tmp = (skiplistnode *)skiplist_alloc(sl, sizeof(skiplistnode));
+ tmp = (ap_skiplistnode *)ap_skiplist_alloc(sl, sizeof(ap_skiplistnode));
tmp->next = m->next;
if (m->next) {
m->next->prev = tmp;
@@ -368,10 +368,10 @@ skiplistnode *skiplist_insert_compare(Sk
* this is a external insertion, we must insert into each index as
* well
*/
- skiplistnode *p, *ni, *li;
+ ap_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);
+ 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;
@@ -384,161 +384,18 @@ skiplistnode *skiplist_insert_compare(Sk
return ret;
}
-#if 0
-/*
- * 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;
-}
-#endif
-
-int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree)
+int ap_skiplist_remove(ap_skiplist *sl, void *data, ap_skiplist_freefunc myfree)
{
if (!sl->compare) {
return 0;
}
- return skiplist_remove_compare(sl, data, myfree, sl->comparek);
+ return ap_skiplist_remove_compare(sl, data, myfree, sl->comparek);
}
#if 0
-void skiplist_print_struct(Skiplist * sl, char *prefix)
+void skiplist_print_struct(ap_skiplist * sl, char *prefix)
{
- skiplistnode *p, *q;
+ ap_skiplistnode *p, *q;
fprintf(stderr, "Skiplist Structure (height: %d)\n", sl->height);
p = sl->bottom;
while (p) {
@@ -554,9 +411,9 @@ void skiplist_print_struct(Skiplist * sl
}
#endif
-static int skiplisti_remove(Skiplist *sl, skiplistnode *m, FreeFunc myfree)
+static int skiplisti_remove(ap_skiplist *sl, ap_skiplistnode *m, ap_skiplist_freefunc myfree)
{
- skiplistnode *p;
+ ap_skiplistnode *p;
if (!m) {
return 0;
}
@@ -577,7 +434,7 @@ static int skiplisti_remove(Skiplist *sl
if (!m && myfree && p->data) {
myfree(p->data);
}
- skiplist_free(sl, p);
+ ap_skiplist_free(sl, p);
}
sl->size--;
while (sl->top && sl->top->next == NULL) {
@@ -587,7 +444,7 @@ static int skiplisti_remove(Skiplist *sl
if (sl->top) {
sl->top->up = NULL; /* Make it think its the top */
}
- skiplist_free(sl, p);
+ ap_skiplist_free(sl, p);
sl->height--;
}
if (!sl->top) {
@@ -597,19 +454,19 @@ static int skiplisti_remove(Skiplist *sl
return sl->height; /* return 1; ?? */
}
-int skiplist_remove_compare(Skiplist *sli,
+int ap_skiplist_remove_compare(ap_skiplist *sli,
void *data,
- FreeFunc myfree, SkiplistComparator comp)
+ ap_skiplist_freefunc myfree, ap_skiplist_compare comp)
{
- skiplistnode *m;
- Skiplist *sl;
+ ap_skiplistnode *m;
+ ap_skiplist *sl;
if (comp == sli->comparek || !sli->index) {
sl = sli;
}
else {
- skiplist_find(sli->index, (void *)comp, &m);
+ ap_skiplist_find(sli->index, (void *)comp, &m);
AP_DEBUG_ASSERT(m);
- sl = (Skiplist *) m->data;
+ sl = (ap_skiplist *) m->data;
}
skiplisti_find_compare(sl, data, &m, comp);
if (!m) {
@@ -621,14 +478,14 @@ int skiplist_remove_compare(Skiplist *sl
return skiplisti_remove(sl, m, myfree);
}
-void skiplist_remove_all(Skiplist *sl, FreeFunc myfree)
+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
*/
- skiplistnode *m, *p, *u;
+ ap_skiplistnode *m, *p, *u;
m = sl->bottom;
while (m) {
p = m->next;
@@ -636,7 +493,7 @@ void skiplist_remove_all(Skiplist *sl, F
myfree(p->data);
while (m) {
u = m->up;
- skiplist_free(sl, p);
+ ap_skiplist_free(sl, p);
m = u;
}
m = p;
@@ -646,11 +503,11 @@ void skiplist_remove_all(Skiplist *sl, F
sl->size = 0;
}
-void *skiplist_pop(Skiplist *a, FreeFunc myfree)
+void *ap_skiplist_pop(ap_skiplist *a, ap_skiplist_freefunc myfree)
{
- skiplistnode *sln;
+ ap_skiplistnode *sln;
void *data = NULL;
- sln = skiplist_getlist(a);
+ sln = ap_skiplist_getlist(a);
if (sln) {
data = sln->data;
skiplisti_remove(a, sln, myfree);
@@ -658,10 +515,10 @@ void *skiplist_pop(Skiplist *a, FreeFunc
return data;
}
-void *skiplist_peek(Skiplist *a)
+void *ap_skiplist_peek(ap_skiplist *a)
{
- skiplistnode *sln;
- sln = skiplist_getlist(a);
+ ap_skiplistnode *sln;
+ sln = ap_skiplist_getlist(a);
if (sln) {
return sln->data;
}
@@ -670,24 +527,24 @@ void *skiplist_peek(Skiplist *a)
static void skiplisti_destroy(void *vsl)
{
- skiplist_destroy((Skiplist *) vsl, NULL);
- skiplist_free((Skiplist *) vsl, vsl);
+ ap_skiplist_destroy((ap_skiplist *) vsl, NULL);
+ ap_skiplist_free((ap_skiplist *) vsl, vsl);
}
-void skiplist_destroy(Skiplist *sl, FreeFunc myfree)
+void ap_skiplist_destroy(ap_skiplist *sl, ap_skiplist_freefunc myfree)
{
- while (skiplist_pop(sl->index, skiplisti_destroy) != NULL)
+ while (ap_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
;
- skiplist_remove_all(sl, myfree);
+ ap_skiplist_remove_all(sl, myfree);
}
-Skiplist *skiplist_merge(Skiplist *sl1, Skiplist *sl2)
+ap_skiplist *ap_skiplist_merge(ap_skiplist *sl1, ap_skiplist *sl2)
{
/* Check integrity! */
- Skiplist temp;
- struct skiplistnode *b2;
+ ap_skiplist temp;
+ struct ap_skiplistnode *b2;
if (sl1->bottomend == NULL || sl1->bottomend->prev == NULL) {
- skiplist_remove_all(sl1, NULL);
+ ap_skiplist_remove_all(sl1, NULL);
temp = *sl1;
*sl1 = *sl2;
*sl2 = temp;
@@ -695,15 +552,15 @@ Skiplist *skiplist_merge(Skiplist *sl1,
return sl1;
}
if(sl2->bottom == NULL || sl2->bottom->next == NULL) {
- skiplist_remove_all(sl2, NULL);
+ ap_skiplist_remove_all(sl2, NULL);
return sl1;
}
/* This is what makes it brute force... Just insert :/ */
- b2 = skiplist_getlist(sl2);
+ b2 = ap_skiplist_getlist(sl2);
while (b2) {
- skiplist_insert(sl1, b2->data);
- skiplist_next(sl2, &b2);
+ ap_skiplist_insert(sl1, b2->data);
+ ap_skiplist_next(sl2, &b2);
}
- skiplist_remove_all(sl2, NULL);
+ ap_skiplist_remove_all(sl2, NULL);
return sl1;
}
Modified: httpd/httpd/trunk/server/mpm/eventopt/skiplist.h
URL: http://svn.apache.org/viewvc/httpd/httpd/trunk/server/mpm/eventopt/skiplist.h?rev=1451616&r1=1451615&r2=1451616&view=diff
==============================================================================
--- httpd/httpd/trunk/server/mpm/eventopt/skiplist.h (original)
+++ httpd/httpd/trunk/server/mpm/eventopt/skiplist.h Fri Mar 1 15:24:05 2013
@@ -24,100 +24,82 @@
/* 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 int (*ap_skiplist_compare) (void *, void *);
+typedef void (*ap_skiplist_freefunc) (void *);
-typedef struct skiplistnode skiplistnode;
-typedef struct Skiplist Skiplist;
+typedef struct ap_skiplistnode ap_skiplistnode;
+typedef struct ap_skiplist ap_skiplist;
-struct Skiplist {
- SkiplistComparator compare;
- SkiplistComparator comparek;
+struct ap_skiplist {
+ ap_skiplist_compare compare;
+ ap_skiplist_compare comparek;
int height;
int preheight;
int size;
- skiplistnode *top;
- skiplistnode *bottom;
+ ap_skiplistnode *top;
+ ap_skiplistnode *bottom;
/* These two are needed for appending */
- skiplistnode *topend;
- skiplistnode *bottomend;
- Skiplist *index;
+ ap_skiplistnode *topend;
+ ap_skiplistnode *bottomend;
+ ap_skiplist *index;
apr_pool_t *pool;
};
-struct skiplistnode {
+struct ap_skiplistnode {
void *data;
- skiplistnode *next;
- skiplistnode *prev;
- skiplistnode *down;
- skiplistnode *up;
- skiplistnode *previndex;
- skiplistnode *nextindex;
- Skiplist *sl;
+ ap_skiplistnode *next;
+ ap_skiplistnode *prev;
+ ap_skiplistnode *down;
+ ap_skiplistnode *up;
+ ap_skiplistnode *previndex;
+ ap_skiplistnode *nextindex;
+ ap_skiplist *sl;
};
-void *skiplist_alloc(Skiplist *sl, size_t size);
+void *ap_skiplist_alloc(ap_skiplist *sl, size_t size);
-void skiplist_free(Skiplist *sl, void *mem);
+void ap_skiplist_free(ap_skiplist *sl, void *mem);
-apr_status_t skiplist_init(Skiplist **sl, apr_pool_t *p);
+apr_status_t ap_skiplist_init(ap_skiplist **sl, apr_pool_t *p);
-void skiplist_set_compare(Skiplist *sl, SkiplistComparator,
- SkiplistComparator);
+void ap_skiplist_set_compare(ap_skiplist *sl, ap_skiplist_compare,
+ ap_skiplist_compare);
-void skiplist_add_index(Skiplist *sl, SkiplistComparator,
- SkiplistComparator);
+void ap_skiplist_add_index(ap_skiplist *sl, ap_skiplist_compare,
+ ap_skiplist_compare);
-skiplistnode *skiplist_getlist(Skiplist *sl);
+ap_skiplistnode *ap_skiplist_getlist(ap_skiplist *sl);
-void *skiplist_find_compare(Skiplist *sl,
+void *ap_skiplist_find_compare(ap_skiplist *sl,
void *data,
- skiplistnode **iter,
- SkiplistComparator func);
+ ap_skiplistnode **iter,
+ ap_skiplist_compare func);
-void *skiplist_find(Skiplist *sl, void *data, skiplistnode **iter);
+void *ap_skiplist_find(ap_skiplist *sl, void *data, ap_skiplistnode **iter);
-void *skiplist_next(Skiplist *sl, skiplistnode **iter);
+void *ap_skiplist_next(ap_skiplist *sl, ap_skiplistnode **iter);
-void *skiplist_previous(Skiplist *sl, skiplistnode **iter);
+void *ap_skiplist_previous(ap_skiplist *sl, ap_skiplistnode **iter);
-skiplistnode *skiplist_insert_compare(Skiplist *sl,
- void *data, SkiplistComparator comp);
+ap_skiplistnode *ap_skiplist_insert_compare(ap_skiplist *sl,
+ void *data, ap_skiplist_compare comp);
-skiplistnode *skiplist_insert(Skiplist* sl, void *data);
+ap_skiplistnode *ap_skiplist_insert(ap_skiplist* sl, void *data);
-int skiplist_remove_compare(Skiplist *sl, void *data,
- FreeFunc myfree, SkiplistComparator comp);
+int ap_skiplist_remove_compare(ap_skiplist *sl, void *data,
+ ap_skiplist_freefunc myfree, ap_skiplist_compare comp);
-int skiplist_remove(Skiplist *sl, void *data, FreeFunc myfree);
+int ap_skiplist_remove(ap_skiplist *sl, void *data, ap_skiplist_freefunc myfree);
-#if 0
-int skiplisti_remove(Skiplist *sl, skiplistnode *m, FreeFunc myfree);
-#endif
-
-void skiplist_remove_all(Skiplist *sl, FreeFunc myfree);
+void ap_skiplist_remove_all(ap_skiplist *sl, ap_skiplist_freefunc myfree);
-void skiplist_destroy(Skiplist *sl, FreeFunc myfree);
+void ap_skiplist_destroy(ap_skiplist *sl, ap_skiplist_freefunc myfree);
-#if 0
-int skiplisti_find_compare(Skiplist *sl,
- void *data,
- skiplistnode **ret,
- SkiplistComparator comp);
-
-#endif
+void *ap_skiplist_pop(ap_skiplist *a, ap_skiplist_freefunc myfree);
-void *skiplist_pop(Skiplist *a, FreeFunc myfree);
-
-void *skiplist_peek(Skiplist *a);
-
-/* Below 2 are buggy */
-#if 0
-Skiplist *skiplist_concat(Skiplist *sl1, Skiplist *sl2);
-skiplistnode *skiplist_append(Skiplist *sl, void *data);
-#endif
+void *ap_skiplist_peek(ap_skiplist *a);
-Skiplist *skiplist_merge(Skiplist *sl1, Skiplist *sl2);
+ap_skiplist *ap_skiplist_merge(ap_skiplist *sl1, ap_skiplist *sl2);
#endif