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

3 files changed, 159 insertions, 17 deletions

diff --git a/include/apr_skiplist.h b/include/apr_skiplist.h
index b85289674..1e7ab258c 100644
--- a/include/apr_skiplist.h
+++ b/include/apr_skiplist.h
@@ -153,6 +153,30 @@ APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl,
 APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter);
 
 /**
+ * Return the last matching element in the skip list using the specified
+ * comparison function.
+ * @param sl The skip list
+ * @param data The value to search for
+ * @param iter A pointer to the returned skip list node representing the element
+ * found
+ * @param func The comparison function to use
+ */
+APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sli, void *data,
+                                              apr_skiplistnode **iter,
+                                              apr_skiplist_compare comp);
+
+/**
+ * Return the last matching element in the skip list using the current comparison
+ * function.
+ * @param sl The skip list
+ * @param data The value to search for
+ * @param iter A pointer to the returned skip list node representing the element
+ * found
+ */
+APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data,
+                                      apr_skiplistnode **iter);
+
+/**
  * Return the next element in the skip list.
  * @param sl The skip list
  * @param iter On entry, a pointer to the skip list node to start with; on return,
@@ -243,6 +267,16 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
                                     void *data, apr_skiplist_freefunc myfree);
 
 /**
+ * Remove a node from the skip list.
+ * @param sl The skip list
+ * @param iter The skip list node to remove
+ * @param myfree A function to be called for the removed element
+ */
+APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
+                                          apr_skiplistnode *iter,
+                                          apr_skiplist_freefunc myfree);
+
+/**
  * Remove an element from the skip list using the specified comparison function for
  * locating the element. In the case of duplicates, the 1st entry will be removed.
  * @param sl The skip list
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;
     }
diff --git a/test/testskiplist.c b/test/testskiplist.c
index 5f5b77c6a..91a4403df 100644
--- a/test/testskiplist.c
+++ b/test/testskiplist.c
@@ -317,6 +317,34 @@ static int acomp(void *a, void *b){
     }
 }
 
+/* If we add multiple duplicates and then try to remove each one
+ * individually (unique pointer) in arbitrary order, by using:
+ * - apr_skiplist_remove_compare(..., scomp, NULL)
+ *   There is no pointer comparison with scomp(), so will likely
+ *   remove any duplicate (the first encountered in the walking path).
+ * - apr_skiplist_remove_compare(..., acomp, NULL)
+ *   The exact element to be removed may be skipped in the walking path
+ *   because some "bigger" element (or duplicate) was added later with a
+ *   higher height.
+ * Hence we use skiplist_remove_scomp() which will go straight to the last
+ * duplicate (using scomp) and then iterate on the previous elements until
+ * pointers match.
+ * This pattern could be reused by any application which wants to remove
+ * elements by (unique) pointer.
+ */
+static void skiplist_remove_scomp(abts_case *tc, apr_skiplist *list, elem *n)
+{
+    elem *e;
+    apr_skiplistnode *iter = NULL;
+    e = apr_skiplist_last(list, n, &iter);
+    while (e && e != n) {
+        ABTS_INT_EQUAL(tc, 0, scomp(n, e));
+        e = apr_skiplist_previous(list, &iter);
+    }
+    ABTS_PTR_EQUAL(tc, n, apr_skiplist_element(iter));
+    apr_skiplist_remove_node(list, iter, NULL);
+}
+
 static void skiplist_test(abts_case *tc, void *data) {
     int test_elems = 10;
     int i = 0, j = 0;
@@ -325,6 +353,7 @@ static void skiplist_test(abts_case *tc, void *data) {
     apr_skiplist * list = NULL;
     apr_skiplist * list2 = NULL;
     apr_skiplist * list3 = NULL;
+    apr_skiplist * list4 = NULL;
     int first_forty_two = 42,
         second_forty_two = 42;
     elem t1, t2, t3, t4, t5;
@@ -426,6 +455,39 @@ static void skiplist_test(abts_case *tc, void *data) {
     val2 = apr_skiplist_find(list3, &t2, NULL);
     ABTS_PTR_EQUAL(tc, NULL, val2);
 
+    ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list4, ptmp));
+    apr_skiplist_set_compare(list4, scomp, scomp);
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t1);
+    }
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t2);
+    }
+    apr_skiplist_add(list4, &t2);
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t2);
+    }
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t3);
+    }
+    apr_skiplist_add(list4, &t3);
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t3);
+    }
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t4);
+    }
+    apr_skiplist_add(list4, &t4);
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t4);
+    }
+    for (i = 0; i < 5; ++i){
+        add_elem_to_skiplist(list4, t5);
+    }
+    skiplist_remove_scomp(tc, list4, &t2);
+    skiplist_remove_scomp(tc, list4, &t3);
+    skiplist_remove_scomp(tc, list4, &t4);
+
     apr_pool_clear(ptmp);
 }