skiplist: fix the minimum height (to one).

The height of a skiplist is always at least one, for the top node,
even if our implementation may delay its creation on the first insert
or delete it on the last remove (for optimization purpose).
This also helps apr_skiplist_remove() to never return zero (not found)
when it deletes the last node.


git-svn-id: https://svn.apache.org/repos/asf/apr/apr/trunk@1672366 13f79535-47bb-0310-9956-ffa450edef68

2 files changed, 18 insertions, 8 deletions

diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c
index 6075bb60c..b5027ecf7 100644
--- a/tables/apr_skiplist.c
+++ b/tables/apr_skiplist.c
@@ -428,24 +428,34 @@ APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter)
 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
                             apr_skiplist_freefunc myfree);
 
+static APR_INLINE int skiplist_height(const apr_skiplist *sl)
+{
+    /* Skiplists (even empty) always have a top node, although this
+     * implementation defers its creation until the first insert, or
+     * deletes it with the last remove. We want the real height here.
+     */
+    return sl->height ? sl->height : 1;
+}
+
 static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
                                         apr_skiplist_compare comp, int add,
                                         apr_skiplist_freefunc myfree)
 {
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
-    int ch, nh = 1;
+    int ch, top_nh, nh = 1;
 
+    ch = skiplist_height(sl);
     if (sl->preheight) {
         while (nh < sl->preheight && get_b_rand()) {
             nh++;
         }
     }
     else {
-        while (nh <= sl->height && get_b_rand()) {
+        while (nh <= ch && get_b_rand()) {
             nh++;
         }
     }
-    ch = sl->height;
+    top_nh = nh;
 
     /* Now we have in nh the height at which we wish to insert our new node,
      * and in ch the current height: don't create skip paths to the inserted
@@ -477,8 +487,8 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
                     if (top != sl->top) {
                         m = sl->top;
                         skiplist_qclear(&sl->stack_q);
-                        ch = sl->height;
-                        nh = ch + 1;
+                        ch = skiplist_height(sl);
+                        nh = top_nh;
                     }
                     continue;
                 }
@@ -673,7 +683,7 @@ static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
         sl->bottom = sl->bottomend = NULL;
         sl->topend = NULL;
     }
-    return sl->height;  /* return 1; ?? */
+    return skiplist_height(sl);
 }
 
 APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
@@ -783,7 +793,7 @@ APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
 
 APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
 {
-    return sl->height;
+    return skiplist_height(sl);
 }
 
 APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
diff --git a/test/testskiplist.c b/test/testskiplist.c
index f342abf4f..3e5570f73 100644
--- a/test/testskiplist.c
+++ b/test/testskiplist.c
@@ -185,7 +185,7 @@ static void skiplist_destroy(abts_case *tc, void *data)
 {
     apr_skiplist_destroy(skiplist, NULL);
     ABTS_TRUE(tc, 0 == apr_skiplist_size(skiplist));
-    ABTS_TRUE(tc, 0 == apr_skiplist_height(skiplist));
+    ABTS_TRUE(tc, 1 == apr_skiplist_height(skiplist));
     ABTS_TRUE(tc, NULL == apr_skiplist_getlist(skiplist));
 }