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 16:50:45 UTC
svn commit: r1672373 - in /apr/apr/branches/1.6.x: ./ include/apr_skiplist.h
tables/apr_skiplist.c test/testskiplist.c
Author: ylavic
Date: Thu Apr 9 14:50:44 2015
New Revision: 1672373
URL: http://svn.apache.org/r1672373
Log:
Merge r1667420, r1667421 and r1667423 from trunk.
skiplist: Introduce apr_skiplist_replace[_compare]().
skiplist: follow up to r1667420: fix bad copy/paste in description.
skiplist: follow up to r1667420: add to the index (never replace).
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 14:50:44 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,1667914-1667916,1671329,1671356,1671389,1671513-1671514,1672354
+/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
/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=1672373&r1=1672372&r2=1672373&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 14:50:44 2015
@@ -217,6 +217,32 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data);
/**
+ * Add an element into the skip list using the specified comparison function
+ * removing the existing duplicates.
+ * @param sl The skip list
+ * @param data The element to insert
+ * @param comp The comparison function to use for placement into the skip list
+ * @param myfree A function to be called for each removed duplicate
+ * @remark If no comparison function has been set for the skip list, the element
+ * will not be inserted, none will be replaced, and NULL will be returned.
+ */
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
+ void *data, apr_skiplist_freefunc myfree,
+ apr_skiplist_compare comp);
+
+/**
+ * Add an element into the skip list using the existing comparison function
+ * removing the existing duplicates.
+ * @param sl The skip list
+ * @param data The element to insert
+ * @param myfree A function to be called for each removed duplicate
+ * @remark If no comparison function has been set for the skip list, the element
+ * will not be inserted, none will be replaced, and NULL will be returned.
+ */
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
+ void *data, 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=1672373&r1=1672372&r2=1672373&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 14:50:44 2015
@@ -201,7 +201,7 @@ static apr_skiplistnode *skiplist_new_no
return m;
}
-static apr_status_t skiplist_free_node(apr_skiplist *sl, apr_skiplistnode *m)
+static apr_status_t skiplist_put_node(apr_skiplist *sl, apr_skiplistnode *m)
{
return skiplist_qpush(&sl->nodes_q, m);
}
@@ -304,8 +304,7 @@ static int skiplisti_find_compare(apr_sk
{
int count = 0;
apr_skiplistnode *m;
- m = sl->top;
- while (m) {
+ for (m = sl->top; m; count++) {
if (m->next) {
int compared = comp(data, m->next->data);
if (compared == 0) {
@@ -318,12 +317,10 @@ static int skiplisti_find_compare(apr_sk
}
if (compared > 0) {
m = m->next;
- count++;
continue;
}
}
m = m->down;
- count++;
}
*ret = NULL;
return count;
@@ -398,11 +395,16 @@ APR_DECLARE(void *) apr_skiplist_element
return node->data;
}
+/* forward declared */
+static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
+ apr_skiplist_freefunc myfree);
+
static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
- apr_skiplist_compare comp, int add)
+ apr_skiplist_compare comp, int add,
+ apr_skiplist_freefunc myfree)
{
apr_skiplistnode *m, *p, *tmp, *ret = NULL;
- int nh = 1, ch;
+ int ch, nh = 1;
if (sl->preheight) {
while (nh < sl->preheight && get_b_rand()) {
@@ -431,10 +433,26 @@ static apr_skiplistnode *insert_compare(
*/
if (m->next) {
int compared = comp(data, m->next->data);
- if (compared == 0 && !add) {
- /* Keep the existing element(s) */
- skiplist_qclear(&sl->stack_q);
- return NULL;
+ if (compared == 0) {
+ if (!add) {
+ /* Keep the existing element(s) */
+ skiplist_qclear(&sl->stack_q);
+ return NULL;
+ }
+ if (add < 0) {
+ /* Remove this element and continue with the next node
+ * or the new top if the current one is also removed.
+ */
+ apr_skiplistnode *top = sl->top;
+ skiplisti_remove(sl, m->next, myfree);
+ if (top != sl->top) {
+ m = sl->top;
+ skiplist_qclear(&sl->stack_q);
+ ch = sl->height;
+ nh = ch + 1;
+ }
+ continue;
+ }
}
if (compared >= 0) {
m = m->next;
@@ -511,7 +529,7 @@ static apr_skiplistnode *insert_compare(
li = ret;
for (p = apr_skiplist_getlist(sl->index); p; apr_skiplist_next(sl->index, &p)) {
apr_skiplist *sli = (apr_skiplist *)p->data;
- ni = insert_compare(sli, ret->data, sli->compare, add);
+ ni = insert_compare(sli, ret->data, sli->compare, 1, NULL);
li->nextindex = ni;
ni->previndex = li;
li = ni;
@@ -527,7 +545,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
if (!comp) {
return NULL;
}
- return insert_compare(sl, data, comp, 0);
+ return insert_compare(sl, data, comp, 0, NULL);
}
APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
@@ -541,7 +559,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
if (!comp) {
return NULL;
}
- return insert_compare(sl, data, comp, 1);
+ return insert_compare(sl, data, comp, 1, NULL);
}
APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
@@ -549,6 +567,22 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
return apr_skiplist_add_compare(sl, data, sl->compare);
}
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace_compare(apr_skiplist *sl,
+ void *data, apr_skiplist_freefunc myfree,
+ apr_skiplist_compare comp)
+{
+ if (!comp) {
+ return NULL;
+ }
+ return insert_compare(sl, data, comp, -1, myfree);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_replace(apr_skiplist *sl,
+ void *data, apr_skiplist_freefunc myfree)
+{
+ return apr_skiplist_replace_compare(sl, data, myfree, sl->compare);
+}
+
#if 0
void skiplist_print_struct(apr_skiplist * sl, char *prefix)
{
@@ -568,7 +602,8 @@ void skiplist_print_struct(apr_skiplist
}
#endif
-static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m, apr_skiplist_freefunc myfree)
+static int skiplisti_remove(apr_skiplist *sl, apr_skiplistnode *m,
+ apr_skiplist_freefunc myfree)
{
apr_skiplistnode *p;
if (!m) {
@@ -580,19 +615,20 @@ static int skiplisti_remove(apr_skiplist
while (m->up) {
m = m->up;
}
- while (m) {
+ do {
p = m;
- p->prev->next = p->next;/* take me out of the list */
+ /* take me out of the list */
+ p->prev->next = p->next;
if (p->next) {
- p->next->prev = p->prev; /* take me out of the list */
+ p->next->prev = p->prev;
}
m = m->down;
/* This only frees the actual data in the bottom one */
if (!m && myfree && p->data) {
myfree(p->data);
}
- skiplist_free_node(sl, p);
- }
+ skiplist_put_node(sl, p);
+ } while (m);
sl->size--;
while (sl->top && sl->top->next == NULL) {
/* While the row is empty and we are not on the bottom row */
@@ -601,7 +637,7 @@ static int skiplisti_remove(apr_skiplist
if (sl->top) {
sl->top->up = NULL; /* Make it think its the top */
}
- skiplist_free_node(sl, p);
+ skiplist_put_node(sl, p);
sl->height--;
}
if (!sl->top) {
@@ -661,7 +697,7 @@ APR_DECLARE(void) apr_skiplist_remove_al
}
do {
u = m->up;
- skiplist_free_node(sl, m);
+ skiplist_put_node(sl, m);
m = u;
} while (m);
m = p;
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=1672373&r1=1672372&r2=1672373&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.6.x/test/testskiplist.c Thu Apr 9 14:50:44 2015
@@ -105,12 +105,16 @@ static void skiplist_insert(abts_case *t
ABTS_STR_EQUAL(tc, "atfirst", val);
}
+#define NUM_ADDS 100
static void skiplist_add(abts_case *tc, void *data)
{
const char *val;
- size_t i, n = skiplist_get_size(tc, skiplist);
+ size_t i, n = 0;
- for (i = 0; i < 100; ++i) {
+ apr_skiplist_remove_all(skiplist, NULL);
+ ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+
+ for (i = 0; i < NUM_ADDS; ++i) {
n++;
ABTS_PTR_NOTNULL(tc, apr_skiplist_add(skiplist, "daton"));
ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
@@ -141,10 +145,48 @@ static void skiplist_add(abts_case *tc,
}
}
+static void skiplist_replace(abts_case *tc, void *data)
+{
+ const char *val;
+ size_t n = skiplist_get_size(tc, skiplist);
+
+ n -= NUM_ADDS - 1;
+ apr_skiplist_replace(skiplist, "daton", NULL);
+ ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "daton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "daton", val);
+
+ n -= NUM_ADDS - 1;
+ apr_skiplist_replace(skiplist, "baton", NULL);
+ ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "baton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "baton", val);
+
+ n -= NUM_ADDS - 1;
+ apr_skiplist_replace(skiplist, "caton", NULL);
+ ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "caton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "caton", val);
+
+ n -= NUM_ADDS - 1;
+ apr_skiplist_replace(skiplist, "aaton", NULL);
+ ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "aaton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "aaton", val);
+
+ ABTS_TRUE(tc, n == 4);
+}
+
static void skiplist_destroy(abts_case *tc, void *data)
{
apr_skiplist_destroy(skiplist, NULL);
- ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+ ABTS_TRUE(tc, 0 == apr_skiplist_size(skiplist));
+ ABTS_TRUE(tc, 0 == apr_skiplist_height(skiplist));
+ ABTS_TRUE(tc, NULL == apr_skiplist_getlist(skiplist));
}
static void skiplist_size(abts_case *tc, void *data)
@@ -399,6 +441,7 @@ abts_suite *testskiplist(abts_suite *sui
abts_run_test(suite, skiplist_dontfind, NULL);
abts_run_test(suite, skiplist_insert, NULL);
abts_run_test(suite, skiplist_add, NULL);
+ abts_run_test(suite, skiplist_replace, NULL);
abts_run_test(suite, skiplist_destroy, NULL);
abts_run_test(suite, skiplist_size, NULL);
abts_run_test(suite, skiplist_remove, NULL);