You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@apr.apache.org by Jim Jagielski <ji...@jaguNET.com> on 2015/03/05 17:19:40 UTC
Skiplist duplicates
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.
Re: Skiplist duplicates
Posted by Branko Čibej <br...@apache.org>.
On 12.03.2015 18:36, Jim Jagielski wrote:
>> No, it's a design error. There's not much helping that... once it
>> ships, that's our implementation. Might caution us to provide more
>> careful code review before n.n.0 releases on new features.
>
> Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
> it out in decimal form, that would be a "design error"? :)
>
> If so, how can we call it a "skiplist" which has a set of compliant
> expectations? It's not a skiplist implementation at all since it
> is broken.
Just to chime in here ... wrowe is correct. Some abstract definition of
"skiplist" is irrelevant. What's relevant is our current API and
implementation and its documented and otherwise discoverable semantics.
Our versioning rules do not allow changing the semantics of a (set of)
function(s) in a backward-incompatible way.
Your analogy is a bit off ... you're arguing for something more like
changing apr_snprintf to write everything right-to-left instead of
left-to-right because, 10 years ago, that's what the intent of the
implementation was but someone accidentally changed a minus to a plus.
After all, the docs for that function don't say left-to-right ...
-- Brane
Re: Skiplist duplicates
Posted by "William A. Rowe Jr." <wr...@rowe-clan.net>.
On Fri, 13 Mar 2015 08:56:14 -0400
Jeff Trawick <tr...@gmail.com> wrote:
> On Fri, Mar 13, 2015 at 8:51 AM, Jim Jagielski <ji...@jagunet.com>
> wrote:
>
> >
> > > On Mar 13, 2015, at 8:04 AM, Yann Ylavic <yl...@gmail.com>
> > > wrote:
> > >
> > > It seems that the implementation is not that broken actually.
> > >
> > > One can still have the add semantic with insert() in 1.5.x by
> > > using the appropriate compare function and
> > > apr_skiplist_insert_compare(), that is, a function that does not
> > > return 0 when entries are equal, but rather <0 for LIFO or >0 for
> > > FIFO (and stability) semantics.
> > >
> >
> > Well... :)
> >
> > It abuses the idea of the compare function :)
> >
> > Whatever though; I've already wasted enough energy on
> > this whole issue. I just don't want httpd to suffer the
> > stagnation obvious within APR.
> >
> >
> Exactly what do you mean by "stagnation"? Not agreeing with you on
> what is API breakage?
Or rather, not enjoying the same 'flexibility' (read: wild west) in
API definition within a library project, v.s. an application (and httpd
surely is more restrictive than a pure 'application' with no integration
points/api)?
What you might ascribe as being 'stagnant', most of us here would view
instead as simply being 'methodical'. If APR 'the project' has fallen
down, it was probably on passing through an API that really wasn't all
that vetted before it was shipped in a .0 release?
For perspective about library/component architects & developers treating
downstream developers badly, my favorite coding-hell-p0rn channel has
to be https://twitter.com/postwait - Nobody else liveblogs the pain of
coding against other peoples sh!t quite like Theo ... and it reminds me
that whatever headache I'm up against today is far from unique :)
Re: Skiplist duplicates
Posted by Jeff Trawick <tr...@gmail.com>.
On Fri, Mar 13, 2015 at 8:51 AM, Jim Jagielski <ji...@jagunet.com> wrote:
>
> > On Mar 13, 2015, at 8:04 AM, Yann Ylavic <yl...@gmail.com> wrote:
> >
> > It seems that the implementation is not that broken actually.
> >
> > One can still have the add semantic with insert() in 1.5.x by using
> > the appropriate compare function and apr_skiplist_insert_compare(),
> > that is, a function that does not return 0 when entries are equal, but
> > rather <0 for LIFO or >0 for FIFO (and stability) semantics.
> >
>
> Well... :)
>
> It abuses the idea of the compare function :)
>
> Whatever though; I've already wasted enough energy on
> this whole issue. I just don't want httpd to suffer the
> stagnation obvious within APR.
>
>
Exactly what do you mean by "stagnation"? Not agreeing with you on what is
API breakage?
--
Born in Roswell... married an alien...
http://emptyhammock.com/
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
> On Mar 13, 2015, at 8:04 AM, Yann Ylavic <yl...@gmail.com> wrote:
>
> It seems that the implementation is not that broken actually.
>
> One can still have the add semantic with insert() in 1.5.x by using
> the appropriate compare function and apr_skiplist_insert_compare(),
> that is, a function that does not return 0 when entries are equal, but
> rather <0 for LIFO or >0 for FIFO (and stability) semantics.
>
Well... :)
It abuses the idea of the compare function :)
Whatever though; I've already wasted enough energy on
this whole issue. I just don't want httpd to suffer the
stagnation obvious within APR.
Re: Skiplist duplicates
Posted by Yann Ylavic <yl...@gmail.com>.
It seems that the implementation is not that broken actually.
One can still have the add semantic with insert() in 1.5.x by using
the appropriate compare function and apr_skiplist_insert_compare(),
that is, a function that does not return 0 when entries are equal, but
rather <0 for LIFO or >0 for FIFO (and stability) semantics.
Add-if-not-exist semantic for apr_skiplist_insert() restored in
r1666411, along with apr_skiplist_add() with the FIFO semantic.
Will now backport to 1.6 and 1.5 branches, the latter without
apr_skiplist_add() of course...
On Fri, Mar 13, 2015 at 11:57 AM, Jim Jagielski <ji...@jagunet.com> wrote:
>
>>
>> Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
>> it out in decimal form, that would be a "design error"? :)
>>
>> That's a terrible analogy :)
>>
>
> Yeah, I agree.
>
>>
>> If so, how can we call it a "skiplist" which has a set of compliant
>> expectations? It's not a skiplist implementation at all since it
>> is broken.
>>
>>
>>
>> That's a useful point. FWIW I very quickly found the doc of an alternative skiplist implementation that says
>>
>> ---cut here---
>> You can enable duplicate keys by using the following:
>>
>> (sample code to create a skiplist via a non-default argument)
>>
>> This is an experimental feature. See the "KNOWN ISSUES" section below.
>> ---cut here---
>>
>
> Looking over the original skiplist impl, which I assume is the
> canon one, duplicates are allowed. Also, fwiw, the wikipedia entry
> also specififically shows that dups are allowed. Plus, any
> discussion on stability of the skiplist also describes handling
> of dups.
>
>> I suppose there's no way to avoid different camps on this: a particular treatment of duplicates by the code that's been released is so basic that an app would likely be dependent on it vs. any callers anticipated that duplicates would be handled in a different way and we need to fix it.
>>
>> IMO here are the salient points:
>>
>> * There's no problem making a backwards-compatible, "compliant" implementation in the APR 1.6.x branch by adding more APIs.
>> * There's no problem making APR trunk behave however is appropriate for the long term with no qualms about supporting existing code
>> * httpd has the issue now, and most people that responded to my query on the httpd list thought it was a good idea for httpd to have its own copy that can more easily track httpd needs without adding any speed bumps to httpd users picking up the new level (i.e., upgrading APR, whether it is a new APR 1.5.x or 1.6.x); (I happen to think that's better for APR in the long term, but perhaps that's just me.)
>
> I am fine w/ APR doing whatever it wants. My point about
> about httpd "suffering" due to APR, and APR suffering due
> to the demands of httpd, are still valid I think.
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
>
> Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
> it out in decimal form, that would be a "design error"? :)
>
> That's a terrible analogy :)
>
Yeah, I agree.
>
> If so, how can we call it a "skiplist" which has a set of compliant
> expectations? It's not a skiplist implementation at all since it
> is broken.
>
>
>
> That's a useful point. FWIW I very quickly found the doc of an alternative skiplist implementation that says
>
> ---cut here---
> You can enable duplicate keys by using the following:
>
> (sample code to create a skiplist via a non-default argument)
>
> This is an experimental feature. See the "KNOWN ISSUES" section below.
> ---cut here---
>
Looking over the original skiplist impl, which I assume is the
canon one, duplicates are allowed. Also, fwiw, the wikipedia entry
also specififically shows that dups are allowed. Plus, any
discussion on stability of the skiplist also describes handling
of dups.
> I suppose there's no way to avoid different camps on this: a particular treatment of duplicates by the code that's been released is so basic that an app would likely be dependent on it vs. any callers anticipated that duplicates would be handled in a different way and we need to fix it.
>
> IMO here are the salient points:
>
> * There's no problem making a backwards-compatible, "compliant" implementation in the APR 1.6.x branch by adding more APIs.
> * There's no problem making APR trunk behave however is appropriate for the long term with no qualms about supporting existing code
> * httpd has the issue now, and most people that responded to my query on the httpd list thought it was a good idea for httpd to have its own copy that can more easily track httpd needs without adding any speed bumps to httpd users picking up the new level (i.e., upgrading APR, whether it is a new APR 1.5.x or 1.6.x); (I happen to think that's better for APR in the long term, but perhaps that's just me.)
I am fine w/ APR doing whatever it wants. My point about
about httpd "suffering" due to APR, and APR suffering due
to the demands of httpd, are still valid I think.
Re: Skiplist duplicates
Posted by Jeff Trawick <tr...@gmail.com>.
On Thu, Mar 12, 2015 at 1:36 PM, Jim Jagielski <ji...@jagunet.com> wrote:
> >
> > No, it's a design error. There's not much helping that... once it
> > ships, that's our implementation. Might caution us to provide more
> > careful code review before n.n.0 releases on new features.
>
>
> Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
> it out in decimal form, that would be a "design error"? :)
>
That's a terrible analogy :)
> If so, how can we call it a "skiplist" which has a set of compliant
> expectations? It's not a skiplist implementation at all since it
> is broken.
>
>
>
That's a useful point. FWIW I very quickly found the doc of an alternative
skiplist implementation that says
---cut here---
You can enable duplicate keys by using the following:
(sample code to create a skiplist via a non-default argument)
This is an experimental feature. See the "KNOWN ISSUES" section below.
---cut here---
I suppose there's no way to avoid different camps on this: a particular
treatment of duplicates by the code that's been released is so basic that
an app would likely be dependent on it vs. any callers anticipated that
duplicates would be handled in a different way and we need to fix it.
IMO here are the salient points:
* There's no problem making a backwards-compatible, "compliant"
implementation in the APR 1.6.x branch by adding more APIs.
* There's no problem making APR trunk behave however is appropriate for the
long term with no qualms about supporting existing code
* httpd has the issue now, and most people that responded to my query on
the httpd list thought it was a good idea for httpd to have its own copy
that can more easily track httpd needs without adding any speed bumps to
httpd users picking up the new level (i.e., upgrading APR, whether it is a
new APR 1.5.x or 1.6.x); (I happen to think that's better for APR in the
long term, but perhaps that's just me.)
==> The APR issue doesn't have to be solved immediately or by finely
parsing what is or is not potential application breakage in order to help
httpd.
--
Born in Roswell... married an alien...
http://emptyhammock.com/
Re: Skiplist duplicates
Posted by "William A. Rowe Jr." <wr...@rowe-clan.net>.
On Thu, 12 Mar 2015 13:36:55 -0400
Jim Jagielski <ji...@jaguNET.com> wrote:
> >
> > No, it's a design error. There's not much helping that... once it
> > ships, that's our implementation. Might caution us to provide more
> > careful code review before n.n.0 releases on new features.
>
> Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
> it out in decimal form, that would be a "design error"? :)
No, because %d's behavior is documented, and you are citing a bug that
is in violation of that behavior.
> If so, how can we call it a "skiplist" which has a set of compliant
> expectations? It's not a skiplist implementation at all since it
> is broken.
But a user is only going to know whether they are loading against a
valid libapr-1.so if there is a new entry point in 1.6.0 that reflects
the (to your phrase) not-broken behavior. Otherwise the entire tower
is built on sand.
This is a multi-project, multi-consumer library, not an httpd sandbox.
There are expectations and we have to meet them, and these are all
very well spelled out in the versioning docs for this project.
Using list/tree functions to identify dups is a very well understood
design pattern. Therefore it is a surprise if you claim 'oh, but was
meant to allow dups' when it was neither documented to allow dups, nor
actually allowed them.
Any structure, btree, hash, linked list, can be designed to allow or
to deny dups, either as a choice of the add function, or an intrinsic
design element that refuses a belief in dups. It seems Yann is already
on to the appropriate solution, so let's go with that and not revisit
the entire versioning rules of the project during the 1.x lifespan.
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
> On Mar 12, 2015, at 1:36 PM, Jim Jagielski <ji...@jaguNET.com> wrote:
>
>>
>> No, it's a design error. There's not much helping that... once it
>> ships, that's our implementation. Might caution us to provide more
>> careful code review before n.n.0 releases on new features.
>
>
> Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
> it out in decimal form, that would be a "design error"? :)
s/decimal/float/p
>
> If so, how can we call it a "skiplist" which has a set of compliant
> expectations? It's not a skiplist implementation at all since it
> is broken.
>
>
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
>
> No, it's a design error. There's not much helping that... once it
> ships, that's our implementation. Might caution us to provide more
> careful code review before n.n.0 releases on new features.
Soooo.... if apr_snprintf("%d" were to, on every 50th int, print
it out in decimal form, that would be a "design error"? :)
If so, how can we call it a "skiplist" which has a set of compliant
expectations? It's not a skiplist implementation at all since it
is broken.
Re: Skiplist duplicates
Posted by "William A. Rowe Jr." <wr...@rowe-clan.net>.
On Sat, 7 Mar 2015 10:57:22 -0500
Jim Jagielski <ji...@jaguNET.com> wrote:
>
> > On Mar 7, 2015, at 2:30 AM, William A. Rowe Jr.
> > <wr...@rowe-clan.net> wrote:
> >
> > On Thu, 5 Mar 2015 11:19:40 -0500
> > Jim Jagielski <ji...@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.
> >
> > If we committed a broken-thing into the 1.x branch, let's move
> > forward and ship 2.0 already, complete with the triage for things
> > we didn't mean to happen?
> >
>
> Not honoring dups IS A BUG. The above seems to imply that any
> patch for any broken feature requires a MMN bump. That is crazy.
> apr_skiplist is a skiplist implementation. Skiplists allow
> for dups. That we don't is a BUG.
No, it's a design error. There's not much helping that... once it
ships, that's our implementation. Might caution us to provide more
careful code review before n.n.0 releases on new features.
The suggestion IIRC was a creation flag to toggle the previously
undocumented and previously unsupported addition of dups to the
skiplist. That can go into 1.next.0 with no issues at all.
Other opinions from APR stability champions?
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
> On Mar 7, 2015, at 2:30 AM, William A. Rowe Jr. <wr...@rowe-clan.net> wrote:
>
> On Thu, 5 Mar 2015 11:19:40 -0500
> Jim Jagielski <ji...@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.
>
> If we committed a broken-thing into the 1.x branch, let's move forward
> and ship 2.0 already, complete with the triage for things we didn't
> mean to happen?
>
Not honoring dups IS A BUG. The above seems to imply that any
patch for any broken feature requires a MMN bump. That is crazy.
apr_skiplist is a skiplist implementation. Skiplists allow
for dups. That we don't is a BUG.
Re: Skiplist duplicates
Posted by Yann Ylavic <yl...@gmail.com>.
On Sat, Mar 7, 2015 at 1:10 PM, Jeff Trawick <tr...@gmail.com> wrote:
> On Sat, Mar 7, 2015 at 5:03 AM, Yann Ylavic <yl...@gmail.com> wrote:
>>
>> On Sat, Mar 7, 2015 at 8:30 AM, William A. Rowe Jr. <wr...@rowe-clan.net>
>> wrote:
>> > On Thu, 5 Mar 2015 11:19:40 -0500
>> > Jim Jagielski <ji...@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
node.
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
+1
>
> 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
Re: Skiplist duplicates
Posted by Jeff Trawick <tr...@gmail.com>.
On Sat, Mar 7, 2015 at 5:03 AM, Yann Ylavic <yl...@gmail.com> wrote:
> On Sat, Mar 7, 2015 at 8:30 AM, William A. Rowe Jr. <wr...@rowe-clan.net>
> wrote:
> > On Thu, 5 Mar 2015 11:19:40 -0500
> > Jim Jagielski <ji...@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."
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))
* Release 1.6.x soon
Meanwhile, I would like to point out ("whine", "nag", whatever) that in my
past, poor effort to bring the API documentation for this up from a
relatively poor state, I didn't figure out everything that needed to be
documented and I wasn't sure that the code was really complete.
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.)
>
> Eg. for trunk:
>
> Index: tables/apr_skiplist.c
> ===================================================================
> --- tables/apr_skiplist.c (revision 1664776)
> +++ tables/apr_skiplist.c (working copy)
> @@ -517,29 +517,39 @@ static apr_skiplistnode *insert_compare(apr_skipli
> APR_DECLARE(apr_skiplistnode *)
> apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
> apr_skiplist_compare comp)
> {
> - return insert_compare(sl, data, comp, 1);
> + if (comp) {
> + return insert_compare(sl, data, comp, 0);
> + }
> + else if (sl->compare) {
> + return insert_compare(sl, data, sl->compare, 1);
> + }
> + else {
> + return NULL;
> + }
> }
>
> APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl,
> void *data)
> {
> - if (!sl->compare) {
> - return NULL;
> - }
> - return insert_compare(sl, data, sl->compare, 1);
> + return apr_skiplist_insert_compare(sl, data, sl->compare);
> }
>
> -APR_DECLARE(apr_skiplistnode *)
> apr_skiplist_addne_compare(apr_skiplist *sl, void *data,
> +APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist
> *sl, void *data,
> apr_skiplist_compare comp)
> {
> - return insert_compare(sl, data, comp, 0);
> + if (comp) {
> + return insert_compare(sl, data, comp, 1);
> + }
> + else if (sl->compare) {
> + return insert_compare(sl, data, sl->compare, 1);
> + }
> + else {
> + return NULL;
> + }
> }
>
> -APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne(apr_skiplist *sl,
> void *data)
> +APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void
> *data)
> {
> - if (!sl->compare) {
> - return NULL;
> - }
> - return insert_compare(sl, data, sl->compare, 0);
> + return apr_skiplist_add_compare(sl, data, sl->compare);
> }
>
> APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data,
> apr_skiplist_freefunc myfree)
> --
>
>
> And for 1.5.x:
>
> Index: tables/apr_skiplist.c
> ===================================================================
> --- tables/apr_skiplist.c (revision 1664805)
> +++ tables/apr_skiplist.c (working copy)
> @@ -394,8 +394,16 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
> apr_skiplist_compare comp)
> {
> apr_skiplistnode *m, *p, *tmp, *ret = NULL;
> - int nh = 1, ch;
> + int add = 0, nh = 1, ch;
>
> + if (!comp) {
> + if (!sl->compare) {
> + return NULL;
> + }
> + comp = sl->compare;
> + add = 1;
> + }
> +
> if (sl->preheight) {
> while (nh < sl->preheight && get_b_rand()) {
> nh++;
> @@ -423,6 +431,11 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
> */
> if (m->next) {
> int compared = comp(data, m->next->data);
> + if (compared == 0 && !add) {
> + /* Keep the existing element(s) */
> + skiplist_qclear(&sl->stack_q);
> + return NULL;
> + }
> if (compared > 0) {
> m = m->next;
> continue;
> --
>
--
Born in Roswell... married an alien...
http://emptyhammock.com/
Re: Skiplist duplicates
Posted by Yann Ylavic <yl...@gmail.com>.
On Sat, Mar 7, 2015 at 11:03 AM, Yann Ylavic <yl...@gmail.com> wrote:
> 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.
Note this wouldn't break any assumption on
apr_skiplist_insert_compare() since the current behaviour with a NULL
compare function is to crash :)
Re: Skiplist duplicates
Posted by Yann Ylavic <yl...@gmail.com>.
On Sat, Mar 7, 2015 at 8:30 AM, William A. Rowe Jr. <wr...@rowe-clan.net> wrote:
> On Thu, 5 Mar 2015 11:19:40 -0500
> Jim Jagielski <ji...@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.
Eg. for trunk:
Index: tables/apr_skiplist.c
===================================================================
--- tables/apr_skiplist.c (revision 1664776)
+++ tables/apr_skiplist.c (working copy)
@@ -517,29 +517,39 @@ static apr_skiplistnode *insert_compare(apr_skipli
APR_DECLARE(apr_skiplistnode *)
apr_skiplist_insert_compare(apr_skiplist *sl, void *data,
apr_skiplist_compare comp)
{
- return insert_compare(sl, data, comp, 1);
+ if (comp) {
+ return insert_compare(sl, data, comp, 0);
+ }
+ else if (sl->compare) {
+ return insert_compare(sl, data, sl->compare, 1);
+ }
+ else {
+ return NULL;
+ }
}
APR_DECLARE(apr_skiplistnode *) apr_skiplist_insert(apr_skiplist *sl,
void *data)
{
- if (!sl->compare) {
- return NULL;
- }
- return insert_compare(sl, data, sl->compare, 1);
+ return apr_skiplist_insert_compare(sl, data, sl->compare);
}
-APR_DECLARE(apr_skiplistnode *)
apr_skiplist_addne_compare(apr_skiplist *sl, void *data,
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_add_compare(apr_skiplist
*sl, void *data,
apr_skiplist_compare comp)
{
- return insert_compare(sl, data, comp, 0);
+ if (comp) {
+ return insert_compare(sl, data, comp, 1);
+ }
+ else if (sl->compare) {
+ return insert_compare(sl, data, sl->compare, 1);
+ }
+ else {
+ return NULL;
+ }
}
-APR_DECLARE(apr_skiplistnode *) apr_skiplist_addne(apr_skiplist *sl,
void *data)
+APR_DECLARE(apr_skiplistnode *) apr_skiplist_add(apr_skiplist *sl, void *data)
{
- if (!sl->compare) {
- return NULL;
- }
- return insert_compare(sl, data, sl->compare, 0);
+ return apr_skiplist_add_compare(sl, data, sl->compare);
}
APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data,
apr_skiplist_freefunc myfree)
--
And for 1.5.x:
Index: tables/apr_skiplist.c
===================================================================
--- tables/apr_skiplist.c (revision 1664805)
+++ tables/apr_skiplist.c (working copy)
@@ -394,8 +394,16 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
apr_skiplist_compare comp)
{
apr_skiplistnode *m, *p, *tmp, *ret = NULL;
- int nh = 1, ch;
+ int add = 0, nh = 1, ch;
+ if (!comp) {
+ if (!sl->compare) {
+ return NULL;
+ }
+ comp = sl->compare;
+ add = 1;
+ }
+
if (sl->preheight) {
while (nh < sl->preheight && get_b_rand()) {
nh++;
@@ -423,6 +431,11 @@ APR_DECLARE(apr_skiplistnode *) apr_skiplist_inser
*/
if (m->next) {
int compared = comp(data, m->next->data);
+ if (compared == 0 && !add) {
+ /* Keep the existing element(s) */
+ skiplist_qclear(&sl->stack_q);
+ return NULL;
+ }
if (compared > 0) {
m = m->next;
continue;
--
Re: Skiplist duplicates
Posted by "William A. Rowe Jr." <wr...@rowe-clan.net>.
On Thu, 5 Mar 2015 11:19:40 -0500
Jim Jagielski <ji...@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.
If we committed a broken-thing into the 1.x branch, let's move forward
and ship 2.0 already, complete with the triage for things we didn't
mean to happen?
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
Plus, the way we do it in trunk breaks the skiplist stability
requirement, so that needs to be fixed as well.
> On Mar 5, 2015, at 11:19 AM, Jim Jagielski <ji...@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.
>
Re: Skiplist duplicates
Posted by Jim Jagielski <ji...@jaguNET.com>.
No, we didn't. But the current behavior is broken, so if people
are expecting our skiplists to act like "real" skiplists, it will
fail. I think fixing broken should be allowed...
> On Mar 5, 2015, at 11:29 AM, Ruediger Pluem <rp...@apache.org> wrote:
>
>
>
> On 03/05/2015 05:19 PM, Jim Jagielski 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.
>>
>>
>
> Guess this is fine for 1.6 as it is not released yet. I am not so sure for 1.5 as it has been released and this is a
> change in behavior. Did we made any promises on the current behavior in 1.5?
>
> Regards
>
> Rüdiger
Re: Skiplist duplicates
Posted by Ruediger Pluem <rp...@apache.org>.
On 03/05/2015 05:19 PM, Jim Jagielski 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.
>
>
Guess this is fine for 1.6 as it is not released yet. I am not so sure for 1.5 as it has been released and this is a
change in behavior. Did we made any promises on the current behavior in 1.5?
Regards
Rüdiger