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:51:40 UTC
svn commit: r1664406 - in /apr/apr/trunk: include/apr_skiplist.h
tables/apr_skiplist.c test/testskiplist.c
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);
Re: svn commit: r1664406 - in /apr/apr/trunk: include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c
Posted by Jim Jagielski <ji...@jaguNET.com>.
> On Mar 5, 2015, at 12:36 PM, Yann Ylavic <yl...@gmail.com> wrote:
>
> On Thu, Mar 5, 2015 at 5:51 PM, <ji...@apache.org> wrote:
>> 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/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)) {
>
> This could be (compare <= 0) alone here, since (compare == 0 && !add)
> is caught above.
>
> Otherwise, ++1 to this!
Nice optimization. +1
Re: svn commit: r1664406 - in /apr/apr/trunk: include/apr_skiplist.h
tables/apr_skiplist.c test/testskiplist.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Thu, Mar 5, 2015 at 5:51 PM, <ji...@apache.org> wrote:
> 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/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)) {
This could be (compare <= 0) alone here, since (compare == 0 && !add)
is caught above.
Otherwise, ++1 to this!