You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@apr.apache.org by yl...@apache.org on 2015/04/09 17:02:42 UTC
svn commit: r1672384 - in /apr/apr/branches/1.5.x: ./ tables/apr_skiplist.c
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,