On Fri, Jul 11, 2014 at 4:28 PM, Jim Jagielski <[email protected]> wrote: > > On Jul 10, 2014, at 8:07 PM, Yann Ylavic <[email protected]> wrote: > >> >> I propose to garantee the ordering presumably at low coding and >> performance (if any) cost, so that one can choose between apr_table or >> apr_skiplist to do similar things (iterate over all the values of a >> key is one such thing, in a deterministic order is an other, both not >> feasible with the current skiplist implementation). >> > > ++1... For me, performance is key. Or, at least, some sort > of option to allow for a skiplist to be created that > guarantees order or not, depending on whether performance > or ordering is more important. > > After all, the intent of skiplist *is* in performance, > and not ordering, so sacrificing performance for ordering > seems kinda wonky, unless one can turn that off :)
I think I can add this option, but in "performance mode", what would be the behaviour of : 1. apr_skiplist_remove(), 2. apr_skiplist_remove_first(), apr_skiplist_remove_last() 3. apr_skiplist_find_last() 2. and 3. are introduced by this patch so the can return NULL (or ENOTIMPL by changing the declaration) because it makes no sense to use them without ordering. 1. is more tricky, should it remove one single value or all doublons? Doublons are a new 1.6 feature, in 1.5 apr_skiplist_remove() had not this to handle. Now we have to rule. In the case apr_skiplist_remove() should act on a single value, the caller would have to loop to remove all the doublons (restarting from the top each time). In the case apr_skiplist_remove() should act on all doublons, I don't think there is an efficient way to do it without ordering (once a value is reached, this is not necessarily the first, and we'd have to compare both up and down->next until none remain). In both case we are stuck with non-ordered-remove performances outside the insert/add()/pop() scheme. Performance for a use case can't apply to all the others (one may not need ordering but still remove to be performant).
