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 2014/07/16 23:16:07 UTC
svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Author: ylavic
Date: Wed Jul 16 21:16:06 2014
New Revision: 1611193
URL: http://svn.apache.org/r1611193
Log:
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).
Modified:
apr/apr/trunk/tables/apr_skiplist.c
Modified: apr/apr/trunk/tables/apr_skiplist.c
URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1611193&r1=1611192&r2=1611193&view=diff
==============================================================================
--- apr/apr/trunk/tables/apr_skiplist.c (original)
+++ apr/apr/trunk/tables/apr_skiplist.c Wed Jul 16 21:16:06 2014
@@ -407,25 +407,15 @@ static apr_skiplistnode *insert_compare(
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;
while (m) {
int compared = -1;
@@ -473,6 +463,31 @@ static apr_skiplistnode *insert_compare(
m->next = tmp;
p = tmp;
}
+
+ /* 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;
+ if (p) {
+ p->up = tmp;
+ }
+ tmp->data = data;
+ tmp->sl = sl;
+ }
if (sl->index != NULL) {
/*
* this is a external insertion, we must insert into each index as
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Fri, Jul 18, 2014 at 2:20 AM, Yann Ylavic <yl...@gmail.com> wrote:
> and 1.6.x (including your commits r1597797, 1597803
> and r1605104 that introduce apr_skiplist_add, plus the latest r1611515
> for apr_skiplist_size/height/preheight/set_preheight, all of which I
> think are good 1.6.x candidates).
You would probably need to merge r1611517 too, a (harmless) follow up
to r1611515 included in the 1.6.x patch.
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Thu, Jul 17, 2014 at 11:26 PM, Jim Jagielski <ji...@jagunet.com> wrote:
>
> On Jul 17, 2014, at 2:24 PM, Yann Ylavic <yl...@gmail.com> wrote:
>
>> On Thu, Jul 17, 2014 at 7:28 PM, Yann Ylavic <yl...@gmail.com> wrote:
>>> I think all the commits so far (r1611023, r1611107, r1611110,
>>> r1611117, r1611120, r1611125, r1611184 and 1611193) can be backported
>>> to 1.5.x, no API change (apr_skiplist.h is not modified).
>>
>> Hm, wait, I didn't figure out apr_skiplist_add() is not in 1.5.x, so
>> r1611184 is probably not backportable as is.
>> I can provide a separate patch to backport the stack optimization from
>> this commit if you like.
>>
>
> Yeah, that seems like it would be v. useful. Thx.
Here are the patches for 1.5.x (without references to
apr_skiplist_add) and 1.6.x (including your commits r1597797, 1597803
and r1605104 that introduce apr_skiplist_add, plus the latest r1611515
for apr_skiplist_size/height/preheight/set_preheight, all of which I
think are good 1.6.x candidates).
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Posted by Jim Jagielski <ji...@jaguNET.com>.
On Jul 17, 2014, at 2:24 PM, Yann Ylavic <yl...@gmail.com> wrote:
> On Thu, Jul 17, 2014 at 7:28 PM, Yann Ylavic <yl...@gmail.com> wrote:
>> I think all the commits so far (r1611023, r1611107, r1611110,
>> r1611117, r1611120, r1611125, r1611184 and 1611193) can be backported
>> to 1.5.x, no API change (apr_skiplist.h is not modified).
>
> Hm, wait, I didn't figure out apr_skiplist_add() is not in 1.5.x, so
> r1611184 is probably not backportable as is.
> I can provide a separate patch to backport the stack optimization from
> this commit if you like.
>
Yeah, that seems like it would be v. useful. Thx.
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Posted by Yann Ylavic <yl...@gmail.com>.
On Thu, Jul 17, 2014 at 7:28 PM, Yann Ylavic <yl...@gmail.com> wrote:
> I think all the commits so far (r1611023, r1611107, r1611110,
> r1611117, r1611120, r1611125, r1611184 and 1611193) can be backported
> to 1.5.x, no API change (apr_skiplist.h is not modified).
Hm, wait, I didn't figure out apr_skiplist_add() is not in 1.5.x, so
r1611184 is probably not backportable as is.
I can provide a separate patch to backport the stack optimization from
this commit if you like.
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Posted by Yann Ylavic <yl...@gmail.com>.
I think all the commits so far (r1611023, r1611107, r1611110,
r1611117, r1611120, r1611125, r1611184 and 1611193) can be backported
to 1.5.x, no API change (apr_skiplist.h is not modified).
Another commit (I'm working on) will provide apr_skiplist_size(),
apr_skiplist_height() and apr_skiplist_set_preheight() (to
respectively get the size, height and set/get the preheight of the
skiplist), and is more a 1.6 candidate.
Then I think I will fork the code for the apr_skipmap we already
talked about, maybe with common things in skiplist_common.[ch] to
avoid duplicating some code?
On Thu, Jul 17, 2014 at 2:10 PM, Jim Jagielski <ji...@jagunet.com> wrote:
> All this is great work! Thx!
>
> How much is applicable to be backported to 1.5 and/or 1.6?
>
> On Jul 16, 2014, at 5:16 PM, ylavic@apache.org wrote:
>
>> Author: ylavic
>> Date: Wed Jul 16 21:16:06 2014
>> New Revision: 1611193
>>
>> URL: http://svn.apache.org/r1611193
>> Log:
>> 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).
>>
>> Modified:
>> apr/apr/trunk/tables/apr_skiplist.c
>>
>> Modified: apr/apr/trunk/tables/apr_skiplist.c
>> URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1611193&r1=1611192&r2=1611193&view=diff
>> ==============================================================================
>> --- apr/apr/trunk/tables/apr_skiplist.c (original)
>> +++ apr/apr/trunk/tables/apr_skiplist.c Wed Jul 16 21:16:06 2014
>> @@ -407,25 +407,15 @@ static apr_skiplistnode *insert_compare(
>> 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;
>> while (m) {
>> int compared = -1;
>> @@ -473,6 +463,31 @@ static apr_skiplistnode *insert_compare(
>> m->next = tmp;
>> p = tmp;
>> }
>> +
>> + /* 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;
>> + if (p) {
>> + p->up = tmp;
>> + }
>> + tmp->data = data;
>> + tmp->sl = sl;
>> + }
>> if (sl->index != NULL) {
>> /*
>> * this is a external insertion, we must insert into each index as
>>
>>
>
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Posted by Jim Jagielski <ji...@jaguNET.com>.
All this is great work! Thx!
How much is applicable to be backported to 1.5 and/or 1.6?
On Jul 16, 2014, at 5:16 PM, ylavic@apache.org wrote:
> Author: ylavic
> Date: Wed Jul 16 21:16:06 2014
> New Revision: 1611193
>
> URL: http://svn.apache.org/r1611193
> Log:
> 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).
>
> Modified:
> apr/apr/trunk/tables/apr_skiplist.c
>
> Modified: apr/apr/trunk/tables/apr_skiplist.c
> URL: http://svn.apache.org/viewvc/apr/apr/trunk/tables/apr_skiplist.c?rev=1611193&r1=1611192&r2=1611193&view=diff
> ==============================================================================
> --- apr/apr/trunk/tables/apr_skiplist.c (original)
> +++ apr/apr/trunk/tables/apr_skiplist.c Wed Jul 16 21:16:06 2014
> @@ -407,25 +407,15 @@ static apr_skiplistnode *insert_compare(
> 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;
> while (m) {
> int compared = -1;
> @@ -473,6 +463,31 @@ static apr_skiplistnode *insert_compare(
> m->next = tmp;
> p = tmp;
> }
> +
> + /* 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;
> + if (p) {
> + p->up = tmp;
> + }
> + tmp->data = data;
> + tmp->sl = sl;
> + }
> if (sl->index != NULL) {
> /*
> * this is a external insertion, we must insert into each index as
>
>