Don't grow the skiplist's height if the element is finally not inserted (preserve semantic).

Do this by moving the top node creation after insertion occured, and linking to the just
inserted node(s).


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

1 files changed, 33 insertions, 18 deletions

diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c
index 6d29b0730..1a57d4ee7 100644
--- a/tables/apr_skiplist.c
+++ b/tables/apr_skiplist.c
@@ -407,25 +407,15 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
             nh++;
         }
     }
-    /* Now we have the new height at which we wish to insert our new node */
-    /*
-     * Let us make sure that our tree is a least that tall (grow if
-     * necessary)
-     */
-    for (; sl->height < nh; sl->height++) {
-        sl->top->up =
-            (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
-        sl->top->up->down = sl->top;
-        sl->top = sl->topend = sl->top->up;
-        sl->top->prev = sl->top->next = sl->top->nextindex =
-            sl->top->previndex = sl->top->up = NULL;
-        sl->top->data = NULL;
-        sl->top->sl = sl;
-    }
     ch = sl->height;
-    /* Find the node (or node after which we would insert) */
-    /* Keep a stack to pop back through for insertion */
-    /* malloc() is OK since we free the temp stack */
+
+    /* 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
+     * element until the walk down through the tree (which decrements ch)
+     * reaches nh. From there, any walk down pushes the current node on a
+     * stack (the node(s) after which we would insert) to pop back through
+     * for insertion later.
+     */
     m = sl->top;
     while (m) {
         int compared = -1;
@@ -473,6 +463,31 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
         m->next = tmp;
         p = tmp;
     }
+
+    /* Now we are sure the node is inserted, grow our tree to 'nh' tall */
+    for (; sl->height < nh; sl->height++) {
+        m = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
+        tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
+        m->up = m->prev = m->nextindex = m->previndex = NULL;
+        m->next = tmp;
+        m->down = sl->top;
+        m->data = NULL;
+        m->sl = sl;
+        if (sl->top) {
+            sl->top->up = m;
+        }
+        else {
+            sl->bottom = sl->bottomend = m;
+        }
+        sl->top = sl->topend = tmp->prev = m;
+        tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
+        tmp->down = p;
+        if (p) {
+            p->up = tmp;
+        }
+        tmp->data = data;
+        tmp->sl = sl;
+    }
     if (sl->index != NULL) {
         /*
          * this is a external insertion, we must insert into each index as