Why does bsearch return a void *?

Question

void * bsearch ( const void * key,
                 const void * base,
                 size_t num,
                 size_t size,
                 int ( * comparator ) ( const void *, const void * ) );

If I pass in a const void * base, shouldn't bsearch also return a const void * result?

Answer 1

When you search for something, it's a valid request that you be able to modify it after you found it. It would be too restrictive if the search function didn't allow you to do that. Of course such a modification could break a subsequent search, but that's a different matter.

The parameters are const as a promise that bsearch itself will not modify them, which is reasonable.

Answer 2

Adding a qualifier to a pointed-to type is an implicit conversion, whereas removing a qualifier needs an explicit cast.

The prototype of bsearch() is written in a way that allows both of the following usages without explicit casting:

int needle = 0xdeadbeef;

int foo[42] = { ... };
int *p = bsearch(&needle, foo, 42, sizeof *foo, cmpi);

const int bar[42] = { ... };
const int *q = bsearch(&needle, bar, 42, sizeof *bar, cmpi);

However, this means that it's possible to use bsearch() - as well as many other libc functions - to remove const-qualification without a warning, eg if we had written

int *q = bsearch(&needle, bar, 42, sizeof *bar, cmpi);

This is perfectly legal: undefined behaviour only occurs if we actually used q to modifiy bar.

You should also keep in mind that const-qualifying a pointer parameter only affects which arguments are accepted without a cast, but does not guarantee that the function won't modify the pointed-to object. That is merely a convention followed by virtually all existing code, but it is not enforced by language semantics.

In particular, compilers can't use this information for optimizations in the calling code - the compiler needs to see the function body because it's legal to remove the const-qualification from the pointer and modify the pointed-to object if the object itself wasn't declared const.

In the past, I assumed that additionally restrict-qualifying the pointer argument would enforce the immutability, but a careful re-reading of section 6.7.3.1 leads me to believe that this is not the case: The constraints placed on objects pointed-to by restrict-qualified pointers only come into effect if the pointer is actually used to access the object, but calling code can't make that assumption from the prototype alone...

Answer 3

I think this is the biggest and most annoying defect in C's type system. Another example of this is strchr, a function with exactly the same problem: It returns a pointer to a resource the user passed in. This function needs to be useful for both const and non-const input parameters. What you see is sort of a compromise.

I find it is most annoying for accessors like this:

const struct list *list_next(const struct list *x) { return x->next; }

For internal use, a macro is a good "polymorphic" implementation

#define LIST_NEXT(x) ((x)->next)

but for external use, you must either use the bsearch compromise or two separate functions list_next and list_next_const.