Mailing-List: contact dev-help@apr.apache.org; run by ezmlm
Precedence: bulk
Received-SPF: pass (nike.apache.org: domain of ylavic.dev@gmail.com designates
 209.85.213.179 as permitted sender)
MIME-Version: 1.0
In-Reply-To: 
 <CAKQ1sVMvoOAtG6CHR2Lnhkm6qVTRfWsqQErMCtZR25K76A9J=g@mail.gmail.com>
References: 
 <CAKQ1sVO1EECMvSOz7Udqv83MJ_BR+KBed6wKgh8VG-ij9+qhtg@mail.gmail.com>
	<581E0F48-0128-4B06-98EC-11D49DB5E507@jaguNET.com>
	<CAKQ1sVOPhL-XCHDiFATW=uMOBxZzOrRLAC5Mvb6iuyRRwxsYzQ@mail.gmail.com>
	<4E51F5E9-FA7B-40D4-A23D-A4B4B7F56C22@jaguNET.com>
	<CAKQ1sVOwAVkFCPyy8ndgA=KBg6ANoEKE7nXZQuwDLjz+pdZz3Q@mail.gmail.com>
	<CAKQ1sVMvoOAtG6CHR2Lnhkm6qVTRfWsqQErMCtZR25K76A9J=g@mail.gmail.com>
Date: Fri, 11 Jul 2014 18:29:48 +0200
Message-ID: 
 <CAKQ1sVM5+Pp=X_G4orYcFxtD+NxKWsut2W8yHnMmrTXrbbM6BQ@mail.gmail.com>
Subject: Re: Skiplist improvements
From: Yann Ylavic <ylavic.dev@gmail.com>
To: apr <dev@apr.apache.org>
Content-Type: text/plain; charset=UTF-8

Grr, off the list...

On Fri, Jul 11, 2014 at 6:29 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
> On Fri, Jul 11, 2014 at 6:24 PM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>> On Fri, Jul 11, 2014 at 4:28 PM, Jim Jagielski <jim@jagunet.com> wrote:
>>>
>>> On Jul 10, 2014, at 8:07 PM, Yann Ylavic <ylavic.dev@gmail.com> 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)...