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/03/07 02:04:45 UTC
svn commit: r1664772 - in /apr/apr/branches/1.6.x: ./ tables/apr_skiplist.c
Author: ylavic
Date: Sat Mar 7 01:04:45 2015
New Revision: 1664772
URL: http://svn.apache.org/r1664772
Log:
skiplist: merge r1664769 from trunk.
More optimizations.
We don't need to create the top before inserting, this will be done
if/once the value is really added (since r1611193).
Check compare value only if m->next is not NULL, otherwise we already
known it is to be handled as negative (down).
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:04:45 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
+/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/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=1664772&r1=1664771&r2=1664772&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:04:45 2015
@@ -311,9 +311,8 @@ static int skiplisti_find_compare(apr_sk
apr_skiplistnode *m;
m = sl->top;
while (m) {
- int compared;
if (m->next) {
- compared = comp(data, m->next->data);
+ int compared = comp(data, m->next->data);
if (compared == 0) {
m = m->next;
while (m->down) {
@@ -322,18 +321,14 @@ static int skiplisti_find_compare(apr_sk
*ret = m;
return count;
}
+ if (compared > 0) {
+ m = m->next;
+ count++;
+ continue;
+ }
}
- else {
- compared = -1;
- }
- if (compared < 0) {
- m = m->down;
- count++;
- }
- else {
- m = m->next;
- count++;
- }
+ m = m->down;
+ count++;
}
*ret = NULL;
return count;
@@ -394,19 +389,7 @@ static apr_skiplistnode *insert_compare(
{
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 =
- (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
- sl->top->next = NULL;
- sl->top->data = NULL;
- sl->top->prev = NULL;
- sl->top->up = NULL;
- sl->top->down = NULL;
- sl->top->nextindex = NULL;
- sl->top->previndex = NULL;
- sl->top->sl = sl;
- }
+
if (sl->preheight) {
while (nh < sl->preheight && get_b_rand()) {
nh++;
@@ -428,33 +411,28 @@ static apr_skiplistnode *insert_compare(
*/
m = sl->top;
while (m) {
- int compared;
+ /*
+ * To maintain stability, dups (compared == 0) must be added
+ * AFTER each other.
+ */
if (m->next) {
- compared = comp(data, m->next->data);
+ int compared = comp(data, m->next->data);
if (compared == 0 && !add) {
/* Keep the existing element(s) */
skiplist_stack_clear(sl);
return NULL;
}
- }
- else {
- compared = -1;
- }
- /*
- * To maintain stability, dups must be added AFTER each
- * other.
- */
- if (compared <= 0) {
- if (ch <= nh) {
- /* push on stack */
- skiplist_stack_push(sl, m);
+ if (compared > 0) {
+ m = m->next;
+ continue;
}
- m = m->down;
- ch--;
}
- else {
- m = m->next;
+ if (ch <= nh) {
+ /* push on stack */
+ skiplist_stack_push(sl, m);
}
+ m = m->down;
+ ch--;
}
/* Pop the stack and insert nodes */
p = NULL;
@@ -501,7 +479,10 @@ static apr_skiplistnode *insert_compare(
tmp->down = p;
tmp->data = data;
tmp->sl = sl;
- p = p->up = tmp;
+ if (p) {
+ p->up = tmp;
+ }
+ p = tmp;
}
if (sl->index != NULL) {
/*