apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yla...@apache.org
Subject svn commit: r1672384 - in /apr/apr/branches/1.5.x: ./ tables/apr_skiplist.c
Date Thu, 09 Apr 2015 15:02:42 GMT
Author: ylavic
Date: Thu Apr  9 15:02:42 2015
New Revision: 1672384

URL: http://svn.apache.org/r1672384
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.5.x/   (props changed)
    apr/apr/branches/1.5.x/tables/apr_skiplist.c

Propchange: apr/apr/branches/1.5.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Thu Apr  9 15:02:42 2015
@@ -1,4 +1,4 @@
 /apr/apr/branches/1.4.x:1003369,1101301
 /apr/apr/branches/1.6.x:1593600,1593612,1648831,1666812
-/apr/apr/trunk:733052,739635,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,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,1438958,1442903,1449568,1456418,1459994,1460179,1460241,1460399,1460405,1462738,1462813,1470186,1470348,147
 5509,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,1561260,1561265,1561321,1561347,1561356,1561361,1561394,1561555,1571894,1575509,1578420,1587063,1587545,1589982,1593611,1604596,1604598,1610854,1611004,1611023,1611107,1611110,1611120,1611125,1611184,1611193,1611466,1626564,1634615,1642159,1648830,1664406,1664447,1664451,1664471,1664769,1664775,1664904,1664911,1664958,1666341,1666411,1666458,1666611,1667914-1667916,1671329,1671356,1671514,1672354
+/apr/apr/trunk:733052,739635,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,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,1438958,1442903,1449568,1456418,1459994,1460179,1460241,1460399,1460405,1462738,1462813,1470186,1470348,147
 5509,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,1561260,1561265,1561321,1561347,1561356,1561361,1561394,1561555,1571894,1575509,1578420,1587063,1587545,1589982,1593611,1604596,1604598,1610854,1611004,1611023,1611107,1611110,1611120,1611125,1611184,1611193,1611466,1626564,1634615,1642159,1648830,1664406,1664447,1664451,1664471,1664769,1664775,1664904,1664911,1664958,1666341,1666411,1666458,1666611,1667914-1667916,1671329,1671356,1671514,1672354,1672366
 /apr/apr/trunk/test/testnames.c:1460405

Modified: apr/apr/branches/1.5.x/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.5.x/tables/apr_skiplist.c?rev=1672384&r1=1672383&r2=1672384&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/tables/apr_skiplist.c (original)
+++ apr/apr/branches/1.5.x/tables/apr_skiplist.c Thu Apr  9 15:02:42 2015
@@ -393,27 +393,36 @@ APR_DECLARE(void *) apr_skiplist_previou
     return (*iter) ? ((*iter)->data) : NULL;
 }
 
+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;
+}
+
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
                                       apr_skiplist_compare comp)
 {
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
-    int nh = 1, ch;
+    int ch, nh = 1;
 
     if (!comp) {
         return NULL;
     }
 
+    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;
 
     /* 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
@@ -580,7 +589,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,



Mime
View raw message