apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From yla...@apache.org
Subject svn commit: r1666446 - in /apr/apr/branches/1.5.x: ./ include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c
Date Fri, 13 Mar 2015 13:37:06 GMT
Author: ylavic
Date: Fri Mar 13 13:37:05 2015
New Revision: 1666446

URL: http://svn.apache.org/r1666446
Log:
Merge r1666411 from trunk.

skiplist: restore back add-if-not-exist semantic to apr_skiplist_insert().

Show in the tests how to achieve add-next-to-any-existing semantic by emulating
apr_skiplist_add() (which is 1.6+ only) with a generic compare function.
This is not very nice (brainer, not thread-safe and with an opaque struct abuse)
but generic hence easing code sync with upper branches...

Modified:
    apr/apr/branches/1.5.x/   (props changed)
    apr/apr/branches/1.5.x/include/apr_skiplist.h
    apr/apr/branches/1.5.x/tables/apr_skiplist.c
    apr/apr/branches/1.5.x/test/testskiplist.c

Propchange: apr/apr/branches/1.5.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Fri Mar 13 13:37:05 2015
@@ -1,4 +1,4 @@
 /apr/apr/branches/1.4.x:1003369,1101301
 /apr/apr/branches/1.6.x:1593600,1593612,1648831
-/apr/apr/trunk:733052,739635,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,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,1475509,14
 78905,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,1626564,1634615,1648830,1664769,1664775,1664904,1664911
+/apr/apr/trunk:733052,739635,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,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,1475509,14
 78905,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,1626564,1634615,1648830,1664769,1664775,1664904,1664911,1666411
 /apr/apr/trunk/test/testnames.c:1460405

Modified: apr/apr/branches/1.5.x/include/apr_skiplist.h
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.5.x/include/apr_skiplist.h?rev=1666446&r1=1666445&r2=1666446&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/include/apr_skiplist.h (original)
+++ apr/apr/branches/1.5.x/include/apr_skiplist.h Fri Mar 13 13:37:05 2015
@@ -172,7 +172,7 @@ APR_DECLARE(void *) apr_skiplist_previou
 
 /**
  * Insert an element into the skip list using the specified comparison function
- * allowing for duplicates.
+ * if it does not already exist.
  * @param sl The skip list
  * @param data The element to insert
  * @param comp The comparison function to use for placement into the skip list
@@ -182,7 +182,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
 
 /**
  * Insert an element into the skip list using the existing comparison function
- * allowing for duplicates.
+ * if it does not already exist.
  * @param sl The skip list
  * @param data The element to insert
  * @remark If no comparison function has been set for the skip list, the element

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=1666446&r1=1666445&r2=1666446&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/tables/apr_skiplist.c (original)
+++ apr/apr/branches/1.5.x/tables/apr_skiplist.c Fri Mar 13 13:37:05 2015
@@ -396,6 +396,10 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
     apr_skiplistnode *m, *p, *tmp, *ret = NULL;
     int nh = 1, ch;
 
+    if (!comp) {
+        return NULL;
+    }
+
     if (sl->preheight) {
         while (nh < sl->preheight && get_b_rand()) {
             nh++;
@@ -417,13 +421,14 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
      */
     m = sl->top;
     while (m) {
-        /*
-         * To maintain stability, dups (compared == 0) must be added
-         * AFTER each other.
-         */
         if (m->next) {
             int compared = comp(data, m->next->data);
-            if (compared >= 0) {
+            if (compared == 0) {
+                /* Keep the existing element(s) */
+                skiplist_qclear(&sl->stack_q);
+                return NULL;
+            }
+            if (compared > 0) {
                 m = m->next;
                 continue;
             }
@@ -506,20 +511,9 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
 
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
 {
-    if (!sl->compare) {
-        return NULL;
-    }
     return apr_skiplist_insert_compare(sl, data, sl->compare);
 }
 
-APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc
myfree)
-{
-    if (!sl->compare) {
-        return 0;
-    }
-    return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
-}
-
 #if 0
 void skiplist_print_struct(apr_skiplist * sl, char *prefix)
 {
@@ -588,6 +582,9 @@ APR_DECLARE(int) apr_skiplist_remove_com
 {
     apr_skiplistnode *m;
     apr_skiplist *sl;
+    if (!comp) {
+        return 0;
+    }
     if (comp == sli->comparek || !sli->index) {
         sl = sli;
     }
@@ -608,6 +605,11 @@ APR_DECLARE(int) apr_skiplist_remove_com
     return skiplisti_remove(sl, m, myfree);
 }
 
+APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc
myfree)
+{
+    return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
+}
+
 APR_DECLARE(void) apr_skiplist_remove_all(apr_skiplist *sl, apr_skiplist_freefunc myfree)
 {
     /*

Modified: apr/apr/branches/1.5.x/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.5.x/test/testskiplist.c?rev=1666446&r1=1666445&r2=1666446&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.5.x/test/testskiplist.c Fri Mar 13 13:37:05 2015
@@ -33,12 +33,26 @@
 static apr_pool_t *ptmp = NULL;
 static apr_skiplist *skiplist = NULL;
 
-/* Missing in 1.5.x, so emulate it */
-static apr_skiplistnode *apr_skiplist_addne(apr_skiplist *sl, void *data)
-{
-    if (apr_skiplist_find(skiplist, data, NULL))
-        return NULL;
-    return apr_skiplist_insert(skiplist, data);
+/* apr_skiplist_add[_compare]() are missing in 1.5.x,
+ * so emulate them (not thread-safe!)...
+ */
+static apr_skiplist_compare current_comp;
+static int add_comp(void *a, void *b)
+{
+    return current_comp(a, b) < 0 ? -1 : +1;
+}
+static apr_skiplistnode *apr_skiplist_add_compare(apr_skiplist *sl, void *data,
+                                                  apr_skiplist_compare comp)
+{
+    current_comp = comp;
+    return apr_skiplist_insert_compare(sl, data, add_comp);
+}
+static apr_skiplistnode *apr_skiplist_add(apr_skiplist *sl, void *data)
+{
+    /* Ugly, really, but should work *while* the compare function is the first
+     * field of the (opaque) skiplist struct, which is the case for now :p
+     */
+    return apr_skiplist_add_compare(sl, data, *(apr_skiplist_compare**)sl);
 }
 
 static int skiplist_get_size(abts_case *tc, apr_skiplist *sl)
@@ -65,7 +79,7 @@ static void skiplist_find(abts_case *tc,
 {
     const char *val;
 
-    apr_skiplist_addne(skiplist, "baton");
+    apr_skiplist_insert(skiplist, "baton");
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
@@ -82,32 +96,58 @@ static void skiplist_dontfind(abts_case
 static void skiplist_insert(abts_case *tc, void *data)
 {
     const char *val;
+    int i;
+
+    for (i = 0; i < 10; ++i) {
+        apr_skiplist_insert(skiplist, "baton");
+        ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
+        val = apr_skiplist_find(skiplist, "baton", NULL);
+        ABTS_PTR_NOTNULL(tc, val);
+        ABTS_STR_EQUAL(tc, "baton", val);
+    }
+
+    apr_skiplist_insert(skiplist, "foo");
+    ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
+    val = apr_skiplist_find(skiplist, "foo", NULL);
+    ABTS_PTR_NOTNULL(tc, val);
+    ABTS_STR_EQUAL(tc, "foo", val);
+
+    apr_skiplist_insert(skiplist, "atfirst");
+    ABTS_TRUE(tc, 3 == skiplist_get_size(tc, skiplist));
+    val = apr_skiplist_find(skiplist, "atfirst", NULL);
+    ABTS_PTR_NOTNULL(tc, val);
+    ABTS_STR_EQUAL(tc, "atfirst", val);
+}
+
+static void skiplist_add(abts_case *tc, void *data)
+{
+    const char *val;
     size_t i, n = skiplist_get_size(tc, skiplist);
 
     for (i = 0; i < 100; ++i) {
         n++;
-        apr_skiplist_insert(skiplist, "daton");
+        apr_skiplist_add(skiplist, "daton");
         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++;
-        apr_skiplist_insert(skiplist, "baton");
+        apr_skiplist_add(skiplist, "baton");
         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++;
-        apr_skiplist_insert(skiplist, "caton");
+        apr_skiplist_add(skiplist, "caton");
         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++;
-        apr_skiplist_insert(skiplist, "aaton");
+        apr_skiplist_add(skiplist, "aaton");
         ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "aaton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
@@ -127,9 +167,9 @@ static void skiplist_size(abts_case *tc,
 
     ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 
-    apr_skiplist_addne(skiplist, "abc");
-    apr_skiplist_addne(skiplist, "ghi");
-    apr_skiplist_addne(skiplist, "def");
+    apr_skiplist_insert(skiplist, "abc");
+    apr_skiplist_insert(skiplist, "ghi");
+    apr_skiplist_insert(skiplist, "def");
     val = apr_skiplist_find(skiplist, "abc", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "abc", val);
@@ -150,13 +190,13 @@ static void skiplist_remove(abts_case *t
 
     ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 
-    apr_skiplist_insert(skiplist, "baton");
+    apr_skiplist_add(skiplist, "baton");
     ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
 
-    apr_skiplist_insert(skiplist, "baton");
+    apr_skiplist_add(skiplist, "baton");
     ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
@@ -168,7 +208,7 @@ static void skiplist_remove(abts_case *t
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
 
-    apr_skiplist_insert(skiplist, "baton");
+    apr_skiplist_add(skiplist, "baton");
     ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
@@ -203,7 +243,7 @@ static void skiplist_random_loop(abts_ca
         else {
             batons[i] = apr_pstrdup(ptmp, batons[i % NUM_RAND]);
         }
-        apr_skiplist_insert(sl, batons[i]);
+        apr_skiplist_add(sl, batons[i]);
         val = apr_skiplist_find(sl, batons[i], NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, batons[i], val);
@@ -221,13 +261,13 @@ typedef struct elem {
 static void add_int_to_skiplist(apr_skiplist *list, int n){
     int* a = apr_skiplist_alloc(list, sizeof(int));
     *a = n;
-    apr_skiplist_insert(list, a);
+    apr_skiplist_add(list, a);
 }
 
 static void add_elem_to_skiplist(apr_skiplist *list, elem n){
     elem* a = apr_skiplist_alloc(list, sizeof(elem));
     *a = n;
-    apr_skiplist_insert(list, a);
+    apr_skiplist_add(list, a);
 }
 
 static int comp(void *a, void *b){
@@ -297,10 +337,10 @@ static void skiplist_test(abts_case *tc,
     val = apr_skiplist_pop(list, NULL);
     ABTS_PTR_EQUAL(tc, val, NULL);
 
-    apr_skiplist_insert(list, &first_forty_two);
+    apr_skiplist_add(list, &first_forty_two);
     add_int_to_skiplist(list, 1);
     add_int_to_skiplist(list, 142);
-    apr_skiplist_insert(list, &second_forty_two);
+    apr_skiplist_add(list, &second_forty_two);
     val = apr_skiplist_peek(list);
     ABTS_INT_EQUAL(tc, *val, 1);
     val = apr_skiplist_pop(list, NULL);
@@ -354,6 +394,7 @@ abts_suite *testskiplist(abts_suite *sui
     abts_run_test(suite, skiplist_find, NULL);
     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_destroy, NULL);
     abts_run_test(suite, skiplist_size, NULL);
     abts_run_test(suite, skiplist_remove, NULL);



Mime
View raw message