This question is about the 'function pointer' version of qsort from K&R (2e), section 5.11 (p118-121). There are a number of places where I don't understand why or how the casts work, and I suspect that the program is not entirely standards-conformant.
Here is the source code. Aside from removing comments and making minor changes to the formatting, I:
qsort to qsort_alt (for "alternative qsort"), because the standard library already contains a function named qsort,main to int main(void), andmain to use input supplied via the linearr and wlinearr variables instead of stdin.#include <stdio.h>
#include <string.h>
#include <wchar.h>
char *linearr[] = {
"13", "5", "10", "9", "23", "2", "5",
"25", "3", "13", "1", "4", "14", "19",
};
wchar_t *wlinearr[] = {
L"13", L"5", L"10", L"9", L"23", L"2", L"5",
L"25", L"3", L"13", L"1", L"4", L"14", L"19",
L"42", L"32", L"25", L"5", L"3", L"34",
L"50", L"40", L"86", L"91", L"100", L"21",
L"29", L"28", L"23", L"93", L"24", L"89",
L"85", L"63", L"10", L"39", L"14", L"18",
L"78", L"73", L"52", L"57", L"26", L"38",
L"91", L"76", L"61", L"46",
};
void qsort_alt(void *v[], int left, int right,
int (*comp)(void *, void *));
int numcmp(char *, char *);
int main(void) {
int nlines = sizeof(linearr) / sizeof(linearr[0]);
int nwlines = sizeof(wlinearr) / sizeof(wlinearr[0]);
int i;
qsort_alt((void **)linearr, 0, nlines - 1,
(int (*)(void *, void *))numcmp);
for (i = 0; i < nlines; i++)
printf("%s%s", linearr[i], (i < nlines - 1) ? " " : "\n");
/* output: 1 2 3 4 5 5 9 10 13 13 14 19 23 25 */
qsort_alt((void **)linearr, 0, nlines - 1,
(int (*)(void *, void *))strcmp);
for (i = 0; i < nlines; i++)
printf("%s%s", linearr[i], (i < nlines - 1) ? " " : "\n");
/* output: 1 10 13 13 14 19 2 23 25 3 4 5 5 9 */
qsort_alt((void **)wlinearr, 0, nwlines - 1,
(int (*)(void *, void *))wcscmp);
for (i = 0; i < nwlines; i++)
wprintf(L"%ls%ls", wlinearr[i], (i < nwlines - 1) ? L" " : L"\n");
/* output: 1 10 10 100 13 13 14 14 18 19 2 21 23 23 24 25 25 26 28 29 3 3 32 34 38 39 4 40 42 46 5 5 5 50 52 57 61 63 73 76 78 85 86 89 9 91 91 93 */
return 0;
}
void qsort_alt(void *v[], int left, int right,
int (*comp)(void *, void *)) {
int i, last;
void swap(void *v[], int, int);
if (left >= right)
return;
swap(v, left, (left + right) / 2);
last = left;
for (i = left + 1; i <= right; i++)
if ((*comp)(v[i], v[left]) < 0)
swap(v, ++last, i);
swap(v, left, last);
qsort_alt(v, left, last - 1, comp);
qsort_alt(v, last + 1, right, comp);
}
#include <stdlib.h>
int numcmp(char *s1, char *s2) {
double v1, v2;
v1 = atof(s1);
v2 = atof(s2);
if (v1 < v2)
return -1;
else if (v1 > v2)
return 1;
else
return 0;
}
void swap(void *v[], int i, int j) {
void *temp;
temp = v[i];
v[i] = v[j];
v[j] = temp;
}
For me, this compiles fine (without warnings) with GCC and compiler flags -std=iso9899:199409 -pedantic -Wall -Wextra and produces the output shown within the comments above. (The choice of iso9899:199409 reflects the fact that <wchar.h> was introduced with C95, but actually this compiles and runs equally well with c90.)
My call to qsort_alt is substantially the same as in K&R (2e). For reference, in the original it was
qsort((void **) lineptr, 0, nlines-1,
(int (*)(void*,void*))(numeric ? numcmp : strcmp));
with int nlines indicating the number of lines stored in char *lineptr[MAXLINES] and numeric being a boolean flag (set via the command line) that decides which of the two functions numcmp/strcmp is used. K&R's main reads input from stdin into char *lineptr[MAXLINES]; I replaced it by char *linearr[]. The input wchar_t *wlinearr[] is my own addition. Relevant here is what K&R write (p119-120):
We have written
qsort[in my code:qsort_alt] so it can process any data type, not just character strings. [...] The elaborate cast of the function argument casts the arguments of the comparison function. These will generally have no effect on actual representation, but assure the compiler that all is well.
Let's see whether all is good, ie: whether the program is portable and whether it would work for other types such as wchar_t, as implied by K&R:
1. Why are the arguments to qsort_alt [orig: qsort] cast explicitly?
The C17 standard draft says (6.5.2.2 ¶7):
If the expression that denotes the called function has a type that does include a prototype [ie: it doesn't use old-style syntax], the arguments are implicitly converted, as if by assignment, to the types of the corresponding parameters, taking the type of each parameter to be the unqualified version of its declared type.
That is, it seems that explicit casts to match the types of the function parameters of qsort_alt aren't necessary, though they may be stylistically justified.
However, is the following wording (6.5.4 ¶3) relevant?
Conversions that involve pointers, other than where permitted by the constraints of 6.5.16.1 ["Simple assignment"], shall be specified by means of an explicit cast.
2. Is the cast (void **)linearr [orig: (void **) lineptr] legal? What about my (void **)wlinearr?
6.3.2.3 ¶7:
A pointer to an object type may be converted to a pointer to a different object type. If the resulting pointer is not correctly aligned[] for the referenced type, the behavior is undefined.
Pointer types are object types, hence char * and void * are object types, and therefore pointers to these types can legally be converted. However, the second sentence is relevant as well. While we know that char * and void * are identically aligned (6.2.5 ¶28), this wouldn't necessarily be true for wchar_t * and void *: it is easy to imagine a situation where the former has half the bit width of the latter. (Recall that K&R claim that their qsort "can process any data type".) That is, even if the cast is fine, my cast (void **)wlinearr might not be.
There is other language in the standard (6.7.6.1 ¶2) where I am not sure whether it has any bearing on these issues:
For two pointer types to be compatible, both shall be identically qualified and both shall be pointers to compatible types.
linearr is of type char * [] and decays to type char ** just before the cast to type void **. For char ** and void ** to be compatible, char * and void * would need to be compatible, but it seems that they technically aren't compatible.
3. Are the casts of numcmp/strcmp from types int (*)(char *, char *)/int (*)(const char *, const char *) to type int (*)(void *, void *) legal? What about my analogous cast of wcscmp from type int (*)(const wchar_t *, const wchar_t *) to type int (*)(void *, void *)? (Note that the difference in constness isn't an issue.)
As the document "Errata for The C Programming Language, Second Edition" by Lucent Technologies (2002/2006) states (code formatting added in some places):
[T]he comparison-routine argument is not treated well. The call shown on p 119, with an argument
(int (*)(void*,void*))(numeric? numcmp : strcmp)
is not only complicated, but only barely passes muster. Bothnumcmpandstrcmptakechar *arguments, but this expression casts pointers to these functions to a function pointer that takesvoid *arguments. The standard does say thatvoid *andchar *have the same representation, so the example will almost certainly work in practice, and is at least defensible under the standard.
According to this answer, the casting of function pointers is only safe (as in: doesn't lead to undefined behavior) if the respective types are "compatible", but char * and void * are technically not compatible (see #2 above).
But perhaps this is really just to appease the compiler (as K&R assure us), so let's have a look at what happens in qsort_alt:
4. Is the call to comp unproblematic?
qsort_alt computes v[i] and v[left], which involves pointer arithmetic on an underlying void * type. (Note that v is of type void **. While pointer arithmetic is illegal on void * (with an underlying void), it is not illegal on void ** (with an underlying void *).) Because pointers to void and to character types "have the same representation and alignment requirements" (6.2.5 ¶28), the index computations seem fine for K&R's original code, but do they also work portably for wchar_t? It seems that a type-generic version of the program would need to supply the size of the underlying type (such as wchar_t *) to qsort_alt.
Furthermore, I am not sure whether it is really true that "[t]he elaborate cast of the function argument [within main] casts the arguments of the comparison function". It seems to me that if any arguments of the comparison function are cast, that would happen within qsort_alt when it calls comp, but not within the call to qsort_alt within main. From the perspective of qsort_alt, comp is a function accepting void * arguments, and any v[index] is of type void *, and therefore there don't seem to be any implicit argument conversions going on. In this regard, I am assuming that implicit argument conversions for function parameters would be performed by the caller, not the callee, but do correct me if I'm wrong. (Caller and callee may, like here, have differing beliefs about the parameters' types.) Despite the absence of a conversion, comp will internally assume that its arguments are char * (for K&R's original) or wchar_t * (for my addition). Things should go well as long as the pointer arithmetic to get to the arguments v[i] and v[left] is proper.
Incidentally, I see calls within qsort_alt to swap as unproblematic, as swap operates on a void ** argument and only reassigns pointers.
First, we should call the attention of any readers of this question to the fact the qsort being discussed here, as defined in Kernighan and Ritchie, The C Programming Language (second edition), page 120, is not the qsort specified in the C standard. The one in the book is archaic and has a defective design. Its prototype is:
void qsort(void *v[], int left, int right, int (*comp)(void *, void *));
The one in the 1990 C standard has prototype:
void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
The most significant difference is the first is designed only to sort an array of pointers, specifically pointers to void (first parameter type is void *[]), whereas the standard version can sort an array of any type (first parameter type is void *, and the third parameter gives the size for each element).
1. Why are the arguments to
qsort_alt[orig:qsort] cast explicitly?
Two arguments are cast, the first and the last. In the first, the authors wish to pass their lineptr, which has type char *[5000], for a parameter nominally of type void *[]. The array lineptr will be automatically converted to char **, and the nominal parameter type will be automatically adjusted to void **, so these are different and incompatible types. For a function call with a prototype, C 2018 6.5.2.2 2 says “… Each argument shall have a type such that its value may be assigned to an object with the unqualified version of the type of its corresponding parameter.” (C 1990 6.3.2.2 is similar.)
Constraints for simple assignment are in C 2018 6.5.16.1 1. (C 1990 6.3.16.1 is similar.) Two of its cases cover when the left operand and the right operand of an assignment are pointer types. One of these says, in part, both are pointers to compatible types except for the qualifiers. This does not apply because char * and void * are not compatible. The other says, in part, the left operand may be a pointer to void, with or without qualifiers. This does not apply because void ** is not a pointer to void. Therefore, a char ** expression does not satisfy the constraints for assignment to a void ** object, so the char ** argument for a void ** does not satisfy the constraints for a function call, so this argument cannot be passed for a void ** parameter without a cast.
In the last argument, the authors wish to pass their numcmp, which, after automatic conversion of a function to a pointer, has type int (*)(char *, char *), for a parameter of type int (*)(void *, void *). Again the constraints for simple assignment apply, and this argument cannot be passed for that parameter without a cast.
2. Is the cast
(void **)linearr[orig:(void **) lineptr] legal? What about my(void **)wlinearr?
The conversion is defined and the conversion and the use of the result to access pointers in the original array is effectively defined by the C standard, albeit by the kludgy specification in C 2018 6.2.5 28 that “A pointer to void shall have the same representation and alignment requirements as a pointer to a character type.”
The initial conversion from char ** to void ** is defined by C 2018 6.3.2.3 7, which says a pointer to an object type may be converted to a pointer to a different object type, but it is undefined if the resulting pointer is not correctly aligned for the referenced type. Since char * and void * have the same alignment requirements, the caveat does not apply. 6.3.2.3 7 further says that converting the result back to the original type yields a value equal to the original pointer. This is the only thing the standard tells us generally about the result of this conversion—for example, it does not tell us that if we convert int *i to float *f, and int and float have the same size and alignment requirements, that *f will access the same bytes as *i will. However, a footnote to 6.2.5 28 tells us “The same representation and alignment requirements are meant to imply interchangeability as arguments to functions,…” This is a bad way to say that a char * may serve as a void * or vice versa, but it does seem the intent was to say we can convert a char ** to a void ** and use the result to access the char * elements. The intent is presumably also to allow this aliasing of different types even though it nominally violates the rules for aliasing in C 2018 6.5 7.
So the conversion from char ** to void ** is defined and may be used to access the char * pointers, even when it is done using a void * type.
On the other hand, your (void **) wlinearr conversion does not enjoy this license. After array-to-pointer conversion, wlinearr yields wchar_t **, and wchar_t * does not necessarily have the same size, representation, or alignment requirements as void *. So the conversion is not guaranteed to work. Even if it does, the resulting value is not specified to be useful for accessing the elements of the wchar_t * array.
3. Are the casts of
numcmp/strcmpfrom typesint (*)(char *, char *)/int (*)(const char *, const char *)to typeint (*)(void *, void *)legal? What about my analogous cast ofwcscmpfrom typeint (*)(const wchar_t *, const wchar_t *)to typeint (*)(void *, void *)? (Note that the difference inconstness isn't an issue.)
The conversions specified by the casts are defined, because C 2018 6.3.2.3 8 says a pointer to any type of function may be converted to a pointer to any other type of function. However, the only defined uses for such a pointer are converting it back to the original type, comparing it for equality to other pointers, or testing whether it is a null pointer. That paragraph says “… If a converted pointer is used to call a function whose type is not compatible with the referenced type, the behavior is undefined.”
4. Is the call to
compunproblematic?
It is problematic because of the rule quoted just above. The qsort defined at this point in the book is defective in standard C and should not be used. Perhaps it was designed for pedagogical purposes, to use types in a more simplistic way than proper use requires to avoid presenting too many new concepts to the student at once. Nonetheless, it is not a good design.
The qsort in the C standard fixes these problems. First, instead of a void ** (equivalently void *[], due to automatic adjustment) parameter, it takes void * and a size_t size parameters. These provide the base address of the elements to be sorted and the size of each element. This allows qsort to manipulate any array by treating its elements as raw bytes (which has defined behavior by the C standard). It does not need type information about the array elements, other than the size.
Second, it specifies the prototype of the comparison function as int ()(const void *, const void *). So no information about the element types is visible or used in this prototype. The function is passed raw pointers to memory, with no type information (other than the const qualifier). Inside the function, the const void * pointers should be converted to pointers to the actual element type (with const). Thus, all of the type information is inside the comparison function the qsort caller provides; none of it is built into qsort.
(The standard qsort also changes int left, int right to size_t nmemb. This simply removes a redundancy, as the caller can specify the “left” endpoint by adding to the base address passed in base, and then the number of elements provides the location of the “right” endpoint.)