On 27.04.2018 11:30, Nick Kew wrote:
>> 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.
If the prerequisite for using the correct data structure is the presence
or absence of an API which documents "linear search," the damage is
probably already too big anyway ... It's not our job to teach
programmers about data structures and algorithms.
>> 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.
You can't just use any of the string comparison functions directly
anyway: first because the signature is wrong, and second because there's
no requirement that array elements are pointers.
>> 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!
Major quibble: The comparator should take a parameter that receives the
array element size. Careful implementations will either use that size or
check that it's the correct size. APR arrays can contain whole
structures, not just pointers.
>> + for (i = start; (i < arr->nelts) && comp(needle, *(void **)(arr->elts +
>> (arr->elt_size * i))); i++) {
>> + /* empty */
>> + }
The comparator should receive the pointer to the array element, not the
array element interpreted as a pointer! See above, array elements don't
have to be pointers. Why else do you think apr_array_t::elt_size exists?
Or the APR_ARRAY_IDX() and APR_ARRAY_PUSH() macros?
> Why not make that much more readable and put the substance inside the loop?
> for (i …) {
> if (!comp(…)) {
> set *index;
> set return value;
> break;
> }
> }
+1
-- Brane
