Can you use a pointer representing a virtual object as the key in bsearch?

Question

In C23, I have an array A sorted relative to a comparison function f. f has the property that if a certain address (say the address of a particular global variable) is passed to it, rather than dereferrencing the special address as normal, the special address is treated as an indicator for a special object. The special address is not the address of anything in A. The special address could be dereferrenced, so its not an invalid pointer or anything.

To be more specific, say A is a sorted list of all integers from 1 to 1000 and f is regular real number comparison. If the special address is passed to f, it does not dereferrence it as an integer, instead it treats it like it is 42 regardless of what data it points to.

I am not sure I could provide an example where the mechanism is meaningful without a lot of code, but I think this describes completely what I am doing.

Is there any C standard violation using bsearch with this array and function, passing the special address as the key to search for?

Answer 1

As long as the results of the comparison function are consistent with whatever values are being passed in, this shouldn't be an issue.

In particular section 7.24.5p4 states:

When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another. That is, for qsort they shall define a total ordering on the array, and for bsearch the same object shall always compare the same way with the key

For example, this would work.

int f(const void *k, const void *v)
{
    int key;
    if (k == SPECIAL) {
        key = 42;
    } else {
        key = *(const int *)k;
    }
    int value = *(const int *)v;

    if (key < value) {
        return -1;
    } else if (key > value) {
        return 1;
    } else {
        return 0;
    }
}

Answer 2

Is there any C standard violation using bsearch with this array and function, passing the special address as the key to search for?

No, I do not find any.

C spec does have ...

The implementation shall ensure that the second argument of the comparison function (when called from bsearch), or both arguments (when called from qsort), are pointers to elements of the array. C23dr § 7.24.5 2

... does not impose any requirement that the first argument (in bsearch()) point to the array.
The first argument is not even required to be the same type.

---

The compare function must:

1. not alter the contents of the array.

2. not alter the contents of any individual element of the array.

3. When the same objects (consisting of size bytes, irrespective of their current positions in the array) are passed more than once to the comparison function, the results shall be consistent with one another.