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 23:37:14 UTC
svn commit: r1672499 - in /apr/apr/branches/1.6.x: ./ test/testskiplist.c
Author: ylavic
Date: Thu Apr 9 21:37:14 2015
New Revision: 1672499
URL: http://svn.apache.org/r1672499
Log:
Merge r1672495 from trunk.
testskiplist: axe buggy compare function acomp() and associated test.
Instead, define and use ecomp() which bases uniqueness on both elem's a and b,
and test it with multiple duplicates inserted/found/removed in arbitray order.
Improve comment on when/how these compare functions could be used in real apps.
Modified:
apr/apr/branches/1.6.x/ (props changed)
apr/apr/branches/1.6.x/test/testskiplist.c
Propchange: apr/apr/branches/1.6.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Thu Apr 9 21:37:14 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,1671957,1672354,1672366
+/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,1671957,1672354,1672366,1672495
/apr/apr/trunk/test/testnames.c:1460405
/httpd/httpd/trunk:1604590
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=1672499&r1=1672498&r2=1672499&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.6.x/test/testskiplist.c Thu Apr 9 21:37:14 2015
@@ -230,7 +230,7 @@ static void skiplist_remove(abts_case *t
ABTS_PTR_NOTNULL(tc, val);
ABTS_STR_EQUAL(tc, "baton", val);
- apr_skiplist_remove(skiplist, "baton", NULL);
+ ABTS_TRUE(tc, apr_skiplist_remove(skiplist, "baton", NULL) != 0);
ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
val = apr_skiplist_find(skiplist, "baton", NULL);
ABTS_PTR_NOTNULL(tc, val);
@@ -308,29 +308,46 @@ static int scomp(void *a, void *b){
return ((elem*) a)->a - ((elem*) b)->a;
}
-static int acomp(void *a, void *b){
- if (a != b) {
- return (scomp(a, b) < 0) ? -1 : 1;
+static int ecomp(void *a, void *b)
+{
+ elem const * const e1 = a;
+ elem const * const e2 = b;
+ if (e1->a < e2->a) {
+ return -1;
+ }
+ else if (e1->a > e2->a) {
+ return +1;
+ }
+ else if (e1->b < e2->b) {
+ return -1;
+ }
+ else if (e1->b > e2->b) {
+ return +1;
}
else {
return 0;
}
}
-/* If we add multiple duplicates and then try to remove each one
- * individually (unique pointer) in arbitrary order, by using:
- * - apr_skiplist_remove_compare(..., scomp, NULL)
- * There is no pointer comparison with scomp(), so will likely
- * remove any duplicate (the first encountered in the walking path).
- * - apr_skiplist_remove_compare(..., acomp, NULL)
- * The exact element to be removed may be skipped in the walking path
- * because some "bigger" element (or duplicate) was added later with a
- * higher height.
- * Hence we use skiplist_remove_scomp() which will go straight to the last
- * duplicate (using scomp) and then iterate on the previous elements until
- * pointers match.
- * This pattern could be reused by any application which wants to remove
- * elements by (unique) pointer.
+/* Some tests below add multiple duplicates and then try to remove each one
+ * individually, in arbitrary order.
+ *
+ * Using apr_skiplist_remove_compare(..., scomp, NULL) would not work because
+ * it will likely remove any duplicate (the first one) encountered on the path,
+ * hence possibly not the expected one.
+ *
+ * Using apr_skiplist_remove_compare(..., ecomp, NULL) works provided all the
+ * duplicates (same a) don't also have the same b (which is the case in the
+ * test below), hence uniqueness is cooked in the elem itself.
+ *
+ * Another possibility is to rely on unique pointers, and then cook a remove
+ * function, like the following skiplist_remove_scomp(), which will go straight
+ * to the last duplicate (using scomp) and then iterate on the previous elems
+ * until pointers match.
+ *
+ * Providing uniqueness in the elem itself is the more clean/efficient option,
+ * but if all you have is a unique pointer the pattern in the function may be
+ * worth it ( or it's just a way to test several skiplist functionalities :)
*/
static void skiplist_remove_scomp(abts_case *tc, apr_skiplist *list, elem *n)
{
@@ -356,6 +373,7 @@ static void skiplist_test(abts_case *tc,
apr_skiplist * list4 = NULL;
int first_forty_two = 42,
second_forty_two = 42;
+ apr_array_header_t *array;
elem t1, t2, t3, t4, t5;
t1.a = 1; t1.b = 1;
t2.a = 42; t2.b = 1;
@@ -441,19 +459,27 @@ static void skiplist_test(abts_case *tc,
ABTS_INT_EQUAL(tc, val2->b, 1);
ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list3, ptmp));
- apr_skiplist_set_compare(list3, acomp, acomp);
- ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(list3, &t2));
- val2 = apr_skiplist_find(list3, &t2, NULL);
- ABTS_PTR_EQUAL(tc, &t2, val2);
- ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(list3, &t3));
- val2 = apr_skiplist_find(list3, &t3, NULL);
- ABTS_PTR_EQUAL(tc, &t3, val2);
- apr_skiplist_remove(list3, &t3, NULL);
- val2 = apr_skiplist_find(list3, &t3, NULL);
- ABTS_PTR_EQUAL(tc, NULL, val2);
- apr_skiplist_remove(list3, &t2, NULL);
- val2 = apr_skiplist_find(list3, &t2, NULL);
- ABTS_PTR_EQUAL(tc, NULL, val2);
+ apr_skiplist_set_compare(list3, ecomp, ecomp);
+ array = apr_array_make(ptmp, 10, sizeof(elem *));
+ for (i = 0; i < 10; ++i) {
+ elem *e = apr_palloc(ptmp, sizeof *e);
+ e->a = 4224;
+ e->b = i;
+ APR_ARRAY_PUSH(array, elem *) = e;
+ ABTS_PTR_NOTNULL(tc, apr_skiplist_insert(list3, e));
+ }
+ for (i = 0; i < 5; ++i) {
+ elem *e = APR_ARRAY_IDX(array, i, elem *);
+ val2 = apr_skiplist_find(list3, e, NULL);
+ ABTS_PTR_EQUAL(tc, e, val2);
+ ABTS_TRUE(tc, apr_skiplist_remove(list3, e, NULL) != 0);
+ }
+ for (i = 0; i < 5; ++i) {
+ elem *e = APR_ARRAY_IDX(array, 9 - i, elem *);
+ val2 = apr_skiplist_find(list3, e, NULL);
+ ABTS_PTR_EQUAL(tc, e, val2);
+ ABTS_TRUE(tc, apr_skiplist_remove(list3, e, NULL) != 0);
+ }
ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list4, ptmp));
apr_skiplist_set_compare(list4, scomp, scomp);