Grr, off the list...
On Fri, Jul 11, 2014 at 6:29 PM, Yann Ylavic <[email protected]> wrote: > On Fri, Jul 11, 2014 at 6:24 PM, Yann Ylavic <[email protected]> wrote: >> 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). > > Maybe we could also leave skiplist as is and introduce a new type > (skipmap?) that would be ordered and that would take both key and > value as arguments (in the relevant functions)...
