different compare funcs for bsearch

user_11628978 0
Viewed 86

Either cmp func seems to work; cant understand how an arg1 of type int* is being resolved in the case of qsort_cmp. As far as I can figure: int* is passed to qsort_cmp where it is changed to void*, then in return statement cast to struct s*. So far no problem, but then cast object is supposed to have a member called b, which its cast type does but its instance does not...

struct s { int a, b; };

int qsort_cmp(const void *r1, const void *r2) {
     return ((struct s*) r1)->b - ((struct s*) r2)->b;
}

int bsearch_cmp(const void *key, const void *r2) {
     return *(int*) key - ((struct s*) r2)->b;
}

/* themap is already qsorted */
int k = 'w'//hatever;
void *ret = bsearch(&k, themap, thenumber_ofelements, sizeof(one_element), qsort_cmp);
bsearch implementation compare c
1 Answers

These comparison function are not interchangeable: one compares the b fields of both arguments, the other compares an int pointed to directly by the first argument and the b field of the structure pointed to by the second argument. They would be equivalent if the a field was used instead of b, as the a field is at the beginning of the structure.

Here is the specification:

7.22.5.1 The bsearch function

[...]

The comparison function pointed to by compar is called with two arguments that point to the key object and to an array element, in that order. The function shall return an integer less than, equal to, or greater than zero if the key object is considered, respectively, to be less than, to match, or to be greater than the array element.

Hence the first argument can be a pointer to an int and the second a pointer to an array of structures, as long as the comparison function is consistent with the bsearch calling scheme

Conversely, the comparison function used in qsort is called with 2 pointers to elements of the array, so both are pointers to s structures.

Note however that subtracting 2 int values is not a reliable way to produce the comparison result as this subtraction can overflow for many values: INT_MIN - 1 for example. A better method is this:

struct s { int a, b; };

int qsort_cmp(const void *r1, const void *r2) {
    const struct s *s1 = r1;
    const struct s *s2 = r2;
    return (s2->b < s1->b) - (s1->b < s2->b);
}

int bsearch_cmp(const void *key, const void *r2) {
    const int *ip = key;
    const struct s *s2 = r2;
    return (s2->b < *ip) - (*ip < s2->b);
}

Modern compilers generate branchless code for this: https://godbolt.org/z/sW3dn6

user_45932670
Related