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

alk
  • 69,737
  • 10
  • 105
  • 255
fredoverflow
  • 256,549
  • 94
  • 388
  • 662

3 Answers3

8

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.

Dabbler
  • 9,733
  • 5
  • 41
  • 64
  • 5
    What if that something was given to you as a `const void*` then? You have made a promise not to modify it. You shouldn't be requesting the ability to modify. However, since C cannot overload functions, I guess this is the compromise you have to live with. – R. Martinho Fernandes Oct 29 '11 at 10:44
  • @R.MartinhoFernandes Even in C++ you couldn't overload simply by the return type. – xanatos Oct 29 '11 at 10:48
  • 1
    @xanatos but you would overload on the parameters too! `const void * bsearch ( const void * key, ...)` and `void * bsearch ( void * key, ...)`. – R. Martinho Fernandes Oct 29 '11 at 10:50
  • 1
    Considering that the `void*` will need to be casted to something to be of any use, I think it isn't a very strong argument :-) But by comparing it to strstr for example (that does something similar to bsearch) we can see the "intelligence" of this argument (they wanted to be uniform) – xanatos Oct 29 '11 at 10:51
  • @R.MartinhoFernandes It would make more sense to overload on the constness of `base` ;) – fredoverflow Oct 29 '11 at 11:19
3

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

Christoph
  • 164,997
  • 36
  • 182
  • 240
  • If `const` does not restrict modification of an object and doesn't help compiler optimizations, what is the meaning of `const` altogether? – Andrey Vihrov Oct 29 '11 at 13:41
  • @Andrey: `const` does restrict modification of an object, but `const *` does not; in a way, marking pointer arguments `const` is only a syntactic consideration: it allows passing in adresses of const-qualified objects without a cast, but makes no real semantic difference; however, `const *restrict` parameters are semantically distinct, but `restrict` only affects the called and not the calling code – Christoph Oct 29 '11 at 14:26
  • A `restrict` pointer only requires that all accesses to the pointed-to object use, directly or indirectly, the value of this pointer. Does this have anything to do with constness at all? – Andrey Vihrov Oct 29 '11 at 14:43
  • @Andrey: that's a simplification; more formally: if an object is (1) accessed through an expression based on a restrict-qualified pointer and (2) the object is modified, then (a) the pointer must not be const-qualified and (b) all access (including the modification) must be based on that pointer; in particuar, an object pointed-to by a restrict-qualified pointer-to-const can't be modified at all (during the lifetime of that pointer), but only if the pointer is used to access that object, ie modification is legal as long as the pointer is never used(!); (more...) – Christoph Oct 29 '11 at 15:00
  • (...) (a) is necessary because if it were not present, you could take a restrict-qualified pointer-to-const, cast the `const` away and legally use that expression to modify the pointed-to object; this means `const *restrict` is a stronger constraint than the combination of `const *` and `*restrict` semantics – Christoph Oct 29 '11 at 15:01
0

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.

u0b34a0f6ae
  • 48,117
  • 14
  • 92
  • 101