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 <j...@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, yla...@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 >> >> >
