BINARY_ARRAY_SEARCH ?

[tridge at samba.org]

Hi Volker,

 > Just found lib/util/binsearch.h. Quick question: What's so
 > bad about bsearch(3)? This is even ANSI C standard.

We could use bsearch(), and maybe I would have if I'd thought of it -
it's not a function I've ever used :-)

To use bsearch() we'd need to make up quite different comparison
functions. The bsearch() interface assumes the comparison function
works on the structure, not on an element in the structure. So when we
are looking for an element in an array where one of the structure
elements contains a GUID, then we'd need to either build a fake
structure containing the target GUID (and then use the sorting
comparison function) or we'd need to create a comparison function that
takes a GUID as the first argument and a structure as the 2nd. That
isn't as natural as an interface I think - right now we can just use
GUID_compare() when the element in the array we want to compare is a
GUID, which is quite neat.

The BINARY_ARRAY_SEARCH() macro is also type-safe. We could make
bsearch() type safe by wrapping it in a macro that first looked for
equality with the first element in the array, then called bsearch on
the rest of the array if the first element didn't match. That would
make it much less error prone.

The way that BINARY_ARRAY_SEARCH() evolved was that we had quite a few
places in Samba that were doing binary searches, and all of them were
re-inventing the same pattern. Having a macro was better than lots of
duplicated (complex!) code.

btw, it's been quite common for us to have problems with qsort() in
Samba because it isn't type safe (it can be a surprisingly tricky
function to use). I wonder if we should wrap it in a type-safe macro?
The macro would call qsort() and then assert that the last element 
is >= the first. The assert would ensure the compiler checked that
the comparison function we use is taking the right types.

Cheers, Tridge