Hi,
I think there is some confusion in the comparek() function set for the
timers' skiplist in mpm_event(opt) (or am I the one confused?).
In the APR skiplist implementation, the comparek() function is used by
apr_skiplist_find[_compare]() and apr_skiplist_remove[_compare]() to
find the given entry (data), calling skiplist->comparek(data,
node->data) until 0 is returned for a skiplist node.
These functions are not used by event(opt), so there is no harm...
But should they, with comparek defined as :
static int indexing_compk(void *ac, void *b)
{
apr_time_t *t1 = (apr_time_t *) ac;
apr_time_t t2 = (apr_time_t) (((timer_event_t *) b)->when);
AP_DEBUG_ASSERT(t2);
return ((*t1 < t2) ? -1 : ((*t1 > t2) ? 1 : 0));
}
we would compare *(apr_time_t *)data to ((timer_event_t
*)node->data)->when, whereas the given data is really (also) a
timer_event_t* (unfortunately "when" is not the first field of the
timer_event_t struct either).
So probably there should be no need for a special indexing_compk() in
event(opt), and we should use indexing_comp() (without the k) as both
compare() and comparek() functions for apr_skiplist_set_compare().
Do you agree I should commit this change?
Moreover, since we don't use apr_skiplist_find*() or
apr_skiplist_remove*(), we probably don't need indexing at all for our
skiplists, and could avoid the overhead of inserting into the
index(es) for each apr_skiplist_insert(). That's an APR patch though
(moving the index creation from apr_skiplist_init() to
apr_skiplist_add_index(), ie. the first time it is used), I'll propose
it on apr@.
Regards,
Yann.
Hi Jim,
sorry to have not been clear enough, my point was not (mainly) about
disabling the index for httpd (this was more the apr@ part of the
mail, which is indeed only an optimization and should be discussed
there), but more about indexing_compk() which I think is falsy (should
it be called, though it's not the case since we don't use
skiplist_find() nor skiplist_remove()).
The code in skiplist is quite tricky about when it uses the compare()
or comparek() function (eg. find() and remove() don't do the same, see
below...), but as I read it, the comparek() form where the first
argument must be the field of the struct to be compared (and not the
struct itself) is only used for indexes, and even maybe for internal
use to find an index (skiplist) from a given compare function
(apr_skiplist_add_index).
I may really have missed something, but the following implementations
of find_compare() (called by find()) and remove_compare() (called by
remove()) does not help me much :
APR_DECLARE(void *) apr_skiplist_find_compare(apr_skiplist *sli, void *data,
apr_skiplistnode **iter,
apr_skiplist_compare comp)
{
apr_skiplistnode *m;
apr_skiplist *sl;
if (comp == sli->compare || !sli->index) {
sl = sli;
}
else {
apr_skiplist_find(sli->index, (void *)comp, &m);
if (!m) {
if (iter) {
*iter = NULL;
}
return NULL;
}
sl = (apr_skiplist *) m->data;
}
skiplisti_find_compare(sl, data, &m, sl->comparek);
if (iter) {
*iter = m;
}
return (m) ? m->data : NULL;
}
APR_DECLARE(void *) apr_skiplist_find(apr_skiplist *sl, void *data,
apr_skiplistnode **iter)
{
if (!sl->compare) {
return NULL;
}
return apr_skiplist_find_compare(sl, data, iter, sl->compare);
}
APR_DECLARE(int) apr_skiplist_remove_compare(apr_skiplist *sli,
void *data,
apr_skiplist_freefunc myfree,
apr_skiplist_compare comp)
{
apr_skiplistnode *m;
apr_skiplist *sl;
if (comp == sli->comparek || !sli->index) {
sl = sli;
}
else {
apr_skiplist_find(sli->index, (void *)comp, &m);
if (!m) {
return 0;
}
sl = (apr_skiplist *) m->data;
}
skiplisti_find_compare(sl, data, &m, comp);
if (!m) {
return 0;
}
while (m->previndex) {
m = m->previndex;
}
return skiplisti_remove(sl, m, myfree);
}
APR_DECLARE(int) apr_skiplist_remove(apr_skiplist *sl, void *data,
apr_skiplist_freefunc myfree)
{
if (!sl->compare) {
return 0;
}
return apr_skiplist_remove_compare(sl, data, myfree, sl->comparek);
}
The first one is called with compare() (but forces comparek() to find
the entry), whereas the latter is called with comparek() (and use it
directly to find the entry), both won't try to find anything from the
index since comp == compare[k] is explicitely checked not to.
Any enlightenmente much appreciated here...
In any case, I think setting indexing_compk as comparek function in
event(opt) does not do the right thing if apr_skiplist_find() or
apr_skiplist_remove() is called, ie :
apr_skiplist_find(sl, timer, &node)
-> apr_skiplist_find_compare(sl, timer, node, sl->compare)
-> skiplisti_find_compare(sl, timer, node, indexing_compk) // <=
forced sl->comparek
-> indexing_compk(timer, node->data)
-> return ((*(apr_time_t *)timer < ((apr_time_t *)node->data)->when) ?
-1 : (.... ? 1 : 0))
apr_skiplist_remove(sl, timer, myfree)
-> apr_skiplist_remove_compare(sl, timer, myfree, sl->comparek)
-> skiplisti_find_compare(sl, timer, &node, indexing_compk) // <=
given comp above
-> indexing_compk(timer, node->data)
-> return ((*(apr_time_t *)timer < ((apr_time_t *)node->data)->when) ?
-1 : (.... ? 1 : 0))
Hence the proposal to do the following in event(opt) :
apr_skiplist_set_compare(timer_skiplist, indexing_comp, indexing_comp)
and not use/have indexing_compk at all.
Regards,
Yann.
On Mon, Oct 13, 2014 at 2:04 PM, Jim Jagielski <ji...@jagunet.com> wrote:
> The skiplist impl was via a donation of the code from Theo
> who developed it as part of mod_spread (iirc) et.al. so
> it likely includes functionality that we don't use *yet*.
> But having functionality in it allows for future use.
>
> On Oct 13, 2014, at 7:25 AM, Yann Ylavic <yl...@gmail.com> wrote:
>
>> Hi,
>>
>> I think there is some confusion in the comparek() function set for the
>> timers' skiplist in mpm_event(opt) (or am I the one confused?).
>>
>> In the APR skiplist implementation, the comparek() function is used by
>> apr_skiplist_find[_compare]() and apr_skiplist_remove[_compare]() to
>> find the given entry (data), calling skiplist->comparek(data,
>> node->data) until 0 is returned for a skiplist node.
>>
>> These functions are not used by event(opt), so there is no harm...
>> But should they, with comparek defined as :
>>
>> static int indexing_compk(void *ac, void *b)
>> {
>> apr_time_t *t1 = (apr_time_t *) ac;
>> apr_time_t t2 = (apr_time_t) (((timer_event_t *) b)->when);
>> AP_DEBUG_ASSERT(t2);
>> return ((*t1 < t2) ? -1 : ((*t1 > t2) ? 1 : 0));
>> }
>>
>> we would compare *(apr_time_t *)data to ((timer_event_t
>> *)node->data)->when, whereas the given data is really (also) a
>> timer_event_t* (unfortunately "when" is not the first field of the
>> timer_event_t struct either).
>>
>> So probably there should be no need for a special indexing_compk() in
>> event(opt), and we should use indexing_comp() (without the k) as both
>> compare() and comparek() functions for apr_skiplist_set_compare().
>>
>> Do you agree I should commit this change?
>>
>> Moreover, since we don't use apr_skiplist_find*() or
>> apr_skiplist_remove*(), we probably don't need indexing at all for our
>> skiplists, and could avoid the overhead of inserting into the
>> index(es) for each apr_skiplist_insert(). That's an APR patch though
>> (moving the index creation from apr_skiplist_init() to
>> apr_skiplist_add_index(), ie. the first time it is used), I'll propose
>> it on apr@.
>>
>> Regards,
>> Yann.
>>
>
The skiplist impl was via a donation of the code from Theo
who developed it as part of mod_spread (iirc) et.al. so
it likely includes functionality that we don't use *yet*.
But having functionality in it allows for future use.
On Oct 13, 2014, at 7:25 AM, Yann Ylavic <yl...@gmail.com> wrote:
> Hi,
>
> I think there is some confusion in the comparek() function set for the
> timers' skiplist in mpm_event(opt) (or am I the one confused?).
>
> In the APR skiplist implementation, the comparek() function is used by
> apr_skiplist_find[_compare]() and apr_skiplist_remove[_compare]() to
> find the given entry (data), calling skiplist->comparek(data,
> node->data) until 0 is returned for a skiplist node.
>
> These functions are not used by event(opt), so there is no harm...
> But should they, with comparek defined as :
>
> static int indexing_compk(void *ac, void *b)
> {
> apr_time_t *t1 = (apr_time_t *) ac;
> apr_time_t t2 = (apr_time_t) (((timer_event_t *) b)->when);
> AP_DEBUG_ASSERT(t2);
> return ((*t1 < t2) ? -1 : ((*t1 > t2) ? 1 : 0));
> }
>
> we would compare *(apr_time_t *)data to ((timer_event_t
> *)node->data)->when, whereas the given data is really (also) a
> timer_event_t* (unfortunately "when" is not the first field of the
> timer_event_t struct either).
>
> So probably there should be no need for a special indexing_compk() in
> event(opt), and we should use indexing_comp() (without the k) as both
> compare() and comparek() functions for apr_skiplist_set_compare().
>
> Do you agree I should commit this change?
>
> Moreover, since we don't use apr_skiplist_find*() or
> apr_skiplist_remove*(), we probably don't need indexing at all for our
> skiplists, and could avoid the overhead of inserting into the
> index(es) for each apr_skiplist_insert(). That's an APR patch though
> (moving the index creation from apr_skiplist_init() to
> apr_skiplist_add_index(), ie. the first time it is used), I'll propose
> it on apr@.
>
> Regards,
> Yann.
>