You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@apr.apache.org by yl...@apache.org on 2015/03/05 22:49:52 UTC
svn commit: r1664491 - in /apr/apr/branches/1.5.x: include/apr_skiplist.h
tables/apr_skiplist.c test/testskiplist.c
Author: ylavic
Date: Thu Mar 5 21:49:52 2015
New Revision: 1664491
URL: http://svn.apache.org/r1664491
Log:
apr_skiplist: merge r1611023,r1611107,r1611110,r1611120,r1611125,
r1611184,r1611193,r1611466,r1664406,r1664447,
r1664451,r1664471 from trunk
r1611023 | ylavic | 2014-07-16 16:32:05 +0200 (Wed, 16 Jul 2014) | 5 lines
Three fixes:
- double size increment in insert_compare(),
- multiple apr_skiplist_free() called on the same value in remove_compare(),
- return 0 instead of NULL for void*.
r1611107 | ylavic | 2014-07-16 19:38:03 +0200 (Wed, 16 Jul 2014) | 6 lines
We do not garantee zero-ed memory for apr_skiplist_alloc(), neither in
the description, nor in the code for reused chunks.
So always allocate raw memory and don't rely on zero-ed one after internal
calls to apr_skiplist_alloc().
r1611110 | ylavic | 2014-07-16 19:42:22 +0200 (Wed, 16 Jul 2014) | 1 line
Improve skiplist tests.
r1611120 | ylavic | 2014-07-16 20:10:33 +0200 (Wed, 16 Jul 2014) | 3 lines
Call free() on the skiplist structure in apr_skiplist_destroy() if it was
apr_skiplist_init()ialized without a pool (ie. malloc()ed).
r1611125 | ylavic | 2014-07-16 20:21:33 +0200 (Wed, 16 Jul 2014) | 3 lines
Let apr_skiplist_find_compare() handle given NULL iterator, and be safe
from NULL returns.
r1611184 | ylavic | 2014-07-16 22:53:11 +0200 (Wed, 16 Jul 2014) | 4 lines
Reuse the skiplist's stack needed by insert_compare() by growing it with adds.
Rename the "replace" argument as "add" (negating the boolean) to avoid confusion
since the skiplist never replaces any element (add or preserve semantic).
r1611193 | ylavic | 2014-07-16 23:16:06 +0200 (Wed, 16 Jul 2014) | 4 lines
Don't grow the skiplist's height if the element is finally not inserted (preserve semantic).
Do this by moving the top node creation after insertion occured, and linking to the just
inserted node(s).
r1611466 | ylavic | 2014-07-17 22:26:30 +0200 (Thu, 17 Jul 2014) | 5 lines
Follow up to r1611193: update the inserted node's top while looping should we
have to create more than one top node (eg. preheight > 0).
(the check on p != NULL can be omited since it can't be here).
r1664406 | jim | 2015-03-05 17:51:39 +0100 (Thu, 05 Mar 2015) | 3 lines
FIX: Skiplists should allow for dups by default. Also, when added, dups
are added *after* each other, not before
r1664447 | ylavic | 2015-03-05 19:31:45 +0100 (Thu, 05 Mar 2015) | 1 line
skiplist: Follow up to r1664406: use insert() in apr_skiplist_merge and optimize test in insert_compare().
r1664451 | ylavic | 2015-03-05 19:42:35 +0100 (Thu, 05 Mar 2015) | 1 line
skiplist: Follow up to r1664406+r1664447: Better optimize test in insert_compare() and keep find_compare() in sync.
r1664471 | ylavic | 2015-03-05 21:00:25 +0100 (Thu, 05 Mar 2015) | 1 line
skiplist: improve duplicates ordering test.
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=1664491&r1=1664490&r2=1664491&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 21:49:52 2015
@@ -192,7 +192,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
/**
* 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
@@ -205,7 +205,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/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=1664491&r1=1664490&r2=1664491&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 21:49:52 2015
@@ -30,7 +30,7 @@ struct apr_skiplist {
apr_skiplist_compare comparek;
int height;
int preheight;
- int size;
+ size_t size;
apr_skiplistnode *top;
apr_skiplistnode *bottom;
/* These two are needed for appending */
@@ -38,6 +38,9 @@ struct apr_skiplist {
apr_skiplistnode *bottomend;
apr_skiplist *index;
apr_array_header_t *memlist;
+ apr_skiplistnode **stack;
+ size_t stack_pos,
+ stack_len;
apr_pool_t *pool;
};
@@ -52,10 +55,6 @@ struct apr_skiplistnode {
apr_skiplist *sl;
};
-#ifndef MIN
-#define MIN(a,b) ((a<b)?(a):(b))
-#endif
-
static int get_b_rand(void)
{
static int ph = 32; /* More bits than we will ever use */
@@ -103,7 +102,7 @@ APR_DECLARE(void *) apr_skiplist_alloc(a
memlist++;
}
/* no free chunks */
- ptr = apr_pcalloc(sl->pool, size);
+ ptr = apr_palloc(sl->pool, size);
if (!ptr) {
return ptr;
}
@@ -122,7 +121,7 @@ APR_DECLARE(void *) apr_skiplist_alloc(a
return ptr;
}
else {
- return calloc(1, size);
+ return malloc(size);
}
}
@@ -149,6 +148,43 @@ APR_DECLARE(void) apr_skiplist_free(apr_
}
}
+static apr_status_t skiplist_stack_push(apr_skiplist *sl, apr_skiplistnode *m)
+{
+ if (sl->stack_pos >= sl->stack_len) {
+ apr_skiplistnode **ptr;
+ size_t len = sl->stack_pos * 2;
+ if (len < 32) {
+ len = 32;
+ }
+ if (sl->pool) {
+ ptr = apr_palloc(sl->pool, len * sizeof(*ptr));
+ if (ptr) {
+ memcpy(ptr, sl->stack, sl->stack_pos * sizeof(*ptr));
+ }
+ }
+ else {
+ ptr = realloc(sl->stack, len * sizeof(*ptr));
+ }
+ if (!ptr) {
+ return APR_ENOMEM;
+ }
+ sl->stack = ptr;
+ sl->stack_len = len;
+ }
+ sl->stack[sl->stack_pos++] = m;
+ return APR_SUCCESS;
+}
+
+static APR_INLINE apr_skiplistnode *skiplist_stack_pop(apr_skiplist *sl)
+{
+ return (sl->stack_pos > 0) ? sl->stack[--sl->stack_pos] : NULL;
+}
+
+static APR_INLINE void skiplist_stack_clear(apr_skiplist *sl)
+{
+ sl->stack_pos = 0;
+}
+
static apr_status_t skiplisti_init(apr_skiplist **s, apr_pool_t *p)
{
apr_skiplist *sl;
@@ -158,6 +194,9 @@ static apr_status_t skiplisti_init(apr_s
}
else {
sl = calloc(1, sizeof(apr_skiplist));
+ if (!sl) {
+ return APR_ENOMEM;
+ }
}
#if 0
sl->compare = (apr_skiplist_compare) NULL;
@@ -258,39 +297,36 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data, apr_skiplistnode **iter)
{
- void *ret;
- apr_skiplistnode *aiter;
if (!sl->compare) {
- return 0;
- }
- if (iter) {
- ret = apr_skiplist_find_compare(sl, data, iter, sl->compare);
- }
- else {
- ret = apr_skiplist_find_compare(sl, data, &aiter, sl->compare);
+ return NULL;
}
- return ret;
+ return apr_skiplist_find_compare(sl, data, iter, sl->compare);
}
static int skiplisti_find_compare(apr_skiplist *sl, void *data,
apr_skiplistnode **ret,
apr_skiplist_compare comp)
{
- apr_skiplistnode *m = NULL;
int count = 0;
+ apr_skiplistnode *m;
m = sl->top;
while (m) {
int compared;
- compared = (m->next) ? comp(data, m->next->data) : -1;
- if (compared == 0) {
- m = m->next;
- while (m->down) {
- m = m->down;
+ if (m->next) {
+ compared = comp(data, m->next->data);
+ if (compared == 0) {
+ m = m->next;
+ while (m->down) {
+ m = m->down;
+ }
+ *ret = m;
+ return count;
}
- *ret = m;
- return count;
}
- if ((m->next == NULL) || (compared < 0)) {
+ else {
+ compared = -1;
+ }
+ if (compared < 0) {
m = m->down;
count++;
}
@@ -307,17 +343,26 @@ APR_DECLARE(void *) apr_skiplist_find_co
apr_skiplistnode **iter,
apr_skiplist_compare comp)
{
- apr_skiplistnode *m = NULL;
+ apr_skiplistnode *m;
apr_skiplist *sl;
if (comp == sli->compare || !sli->index) {
sl = sli;
}
else {
apr_skiplist_find(sli->index, (void *)comp, &m);
+ if (!m) {
+ if (iter) {
+ *iter = NULL;
+ }
+ return NULL;
+ }
sl = (apr_skiplist *) m->data;
}
- skiplisti_find_compare(sl, data, iter, sl->comparek);
- return (iter && *iter) ? ((*iter)->data) : NULL;
+ skiplisti_find_compare(sl, data, &m, sl->comparek);
+ if (iter) {
+ *iter = m;
+ }
+ return (m) ? m->data : NULL;
}
@@ -339,32 +384,22 @@ APR_DECLARE(void *) apr_skiplist_previou
return (*iter) ? ((*iter)->data) : NULL;
}
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
-{
- if (!sl->compare) {
- return 0;
- }
- return apr_skiplist_insert_compare(sl, data, sl->compare);
-}
-
APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
apr_skiplist_compare comp)
{
- apr_skiplistnode *m, *p, *tmp, *ret = NULL, **stack;
- int nh = 1, ch, stacki;
+ apr_skiplistnode *m, *p, *tmp, *ret = NULL;
+ int nh = 1, ch;
if (!sl->top) {
sl->height = 1;
sl->topend = sl->bottomend = sl->top = sl->bottom =
(apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
-#if 0
- sl->top->next = (apr_skiplistnode *)NULL;
- sl->top->data = (apr_skiplistnode *)NULL;
- sl->top->prev = (apr_skiplistnode *)NULL;
- sl->top->up = (apr_skiplistnode *)NULL;
- sl->top->down = (apr_skiplistnode *)NULL;
- sl->top->nextindex = (apr_skiplistnode *)NULL;
- sl->top->previndex = (apr_skiplistnode *)NULL;
-#endif
+ sl->top->next = NULL;
+ sl->top->data = NULL;
+ sl->top->prev = NULL;
+ sl->top->up = NULL;
+ sl->top->down = NULL;
+ sl->top->nextindex = NULL;
+ sl->top->previndex = NULL;
sl->top->sl = sl;
}
if (sl->preheight) {
@@ -377,41 +412,32 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
nh++;
}
}
- /* Now we have the new height at which we wish to insert our new node */
- /*
- * Let us make sure that our tree is a least that tall (grow if
- * necessary)
- */
- for (; sl->height < nh; sl->height++) {
- sl->top->up =
- (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
- sl->top->up->down = sl->top;
- sl->top = sl->topend = sl->top->up;
- sl->top->prev = sl->top->next = sl->top->nextindex =
- sl->top->previndex = sl->top->up = NULL;
- sl->top->data = NULL;
- sl->top->sl = sl;
- }
ch = sl->height;
- /* Find the node (or node after which we would insert) */
- /* Keep a stack to pop back through for insertion */
- /* malloc() is OK since we free the temp stack */
+
+ /* Now we have in nh the height at which we wish to insert our new node,
+ * and in ch the current height: don't create skip paths to the inserted
+ * element until the walk down through the tree (which decrements ch)
+ * reaches nh. From there, any walk down pushes the current node on a
+ * stack (the node(s) after which we would insert) to pop back through
+ * for insertion later.
+ */
m = sl->top;
- stack = (apr_skiplistnode **)malloc(sizeof(apr_skiplistnode *) * (nh));
- stacki = 0;
while (m) {
- int compared = -1;
+ int compared;
if (m->next) {
compared = comp(data, m->next->data);
}
+ else {
+ compared = -1;
+ }
/*
* To maintain stability, dups must be added AFTER each
* other.
*/
- if ((m->next == NULL) || (compared <= 0)) {
+ if (compared <= 0) {
if (ch <= nh) {
/* push on stack */
- stack[stacki++] = m;
+ skiplist_stack_push(sl, m);
}
m = m->down;
ch--;
@@ -422,8 +448,7 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
}
/* Pop the stack and insert nodes */
p = NULL;
- for (; stacki > 0; stacki--) {
- m = stack[stacki - 1];
+ while ((m = skiplist_stack_pop(sl))) {
tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
tmp->next = m->next;
if (m->next) {
@@ -436,17 +461,38 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
if (p) {
p->up = tmp;
}
+ else {
+ /* This sets ret to the bottom-most node we are inserting */
+ ret = tmp;
+ }
tmp->data = data;
tmp->sl = sl;
m->next = tmp;
- /* This sets ret to the bottom-most node we are inserting */
- if (!p) {
- ret = tmp;
- sl->size++; /* this seems to go here got each element to be counted */
- }
p = tmp;
}
- free(stack); /* OK. was malloc'ed */
+
+ /* Now we are sure the node is inserted, grow our tree to 'nh' tall */
+ for (; sl->height < nh; sl->height++) {
+ m = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
+ tmp = (apr_skiplistnode *)apr_skiplist_alloc(sl, sizeof(apr_skiplistnode));
+ m->up = m->prev = m->nextindex = m->previndex = NULL;
+ m->next = tmp;
+ m->down = sl->top;
+ m->data = NULL;
+ m->sl = sl;
+ if (sl->top) {
+ sl->top->up = m;
+ }
+ else {
+ sl->bottom = sl->bottomend = m;
+ }
+ sl->top = sl->topend = tmp->prev = m;
+ tmp->up = tmp->next = tmp->nextindex = tmp->previndex = NULL;
+ tmp->down = p;
+ tmp->data = data;
+ tmp->sl = sl;
+ p = p->up = tmp;
+ }
if (sl->index != NULL) {
/*
* this is a external insertion, we must insert into each index as
@@ -461,13 +507,18 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
li = ni;
}
}
- else {
- /* sl->size++; */
- }
sl->size++;
return ret;
}
+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) {
@@ -548,6 +599,9 @@ APR_DECLARE(int) apr_skiplist_remove_com
}
else {
apr_skiplist_find(sli->index, (void *)comp, &m);
+ if (!m) {
+ return 0;
+ }
sl = (apr_skiplist *) m->data;
}
skiplisti_find_compare(sl, data, &m, comp);
@@ -575,12 +629,13 @@ APR_DECLARE(void) apr_skiplist_remove_al
myfree(p->data);
while (m) {
u = m->up;
- apr_skiplist_free(sl, p);
+ apr_skiplist_free(sl, m);
m = u;
}
m = p;
}
sl->top = sl->bottom = NULL;
+ sl->topend = sl->bottomend = NULL;
sl->height = 0;
sl->size = 0;
}
@@ -618,6 +673,9 @@ APR_DECLARE(void) apr_skiplist_destroy(a
while (apr_skiplist_pop(sl->index, skiplisti_destroy) != NULL)
;
apr_skiplist_remove_all(sl, myfree);
+ if (!sl->pool) {
+ free(sl);
+ }
}
APR_DECLARE(apr_skiplist *) apr_skiplist_merge(apr_skiplist *sl1, apr_skiplist *sl2)
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=1664491&r1=1664490&r2=1664491&view=diff
==============================================================================
--- apr/apr/branches/1.5.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.5.x/test/testskiplist.c Thu Mar 5 21:49:52 2015
@@ -30,6 +30,189 @@
#include <string.h>
#endif
+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);
+}
+
+static int skiplist_get_size(abts_case *tc, apr_skiplist *sl)
+{
+ size_t size = 0;
+ apr_skiplistnode *n;
+ for (n = apr_skiplist_getlist(sl); n; apr_skiplist_next(sl, &n)) {
+ ++size;
+ }
+ return size;
+}
+
+static void skiplist_init(abts_case *tc, void *data)
+{
+ apr_time_t now = apr_time_now();
+ srand((unsigned int)(((now >> 32) ^ now) & 0xffffffff));
+
+ ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&skiplist, p));
+ ABTS_PTR_NOTNULL(tc, skiplist);
+ apr_skiplist_set_compare(skiplist, (void*)strcmp, (void*)strcmp);
+}
+
+static void skiplist_find(abts_case *tc, void *data)
+{
+ const char *val;
+
+ apr_skiplist_addne(skiplist, "baton");
+ val = apr_skiplist_find(skiplist, "baton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "baton", val);
+}
+
+static void skiplist_dontfind(abts_case *tc, void *data)
+{
+ const char *val;
+
+ val = apr_skiplist_find(skiplist, "keynotthere", NULL);
+ ABTS_PTR_EQUAL(tc, NULL, (void *)val);
+}
+
+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_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_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_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_insert(skiplist, "aaton");
+ ABTS_TRUE(tc, n == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "aaton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "aaton", val);
+ }
+}
+
+static void skiplist_destroy(abts_case *tc, void *data)
+{
+ apr_skiplist_destroy(skiplist, NULL);
+ ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+}
+
+static void skiplist_size(abts_case *tc, void *data)
+{
+ const char *val;
+
+ ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+
+ 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);
+ val = apr_skiplist_find(skiplist, "ghi", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "ghi", val);
+ val = apr_skiplist_find(skiplist, "def", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "def", val);
+
+ ABTS_TRUE(tc, 3 == skiplist_get_size(tc, skiplist));
+ apr_skiplist_destroy(skiplist, NULL);
+}
+
+static void skiplist_remove(abts_case *tc, void *data)
+{
+ const char *val;
+
+ ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+
+ 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, "baton");
+ ABTS_TRUE(tc, 2 == 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_remove(skiplist, "baton", NULL);
+ 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");
+ ABTS_TRUE(tc, 2 == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "baton", NULL);
+ ABTS_PTR_NOTNULL(tc, val);
+ ABTS_STR_EQUAL(tc, "baton", val);
+
+ /* remove all "baton"s */
+ while (apr_skiplist_remove(skiplist, "baton", NULL))
+ ;
+ ABTS_TRUE(tc, 0 == skiplist_get_size(tc, skiplist));
+ val = apr_skiplist_find(skiplist, "baton", NULL);
+ ABTS_PTR_EQUAL(tc, NULL, val);
+}
+
+#define NUM_RAND (100)
+#define NUM_FIND (3 * NUM_RAND)
+static void skiplist_random_loop(abts_case *tc, void *data)
+{
+ char **batons;
+ apr_skiplist *sl;
+ const char *val;
+ int i;
+
+ ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&sl, ptmp));
+ apr_skiplist_set_compare(sl, (void*)strcmp, (void*)strcmp);
+
+ batons = apr_palloc(ptmp, NUM_FIND * sizeof(char*));
+
+ for (i = 0; i < NUM_FIND; ++i) {
+ if (i < NUM_RAND) {
+ batons[i] = apr_psprintf(ptmp, "%.6u", rand() % 1000000);
+ }
+ else {
+ batons[i] = apr_pstrdup(ptmp, batons[i % NUM_RAND]);
+ }
+ 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);
+ }
+
+ apr_pool_clear(ptmp);
+}
+
+
static void add_int_to_skiplist(apr_skiplist *list, int n){
int* a = apr_skiplist_alloc(list, sizeof(int));
*a = n;
@@ -40,7 +223,6 @@ static int comp(void *a, void *b){
return *((int*) a) - *((int*) b);
}
-
static int compk(void *a, void *b){
return comp(a, b);
}
@@ -50,10 +232,10 @@ static void skiplist_test(abts_case *tc,
int i = 0, j = 0;
int *val = NULL;
apr_skiplist * list = NULL;
- apr_pool_t *p;
+ int first_forty_two = 42,
+ second_forty_two = 42;
- apr_pool_create(&p, NULL);
- apr_skiplist_init(&list, p);
+ ABTS_INT_EQUAL(tc, APR_SUCCESS, apr_skiplist_init(&list, ptmp));
apr_skiplist_set_compare(list, comp, compk);
/* insert 10 objects */
@@ -88,31 +270,49 @@ static void skiplist_test(abts_case *tc,
val = apr_skiplist_pop(list, NULL);
ABTS_PTR_EQUAL(tc, val, NULL);
- add_int_to_skiplist(list, 42);
+ apr_skiplist_insert(list, &first_forty_two);
add_int_to_skiplist(list, 1);
add_int_to_skiplist(list, 142);
- add_int_to_skiplist(list, 42);
+ apr_skiplist_insert(list, &second_forty_two);
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_PTR_EQUAL(tc, val, &second_forty_two);
ABTS_INT_EQUAL(tc, *val, 42);
val = apr_skiplist_pop(list, NULL);
+ ABTS_PTR_EQUAL(tc, val, &second_forty_two);
ABTS_INT_EQUAL(tc, *val, 42);
val = apr_skiplist_pop(list, NULL);
+ ABTS_PTR_EQUAL(tc, val, &first_forty_two);
ABTS_INT_EQUAL(tc, *val, 42);
val = apr_skiplist_peek(list);
ABTS_INT_EQUAL(tc, *val, 142);
+ apr_pool_clear(ptmp);
}
+
abts_suite *testskiplist(abts_suite *suite)
{
suite = ADD_SUITE(suite)
+ apr_pool_create(&ptmp, p);
+
+ 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_insert, NULL);
+ abts_run_test(suite, skiplist_destroy, NULL);
+ abts_run_test(suite, skiplist_size, NULL);
+ abts_run_test(suite, skiplist_remove, NULL);
+ abts_run_test(suite, skiplist_random_loop, NULL);
+
abts_run_test(suite, skiplist_test, NULL);
+ apr_pool_destroy(ptmp);
+
return suite;
}