4

is it just me or this code in Programming Pearls is wrong (quicksort wants 2 const voids, no?) If so, is my solution right? Apologies, just learning...

int wordncmp(char *p, char* q)
{   int n = k;
    for ( ; *p == *q; p++, q++)
        if (*p == 0 && --n == 0)
            return 0;
    return *p - *q;
}

int sortcmp(char **p, char **q)
{   return wordncmp(*p, *q);
}
...

qsort(word, nword, sizeof(word[0]), sortcmp);

Is this a solution?

int sortcmp(const void *p, const void *q)
{   return wordncmp(* (char * const *) p, * (char * const *) q);
}
Michal Sznajder
  • 9,338
  • 4
  • 44
  • 62
Dervin Thunk
  • 19,515
  • 28
  • 127
  • 217

2 Answers2

7

The first code sample will probably work with virtually any compiler and CPU; however, it is technically undefined behavior, if you follow the C standard to the letter.

As you said, the last argument to qsort() is a pointer to a function taking two arguments of type const void*. sortcmp takes different arguments. Your compiler should give you a warning about incompatible type signatures or something. In any case, a cast is being performed from a function of one type to a function of another type.

The C standard specifies that you can cast function pointers to other function pointers with different types, but you cannot dereference and invoke the casted function pointer. However, if you re-cast the function pointer back to its original type, then calling that has defined behavior -- it calls the original function.

Since you're casting from a int (*)(char**, char**) to a int (*)(const void*, const void*), and then eventually qsort() is invoking your comparator function without casting it back to int (*)(char**, char**), that's undefined behavior.

However, since virtually on all architectures, a char ** and a const void* are represented the same way, the function call will pretty much always work.

If you want to get defined behavior, you have to make sure your comparator function has the proper type signature, and then you can cast the arguments to the proper type. Your solution is exactly correct and does not violate the C standard there. Well done on const-correctness -- a lot of people don't understand exactly what char * const * means.

You should also make wordncmp() take parameters of const char*, since you're not modifying the parameters.

Side note: You also technically can't cast a function pointer to a data pointer (e.g. a void*) or vice-versa. The standard allows for function pointers and data pointers to have different sizes. Even if it works on your computer, it's not guaranteed to always work.

Adam Rosenfield
  • 390,455
  • 97
  • 512
  • 589
  • Doesn't the standard actually guarantee that `char *` and `void *` have the same representation? I agree it's still UB to make the call with the wrong function pointer type, but I don't believe the representation of the arguments is the issue. Rather the issue is that a pathological implementation could use different calling convention for passing `void *` versus `char *`, e.g. having a separate set of argument registers for each type. – R.. GitHub STOP HELPING ICE Feb 20 '12 at 16:13
  • @R.: Yes, the standard guarantees that `char*` and `void*` have the same representation and alignment requirements (C99 §6.2.5/27), but `char**` and `void*` aren't necessarily compatible. – Adam Rosenfield Feb 21 '12 at 22:04
2

You are correct, the signature for sortcmp does not match what qsort expects. Your correction is right. wordcmp should also be made const-correct as you are technically losing some of the const-ness along the way.

int wordncmp(const char *p, const char* q)
John Kugelman
  • 349,597
  • 67
  • 533
  • 578