Re: [RFC] apr_array_find()

[Jim Riggs]

> On 27 Apr 2018, at 11:50, William A Rowe Jr  wrote:
> 
> If we code this abstractly, comparator declaration is not type-safe, but can
> be declared so that it is usable by table, hash, b-tree and many other 
> approaches to data organization. With clever use of wrappers, we should
> be able to make a derivation (counted-byte-string tables, for example)
> behave in a type-safe manner at no performance penalty.
> 
> We should cross check the subversion util feature set to ensure we don't
> have something ready to borrow, already.

I fear things have now started going over my head. :-) I'll try to keep up.

Re: [RFC] apr_array_find()

[Jim Riggs]

> On 27 Apr 2018, at 11:44, Jim Riggs <jim...@riggs.me> wrote:
> 
>> 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.
> 
> Again, the comparator has to be smart. It should know what it is receiving. 
> They may be ints, structs, strings, whatever. It can and should cast as 
> necessary. The void* is just a way of saying "I'm passing you something. You 
> have to know how to handle it." It may or may not be a pointer. I have 
> successfully tested it with char* (using strcmp/strcasecmp) as well as int 
> and char using custom comp callback functions. They all worked as expected.

Though, I now admit that this presumably only works for types where 
sizeof() <= sizeof(void*) due to casting, but that seems like a 
documentation issue, not a technical one. Personally, I haven't seen or worked 
with many apr_arrays being used with anything other than pointers, not to say 
there aren't lots of them. (I am the newish guy on the block.)

Heck, even if we were to restrict this function to only working with arrays 
whose elements are pointers, it would still be useful and help remove some code 
duplication, IMO.

Re: [RFC] apr_array_find()

[Jim Riggs]

> On 27 Apr 2018, at 05:06, Branko Čibej  wrote:
> 
> On 27.04.2018 11:30, Nick Kew wrote:
>>> 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.

Nick - I don't expect that comp would ever do just a memcmp...unless that's how 
someone implements it, but then that implementation would have to know what 
kind of data (and the size) it is dealing with. The comparator would be a 
custom written function that expects int or char* or struct* or _ and do 
whatever it considers an equality comparison. It may receive struct*s and only 
compare one or two members to consider them "equal" in the comparator's context.

Branko - First, I can use them directly with either a compiler warning 
(implicit cast char* to void*) or an explicit cast. Second, this does not 
require that the elements be pointers. If they are char*, though, strcmp and 
strcasecmp work fine.


>>> 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!

Agreed, but it's not something that really gets used much, though. I just based 
it off the apr_table_do callback's name.


> 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.

Again, the comparator has to be smart. It should know what it is receiving. 
They may be ints, structs, strings, whatever. It can and should cast as 
necessary. The void* is just a way of saying "I'm passing you something. You 
have to know how to handle it." It may or may not be a pointer. I have 
successfully tested it with char* (using strcmp/strcasecmp) as well as int and 
char using custom comp callback functions. They all worked as expected.


> 
>>> +  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?

Again, see above. It is only void* to say "I am passing you something, but 
*you* know what it really is."


>> 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

Agreed:

diff -r 335976d9e7cb tables/apr_tables.c
--- a/tables/apr_tables.c   Wed Apr 04 16:41:28 2018 +
+++ b/tables/apr_tables.c   Fri Apr 27 11:40:48 2018 -0500
@@ -281,6 +281,31 @@
 return res;
 }

+APR_DECLARE(void *) apr_array_find(apr_array_header_t *arr,
+   const void *needle,
+   apr_array_find_comparison_callback_fn_t 
*comp,
+   int start,
+   int *index)
+{
+  int i;
+
+  if (!arr || !needle || !comp || (start < 0)) {
+return NULL;
+  }
+
+  for (i = start; i < arr->nelts; i++) {
+if (comp(needle, *(void **)(arr->elts + (arr->elt_size * i))) == 0) {
+  if (index) {
+*index = i;
+  }
+
+  return *(void **)(arr->elts + (arr->elt_size * i));
+}
+  }
+
+  return NULL;
+}
+

 /*
  *

[RFC] apr_array_find()

[Jim Riggs]

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);

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.
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'm thinking 
something like this:

diff -r 335976d9e7cb include/apr_tables.h
--- a/include/apr_tables.h  Wed Apr 04 16:41:28 2018 +
+++ b/include/apr_tables.h  Thu Apr 26 19:07:44 2018 -0500
@@ -223,6 +223,40 @@
  const char sep);
 
 /**
+ * Declaration prototype for the comparison callback function of
+ * apr_array_find().
+ * @param x The first item to compare
+ * @param y The second item to compare
+ * @return 0 if the items are "equal" (whatever "equal" means in the context of
+ * the apr_array_find() call)
+ * @see apr_array_find
+ */
+typedef int (apr_array_find_comparison_callback_fn_t)(const void *x, const 
void *y);
+
+/**
+ * Find an element in an array by using a callback function for comparison.
+ * Existing functions such as strcmp() and strcasecmp() or custom callbacks can
+ * be used. Finding multiple occurrences of an item can be accomplished by 
using
+ * the start and index parameters in successive calls.
+ * @param arr The array to search
+ * @param needle The value for which to search
+ * @param comp The comparison callback function
+ * @param start The index in the array at which the search should begin
+ * @param index If not NULL, will contain the index of the found item's offset
+ *within the array upon return; if the item is not found, this value is
+ *untouched (check for a return of NULL)
+ * @return The matching item from the array
+ * @remark The return value of this function should be used to test for success
+ * (finding the value) rather than the index parameter which is only
+ * modified if the value is found.
+ */
+APR_DECLARE(void *) apr_array_find(apr_array_header_t *arr,
+   const void *needle,
+   apr_array_find_comparison_callback_fn_t 
*comp,
+   int start,
+   int *index);
+
+/**
  * Make a new table.
  * @param p The pool to allocate the pool out of
  * @param nelts The number of elements in the initial table.
diff -r 335976d9e7cb tables/apr_tables.c
--- a/tables/apr_tables.c   Wed Apr 04 16:41:28 2018 +
+++ b/tables/apr_tables.c   Thu Apr 26 19:07:44 2018 -0500
@@ -281,6 +281,33 @@
 return res;
 }
 
+APR_DECLARE(void *) apr_array_find(apr_array_header_t *arr,
+   const void *needle,
+   apr_array_find_comparison_callback_fn_t 
*comp,
+   int start,
+   int *index)
+{
+  int i;
+
+  if (!arr || !needle || !comp || (start < 0)) {
+return NULL;
+  }
+
+  for (i = start; (i < arr->nelts) && comp(needle, *(void **)(arr->elts + 
(arr->elt_size * i))); i++) {
+/* empty */
+  }
+
+  if (i < arr->nelts) {
+if (index) {
+  *index = i;
+}
+
+return *(void **)(arr->elts + (arr->elt_size * i));
+  }
+
+  return NULL;
+}
+
 
 /*
  *