apr-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From j..@apache.org
Subject svn commit: r1664406 - in /apr/apr/trunk: include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c
Date Thu, 05 Mar 2015 16:51:40 GMT
Author: jim
Date: Thu Mar  5 16:51:39 2015
New Revision: 1664406

URL: http://svn.apache.org/r1664406
Log:
FIX: Skiplists should allow for dups by default. Also, when added, dups
are added *after* each other, not before

Modified:
    apr/apr/trunk/include/apr_skiplist.h
    apr/apr/trunk/tables/apr_skiplist.c
    apr/apr/trunk/test/testskiplist.c

Modified: apr/apr/trunk/include/apr_skiplist.h
URL: http://svn.apache.org/viewvc/apr/apr/trunk/include/apr_skiplist.h?rev=1664406&r1=1664405&r2=1664406&view=diff
==============================================================================
--- apr/apr/trunk/include/apr_skiplist.h (original)
+++ apr/apr/trunk/include/apr_skiplist.h Thu Mar  5 16:51:39 2015
@@ -171,7 +171,8 @@ APR_DECLARE(void *) apr_skiplist_next(ap
 APR_DECLARE(void *) apr_skiplist_previous(apr_skiplist *sl, apr_skiplistnode **iter);
 
 /**
- * Insert an element into the skip list using the specified comparison function.
+ * Insert an element into the skip list using the specified comparison function
+ * allowing for 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
@@ -180,37 +181,38 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
                                           void *data, apr_skiplist_compare comp);
 
 /**
- * Add an element into the skip list using the specified comparison function.
+ * Add an element into the skip list using the specified comparison function
+ * if it does not already exist.
  * @param sl The skip list
  * @param data The element to add
  * @param comp The comparison function to use for placement into the skip list
  */
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl,
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne_compare(apr_skiplist *sl,
                                           void *data, apr_skiplist_compare comp);
 
 /**
- * Add an element into the skip list using the existing comparison function.
+ * Add an element into the skip list using the existing comparison function
+ * 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
- * will not be inserted and NULL will be returned. This allows for multiple
- * values to be added to the skiplist. To retain value, use apr_skiplist_insert().
+ * will not be inserted and NULL will be returned.
  */
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist* sl, void *data);
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne(apr_skiplist* sl, void *data);
 
 /**
- * Insert an element into the skip list using the existing comparison function.
+ * Insert an element into the skip list using the existing comparison function
+ * allowing for duplicates.
  * @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
- * will not be inserted and NULL will be returned. Previous values will
- * be not be over-written. Use apr_skiplist_add() to allow multiple values.
+ * will not be inserted and NULL will be returned.
  */
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist* sl, void *data);
 
 /**
  * Remove an element from the skip list using the specified comparison function for
- * locating the element.
+ * locating the element. In the case of duplicates, the 1st entry will be removed.
  * @param sl The skip list
  * @param data The element to remove
  * @param myfree A function to be called for each removed element
@@ -223,7 +225,7 @@ APR_DECLARE(int) apr_skiplist_remove_com
 
 /**
  * Remove an element from the skip list using the existing comparison function for
- * locating the element.
+ * locating the element. In the case of duplicates, the 1st entry will be removed.
  * @param sl The skip list
  * @param data The element to remove
  * @param myfree A function to be called for each removed element

Modified: apr/apr/trunk/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1664406&r1=1664405&r2=1664406&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_skiplist.c (original)
+++ apr/apr/trunk/tables/apr_skiplist.c Thu Mar  5 16:51:39 2015
@@ -427,7 +427,7 @@ static apr_skiplistnode *insert_compare(
             skiplist_stack_clear(sl);
             return NULL;
         }
-        if (compared < 0) {
+        if (compared < 0 || ((compared <= 0) && add)) {
             if (ch <= nh) {
                 /* push on stack */
                 skiplist_stack_push(sl, m);
@@ -507,7 +507,7 @@ static apr_skiplistnode *insert_compare(
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
                                       apr_skiplist_compare comp)
 {
-    return insert_compare(sl, data, comp, 0);
+    return insert_compare(sl, data, comp, 1);
 }
 
 APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
@@ -515,21 +515,21 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
     if (!sl->compare) {
         return NULL;
     }
-    return insert_compare(sl, data, sl->compare, 0);
+    return insert_compare(sl, data, sl->compare, 1);
 }
 
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist *sl, void *data,
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne_compare(apr_skiplist *sl, void *data,
                                       apr_skiplist_compare comp)
 {
-    return insert_compare(sl, data, comp, 1);
+    return insert_compare(sl, data, comp, 0);
 }
 
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne(apr_skiplist *sl, void *data)
 {
     if (!sl->compare) {
         return NULL;
     }
-    return insert_compare(sl, data, sl->compare, 1);
+    return insert_compare(sl, data, sl->compare, 0);
 }
 
 APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc
myfree)

Modified: apr/apr/trunk/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/test/testskiplist.c?rev=1664406&r1=1664405&r2=1664406&view=diff
==============================================================================
--- apr/apr/trunk/test/testskiplist.c (original)
+++ apr/apr/trunk/test/testskiplist.c Thu Mar  5 16:51:39 2015
@@ -58,7 +58,7 @@ static void skiplist_find(abts_case *tc,
 {
     const char *val;
 
-    apr_skiplist_insert(skiplist, "baton");
+    apr_skiplist_addne(skiplist, "baton");
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
@@ -72,13 +72,13 @@ static void skiplist_dontfind(abts_case
     ABTS_PTR_EQUAL(tc, NULL, (void *)val);
 }
 
-static void skiplist_insert(abts_case *tc, void *data)
+static void skiplist_addne(abts_case *tc, void *data)
 {
     const char *val;
     int i, height = 0;
 
     for (i = 0; i < 10; ++i) {
-        apr_skiplist_insert(skiplist, "baton");
+        apr_skiplist_addne(skiplist, "baton");
         ABTS_TRUE(tc, 1 == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "baton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
@@ -92,48 +92,48 @@ static void skiplist_insert(abts_case *t
         }
     }
 
-    apr_skiplist_insert(skiplist, "foo");
+    apr_skiplist_addne(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");
+    apr_skiplist_addne(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)
+static void skiplist_insert(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_add(skiplist, "daton");
+        apr_skiplist_insert(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_add(skiplist, "baton");
+        apr_skiplist_insert(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_add(skiplist, "caton");
+        apr_skiplist_insert(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_add(skiplist, "aaton");
+        apr_skiplist_insert(skiplist, "aaton");
         ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
         val = apr_skiplist_find(skiplist, "aaton", NULL);
         ABTS_PTR_NOTNULL(tc, val);
@@ -153,9 +153,9 @@ static void skiplist_size(abts_case *tc,
 
     ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 
-    apr_skiplist_insert(skiplist, "abc");
-    apr_skiplist_insert(skiplist, "ghi");
-    apr_skiplist_insert(skiplist, "def");
+    apr_skiplist_addne(skiplist, "abc");
+    apr_skiplist_addne(skiplist, "ghi");
+    apr_skiplist_addne(skiplist, "def");
     val = apr_skiplist_find(skiplist, "abc", NULL);
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "abc", val);
@@ -176,13 +176,13 @@ static void skiplist_remove(abts_case *t
 
     ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
 
-    apr_skiplist_add(skiplist, "baton");
+    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_add(skiplist, "baton");
+    apr_skiplist_insert(skiplist, "baton");
     ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
@@ -194,7 +194,7 @@ static void skiplist_remove(abts_case *t
     ABTS_PTR_NOTNULL(tc, val);
     ABTS_STR_EQUAL(tc, "baton", val);
 
-    apr_skiplist_add(skiplist, "baton");
+    apr_skiplist_insert(skiplist, "baton");
     ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
     val = apr_skiplist_find(skiplist, "baton", NULL);
     ABTS_PTR_NOTNULL(tc, val);
@@ -231,7 +231,7 @@ static void skiplist_random_loop(abts_ca
         else {
             batons[i] = apr_pstrdup(ptmp, batons[i % NUM_RAND]);
         }
-        apr_skiplist_add(sl, batons[i]);
+        apr_skiplist_insert(sl, batons[i]);
         val = apr_skiplist_find(sl, batons[i], NULL);
         ABTS_PTR_NOTNULL(tc, val);
         ABTS_STR_EQUAL(tc, batons[i], val);
@@ -244,7 +244,7 @@ static void skiplist_random_loop(abts_ca
 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_addne(list, a);
 }
 
 static int comp(void *a, void *b){
@@ -309,8 +309,8 @@ abts_suite *testskiplist(abts_suite *sui
     abts_run_test(suite, skiplist_init, NULL);
     abts_run_test(suite, skiplist_find, NULL);
     abts_run_test(suite, skiplist_dontfind, NULL);
+    abts_run_test(suite, skiplist_addne, 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