Merge r1672366 from trunk.

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: http://svn.apache.org/repos/asf/apr/apr/branches/1.5.x@1672384 13f79535-47bb-0310-9956-ffa450edef68

1 files changed, 13 insertions, 4 deletions

diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c
index 8b8f2fa1e..a61ec25a3 100644
--- a/tables/apr_skiplist.c
+++ b/tables/apr_skiplist.c
@@ -393,27 +393,36 @@ APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **i
     return (*iter) ? ((*iter)->data) : NULL;
 }
 
+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;
+}
+
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
                                       apr_skiplist_compare comp)
 {
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
-    int nh = 1, ch;
+    int ch, nh = 1;
 
     if (!comp) {
         return NULL;
     }
 
+    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;
 
     /* 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
@@ -580,7 +589,7 @@ static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_
         sl->bottom = sl->bottomend = NULL;
         sl->topend = NULL;
     }
-    return sl->height;  /* return 1; ?? */
+    return skiplist_height(sl);
 }
 
 APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,