apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Jim Jagielski <...@jaguNET.com>
Subject Re: svn commit: r1611193 - /apr/apr/trunk/tables/apr_skiplist.c
Date Thu, 17 Jul 2014 12:10:20 GMT
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
> 
> 


Mime
View raw message