I think I have an acceptable solution for still APR-1.5's skiplists
(having insert() with addne semantic) in httpd.
For add semantic, simply use the following compare function and
insert_compare():
static int indexing_add_comp(void *a, void *b)
{
apr_time_t t1 = (apr_time_t) (((timer_event_t *) a)->when);
apr_time_t t2 = (apr_time_t) (((timer_event_t *) b)->when);
return (t1 < t2) ? -1 : +1;
}
It never returns 0, hence the entry never exists, and duplicates are added next!
That's all is needed for mpm_event, which only uses skiplist_insert()
and skiplist_pop(), so it could even become the default compare
function (ie. set with apr_skiplist_set_compare()).
For mpm_motorz, we also need skiplist_remove(), so we can keep the
existing indexing_comp() function as the default (we still need the
exact match to find or remove an entry :), while the new
indexing_add_comp() would only be used for insertions (with
insert_compare()).
Any issue with this?
On Sat, Mar 7, 2015 at 8:02 PM, Jim Jagielski <[email protected]> wrote:
> My 2c is that I don't like the idea that "add" and "insert"
> means 2 different things with 2 different behaviors. I
> know we were kinda forced into that due to me, mistakenly,
> not realizing that dups were the *compliant* impl.
>
> The real rub is what do we call "place into skiplist
> unless it would overwrite a previously placed element".
> My choice of "addne" was shorthand for "ADD if element
> does Not Exist".
>
>> On Mar 7, 2015, at 11:38 AM, Yann Ylavic <[email protected]> wrote:
>>
>> +1
>>
>> If/before we do this, maybe we can at least agree on
>> skiplist_insert/add() vs skiplist_insert/addne().
>> I known it depends on whether or not names will finally be rollbacked
>> in APR, but we'd better not copy skiplist's code from there before
>> this is decided.
>> Just to avoid having different semantics in APR and httpd, and ease
>> keeping the code in sync when necessary...
>>
>>
>> On Sat, Mar 7, 2015 at 5:10 PM, Jim Jagielski <[email protected]> wrote:
>>> I'm +1 on that.
>>>
>>> <rant>
>>> I'll be honest, I think that in several ways the "lag"
>>> between httpd and APR is putting httpd at risk. Every
>>> possible change to APR is being held-up by, imo, irrational
>>> concepts of what "breaks" the API. Now this wouldn't be
>>> so bad if we saw releases of APR more often than every
>>> year or so. As it is, we end up with things that should
>>> be in APR, but aren't, because we want to be able to keep
>>> development and release of httpd at a rationale level,
>>> OR things get "pushed" into APR quickly because, well,
>>> with such infrequent releases, people (myself very included)
>>> rush stuff in because we know it'll be months (several!)
>>> before the idea of an APR release is even envisioned. ("Hurry
>>> up and commit! God knows when the next release will be!!")
>>>
>>> Personally, I think any "new" features that httpd requires
>>> than would historically go into APR, STAY in httpd. Call
>>> it aprx_ or whatever. APR can decide to pick those up when/if
>>> it chooses. It can even live in ./srclib.
>>> </rant>
>>>
>>> As far as what to do w/ skiplist itself: httpd (event and motorz
>>> and likely others, when its available) requires a *compliant*
>>> skiplist implementation. If APR can't provide it, then we
>>> provide our own.
>>>
>>>> On Mar 7, 2015, at 7:40 AM, Jeff Trawick <[email protected]> wrote:
>>>>
>>>> Looking back, I think that apr_skiplist wasn't ready for general use (both
>>>> doc and code) when it was put in APR and released, and at the same time it
>>>> was unfortunate that it placed a prereq on a new APR release in order to
>>>> use Event, introducing another speedbump to using httpd's latest and
>>>> greatest.
>>>>
>>>> Looking forward, I see the same thing; apr_skiplist needs design changes
>>>> to supply what httpd needs, and doing so means extra work in APR to
>>>> preserve compatibility, as well as dependence of Event on a new APR
>>>> release stream. That's another speedbump that httpd 2.4 users don't need.
>>>>
>>>> The best thing for httpd (Event) w.r.t. skiplist is the best thing for
>>>> apr_skiplist itself: for the codebase to evolve naturally to support this
>>>> important (primary, only???) consumer, without the constraints of APR
>>>> versioning rules and APR release cycles (and perhaps without the
>>>> constraints of any versioning rules).
>>>>
>>>> Pull this small amount of code into httpd, perhaps as a private interface
>>>> for 1-2 modules that need it. Let it improve with fewer constraints.
>>>> Future APR 2.0 will improve from the relatively unfettered changes, and
>>>> httpd 2.4 users won't have speedbumps introduced by dependence on an
>>>> evolving skiplist implementation.
>>>>
>>>> (Keep the skiplist code in APR trunk up to date with changes needed for
>>>> httpd. The APR stable releases can pick up compatible code fixes, but
>>>> that probably won't be a priority for anyone but non-httpd consumers, and
>>>> I'm not aware of any such people working on skiplist thus far.)
>>>>
>>>> Thoughts?
>>>>
>>>> --
>>>> Born in Roswell... married an alien...
>>>> http://emptyhammock.com/
>>>>
>>>
>
