From 1979f12a56c55862dfc47c079ca9456fed5ac460 Mon Sep 17 00:00:00 2001 From: ylavic Date: Tue, 17 Mar 2015 22:42:46 +0000 Subject: skiplist: Introduce apr_skiplist_replace[_compare](). git-svn-id: http://svn.apache.org/repos/asf/apr/apr/trunk@1667420 13f79535-47bb-0310-9956-ffa450edef68 --- tables/apr_skiplist.c | 80 +++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 58 insertions(+), 22 deletions(-) (limited to 'tables/apr_skiplist.c') diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c index 6ceb7df9d..e053c56e3 100644 --- a/tables/apr_skiplist.c +++ b/tables/apr_skiplist.c @@ -201,7 +201,7 @@ static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl) return m; } -static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m) +static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m) { return skiplist_qpush(&sl->nodes_q, m); } @@ -304,8 +304,7 @@ static int skiplisti_find_compare(apr_skiplist *sl, void *data, { int count = 0; apr_skiplistnode *m; - m = sl->top; - while (m) { + for (m = sl->top; m; count++) { if (m->next) { int compared = comp(data, m->next->data); if (compared == 0) { @@ -318,12 +317,10 @@ static int skiplisti_find_compare(apr_skiplist *sl, void *data, } if (compared > 0) { m = m->next; - count++; continue; } } m = m->down; - count++; } *ret = NULL; return count; @@ -398,11 +395,16 @@ APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *node) return node->data; } +/* forward declared */ +static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, + apr_skiplist_freefunc myfree); + static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data, - apr_skiplist_compare comp, int add) + apr_skiplist_compare comp, int add, + apr_skiplist_freefunc myfree) { apr_skiplistnode *m, *p, *tmp, *ret = NULL; - int nh = 1, ch; + int ch, nh = 1; if (sl->preheight) { while (nh < sl->preheight && get_b_rand()) { @@ -431,10 +433,26 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data, */ if (m->next) { int compared = comp(data, m->next->data); - if (compared == 0 && !add) { - /* Keep the existing element(s) */ - skiplist_qclear(&sl->stack_q); - return NULL; + if (compared == 0) { + if (!add) { + /* Keep the existing element(s) */ + skiplist_qclear(&sl->stack_q); + return NULL; + } + if (add < 0) { + /* Remove this element and continue with the next node + * or the new top if the current one is also removed. + */ + apr_skiplistnode *top = sl->top; + skiplisti_remove(sl, m->next, myfree); + if (top != sl->top) { + m = sl->top; + skiplist_qclear(&sl->stack_q); + ch = sl->height; + nh = ch + 1; + } + continue; + } } if (compared >= 0) { m = m->next; @@ -507,7 +525,7 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data, li = ret; for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) { apr_skiplist *sli = (apr_skiplist *)p->data; - ni = insert_compare(sli, ret->data, sli->compare, add); + ni = insert_compare(sli, ret->data, sli->compare, add, myfree); li->nextindex = ni; ni->previndex = li; li = ni; @@ -523,7 +541,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, vo if (!comp) { return NULL; } - return insert_compare(sl, data, comp, 0); + return insert_compare(sl, data, comp, 0, NULL); } APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data) @@ -537,7 +555,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void if (!comp) { return NULL; } - return insert_compare(sl, data, comp, 1); + return insert_compare(sl, data, comp, 1, NULL); } APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data) @@ -545,6 +563,22 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data) return apr_skiplist_add_compare(sl, data, sl->compare); } +APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl, + void *data, apr_skiplist_freefunc myfree, + apr_skiplist_compare comp) +{ + if (!comp) { + return NULL; + } + return insert_compare(sl, data, comp, -1, myfree); +} + +APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl, + void *data, apr_skiplist_freefunc myfree) +{ + return apr_skiplist_replace_compare(sl, data, myfree, sl->compare); +} + #if 0 void skiplist_print_struct(apr_skiplist * sl, char *prefix) { @@ -564,7 +598,8 @@ void skiplist_print_struct(apr_skiplist * sl, char *prefix) } #endif -static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree) +static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, + apr_skiplist_freefunc myfree) { apr_skiplistnode *p; if (!m) { @@ -576,19 +611,20 @@ static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_ while (m->up) { m = m->up; } - while (m) { + do { p = m; - p->prev->next = p->next;/* take me out of the list */ + /* take me out of the list */ + p->prev->next = p->next; if (p->next) { - p->next->prev = p->prev; /* take me out of the list */ + p->next->prev = p->prev; } m = m->down; /* This only frees the actual data in the bottom one */ if (!m && myfree && p->data) { myfree(p->data); } - skiplist_free_node(sl, p); - } + skiplist_put_node(sl, p); + } while (m); sl->size--; while (sl->top && sl->top->next == NULL) { /* While the row is empty and we are not on the bottom row */ @@ -597,7 +633,7 @@ static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_ if (sl->top) { sl->top->up = NULL; /* Make it think its the top */ } - skiplist_free_node(sl, p); + skiplist_put_node(sl, p); sl->height--; } if (!sl->top) { @@ -657,7 +693,7 @@ APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefun } do { u = m->up; - skiplist_free_node(sl, m); + skiplist_put_node(sl, m); m = u; } while (m); m = p; -- cgit v1.2.1