skiplist: more optimizations.

We don't need to create the top before inserting, this will be done
if/once the value is really added (since r1611193).

Check compare value only if m->next is not NULL, otherwise we already
known it is to be handled as negative (down).


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

1 files changed, 26 insertions, 45 deletions

diff --git a/tables/apr_skiplist.c b/tables/apr_skiplist.c
index 9dd595f0f..1bc38e64f 100644
--- a/tables/apr_skiplist.c
+++ b/tables/apr_skiplist.c
@@ -311,9 +311,8 @@ static int skiplisti_find_compare(apr_skiplist *sl, void *data,
     apr_skiplistnode *m;
     m = sl->top;
     while (m) {
-        int compared;
         if (m->next) {
-            compared = comp(data, m->next->data);
+            int compared = comp(data, m->next->data);
             if (compared == 0) {
                 m = m->next;
                 while (m->down) {
@@ -322,18 +321,14 @@ static int skiplisti_find_compare(apr_skiplist *sl, void *data,
                 *ret = m;
                 return count;
             }
+            if (compared > 0) {
+                m = m->next;
+                count++;
+                continue;
+            }
         }
-        else {
-            compared = -1;
-        }
-        if (compared < 0) {
-            m = m->down;
-            count++;
-        }
-        else {
-            m = m->next;
-            count++;
-        }
+        m = m->down;
+        count++;
     }
     *ret = NULL;
     return count;
@@ -389,19 +384,7 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
 {
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
     int nh = 1, ch;
-    if (!sl->top) {
-        sl->height = 1;
-        sl->topend = sl->bottomend = sl->top = sl->bottom =
-            (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
-        sl->top->next = NULL;
-        sl->top->data = NULL;
-        sl->top->prev = NULL;
-        sl->top->up = NULL;
-        sl->top->down = NULL;
-        sl->top->nextindex = NULL;
-        sl->top->previndex = NULL;
-        sl->top->sl = sl;
-    }
+
     if (sl->preheight) {
         while (nh < sl->preheight && get_b_rand()) {
             nh++;
@@ -423,33 +406,28 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
      */
     m = sl->top;
     while (m) {
-        int compared;
+        /*
+         * To maintain stability, dups (compared == 0) must be added
+         * AFTER each other.
+         */
         if (m->next) {
-            compared = comp(data, m->next->data);
+            int compared = comp(data, m->next->data);
             if (compared == 0 && !add) {
                 /* Keep the existing element(s) */
                 skiplist_stack_clear(sl);
                 return NULL;
             }
-        }
-        else {
-            compared = -1;
-        }
-        /*
-         * To maintain stability, dups must be added AFTER each
-         * other.
-         */
-        if (compared <= 0) {
-            if (ch <= nh) {
-                /* push on stack */
-                skiplist_stack_push(sl, m);
+            if (compared > 0) {
+                m = m->next;
+                continue;
             }
-            m = m->down;
-            ch--;
         }
-        else {
-            m = m->next;
+        if (ch <= nh) {
+            /* push on stack */
+            skiplist_stack_push(sl, m);
         }
+        m = m->down;
+        ch--;
     }
     /* Pop the stack and insert nodes */
     p = NULL;
@@ -496,7 +474,10 @@ static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
         tmp->down = p;
         tmp->data = data;
         tmp->sl = sl;
-        p = p->up = tmp;
+        if (p) {
+            p->up = tmp;
+        }
+        p = tmp;
     }
     if (sl->index != NULL) {
         /*