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:35:12 UTC
svn commit: r1672498 - in /apr/apr/branches/1.6.x: ./ include/apr_skiplist.h
tables/apr_skiplist.c test/testskiplist.c
Author: ylavic
Date: Thu Apr 9 21:35:12 2015
New Revision: 1672498
URL: http://svn.apache.org/r1672498
Log:
Merge r1671957 from trunk.
Introduce apr_skiplist_last[_compare]() and apr_skiplist_remove_node().
The apr_skiplist_last[_compare]() functions return the last matching element
(duplicate) whereas the existing apr_skiplist_find[_compare]() return the first
one encountered during the walk.
The function apr_skiplist_remove_node() function allows to remove an element
given its node, e.g. an iterator from apr_skiplist_{getlist,previous,next}().
The goal is to have a reliable way to find (and remove) any element having a
unique address/pointer, by starting with the last duplicate and then iterating
on the previous ones until the match (see example in testskiplist.c).
apr_skiplist_last() is much more efficient than apr_skiplist_first() would be,
Modified:
apr/apr/branches/1.6.x/ (props changed)
apr/apr/branches/1.6.x/include/apr_skiplist.h
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 21:35:12 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,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
/apr/apr/trunk/test/testnames.c:1460405
/httpd/httpd/trunk:1604590
Modified: apr/apr/branches/1.6.x/include/apr_skiplist.h
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/include/apr_skiplist.h?rev=1672498&r1=1672497&r2=1672498&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/include/apr_skiplist.h (original)
+++ apr/apr/branches/1.6.x/include/apr_skiplist.h Thu Apr 9 21:35:12 2015
@@ -153,6 +153,30 @@ APR_DECLARE(void *) apr_skiplist_find_co
APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter);
/**
+ * Return the last matching element in the skip list using the specified
+ * comparison function.
+ * @param sl The skip list
+ * @param data The value to search for
+ * @param iter A pointer to the returned skip list node representing the element
+ * found
+ * @param func The comparison function to use
+ */
+APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sli, void *data,
+ apr_skiplistnode **iter,
+ apr_skiplist_compare comp);
+
+/**
+ * Return the last matching element in the skip list using the current comparison
+ * function.
+ * @param sl The skip list
+ * @param data The value to search for
+ * @param iter A pointer to the returned skip list node representing the element
+ * found
+ */
+APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data,
+ apr_skiplistnode **iter);
+
+/**
* Return the next element in the skip list.
* @param sl The skip list
* @param iter On entry, a pointer to the skip list node to start with; on return,
@@ -243,6 +267,16 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
void *data, apr_skiplist_freefunc myfree);
/**
+ * Remove a node from the skip list.
+ * @param sl The skip list
+ * @param iter The skip list node to remove
+ * @param myfree A function to be called for the removed element
+ */
+APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
+ apr_skiplistnode *iter,
+ apr_skiplist_freefunc myfree);
+
+/**
* Remove an element from the skip list using the specified comparison function for
* locating the element. In the case of duplicates, the 1st entry will be removed.
* @param sl The skip list
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=1672498&r1=1672497&r2=1672498&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 21:35:12 2015
@@ -299,21 +299,21 @@ APR_DECLARE(void) apr_skiplist_add_index
}
static int skiplisti_find_compare(apr_skiplist *sl, void *data,
- apr_skiplistnode **ret,
- apr_skiplist_compare comp)
+ apr_skiplistnode **ret,
+ apr_skiplist_compare comp,
+ int last)
{
int count = 0;
- apr_skiplistnode *m;
+ apr_skiplistnode *m, *found = NULL;
for (m = sl->top; m; count++) {
if (m->next) {
int compared = comp(data, m->next->data);
if (compared == 0) {
- m = m->next;
- while (m->down) {
- m = m->down;
+ found = m = m->next;
+ if (!last) {
+ break;
}
- *ret = m;
- return count;
+ continue;
}
if (compared > 0) {
m = m->next;
@@ -322,13 +322,22 @@ static int skiplisti_find_compare(apr_sk
}
m = m->down;
}
- *ret = NULL;
+ if (found) {
+ while (found->down) {
+ found = found->down;
+ }
+ *ret = found;
+ }
+ else {
+ *ret = NULL;
+ }
return count;
}
-APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
- apr_skiplistnode **iter,
- apr_skiplist_compare comp)
+static void *find_compare(apr_skiplist *sli, void *data,
+ apr_skiplistnode **iter,
+ apr_skiplist_compare comp,
+ int last)
{
apr_skiplistnode *m;
apr_skiplist *sl;
@@ -351,16 +360,36 @@ APR_DECLARE(void *) apr_skiplist_find_co
}
sl = (apr_skiplist *) m->data;
}
- skiplisti_find_compare(sl, data, &m, sl->comparek);
+ skiplisti_find_compare(sl, data, &m, sl->comparek, last);
if (iter) {
*iter = m;
}
return (m) ? m->data : NULL;
}
+APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sl, void *data,
+ apr_skiplistnode **iter,
+ apr_skiplist_compare comp)
+{
+ return find_compare(sl, data, iter, comp, 0);
+}
+
APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
{
- return apr_skiplist_find_compare(sl, data, iter, sl->compare);
+ return find_compare(sl, data, iter, sl->compare, 0);
+}
+
+APR_DECLARE(void *) apr_skiplist_last_compare(apr_skiplist *sl, void *data,
+ apr_skiplistnode **iter,
+ apr_skiplist_compare comp)
+{
+ return find_compare(sl, data, iter, comp, 1);
+}
+
+APR_DECLARE(void *) apr_skiplist_last(apr_skiplist *sl, void *data,
+ apr_skiplistnode **iter)
+{
+ return find_compare(sl, data, iter, sl->compare, 1);
}
@@ -390,9 +419,9 @@ APR_DECLARE(void *) apr_skiplist_previou
return (*iter) ? ((*iter)->data) : NULL;
}
-APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *node)
+APR_DECLARE(void *) apr_skiplist_element(apr_skiplistnode *iter)
{
- return node->data;
+ return (iter) ? iter->data : NULL;
}
/* forward declared */
@@ -657,6 +686,23 @@ static int skiplisti_remove(apr_skiplist
return skiplist_height(sl);
}
+APR_DECLARE(int) apr_skiplist_remove_node(apr_skiplist *sl,
+ apr_skiplistnode *iter,
+ apr_skiplist_freefunc myfree)
+{
+ apr_skiplistnode *m = iter;
+ if (!m) {
+ return 0;
+ }
+ while (m->down) {
+ m = m->down;
+ }
+ while (m->previndex) {
+ m = m->previndex;
+ }
+ return skiplisti_remove(sl, m, myfree);
+}
+
APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
void *data,
apr_skiplist_freefunc myfree, apr_skiplist_compare comp)
@@ -676,7 +722,7 @@ APR_DECLARE(int) apr_skiplist_remove_com
}
sl = (apr_skiplist *) m->data;
}
- skiplisti_find_compare(sl, data, &m, comp);
+ skiplisti_find_compare(sl, data, &m, comp, 0);
if (!m) {
return 0;
}
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=1672498&r1=1672497&r2=1672498&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:35:12 2015
@@ -317,6 +317,34 @@ static int acomp(void *a, void *b){
}
}
+/* 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.
+ */
+static void skiplist_remove_scomp(abts_case *tc, apr_skiplist *list, elem *n)
+{
+ elem *e;
+ apr_skiplistnode *iter = NULL;
+ e = apr_skiplist_last(list, n, &iter);
+ while (e && e != n) {
+ ABTS_INT_EQUAL(tc, 0, scomp(n, e));
+ e = apr_skiplist_previous(list, &iter);
+ }
+ ABTS_PTR_EQUAL(tc, n, apr_skiplist_element(iter));
+ apr_skiplist_remove_node(list, iter, NULL);
+}
+
static void skiplist_test(abts_case *tc, void *data) {
int test_elems = 10;
int i = 0, j = 0;
@@ -325,6 +353,7 @@ static void skiplist_test(abts_case *tc,
apr_skiplist * list = NULL;
apr_skiplist * list2 = NULL;
apr_skiplist * list3 = NULL;
+ apr_skiplist * list4 = NULL;
int first_forty_two = 42,
second_forty_two = 42;
elem t1, t2, t3, t4, t5;
@@ -426,6 +455,39 @@ static void skiplist_test(abts_case *tc,
val2 = apr_skiplist_find(list3, &t2, NULL);
ABTS_PTR_EQUAL(tc, NULL, val2);
+ ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list4, ptmp));
+ apr_skiplist_set_compare(list4, scomp, scomp);
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t1);
+ }
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t2);
+ }
+ apr_skiplist_add(list4, &t2);
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t2);
+ }
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t3);
+ }
+ apr_skiplist_add(list4, &t3);
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t3);
+ }
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t4);
+ }
+ apr_skiplist_add(list4, &t4);
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t4);
+ }
+ for (i = 0; i < 5; ++i){
+ add_elem_to_skiplist(tc, list4, t5);
+ }
+ skiplist_remove_scomp(tc, list4, &t2);
+ skiplist_remove_scomp(tc, list4, &t3);
+ skiplist_remove_scomp(tc, list4, &t4);
+
apr_pool_clear(ptmp);
}