apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yla...@apache.org
Subject svn commit: r1611184 - /apr/apr/trunk/tables/apr_skiplist.c
Date Wed, 16 Jul 2014 20:53:11 GMT
Author: ylavic
Date: Wed Jul 16 20:53:11 2014
New Revision: 1611184

URL: http://svn.apache.org/r1611184
Log:
Reuse the skiplist's stack needed by insert_compare() by growing it with adds.
Rename the "replace" as "add" (negating the boolean) to avoid confusion since
the skiplist never replaces any element (add or preserve semantic).

Modified:
    apr/apr/trunk/tables/apr_skiplist.c

Modified: apr/apr/trunk/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1611184&r1=1611183&r2=1611184&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_skiplist.c (original)
+++ apr/apr/trunk/tables/apr_skiplist.c Wed Jul 16 20:53:11 2014
@@ -38,6 +38,9 @@ struct apr_skiplist {
     apr_skiplistnode *bottomend;
     apr_skiplist *index;
     apr_array_header_t *memlist;
+    apr_skiplistnode **stack;
+    size_t stack_pos,
+           stack_len;
     apr_pool_t *pool;
 };
 
@@ -145,6 +148,43 @@ APR_DECLARE(void) apr_skiplist_free(apr_
     }
 }
 
+static apr_status_t skiplist_stack_push(apr_skiplist *sl, apr_skiplistnode *m)
+{
+    if (sl->stack_pos >= sl->stack_len) {
+        apr_skiplistnode **ptr;
+        size_t len = sl->stack_pos * 2;
+        if (len < 32) {
+            len = 32;
+        }
+        if (sl->pool) {
+            ptr = apr_palloc(sl->pool, len * sizeof(*ptr));
+            if (ptr) {
+                memcpy(ptr, sl->stack, sl->stack_pos * sizeof(*ptr));
+            }
+        }
+        else {
+            ptr = realloc(sl->stack, len * sizeof(*ptr));
+        }
+        if (!ptr) {
+            return APR_ENOMEM;
+        }
+        sl->stack = ptr;
+        sl->stack_len = len;
+    }
+    sl->stack[sl->stack_pos++] = m;
+    return APR_SUCCESS;
+}
+
+static APR_INLINE apr_skiplistnode *skiplist_stack_pop(apr_skiplist *sl)
+{
+    return (sl->stack_pos > 0) ? sl->stack[--sl->stack_pos] : NULL;
+}
+
+static APR_INLINE void skiplist_stack_clear(apr_skiplist *sl)
+{
+    sl->stack_pos = 0;
+}
+
 static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
 {
     apr_skiplist *sl;
@@ -340,10 +380,10 @@ APR_DECLARE(void *) apr_skiplist_previou
 }
 
 static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
-                                        apr_skiplist_compare comp, int replace)
+                                        apr_skiplist_compare comp, int add)
 {
-    apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack;
-    int nh = 1, ch, stacki;
+    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 =
@@ -387,21 +427,20 @@ static apr_skiplistnode *insert_compare(
     /* Keep a stack to pop back through for insertion */
     /* malloc() is OK since we free the temp stack */
     m = sl->top;
-    stack = (apr_skiplistnode **)malloc(sizeof(apr_skiplistnode *) * (nh));
-    stacki = 0;
     while (m) {
         int compared = -1;
         if (m->next) {
             compared = comp(data, m->next->data);
         }
-        if (compared == 0 && replace) {
-            free(stack);    /* OK. was malloc'ed */
+        if (compared == 0 && !add) {
+            /* Keep the existing element(s) */
+            skiplist_stack_clear(sl);
             return NULL;
         }
-        if ( (compared < 0) || (replace && (m->next == NULL)) ) {
+        if (compared < 0) {
             if (ch <= nh) {
                 /* push on stack */
-                stack[stacki++] = m;
+                skiplist_stack_push(sl, m);
             }
             m = m->down;
             ch--;
@@ -412,8 +451,7 @@ static apr_skiplistnode *insert_compare(
     }
     /* Pop the stack and insert nodes */
     p = NULL;
-    for (; stacki > 0; stacki--) {
-        m = stack[stacki - 1];
+    while ((m = skiplist_stack_pop(sl))) {
         tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
         tmp->next = m->next;
         if (m->next) {
@@ -426,16 +464,15 @@ static apr_skiplistnode *insert_compare(
         if (p) {
             p->up = tmp;
         }
+        else {
+            /* This sets ret to the bottom-most node we are inserting */
+            ret = tmp;
+        }
         tmp->data = data;
         tmp->sl = sl;
         m->next = tmp;
-        /* This sets ret to the bottom-most node we are inserting */
-        if (!p) {
-            ret = tmp;
-        }
         p = tmp;
     }
-    free(stack); /* OK. was malloc'ed */
     if (sl->index != NULL) {
         /*
          * this is a external insertion, we must insert into each index as
@@ -454,18 +491,24 @@ static apr_skiplistnode *insert_compare(
     return ret;
 }
 
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
+                                      apr_skiplist_compare comp)
+{
+    return insert_compare(sl, data, comp, 0);
+}
+
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
 {
     if (!sl->compare) {
         return NULL;
     }
-    return insert_compare(sl, data, sl->compare, 1);
+    return insert_compare(sl, data, sl->compare, 0);
 }
 
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void *data,
                                       apr_skiplist_compare comp)
 {
-    return insert_compare(sl, data, comp, 0);
+    return insert_compare(sl, data, comp, 1);
 }
 
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
@@ -473,13 +516,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
     if (!sl->compare) {
         return NULL;
     }
-    return insert_compare(sl, data, sl->compare, 0);
-}
-
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
-                                      apr_skiplist_compare comp)
-{
-    return insert_compare(sl, data, comp, 1);
+    return insert_compare(sl, data, sl->compare, 1);
 }
 
 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc
myfree)



Mime
View raw message