apr-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Yann Ylavic <ylavic....@gmail.com>
Subject Re: Skiplist duplicates
Date Sat, 07 Mar 2015 15:51:17 GMT
On Sat, Mar 7, 2015 at 1:10 PM, Jeff Trawick <trawick@gmail.com> wrote:
> On Sat, Mar 7, 2015 at 5:03 AM, Yann Ylavic <ylavic.dev@gmail.com> wrote:
>> On Sat, Mar 7, 2015 at 8:30 AM, William A. Rowe Jr. <wrowe@rowe-clan.net>
>> wrote:
>> > On Thu, 5 Mar 2015 11:19:40 -0500
>> > Jim Jagielski <jim@jaguNET.com> wrote:
>> >
>> >> After doing some additional research, I think that the
>> >> current implementation of NOT allowing duplicates (in
>> >> APR 1.5/1.6) is BROKEN. In trunk this is determined by
>> >> a flag w/ the insert statement, but the default *should*
>> >> be to allow dups.
>> >>
>> >> As such, I'd like to adjust 1.5/1.6 to the correct and,
>> >> afaict, canonical behavior.
>> >
>> > I don't believe we can do this, it defies all rational API compatibility
>> > revisioning policies of any project, anywhere.
>> There is a possibility to both preserve/restore the addn semantic to
>> skiplist_insert() and still have the add semantic in 1.5.x.
>> It would be to give apr_skiplist_insert_compare(), which exists in
>> 1.5.x, the add semantic when its compare function arg is NULL.
> While it doesn't change the function signature, it still is an API change in
> that an application would require a certain minimum 1.5.x release for a an
> API "feature."

OK, understood.

> IMO:
> * Add APIs as necessary to 1.6.x so that existing 1.5.x calls work as-is.
> (e.g., apr_skiplist_init_ex(..., new_parameters))

I already backported some missing functions
(apr_skiplist_size/element/[set_]height/addne[_compare], the latter
would need to re-become add[_compare]() to fix the API change issue).
With the existing ones, this gives the user the ability to
insert/add/find/remove in the list in O(log n), walk through the nodes
as with a double-linked list (iterators), and get the element of a
The only missing thing I can think of is
{add,remove}_{next,previous}() a node, which could be useful when
using iterators.

I don't think there is a need for apr_skiplist_init_ex() for now, we'd
better let the user choose the semantic at insert()/add() time, IMHO.

If you agree I will restore add-if-not-exist semantic to insert() to
address the API issue, and do the add-with-duplicates semantic in
add[_compare]() (as it was in trunk before the semantic was changed
into insert()), hence unreleased addne[_compare]() functions will not
be needed anymore and abandonned.

> * Release 1.6.x soon


> This is an appropriate point to stop and see what else is lurking.  One way
> to approach it would be to work on improving the documentation, and seeing
> where that takes you in the code.  (Easy to say...  I probably don't have
> time myself, so I'm just throwing that out into the wind.)

I think I could better document the existing soon (modulo for now the
misterious compare vs comparek, see [1]), and see where it leads.
Regarding 1.6.x functionalities (with the changes above), it looks good to me.

[1] https://www.mail-archive.com/dev@httpd.apache.org/msg60788.html

View raw message