newbie-A line from K&R that puzzles me

[Bob]

In K&R Chapter 5.11 about function pointers there is a line

qsort((void**) lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric ?
numcmp : strcmp));

Now qsort expects an array of pointers, two integers, and a function
with two pointer arguments.

The third argument (a function with two pointer arguments) above is

(int (*)(void*,void*)) (numeric ? numcmp : strcmp)

Say that numeric is 0 then it evaluates to

(int (*)(void*,void*)) (strcmp)

Now I would have expected something like

int (*strcmp) (void*,void*)

Are these two statements the same, and which rule in C says that they
are same?

Bob

 

[pemo]

In K&R Chapter 5.11 about function pointers there is a line

qsort((void**) lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric ?
numcmp : strcmp));

Now qsort expects an array of pointers, two integers, and a function
with two pointer arguments.

The third argument (a function with two pointer arguments) above is

(int (*)(void*,void*)) (numeric ? numcmp : strcmp)

Say that numeric is 0 then it evaluates to

(int (*)(void*,void*)) (strcmp)

Now I would have expected something like

int (*strcmp) (void*,void*)

Are these two statements the same, and which rule in C says that they
are same?

This bit is causing confusion?

(int (*)(void*,void*))(numeric ? numcmp : strcmp)

numeric is tested, and if found to be non zero, numcmp replaces 'numeric ?
numcmp : strcmp', if numeric is zero, strcmp replaces 'numeric ? numcmp :
strcmp'.

Say numeric is '1', the statement now looks liike this

(int (*)(void*,void*))(numcmp)

So, numcmp is being cast to a pointer to a function that returns an int, and
takes two void * args.

Clear now?

 

[Bob]

Still confused. What's probably causing my confusion is the rules for
casting. I have difficulty understanding the line

(int (*)(void*,void*))(numcmp)

In general when casting you have

(type) expression

Is int (*)(void*,void*) a type?

int is a type that I know
int * is also a type (a pointer to an int)

But what kind of type is int (*)(void*,void*)?

That I do not understand. If it is a type, then I would appreciate a
reference where I can read and learn about that.

Thanks Bob

 

[pemo]

Still confused. What's probably causing my confusion is the rules for
casting. I have difficulty understanding the line

(int (*)(void*,void*))(numcmp)

In general when casting you have

(type) expression

Is int (*)(void*,void*) a type?

int is a type that I know
int * is also a type (a pointer to an int)

But what kind of type is int (*)(void*,void*)?

That I do not understand. If it is a type, then I would appreciate a
reference where I can read and learn about that.

Any valid cast expression involves a type.

From 6.5.4.4

Preceding an expression by a parenthesized type name converts the value of
the
expression to the named type. This construction is called a cast.

Yes, used here it's of type function pointer. Specifically, it's a pointer
to a function that's also typed ... , i.e., the function pointed to returns
an int and takes two void * parameters. So the type is:

pointer to function that returns an int,a nd takes two void * args.

 

[pemo]

This may help -or- hinder?

http://citeseer.ist.psu.edu/cache/p...szSzBL-0113590-990202-03.pdf/siff99coping.pdf

 

[Eric Sosman]

In K&R Chapter 5.11 about function pointers there is a line

qsort((void**) lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric ?
numcmp : strcmp));

This is very odd indeed, assuming qsort() and strcmp()
are the Standard library functions and not some user-defined
functions with the same name (and static linkage). There are
at least four peculiarities:

- The first argument to qsort() should be a `void*', but
a `void**' is supplied instead. This may be all right
if <stdlib.h> has been included (see below, though), but
is risky and could fail on some machines, depending on
the actual type and value of `lineptr'.

- qsort() is being asked to sort an array of length zero.
That's not illegal, but it's weird.

- The fourth argument to qsort() should be of type
`int (*)(const void*,const void*)'. Since the cast
you've shown lacks the `const' qualifiers, the compiler
is required to protest if <stdlib.h> has been included.

- It is incorrect to use strcmp() as the fourth argument
to qsort(), even if you disguise its true type with a
cast. Since the array being sorted contains no elements
strcmp() will not be called and the error won't hurt,
but it's certainly odd to find strcmp() there.

Since Messrs. K and R are perfectly familiar with all the
above, I'm guessing that there must be additional context that
puts this peculiar line of code in a different light. Taken
in isolation, it just doesn't make sense. Not to me, anyhow.

Now qsort expects an array of pointers, two integers, and a function
with two pointer arguments.

Not quite. qsort() expects a `void*' pointer (what it
points to is usually an array of pointers, but need not be),
two `size_t' (not `int') arguments, and a pointer to an `int'-
valued function of two `const void*' arguments; there are also
requirements on how the pointed-to function must behave.

The third argument (a function with two pointer arguments) above is

s/third/fourth/

(int (*)(void*,void*)) (numeric ? numcmp : strcmp)

Say that numeric is 0 then it evaluates to

(int (*)(void*,void*)) (strcmp)

Now I would have expected something like

int (*strcmp) (void*,void*)

Are these two statements the same, and which rule in C says that they
are same?

The two are not the same. The first starts with a pointer
to the strcmp() function and converts it to a pointer to a
different type of function, namely, an `int'-valued function
of two `void*' arguments (note that strcmp() has different
argument types). The second could be a declaration of a pointer
variable named `strcmp', capable of pointing to `int'-values
functions of two `void*' arguments, but I don't see how the
second form could appear in an expression.

 

[Bob]

Thanks very much for the help,

I understand now. I found a simple explenation at

http://gethelp.devx.com/techtips/cpp_pro/10min/10min0300.asp

It's a short article written by Danny Kalev called "Declaring Function
Pointers and Implementing Callbacks"

(Remark. It's somewhat strange that K&R used this rather complicated
construction in the middle of a program without warning and without
explaination. Otherwise they always explain things they introduce.)

Bob

 

[pemo]

This is very odd indeed, assuming qsort() and strcmp()
are the Standard library functions and not some user-defined
functions with the same name (and static linkage). There are
at least four peculiarities:

- The first argument to qsort() should be a `void*', but
a `void**' is supplied instead. This may be all right
if <stdlib.h> has been included (see below, though), but
is risky and could fail on some machines, depending on
the actual type and value of `lineptr'.

- qsort() is being asked to sort an array of length zero.
That's not illegal, but it's weird.

- The fourth argument to qsort() should be of type
`int (*)(const void*,const void*)'. Since the cast
you've shown lacks the `const' qualifiers, the compiler
is required to protest if <stdlib.h> has been included.

- It is incorrect to use strcmp() as the fourth argument
to qsort(), even if you disguise its true type with a
cast. Since the array being sorted contains no elements
strcmp() will not be called and the error won't hurt,
but it's certainly odd to find strcmp() there.

Since Messrs. K and R are perfectly familiar with all the
above, I'm guessing that there must be additional context that
puts this peculiar line of code in a different light. Taken
in isolation, it just doesn't make sense. Not to me, anyhow.


Not quite. qsort() expects a `void*' pointer (what it
points to is usually an array of pointers, but need not be),
two `size_t' (not `int') arguments, and a pointer to an `int'-
valued function of two `const void*' arguments; there are also
requirements on how the pointed-to function must behave.


The two are not the same. The first starts with a pointer
to the strcmp() function and converts it to a pointer to a
different type of function, namely, an `int'-valued function
of two `void*' arguments (note that strcmp() has different
argument types). The second could be a declaration of a pointer
variable named `strcmp', capable of pointing to `int'-values
functions of two `void*' arguments, but I don't see how the
second form could appear in an expression.

The code that the OP's referring to is more or less this:


#include <stdio.h>
#include <string.h>


#define MAXLINES 5000 /* max /lines to be sorted */
char *lineptr[MAXLINES]; /* pointers to text lines */


int readlines(char *lineptr[], int nlines);
void writelines(char *lineptr[], int nlines);
void qsort(void *lineptr[], int left, int right, int (*comp)(void *,
void *));
int numcmp(char *, char *);

/* sort input lines */
main(int argc, char *argv[])
{
int nlines; /* number of input lines read */
int numeric =0; /* 1 if numeric sort */ , o
if (argc > 1 && strcmp(argv[ 1], "-n") == 0)
numeric = 1;
if ((nlines = readlines[lneptr, MAXLINES)) >= 0)
{
qsort((void **)lineptr, 0, nlines-1, (int (*)(void*,void*))(numeric
? numcmp : strcmp));
writelines(lineptr, nlines);
return 0;
}
else
{
printf("input too big to sort\n return 1 ;
}
}

 

[Dik T. Winter]

>
> This is very odd indeed, assuming qsort() and strcmp()
> are the Standard library functions and not some user-defined
> functions with the same name (and static linkage).

From: <http://cm.bell-labs.com/cm/cs/cbook/2ediffs.html>, errata for The
C Programming Language, Second Edition:

"
119-121(§5.11): The qsort discussion needs recasting in several ways.
First, qsort is a standard routine in ANSI/ISO C, so the rendition
here should be given a different name, especially because the arguments
to standard qsort are a bit different: the standard accepts a base
pointer and a count, while this example uses a base pointer and two
offsets.

Also, the 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. Both numcmp
and strcmp take char * arguments, but this expression casts pointers
to these functions to a function pointer that takes void * arguments.
The standard does say that void * and char * have the same representation,
so the example will almost certainly work in practice, and is at least
defensible under the standard. There are too many lessons in these pages.
"

 

[Dave Thompson]

Bob wrote:

Not quite. qsort() expects a `void*' pointer (what it
points to is usually an array of pointers, but need not be),
two `size_t' (not `int') arguments, and a pointer to an `int'-
valued function of two `const void*' arguments; there are also
requirements on how the pointed-to function must behave.

Standard qsort expects a void* pointer to an array of _something_:
sometimes an array of pointers, sometimes an array of actual data.
size_t is an integer type though definitely not signed int and
possibly/probably not unsigned int. void* and qualified (including
const) void* are officially not compatible types and thus neither are
(pointers to) functions taking them, but they are required to have the
same representation and alignment which is nonnormatively "meant to
imply interchangeability as arguments to functions ..." so it seems
very unlikely this will actually fail; char* and void* (and their
qualified versions) are similarly required to be the same, and again
likely to work, although it is remotely conceivable an implementation
might want to pass q-char* arguments differently from q-void*.

<snip rest>

- David.Thompson1 at worldnet.att.net

 

[pete]

This is very odd indeed, assuming qsort() and strcmp()
are the Standard library functions and not some user-defined
functions with the same name (and static linkage).

In that part of K&R2,
they are user-defined functions with the same name.

 

[Jordan Abel]

In that part of K&R2,
they are user-defined functions with the same name.

In what way is strcmp not suitable for either that cast or for being
passed to [standard] qsort? void * and char * are required to have the
same representation - are const pointers and non-const ones allowed to
have a different representation?

 

[Eric Sosman]

In that part of K&R2,
they are user-defined functions with the same name.

In what way is strcmp not suitable for either that cast or for being
passed to [standard] qsort? void * and char * are required to have the
same representation - are const pointers and non-const ones allowed to
have a different representation?

Objects qualified with const (or volatile or restrict)
have the same representations as if unqualified. That's not
the issue, though: the arguments to strcmp() have the same
qualifiers as the arguments to qsort()'s comparison function.

`void*' and `char*' have the same reprentation, but that's
not the issue either. The problem is that `char*' and `void*'
are different types -- incompatible types, in fact. This in
turn means that `int(*)(const char*,const char*)' is incompatible
with `int(*)(const void*,const void*)'. They are different types.

You can cast a pointer to strcmp() to the type expected by
qsort(), but the calls through that pointer invoke undefined
behavior: You must call a function through a pointer that
matches the function's type.

You'll get away with it 99.44% of the time, but it's wrong,
R-O-N-G, wrong. (It's also not what you want unless you happen
to be sorting an array of fixed-length strings, not an array
of character pointers.)