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, [email protected] 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 > >
