apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yla...@apache.org
Subject svn commit: r1672377 - in /apr/apr/branches/1.6.x: ./ tables/apr_skiplist.c test/testskiplist.c
Date Thu, 09 Apr 2015 14:54:03 GMT
Author: ylavic
Date: Thu Apr  9 14:54:03 2015
New Revision: 1672377

URL: http://svn.apache.org/r1672377
Log:
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.

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

Propchange: apr/apr/branches/1.6.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Thu Apr  9 14:54:03 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,767895,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,146
 0179-1460180,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,1642159,1648830,
 1664406,1664447,1664451,1664471,1664769-1664770,1664775,1664904,1664911,1664958,1666341,1666411,1666458,1666611,1667420-1667421,1667423,1667914-1667916,1671329,1671356,1671389,1671513-1671514,1672354
+/apr/apr/trunk:733052,739635,741862,741866-741867,741869,741871,745763-745764,746310,747990,748080,748361,748371,748565,748888,748902,748988,749810,760443,767895,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,146
 0179-1460180,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,1642159,1648830,
 1664406,1664447,1664451,1664471,1664769-1664770,1664775,1664904,1664911,1664958,1666341,1666411,1666458,1666611,1667420-1667421,1667423,1667914-1667916,1671329,1671356,1671389,1671513-1671514,1672354,1672366
 /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=1672377&r1=1672376&r2=1672377&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/tables/apr_skiplist.c (original)
+++ apr/apr/branches/1.6.x/tables/apr_skiplist.c Thu Apr  9 14:54:03 2015
@@ -399,24 +399,34 @@ APR_DECLARE(void *) apr_skiplist_element
 static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
                             apr_skiplist_freefunc myfree);
 
+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;
+}
+
 static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
                                         apr_skiplist_compare comp, int add,
                                         apr_skiplist_freefunc myfree)
 {
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
-    int ch, nh = 1;
+    int ch, top_nh, nh = 1;
 
+    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;
+    top_nh = nh;
 
     /* 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
@@ -448,8 +458,8 @@ static apr_skiplistnode *insert_compare(
                     if (top != sl->top) {
                         m = sl->top;
                         skiplist_qclear(&sl->stack_q);
-                        ch = sl->height;
-                        nh = ch + 1;
+                        ch = skiplist_height(sl);
+                        nh = top_nh;
                     }
                     continue;
                 }
@@ -644,7 +654,7 @@ static int skiplisti_remove(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,
@@ -737,7 +747,7 @@ APR_DECLARE(size_t) apr_skiplist_size(co
 
 APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
 {
-    return sl->height;
+    return skiplist_height(sl);
 }
 
 APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)

Modified: apr/apr/branches/1.6.x/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/test/testskiplist.c?rev=1672377&r1=1672376&r2=1672377&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.6.x/test/testskiplist.c Thu Apr  9 14:54:03 2015
@@ -185,7 +185,7 @@ static void skiplist_destroy(abts_case *
 {
     apr_skiplist_destroy(skiplist, NULL);
     ABTS_TRUE(tc, 0 == apr_skiplist_size(skiplist));
-    ABTS_TRUE(tc, 0 == apr_skiplist_height(skiplist));
+    ABTS_TRUE(tc, 1 == apr_skiplist_height(skiplist));
     ABTS_TRUE(tc, NULL == apr_skiplist_getlist(skiplist));
 }
 



Mime
View raw message