> On 27 Apr 2018, at 03:37, Jim Riggs <jim...@riggs.me> wrote:
>
> I am working on some httpd changes/features/ideas and have multiple needs to
> find items in an array. In httpd, we currently have these:
>
> AP_DECLARE(int) ap_array_str_index(const apr_array_header_t *array,
> const char *s,
> int start);
>
> AP_DECLARE(int) ap_array_str_contains(const apr_array_header_t *array,
> const char *s);
Both of which could - perhaps should - really be APR functions!
That is, with one reservation, that applies to both those and your proposal.
This is (inevitably) linear search. If we provide search within APR, we could
be misleading developers into using it for very big arrays, where they should
be avoiding linear search.
I think I’ve been through that thought process myself:
1. I need a searchable set structure.
2. Hmm. Why do I need to reinvent the obvious wheel of apr_array_find()???
3. Oh I see, it’s linear search.
4. How scalable do I want my array to be?
5. Damn. Better use hash instead.
In the absence of step 2, I’d probably never have reached steps 3-5.
> In my use cases, the search may often be strings, but not always, so I
> thought that maybe APR could/should provide something more generic. The above
> functions could then be rewritten to use this new function. Here are my
> thoughts:
>
> 1. The search item (needle) can be anything rather than just a string as
> above.
> 2. The caller provides a callback that compares the values to needle in the
> same way strcmp()/strcasecmp() do. That is, 0 means "equal". In fact,
> strcmp()/strcasecmp() can -- and probably often will -- be used as the
> callback for strings.
There’s a bit of a mismatch between that and the “can be anything”.
The latter would call for a size parameter that could be passed to memcmp,
as well as of course strncmp/strncasecmp.
> 3. A start (input) and index (output) parameter can be used to iterate and
> find all occurrences.
> What do others think? Is there value in this, or is it just me?
I’ve had occasion to search an array, though I don’t think I’ve needed anything
more
generic than the HTTPD functions you name above.
> +typedef int (apr_array_find_comparison_callback_fn_t)(const void *x, const
> void *y);
Minor quibble: the name seems quite tortuously overdescriptive!
> + for (i = start; (i < arr->nelts) && comp(needle, *(void **)(arr->elts +
> (arr->elt_size * i))); i++) {
> + /* empty */
> + }
Why not make that much more readable and put the substance inside the loop?
for (i …) {
if (!comp(…)) {
set *index;
set return value;
break;
}
}
—
Nick Kew
