apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yla...@apache.org
Subject svn commit: r1664776 - in /apr/apr/branches/1.6.x: ./ tables/apr_skiplist.c
Date Sat, 07 Mar 2015 01:32:33 GMT
Author: ylavic
Date: Sat Mar  7 01:32:32 2015
New Revision: 1664776

URL: http://svn.apache.org/r1664776
Log:
skiplist: merge r1664775 from trunk.

Generalize the internal stack structure as a queue (FIFO), and use it for the
spare nodes (instead of apr_skiplist_alloc()/free()) and the insertion stack.

Fix a memory leak in destroy() when memory is malloc()ed (pool is NULL).

Modified:
    apr/apr/branches/1.6.x/   (props changed)
    apr/apr/branches/1.6.x/tables/apr_skiplist.c

Propchange: apr/apr/branches/1.6.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Sat Mar  7 01:32:32 2015
@@ -1,4 +1,4 @@
 /apr/apr/branches/1.4.x:1003369,1101301
-/apr/apr/trunk:733052,739635,741862,741866-741867,741869,741871,745763-745764,746310,747990,748080,748361,748371,748565,748888,748902,748988,749810,760443,775683,782838,783398,783958,784633,784773,788588,789050,793192-793193,794118,794485,795267,799497,800627,809745,809854,810472,811455,813063,821306,829490,831641,832904,835607,888669,892028,892159,892435,892909,896382,896653,908427,910419,910597,917819,917837-917838,925965,929796,931973,951771,960665,960671,979891,983618,989450,990435,1003338,1044440,1044447,1055657,1072165,1078845,1081462,1081495,1083038,1083242,1084662,1086695,1088023,1089031,1089129,1089438,1099348,1103310,1183683,1183685-1183686,1183688,1183693,1183698,1213382,1235047,1236970,1237078,1237507,1240472,1340286,1340288,1340470,1341193,1341196,1343233,1343243,1367050,1368819,1370494,1372018,1372022,1372093,1372849,1376957,1384764,1389077,1400200,1402868,1405985,1406690,1420106,1420109,1425356,1428809,1438940,1438957-1438959,1442903,1449568,1456418,1459994,1460179-14
 60180,1460241,1460399,1460405,1462738,1462813,1470186,1470348,1475509,1478905,1480067,1481262,1481265,1484271,1487796,1489517,1496407,1502804,1510354,1516261,1523384,1523479,1523484,1523505,1523521,1523604,1523613,1523615,1523844-1523845,1523853,1524014,1524031,1528797,1528809,1529488,1529495,1529515,1529521,1529668,1530786,1530800,1530988,1531554,1531768,1531884,1532022,1533104,1533111,1533979,1535027,1535157,1536744,1538171,1539374,1539389,1539455,1539603,1541054,1541061,1541486,1541655,1541666,1541744,1542601,1542779,1543033,1543056,1548575,1550907,1551650,1551659,1558905,1559382,1559873,1559975,1561040,1561260,1561265,1561321,1561347,1561356,1561361,1561394,1561555,1571894,1575509,1578420,1587045,1587063,1587543,1587545,1588878,1588937,1593611,1593614-1593615,1593680,1594684,1594708,1595549,1597797,1597803,1604590,1604596,1604598,1605104,1610854,1611023,1611107,1611110,1611117,1611120,1611125,1611184,1611193,1611466,1611515,1611517,1625173,1626564,1634615,1648830,1664406,1664447
 ,1664451,1664471,1664769
+/apr/apr/trunk:733052,739635,741862,741866-741867,741869,741871,745763-745764,746310,747990,748080,748361,748371,748565,748888,748902,748988,749810,760443,775683,782838,783398,783958,784633,784773,788588,789050,793192-793193,794118,794485,795267,799497,800627,809745,809854,810472,811455,813063,821306,829490,831641,832904,835607,888669,892028,892159,892435,892909,896382,896653,908427,910419,910597,917819,917837-917838,925965,929796,931973,951771,960665,960671,979891,983618,989450,990435,1003338,1044440,1044447,1055657,1072165,1078845,1081462,1081495,1083038,1083242,1084662,1086695,1088023,1089031,1089129,1089438,1099348,1103310,1183683,1183685-1183686,1183688,1183693,1183698,1213382,1235047,1236970,1237078,1237507,1240472,1340286,1340288,1340470,1341193,1341196,1343233,1343243,1367050,1368819,1370494,1372018,1372022,1372093,1372849,1376957,1384764,1389077,1400200,1402868,1405985,1406690,1420106,1420109,1425356,1428809,1438940,1438957-1438959,1442903,1449568,1456418,1459994,1460179-14
 60180,1460241,1460399,1460405,1462738,1462813,1470186,1470348,1475509,1478905,1480067,1481262,1481265,1484271,1487796,1489517,1496407,1502804,1510354,1516261,1523384,1523479,1523484,1523505,1523521,1523604,1523613,1523615,1523844-1523845,1523853,1524014,1524031,1528797,1528809,1529488,1529495,1529515,1529521,1529668,1530786,1530800,1530988,1531554,1531768,1531884,1532022,1533104,1533111,1533979,1535027,1535157,1536744,1538171,1539374,1539389,1539455,1539603,1541054,1541061,1541486,1541655,1541666,1541744,1542601,1542779,1543033,1543056,1548575,1550907,1551650,1551659,1558905,1559382,1559873,1559975,1561040,1561260,1561265,1561321,1561347,1561356,1561361,1561394,1561555,1571894,1575509,1578420,1587045,1587063,1587543,1587545,1588878,1588937,1593611,1593614-1593615,1593680,1594684,1594708,1595549,1597797,1597803,1604590,1604596,1604598,1605104,1610854,1611023,1611107,1611110,1611117,1611120,1611125,1611184,1611193,1611466,1611515,1611517,1625173,1626564,1634615,1648830,1664406,1664447
 ,1664451,1664471,1664769,1664775
 /apr/apr/trunk/test/testnames.c:1460405
 /httpd/httpd/trunk:1604590

Modified: apr/apr/branches/1.6.x/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/tables/apr_skiplist.c?rev=1664776&r1=1664775&r2=1664776&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/tables/apr_skiplist.c (original)
+++ apr/apr/branches/1.6.x/tables/apr_skiplist.c Sat Mar  7 01:32:32 2015
@@ -25,6 +25,12 @@
 
 #include "apr_skiplist.h"
 
+typedef struct {
+    apr_skiplistnode **data;
+    size_t size, pos;
+    apr_pool_t *p;
+} apr_skiplist_q; 
+
 struct apr_skiplist {
     apr_skiplist_compare compare;
     apr_skiplist_compare comparek;
@@ -38,9 +44,8 @@ struct apr_skiplist {
     apr_skiplistnode *bottomend;
     apr_skiplist *index;
     apr_array_header_t *memlist;
-    apr_skiplistnode **stack;
-    size_t stack_pos,
-           stack_len;
+    apr_skiplist_q nodes_q,
+                   stack_q;
     apr_pool_t *pool;
 };
 
@@ -148,41 +153,57 @@ APR_DECLARE(void) apr_skiplist_free(apr_
     }
 }
 
-static apr_status_t skiplist_stack_push(apr_skiplist *sl, apr_skiplistnode *m)
+static apr_status_t skiplist_qpush(apr_skiplist_q *q, 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));
+    if (q->pos >= q->size) {
+        apr_skiplistnode **data;
+        size_t size = (q->pos) ? q->pos * 2 : 32;
+        if (q->p) {
+            data = apr_palloc(q->p, size * sizeof(*data));
+            if (data) {
+                memcpy(data, q->data, q->pos * sizeof(*data));
             }
         }
         else {
-            ptr = realloc(sl->stack, len * sizeof(*ptr));
+            data = realloc(q->data, size * sizeof(*data));
         }
-        if (!ptr) {
+        if (!data) {
             return APR_ENOMEM;
         }
-        sl->stack = ptr;
-        sl->stack_len = len;
+        q->data = data;
+        q->size = size;
     }
-    sl->stack[sl->stack_pos++] = m;
+    q->data[q->pos++] = m;
     return APR_SUCCESS;
 }
 
-static APR_INLINE apr_skiplistnode *skiplist_stack_pop(apr_skiplist *sl)
+static APR_INLINE apr_skiplistnode *skiplist_qpop(apr_skiplist_q *q)
 {
-    return (sl->stack_pos > 0) ? sl->stack[--sl->stack_pos] : NULL;
+    return (q->pos > 0) ? q->data[--q->pos] : NULL;
 }
 
-static APR_INLINE void skiplist_stack_clear(apr_skiplist *sl)
+static APR_INLINE void skiplist_qclear(apr_skiplist_q *q)
 {
-    sl->stack_pos = 0;
+    q->pos = 0;
+}
+
+static apr_skiplistnode *skiplist_new_node(apr_skiplist *sl)
+{
+    apr_skiplistnode *m = skiplist_qpop(&sl->nodes_q);
+    if (!m) {
+        if (sl->pool) {
+            m = apr_palloc(sl->pool, sizeof *m);
+        }
+        else {
+            m = malloc(sizeof *m);
+        }
+    }
+    return m;
+}
+
+static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m)
+{
+    return skiplist_qpush(&sl->nodes_q, m);
 }
 
 static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
@@ -191,6 +212,7 @@ static apr_status_t skiplisti_init(apr_s
     if (p) {
         sl = apr_pcalloc(p, sizeof(apr_skiplist));
         sl->memlist = apr_array_make(p, 20, sizeof(memlist_t));
+        sl->pool = sl->nodes_q.p = sl->stack_q.p = p;
     }
     else {
         sl = calloc(1, sizeof(apr_skiplist));
@@ -198,17 +220,6 @@ static apr_status_t skiplisti_init(apr_s
             return APR_ENOMEM;
         }
     }
-#if 0
-    sl->compare = (apr_skiplist_compare) NULL;
-    sl->comparek = (apr_skiplist_compare) NULL;
-    sl->height = 0;
-    sl->preheight = 0;
-    sl->size = 0;
-    sl->top = NULL;
-    sl->bottom = NULL;
-    sl->index = NULL;
-#endif
-    sl->pool = p;
     *s = sl;
     return APR_SUCCESS;
 }
@@ -419,7 +430,7 @@ static apr_skiplistnode *insert_compare(
             int compared = comp(data, m->next->data);
             if (compared == 0 && !add) {
                 /* Keep the existing element(s) */
-                skiplist_stack_clear(sl);
+                skiplist_qclear(&sl->stack_q);
                 return NULL;
             }
             if (compared > 0) {
@@ -429,19 +440,20 @@ static apr_skiplistnode *insert_compare(
         }
         if (ch <= nh) {
             /* push on stack */
-            skiplist_stack_push(sl, m);
+            skiplist_qpush(&sl->stack_q, m);
         }
         m = m->down;
         ch--;
     }
     /* Pop the stack and insert nodes */
     p = NULL;
-    while ((m = skiplist_stack_pop(sl))) {
-        tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
+    while ((m = skiplist_qpop(&sl->stack_q))) {
+        tmp = skiplist_new_node(sl);
         tmp->next = m->next;
         if (m->next) {
             m->next->prev = tmp;
         }
+        m->next = tmp;
         tmp->prev = m;
         tmp->up = NULL;
         tmp->nextindex = tmp->previndex = NULL;
@@ -455,14 +467,13 @@ static apr_skiplistnode *insert_compare(
         }
         tmp->data = data;
         tmp->sl = sl;
-        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 = skiplist_new_node(sl);
+        tmp = skiplist_new_node(sl);
         m->up = m->prev = m->nextindex = m->previndex = NULL;
         m->next = tmp;
         m->down = sl->top;
@@ -492,7 +503,8 @@ static apr_skiplistnode *insert_compare(
         apr_skiplistnode *ni, *li;
         li = ret;
         for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p))
{
-            ni = apr_skiplist_insert((apr_skiplist *) p->data, ret->data);
+            apr_skiplist *sli = (apr_skiplist *)p->data;
+            ni = insert_compare(sli, ret->data, sli->compare, add);
             li->nextindex = ni;
             ni->previndex = li;
             li = ni;
@@ -580,7 +592,7 @@ static int skiplisti_remove(apr_skiplist
         if (!m && myfree && p->data) {
             myfree(p->data);
         }
-        apr_skiplist_free(sl, p);
+        skiplist_free_node(sl, p);
     }
     sl->size--;
     while (sl->top && sl->top->next == NULL) {
@@ -590,7 +602,7 @@ static int skiplisti_remove(apr_skiplist
         if (sl->top) {
             sl->top->up = NULL; /* Make it think its the top */
         }
-        apr_skiplist_free(sl, p);
+        skiplist_free_node(sl, p);
         sl->height--;
     }
     if (!sl->top) {
@@ -636,13 +648,14 @@ APR_DECLARE(void) apr_skiplist_remove_al
     m = sl->bottom;
     while (m) {
         p = m->next;
-        if (p && myfree && p->data)
+        if (myfree && p && p->data) {
             myfree(p->data);
-        while (m) {
+        }
+        do {
             u = m->up;
-            apr_skiplist_free(sl, m);
+            skiplist_free_node(sl, m);
             m = u;
-        }
+        } while (m);
         m = p;
     }
     sl->top = sl->bottom = NULL;
@@ -695,8 +708,7 @@ APR_DECLARE(void) apr_skiplist_set_prehe
 
 static void skiplisti_destroy(void *vsl)
 {
-    apr_skiplist_destroy((apr_skiplist *) vsl, NULL);
-    apr_skiplist_free((apr_skiplist *) vsl, vsl);
+    apr_skiplist_destroy(vsl, NULL);
 }
 
 APR_DECLARE(void) apr_skiplist_destroy(apr_skiplist *sl, apr_skiplist_freefunc myfree)
@@ -705,6 +717,10 @@ APR_DECLARE(void) apr_skiplist_destroy(a
         ;
     apr_skiplist_remove_all(sl, myfree);
     if (!sl->pool) {
+        while (sl->nodes_q.pos)
+            free(sl->nodes_q.data[--sl->nodes_q.pos]);
+        free(sl->nodes_q.data);
+        free(sl->stack_q.data);
         free(sl);
     }
 }



Mime
View raw message