You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@apr.apache.org by ji...@apache.org on 2015/03/05 17:53:25 UTC
svn commit: r1664408 - in /apr/apr/branches/1.6.x: include/apr_skiplist.h
tables/apr_skiplist.c test/testskiplist.c
Author: jim
Date: Thu Mar 5 16:53:25 2015
New Revision: 1664408
URL: http://svn.apache.org/r1664408
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.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
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=1664408&r1=1664407&r2=1664408&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/include/apr_skiplist.h (original)
+++ apr/apr/branches/1.6.x/include/apr_skiplist.h Thu Mar 5 16:53:25 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.6.x/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/tables/apr_skiplist.c?rev=1664408&r1=1664407&r2=1664408&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/tables/apr_skiplist.c (original)
+++ apr/apr/branches/1.6.x/tables/apr_skiplist.c Thu Mar 5 16:53:25 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.6.x/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/test/testskiplist.c?rev=1664408&r1=1664407&r2=1664408&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.6.x/test/testskiplist.c Thu Mar 5 16:53:25 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)