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 21:31:21 UTC
svn commit: r1664475 - in /apr/apr/branches/1.6.x: ./ CHANGES
include/apr_skiplist.h tables/apr_skiplist.c test/testskiplist.c
Author: ylavic
Date: Thu Mar 5 20:31:21 2015
New Revision: 1664475
URL: http://svn.apache.org/r1664475
Log:
apr_skiplist: merge r1597797,r1597803,r1605104,r1611023,r1611107,r1611110,
r1611117,r1611120,r1611125,r1611184,r1611193,r1611466,
r1611515,r1611517,r1664406,r1664447,r1664451,r1664471
from trunk
r1597797 | jim | 2014-05-27 16:20:29 +0200 (Tue, 27 May 2014) | 2 lines
apr_skiplist_add()... idea from yann
r1597803 | jim | 2014-05-27 17:14:44 +0200 (Tue, 27 May 2014) | 2 lines
update docco
r1605104 | jim | 2014-06-24 17:05:26 +0200 (Tue, 24 Jun 2014) | 2 lines
missing proto
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.
r1611117 | ylavic | 2014-07-16 19:59:50 +0200 (Wed, 16 Jul 2014) | 3 lines
Use apr_skiplist_add() instead of apr_skiplist_insert() to merge skiplists
since doublons need to be merged too.
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).
r1611515 | ylavic | 2014-07-18 01:58:02 +0200 (Fri, 18 Jul 2014) | 3 lines
Provide apr_skiplist_size/height/preheight() to get the corresponding values
in O(1), and apr_skiplist_set_preheight() to configure preheight mode.
r1611517 | ylavic | 2014-07-18 02:25:24 +0200 (Fri, 18 Jul 2014) | 2 lines
Follow up to r1611515: remove useless <limits.h> inclusion (for unused INT_MAX).
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.6.x/ (props changed)
apr/apr/branches/1.6.x/CHANGES
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
Propchange: apr/apr/branches/1.6.x/
------------------------------------------------------------------------------
--- svn:mergeinfo (original)
+++ svn:mergeinfo Thu Mar 5 20:31:21 2015
@@ -1,4 +1,4 @@
/apr/apr/branches/1.4.x:1003369,1101301
-/apr/apr/trunk:733052,739635,741862,741866-741867,741869,741871,745763-745764,746310,747990,748080,748361,748371,748565,748888,748902,748988,749810,760443,775683,782838,783398,783958,784633,784773,788588,789050,793192-793193,794118,794485,795267,799497,800627,809745,809854,810472,811455,813063,821306,829490,831641,832904,835607,888669,892028,892159,892435,892909,896382,896653,908427,910419,910597,917819,917837-917838,925965,929796,931973,951771,960665,960671,979891,983618,989450,990435,1003338,1044440,1044447,1055657,1072165,1078845,1081462,1081495,1083038,1083242,1084662,1086695,1088023,1089031,1089129,1089438,1099348,1103310,1183683,1183685-1183686,1183688,1183693,1183698,1213382,1235047,1236970,1237078,1237507,1240472,1340286,1340288,1340470,1341193,1341196,1343233,1343243,1367050,1368819,1370494,1372018,1372022,1372093,1372849,1376957,1384764,1389077,1400200,1402868,1405985,1406690,1420106,1420109,1425356,1428809,1438940,1438957-1438959,1442903,1449568,1456418,1459994,1460179-14
60180,1460241,1460399,1460405,1462738,1462813,1470186,1470348,1475509,1478905,1480067,1481262,1481265,1484271,1487796,1489517,1496407,1502804,1510354,1516261,1523384,1523479,1523484,1523505,1523521,1523604,1523613,1523615,1523844-1523845,1523853,1524014,1524031,1528797,1528809,1529488,1529495,1529515,1529521,1529668,1530786,1530800,1530988,1531554,1531768,1531884,1532022,1533104,1533111,1533979,1535027,1535157,1536744,1538171,1539374,1539389,1539455,1539603,1541054,1541061,1541486,1541655,1541666,1541744,1542601,1542779,1543033,1543056,1548575,1550907,1551650,1551659,1558905,1559382,1559873,1559975,1561040,1561260,1561265,1561321,1561347,1561356,1561361,1561394,1561555,1571894,1575509,1578420,1587045,1587063,1587543,1587545,1588878,1588937,1593611,1593614-1593615,1593680,1594684,1594708,1595549,1604590,1604596,1604598,1610854,1625173,1626564,1634615,1648830
+/apr/apr/trunk:733052,739635,741862,741866-741867,741869,741871,745763-745764,746310,747990,748080,748361,748371,748565,748888,748902,748988,749810,760443,775683,782838,783398,783958,784633,784773,788588,789050,793192-793193,794118,794485,795267,799497,800627,809745,809854,810472,811455,813063,821306,829490,831641,832904,835607,888669,892028,892159,892435,892909,896382,896653,908427,910419,910597,917819,917837-917838,925965,929796,931973,951771,960665,960671,979891,983618,989450,990435,1003338,1044440,1044447,1055657,1072165,1078845,1081462,1081495,1083038,1083242,1084662,1086695,1088023,1089031,1089129,1089438,1099348,1103310,1183683,1183685-1183686,1183688,1183693,1183698,1213382,1235047,1236970,1237078,1237507,1240472,1340286,1340288,1340470,1341193,1341196,1343233,1343243,1367050,1368819,1370494,1372018,1372022,1372093,1372849,1376957,1384764,1389077,1400200,1402868,1405985,1406690,1420106,1420109,1425356,1428809,1438940,1438957-1438959,1442903,1449568,1456418,1459994,1460179-14
60180,1460241,1460399,1460405,1462738,1462813,1470186,1470348,1475509,1478905,1480067,1481262,1481265,1484271,1487796,1489517,1496407,1502804,1510354,1516261,1523384,1523479,1523484,1523505,1523521,1523604,1523613,1523615,1523844-1523845,1523853,1524014,1524031,1528797,1528809,1529488,1529495,1529515,1529521,1529668,1530786,1530800,1530988,1531554,1531768,1531884,1532022,1533104,1533111,1533979,1535027,1535157,1536744,1538171,1539374,1539389,1539455,1539603,1541054,1541061,1541486,1541655,1541666,1541744,1542601,1542779,1543033,1543056,1548575,1550907,1551650,1551659,1558905,1559382,1559873,1559975,1561040,1561260,1561265,1561321,1561347,1561356,1561361,1561394,1561555,1571894,1575509,1578420,1587045,1587063,1587543,1587545,1588878,1588937,1593611,1593614-1593615,1593680,1594684,1594708,1595549,1597797,1597803,1604590,1604596,1604598,1605104,1610854,1611023,1611107,1611110,1611117,1611120,1611125,1611184,1611193,1611466,1611515,1611517,1625173,1626564,1634615,1648830,1664406,1664447
,1664451,1664471
/apr/apr/trunk/test/testnames.c:1460405
/httpd/httpd/trunk:1604590
Modified: apr/apr/branches/1.6.x/CHANGES
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/CHANGES?rev=1664475&r1=1664474&r2=1664475&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/CHANGES [utf-8] (original)
+++ apr/apr/branches/1.6.x/CHANGES [utf-8] Thu Mar 5 20:31:21 2015
@@ -1,6 +1,11 @@
-*- coding: utf-8 -*-
Changes for APR 1.6.0
+ *) apr_skiplist: Add apr_skiplist_addne*() family to preserve existing
+ values (no duplicate), add apr_skiplist_size(), apr_skiplist_height()
+ and apr_skiplist_preheight() to get the corresponding current values,
+ and apr_skiplist_set_preheight() to modify it. [ Yann Ylavic ]
+
*) apr_pollset: On z/OS, threadsafe apr_pollset_poll() may return
"EDC8102I Operation would block" under load.
[Pat Odonnell <patod us.ibm.com>]
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=1664475&r1=1664474&r2=1664475&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 20:31:21 2015
@@ -171,7 +171,7 @@ 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
@@ -181,6 +181,26 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
void *data, apr_skiplist_compare comp);
/**
+ * 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_addne_compare(apr_skiplist *sl,
+ void *data, apr_skiplist_compare comp);
+
+/**
+ * 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.
+ */
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne(apr_skiplist* sl, void *data);
+
+/**
* Insert an element into the skip list using the existing comparison function
* allowing for duplicates.
* @param sl The skip list
@@ -192,7 +212,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 +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
@@ -246,6 +266,40 @@ APR_DECLARE(void *) apr_skiplist_pop(apr
APR_DECLARE(void *) apr_skiplist_peek(apr_skiplist *sl);
/**
+ * Return the size of the list (number of elements), in O(1).
+ * @param sl The skip list
+ */
+APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl);
+
+/**
+ * Return the height of the list (number of skip paths), in O(1).
+ * @param sl The skip list
+ */
+APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl);
+
+/**
+ * Return the predefined maximum height of the skip list.
+ * @param sl The skip list
+ */
+APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl);
+
+/**
+ * Set a predefined maximum height for the skip list.
+ * @param sl The skip list
+ * @param to The preheight to set, or a nul/negative value to disable.
+ * @remark When a preheight is used, the height of each inserted element is
+ * computed randomly up to this preheight instead of the current skip list's
+ * height plus one used by the default implementation. Using a preheight can
+ * probably ensure more fairness with long living elements (since with an
+ * adaptative height, former elements may have been created with a low height,
+ * hence a longest path to reach them while the skip list grows). On the other
+ * hand, the default behaviour (preheight <= 0) with a growing and decreasing
+ * maximum height is more adaptative/suitable for short living values.
+ * @note Should be called before any insertion/add.
+ */
+APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to);
+
+/**
* Merge two skip lists. XXX SEMANTICS
* @param sl1 One of two skip lists to be merged
* @param sl2 The other of two skip lists to be merged
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=1664475&r1=1664474&r2=1664475&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 20:31:21 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)
+static apr_skiplistnode *insert_compare(apr_skiplist *sl, void *data,
+ apr_skiplist_compare comp, int add)
{
- 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,37 @@ 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);
+ if (compared == 0 && !add) {
+ /* Keep the existing element(s) */
+ skiplist_stack_clear(sl);
+ return NULL;
+ }
+ }
+ 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 +453,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 +466,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 +512,38 @@ APR_DECLARE(apr_skiplistnode *) apr_skip
li = ni;
}
}
- else {
- /* sl->size++; */
- }
sl->size++;
return ret;
}
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
+ apr_skiplist_compare comp)
+{
+ return insert_compare(sl, data, comp, 1);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl, void *data)
+{
+ if (!sl->compare) {
+ return NULL;
+ }
+ return insert_compare(sl, data, sl->compare, 1);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne_compare(apr_skiplist *sl, void *data,
+ apr_skiplist_compare comp)
+{
+ return insert_compare(sl, data, comp, 0);
+}
+
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne(apr_skiplist *sl, void *data)
+{
+ if (!sl->compare) {
+ return NULL;
+ }
+ return insert_compare(sl, data, sl->compare, 0);
+}
+
APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data, apr_skiplist_freefunc myfree)
{
if (!sl->compare) {
@@ -548,6 +624,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 +654,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;
}
@@ -607,6 +687,26 @@ APR_DECLARE(void *) apr_skiplist_peek(ap
return NULL;
}
+APR_DECLARE(size_t) apr_skiplist_size(const apr_skiplist *sl)
+{
+ return sl->size;
+}
+
+APR_DECLARE(int) apr_skiplist_height(const apr_skiplist *sl)
+{
+ return sl->height;
+}
+
+APR_DECLARE(int) apr_skiplist_preheight(const apr_skiplist *sl)
+{
+ return sl->preheight;
+}
+
+APR_DECLARE(void) apr_skiplist_set_preheight(apr_skiplist *sl, int to)
+{
+ sl->preheight = (to > 0) ? to : 0;
+}
+
static void skiplisti_destroy(void *vsl)
{
apr_skiplist_destroy((apr_skiplist *) vsl, NULL);
@@ -618,6 +718,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.6.x/test/testskiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/branches/1.6.x/test/testskiplist.c?rev=1664475&r1=1664474&r2=1664475&view=diff
==============================================================================
--- apr/apr/branches/1.6.x/test/testskiplist.c (original)
+++ apr/apr/branches/1.6.x/test/testskiplist.c Thu Mar 5 20:31:21 2015
@@ -30,6 +30,217 @@
#include <string.h>
#endif
+static apr_pool_t *ptmp = NULL;
+static apr_skiplist *skiplist = NULL;
+
+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;
+ }
+ ABTS_TRUE(tc, size == apr_skiplist_size(sl));
+ 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_addne(abts_case *tc, void *data)
+{
+ const char *val;
+ int i, height = 0;
+
+ for (i = 0; i < 10; ++i) {
+ 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);
+ ABTS_STR_EQUAL(tc, "baton", val);
+
+ if (height == 0) {
+ height = apr_skiplist_height(skiplist);
+ }
+ else {
+ ABTS_INT_EQUAL(tc, height, apr_skiplist_height(skiplist));
+ }
+ }
+
+ 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_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_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);
+ apr_skiplist_set_preheight(sl, 7);
+ ABTS_INT_EQUAL(tc, 7, apr_skiplist_preheight(sl));
+
+ 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 +251,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 +260,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 +298,50 @@ 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_addne, 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;
}