diff options
author | Yann Ylavic <ylavic@apache.org> | 2015-04-07 21:35:50 +0000 |
---|---|---|
committer | Yann Ylavic <ylavic@apache.org> | 2015-04-07 21:35:50 +0000 |
commit | 4f77d951481f9b8090f28aa21b34512baf5f206e (patch) | |
tree | b15668d0339ebb20a56be17bfc78971cd1424cd0 /tables | |
parent | 159af04c9ec57e460b15e4ed602b7387720a03c5 (diff) | |
download | apr-4f77d951481f9b8090f28aa21b34512baf5f206e.tar.gz |
Introduce apr_skiplist_last[_compare]() and apr_skiplist_remove_node().
The apr_skiplist_last[_compare]() functions return the last matching element
(duplicate) whereas the existing apr_skiplist_find[_compare]() return the first
one encountered during the walk.
The function apr_skiplist_remove_node() function allows to remove an element
given its node, e.g. an iterator from apr_skiplist_{getlist,previous,next}().
The goal is to have a reliable way to find (and remove) any element having a
unique address/pointer, by starting with the last duplicate and then iterating
on the previous ones until the match (see example in testskiplist.c).
apr_skiplist_last() is much more efficient than apr_skiplist_first() would be,
git-svn-id: https://svn.apache.org/repos/asf/apr/apr/trunk@1671957 13f79535-47bb-0310-9956-ffa450edef68
Diffstat (limited to 'tables')
-rw-r--r-- | tables/apr_skiplist.c | 80 |
1 files changed, 63 insertions, 17 deletions
diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c index a8794c069..4078dd03e 100644 --- a/tables/apr_skiplist.c +++ b/tables/apr_skiplist.c @@ -299,21 +299,21 @@ APR_DECLARE(void) apr_skiplist_add_index(apr_skiplist *sl, } static int skiplisti_find_compare(apr_skiplist *sl, void *data, - apr_skiplistnode **ret, - apr_skiplist_compare comp) + apr_skiplistnode **ret, + apr_skiplist_compare comp, + int last) { int count = 0; - apr_skiplistnode *m; + apr_skiplistnode *m, *found = NULL; for (m = sl->top; m; count++) { if (m->next) { int compared = comp(data, m->next->data); if (compared == 0) { - m = m->next; - while (m->down) { - m = m->down; + found = m = m->next; + if (!last) { + break; } - *ret = m; - return count; + continue; } if (compared > 0) { m = m->next; @@ -322,13 +322,22 @@ static int skiplisti_find_compare(apr_skiplist *sl, void *data, } m = m->down; } - *ret = NULL; + if (found) { + while (found->down) { + found = found->down; + } + *ret = found; + } + else { + *ret = NULL; + } return count; } -APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data, - apr_skiplistnode **iter, - apr_skiplist_compare comp) +static void *find_compare(apr_skiplist *sli, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp, + int last) { apr_skiplistnode *m; apr_skiplist *sl; @@ -351,16 +360,36 @@ APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data, } sl = (apr_skiplist *) m->data; } - skiplisti_find_compare(sl, data, &m, sl->comparek); + skiplisti_find_compare(sl, data, &m, sl->comparek, last); if (iter) { *iter = m; } return (m) ? m->data : NULL; } +APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp) +{ + return find_compare(sl, data, iter, comp, 0); +} + APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter) { - return apr_skiplist_find_compare(sl, data, iter, sl->compare); + return find_compare(sl, data, iter, sl->compare, 0); +} + +APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data, + apr_skiplistnode **iter, + apr_skiplist_compare comp) +{ + return find_compare(sl, data, iter, comp, 1); +} + +APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data, + apr_skiplistnode **iter) +{ + return find_compare(sl, data, iter, sl->compare, 1); } @@ -390,9 +419,9 @@ APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **i return (*iter) ? ((*iter)->data) : NULL; } -APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *node) +APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter) { - return node->data; + return (iter) ? iter->data : NULL; } /* forward declared */ @@ -643,6 +672,23 @@ static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, return sl->height; /* return 1; ?? */ } +APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl, + apr_skiplistnode *iter, + apr_skiplist_freefunc myfree) +{ + apr_skiplistnode *m = iter; + if (!m) { + return 0; + } + while (m->down) { + m = m->down; + } + while (m->previndex) { + m = m->previndex; + } + return skiplisti_remove(sl, m, myfree); +} + APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli, void *data, apr_skiplist_freefunc myfree, apr_skiplist_compare comp) @@ -662,7 +708,7 @@ APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli, } sl = (apr_skiplist *) m->data; } - skiplisti_find_compare(sl, data, &m, comp); + skiplisti_find_compare(sl, data, &m, comp, 0); if (!m) { return 0; } |