svn commit: r1664409 - in /apr/apr/branches/1.5.x: include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c

[ji...@apache.org]

Author: jim
Date: Thu Mar  5 16:54:09 2015
New Revision: 1664409

URL: http://svn.apache.org/r1664409
Log:
Skiplists should allow for dups by default (canon description).
Also, dups are added *after* each other, not before (for stability).

Modified:
    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

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=1664409&r1=1664408&r2=1664409&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/include/apr_skiplist.h (original)
+++ apr/apr/branches/1.5.x/include/apr_skiplist.h Thu Mar  5 16:54:09 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,7 +181,8 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
                                           void *data, apr_skiplist_compare comp);
 
 /**
- * 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

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=1664409&r1=1664408&r2=1664409&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/tables/apr_skiplist.c (original)
+++ apr/apr/branches/1.5.x/tables/apr_skiplist.c Thu Mar  5 16:54:09 2015
@@ -404,11 +404,11 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
         if (m->next) {
             compared = comp(data, m->next->data);
         }
-        if (compared == 0) {
-            free(stack);    /* OK. was malloc'ed */
-            return 0;
-        }
-        if ((m->next == NULL) || (compared < 0)) {
+        /*
+         * To maintain stability, dups must be added AFTER each
+         * other.
+         */
+        if ((m->next == NULL) || (compared <= 0)) {
             if (ch <= nh) {
                 /* push on stack */
                 stack[stacki++] = m;

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=1664409&r1=1664408&r2=1664409&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.5.x/test/testskiplist.c Thu Mar  5 16:54:09 2015
@@ -87,6 +87,24 @@ static void skiplist_test(abts_case *tc,
     /* empty */
     val = apr_skiplist_pop(list, NULL);
     ABTS_PTR_EQUAL(tc, val, NULL);
+
+    add_int_to_skiplist(list, 42);
+    add_int_to_skiplist(list, 1);
+    add_int_to_skiplist(list, 142);
+    add_int_to_skiplist(list, 42);
+    val = apr_skiplist_peek(list);
+    ABTS_INT_EQUAL(tc, *val, 1);
+    val = apr_skiplist_pop(list, NULL);
+    ABTS_INT_EQUAL(tc, *val, 1);
+    val = apr_skiplist_peek(list);
+    ABTS_INT_EQUAL(tc, *val, 42);
+    val = apr_skiplist_pop(list, NULL);
+    ABTS_INT_EQUAL(tc, *val, 42);
+    val = apr_skiplist_pop(list, NULL);
+    ABTS_INT_EQUAL(tc, *val, 42);
+    val = apr_skiplist_peek(list);
+    ABTS_INT_EQUAL(tc, *val, 142);
+
 }
 
 abts_suite *testskiplist(abts_suite *suite)