You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by Jim Jagielski <ji...@jaguNET.com> on 2014/07/17 14:10:20 UTC
Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
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 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
>>
>>
>