A question about 13.9 from the c faq.

C

Chad

At the following url http://c-faq.com/lib/qsort2.html, they have the
following

Q: Now I'm trying to sort an array of structures with qsort. My
comparison function takes pointers to structures, but the compiler
complains that the function is of the wrong type for qsort. How can I
cast the function pointer to shut off the warning?

A: The conversions must be in the comparison function, which must be
declared as accepting ``generic pointers'' (const void *) as discussed
in question 13.8 above. For a hypothetical little date structure

struct mystruct {
int year, month, day;
};

the comparison function might look like [footnote]

int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if(sp1->year < sp2->year) return -1;
else if(sp1->year > sp2->year) return 1;
else if(sp1->month < sp2->month) return -1;
else if(sp1->month > sp2->month) return 1;
else if(sp1->day < sp2->day) return -1;
else if(sp1->day > sp2->day) return 1;
else return 0;
}

(The conversions from generic pointers to struct mystruct pointers
happen in the initializations sp1 = p1 and sp2 = p2; the compiler
performs the conversions implicitly since p1 and p2 are void
pointers.)

The question is, why don't you use something like

const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;


Chad
 
T

Thad Smith

Chad said:
struct mystruct {
int year, month, day;
};

the comparison function might look like [footnote]

int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if(sp1->year < sp2->year) return -1;
else if(sp1->year > sp2->year) return 1;
else if(sp1->month < sp2->month) return -1;
else if(sp1->month > sp2->month) return 1;
else if(sp1->day < sp2->day) return -1;
else if(sp1->day > sp2->day) return 1;
else return 0;
}

The question is, why don't you use something like

const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

The initializer would have the wrong type and value. You want to assign
the pointer value, not the address of it.
 
D

Don Bruder

Chad said:
At the following url http://c-faq.com/lib/qsort2.html, they have the
following

Q: Now I'm trying to sort an array of structures with qsort. My
comparison function takes pointers to structures, but the compiler
complains that the function is of the wrong type for qsort. How can I
cast the function pointer to shut off the warning?

A: The conversions must be in the comparison function, which must be
declared as accepting ``generic pointers'' (const void *) as discussed
in question 13.8 above. For a hypothetical little date structure

struct mystruct {
int year, month, day;
};

the comparison function might look like [footnote]

int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if(sp1->year < sp2->year) return -1;
else if(sp1->year > sp2->year) return 1;
else if(sp1->month < sp2->month) return -1;
else if(sp1->month > sp2->month) return 1;
else if(sp1->day < sp2->day) return -1;
else if(sp1->day > sp2->day) return 1;
else return 0;
}

(The conversions from generic pointers to struct mystruct pointers
happen in the initializations sp1 = p1 and sp2 = p2; the compiler
performs the conversions implicitly since p1 and p2 are void
pointers.)

The question is, why don't you use something like

const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

Because:

&p1 == the address of the variable (parameter, actually) p1

p1 == the variable holding the address of the struct under comparison

*p1 == the struct under comparison

Assuming p1 contains the (randomly chosen) address 5, and assuming p1 is
located in memory at (randomly chosen) location 27, and that the "..."
is replaced by the "const struct mystruct *" as shown above, the
following would be true:

assignment result
....sp1 = &p1 sp now holds 27 (the address of p1)
....sp1 = p1 sp now holds 5 (the contents of p1)
....sp1 = *p1 sp now holds <whatever value is found at location 5>

BUT...
Since p1 is a function parameter, rather than an actual variable, I
believe trying to take its address will result in undefined behavior.
(unless special steps are taken to make things happen differently,
parameters are usually passed on the stack, which makes taking their
address either impossible, or pointless, because for practical purposes,
they don't really HAVE an address to take.)
 
E

Eric Sosman

Chad said:
[... sorting arrays of structs with qsort() ...]

struct mystruct {
int year, month, day;
};

the comparison function might look like [footnote]

int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
[...]

The question is, why don't you use something like

const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

Why don't you try it, and see what happens?

To understand why <<spoiler alert>> the compiler complains,
ask yourself: What is the type of `&p1'? And what does `&p1'
point to? And to understand the FAQ's code, ask yourself:
What does `p1' point to?
 
J

James Kuyper

Don Bruder wrote:
....
Since p1 is a function parameter, rather than an actual variable, I
believe trying to take its address will result in undefined behavior.
Click to expand...

A function parameter is an actual variable, and it's perfectly legal to
take its address. The only problem is that it's the wrong address, in
this context.
(unless special steps are taken to make things happen differently,
parameters are usually passed on the stack, which makes taking their
address either impossible, or pointless, because for practical purposes,
they don't really HAVE an address to take.)
Click to expand...

On the machines where I've had to be familiar with such details, the
stack was a piece of memory that served a different purpose from the
heap and other pieces of memory, but was just as addressable as any of
those other pieces. If an implementation used something for parameter
passing for which that wasn't true (such as registers), it must copy the
values out of the registers into addressable memory, at least if the
code ever actually takes the address of the parameter.
 
C

Chad

Chad said:
[... sorting arrays of structs with qsort() ...]
Click to expand...
struct mystruct {
int year, month, day;
};
Click to expand...
the comparison function might look like [footnote]
Click to expand...
int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
[...]
Click to expand...
The question is, why don't you use something like
Click to expand...
const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

Why don't you try it, and see what happens?

To understand why <<spoiler alert>> the compiler complains,
ask yourself: What is the type of `&p1'? And what does `&p1'
point to? And to understand the FAQ's code, ask yourself:
What does `p1' point to?
Click to expand...


Maybe this is lack of experience or maybe it's because I will still
once in a while get this burning sensation when I try to think, but it
appears that p1 points to thing.
 
W

Willem

James wrote:
) On the machines where I've had to be familiar with such details, the
) stack was a piece of memory that served a different purpose from the
) heap and other pieces of memory, but was just as addressable as any of
) those other pieces. If an implementation used something for parameter
) passing for which that wasn't true (such as registers), it must copy the
) values out of the registers into addressable memory, at least if the
) code ever actually takes the address of the parameter.

Doesn't the standard allow an implementation that has a pointer type
which can point to registers as well as memory ? I could imagine having
some kind of 'fat' pointer type with a flag that indicates 'this is a
pointer to register X'.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
D

Don Bruder

James Kuyper said:
Don Bruder wrote:
...

A function parameter is an actual variable, and it's perfectly legal to
take its address.
Click to expand...

OK, then I've been operating under a misconception for a while. While
they BEHAVE as variables, I've always been under the impression that
they "weren't really" due to the passing mechanism.
The only problem is that it's the wrong address, in
this context.
Click to expand...

Right. The comparison would be against who-knows-what, but whatever that
turned out to be, it wouldn't be the desired data.
 
E

Eric Sosman

Chad said:
Chad said:
[... sorting arrays of structs with qsort() ...]
struct mystruct {
int year, month, day;
};
the comparison function might look like [footnote]
int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
[...]
The question is, why don't you use something like
const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...
Why don't you try it, and see what happens?

To understand why <<spoiler alert>> the compiler complains,
ask yourself: What is the type of `&p1'? And what does `&p1'
point to? And to understand the FAQ's code, ask yourself:
What does `p1' point to?
Click to expand...

Maybe this is lack of experience or maybe it's because I will still
once in a while get this burning sensation when I try to think, but it
appears that p1 points to thing.
Click to expand...

Right: `p1' points to one of the things in the array
being sorted, that is, to a `struct mystruct' instance. The
only problem is the type: `p1' is a `void*', but to get at
the struct elements you need a `struct mystruct*'. Hence
the conversion to `sp1'.

How did you make out with the other two questions? (And
did you try the experiment I suggested, or did you just accept
my spoiler as Gospel? It's flattering when people believe
what I say, but it's not always their wisest course ...)
 
K

Keith Thompson

Chad said:
At the following url http://c-faq.com/lib/qsort2.html, they have the
following

Q: Now I'm trying to sort an array of structures with qsort. My
comparison function takes pointers to structures, but the compiler
complains that the function is of the wrong type for qsort. How can I
cast the function pointer to shut off the warning?

A: The conversions must be in the comparison function, which must be
declared as accepting ``generic pointers'' (const void *) as discussed
in question 13.8 above. For a hypothetical little date structure

struct mystruct {
int year, month, day;
};

the comparison function might look like [footnote]

int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if(sp1->year < sp2->year) return -1;
else if(sp1->year > sp2->year) return 1;
else if(sp1->month < sp2->month) return -1;
else if(sp1->month > sp2->month) return 1;
else if(sp1->day < sp2->day) return -1;
else if(sp1->day > sp2->day) return 1;
else return 0;
}

(The conversions from generic pointers to struct mystruct pointers
happen in the initializations sp1 = p1 and sp2 = p2; the compiler
performs the conversions implicitly since p1 and p2 are void
pointers.)

The question is, why don't you use something like

const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

Um, because it's illegal (a constraint violation), and even if it
weren't it wouldn't work.

p1 is a parameter (a local object) of type void* (I'm ignoring the
const qualifier). When converted to type ``struct mystruct*'',
assuming the caller has passed the right arguments, it points to an
object of type ``struct mystruct''.

You propose instead to use ``&p1'', i.e., the *address* of p1. This
is the address of a pointer object, and is of type void**.

The question is, why would you want to use ``&p1'' when ``p1'' is
correct?
 
C

Chad

Chad said:
Chad wrote:
[... sorting arrays of structs with qsort() ...]
struct mystruct {
int year, month, day;
};
the comparison function might look like [footnote]
int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
[...]
The question is, why don't you use something like
const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Why don't you try it, and see what happens?
To understand why <<spoiler alert>> the compiler complains,
ask yourself: What is the type of `&p1'? And what does `&p1'
point to? And to understand the FAQ's code, ask yourself:
What does `p1' point to?
Click to expand...
Click to expand...
Maybe this is lack of experience or maybe it's because I will still
once in a while get this burning sensation when I try to think, but it
appears that p1 points to thing.
Click to expand...

Right: `p1' points to one of the things in the array
being sorted, that is, to a `struct mystruct' instance. The
only problem is the type: `p1' is a `void*', but to get at
the struct elements you need a `struct mystruct*'. Hence
the conversion to `sp1'.

How did you make out with the other two questions? (And
did you try the experiment I suggested, or did you just accept
my spoiler as Gospel? It's flattering when people believe
what I say, but it's not always their wisest course ...)
Click to expand...


The example in 13.9 as the same as the lines of code in a project that
I'm working on. Anyhow, here is what happens when I take the address.

int
compare (const void *a, const void *b)
{
/*const struct utmp *ma = *(const struct utmp *const*)a;
const struct utmp *mb = *(const struct utmp *const*)b;*/

const struct utmp *ma = &a;
const struct utmp *mb = &b;
int32_t time1, time2;
time1 = ma->ut_time;
time2 = mb->ut_time;

if(time1 < time2)
return -1;
else if(time1 > time2)
return 1;
else
return 0;
}


% gcc -g no.c -o no -lkvm
no.c: In function `compare':
no.c:135: warning: initialization from incompatible pointer type
no.c:136: warning: initialization from incompatible pointer type

Without look at the disassembler, I would venture to say that a and b
are of type (struct utmp)
 
J

James Kuyper

Willem said:
James wrote:
) On the machines where I've had to be familiar with such details, the
) stack was a piece of memory that served a different purpose from the
) heap and other pieces of memory, but was just as addressable as any of
) those other pieces. If an implementation used something for parameter
) passing for which that wasn't true (such as registers), it must copy the
) values out of the registers into addressable memory, at least if the
) code ever actually takes the address of the parameter.

Doesn't the standard allow an implementation that has a pointer type
which can point to registers as well as memory ? I could imagine having
some kind of 'fat' pointer type with a flag that indicates 'this is a
pointer to register X'.
Click to expand...

Sure. I was talking about hypothetical implementations which passed
arguments using non-addressable memory; an implementation such as you
describe wouldn't qualify.
 
J

James Kuyper

Chad wrote:
....
int
compare (const void *a, const void *b)
{
/*const struct utmp *ma = *(const struct utmp *const*)a;
const struct utmp *mb = *(const struct utmp *const*)b;*/

const struct utmp *ma = &a;
const struct utmp *mb = &b;
int32_t time1, time2;
time1 = ma->ut_time;
time2 = mb->ut_time;

if(time1 < time2)
return -1;
else if(time1 > time2)
return 1;
else
return 0;
}


% gcc -g no.c -o no -lkvm
no.c: In function `compare':
no.c:135: warning: initialization from incompatible pointer type
no.c:136: warning: initialization from incompatible pointer type

Without look at the disassembler, I would venture to say that a and b
are of type (struct utmp)
Click to expand...

Both a and b are declared as pointers to void. Neither one has the type
(struct utmp). When compare() is called by qsort() to compare two struct
utmp objects, then a and b will each point at the positions in memory
containing those objects. However, they don't have the correct type to
be used to directly access those structs. Both ma and mb have the
correct type to be used for accessing a struct utmp, but they can only
be used that way if correctly initialized.

If you had initialized ma with the converted value of a, it would have
been correct. However, you used "&a". The value of that expression is a
pointer which points at the object named 'a'. That object is in a
completely different piece of memory than the piece of memory that 'a'
points at.

There is something wrong about the way you're thinking about this, but
I'm not quite sure what it is.
 
L

lovecreatesbea...

Chad said:
At the following urlhttp://c-faq.com/lib/qsort2.html, they have the
following
Click to expand...
Q: Now I'm trying to sort an array of structures with qsort. My
comparison function takes pointers to structures, but the compiler
complains that the function is of the wrong type for qsort. How can I
cast the function pointer to shut off the warning?
Click to expand...
A: The conversions must be in the comparison function, which must be
declared as accepting ``generic pointers'' (const void *) as discussed
in question 13.8 above. For a hypothetical little date structure
Click to expand...
struct mystruct {
int year, month, day;
};
Click to expand...
the comparison function might look like [footnote]
Click to expand...
int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if(sp1->year < sp2->year) return -1;
else if(sp1->year > sp2->year) return 1;
else if(sp1->month < sp2->month) return -1;
else if(sp1->month > sp2->month) return 1;
else if(sp1->day < sp2->day) return -1;
else if(sp1->day > sp2->day) return 1;
else return 0;
}
Click to expand...
(The conversions from generic pointers to struct mystruct pointers
happen in the initializations sp1 = p1 and sp2 = p2; the compiler
performs the conversions implicitly since p1 and p2 are void
pointers.)
Click to expand...
The question is, why don't you use something like
Click to expand...
const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

Um, because it's illegal (a constraint violation), and even if it
weren't it wouldn't work.

p1 is a parameter (a local object) of type void* (I'm ignoring the
const qualifier). When converted to type ``struct mystruct*'',
assuming the caller has passed the right arguments, it points to an
object of type ``struct mystruct''.

You propose instead to use ``&p1'', i.e., the *address* of p1. This
is the address of a pointer object, and is of type void**.
Click to expand...

Does the operation &expr yield value of void* type? Is void* the
default data type for pointers. I ever heard that there is not a data
type called `pointer type', but there are `pointer types' of pointers
pointed to data of some kinds of types.
 
W

Willem

(e-mail address removed) wrote:
) Does the operation &expr yield value of void* type?

No.

) Is void* the default data type for pointers.

No.

) I ever heard that there is not a data type called `pointer type', but
) there are `pointer types' of pointers pointed to data of some kinds of
) types.

Almost.
There are 'pointer types' of pointers to data of _all_ kinds of types.
Even to pointer types. Even to pointer types pointing to pointer types.
Etcetera.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT
 
K

Keith Thompson

[email protected] said:
Does the operation &expr yield value of void* type? Is void* the
default data type for pointers. I ever heard that there is not a data
type called `pointer type', but there are `pointer types' of pointers
pointed to data of some kinds of types.
Click to expand...

Do you have a C textbook?

No, the "&" operator does not yield a result of type void*. "&expr"
is of type "pointer to FOO", where "FOO" is the type of the expression
(which must be an lvalue).

There is no "default data type for pointers". void* is a generic
pointer type, in the sense that (a) a value of any pointer-to-object
type or pointer-to-incomplete type can be implicitly converted to
void* or vice versa, and (b) converting a pointer value to void* and
back again is guaranteed to yield the orginial value.

For each data type, there is a distinct pointer type that points to
objects of that data type.
 
P

Paul Sinnett

Chad said:
int
compare (const void *a, const void *b)
....

Without look at the disassembler, I would venture to say that a and b
are of type (struct utmp)
Click to expand...

No, a and b as you've declared them are of type "pointer to void." You
can think of this as a pointer to something you don't know about.

To make them into pointers to something you want, you have to cast them.
And you cast them from type "pointer to void" to "pointer to utmp".

Since you're casting from one type of pointer to another, you shouldn't
try to take the address with &a. If you use &a you will get the address
of a pointer, not the address of the utmp structure you are after.
 
P

pete

Don said:
OK, then I've been operating under a misconception for a while. While
they BEHAVE as variables, I've always been under the impression that
they "weren't really" due to the passing mechanism.
Click to expand...

Parameters are local objects in function definitions.
Parameters are initialised
by the values of arguments in function calls.
Click to expand...
 
T

Thad Smith

Don said:
struct mystruct {
int year, month, day;
};

the comparison function might look like [footnote]

int mystructcmp(const void *p1, const void *p2)
{
const struct mystruct *sp1 = p1;
const struct mystruct *sp2 = p2;
if(sp1->year < sp2->year) return -1;
else if(sp1->year > sp2->year) return 1;
else if(sp1->month < sp2->month) return -1;
else if(sp1->month > sp2->month) return 1;
else if(sp1->day < sp2->day) return -1;
else if(sp1->day > sp2->day) return 1;
else return 0;
}
...
The question is, why don't you use something like

const struct mystruct *sp1 = &p1;
const struct mystruct *sp2 = &p2;
Click to expand...

Because:

&p1 == the address of the variable (parameter, actually) p1

p1 == the variable holding the address of the struct under comparison

*p1 == the struct under comparison

Assuming p1 contains the (randomly chosen) address 5, and assuming p1 is
located in memory at (randomly chosen) location 27, and that the "..."
is replaced by the "const struct mystruct *" as shown above, the
following would be true:

assignment result
...sp1 = &p1 sp now holds 27 (the address of p1)
...sp1 = p1 sp now holds 5 (the contents of p1)
...sp1 = *p1 sp now holds <whatever value is found at location 5>
Click to expand...

This approach works well for me and I encourage others to use it by
"playing computer" and assign sample values for variables. While
pointers aren't necessarily simple addresses, I use addresses for
examples because addresses are
1) a simple model which can help understanding
2) accurate description for many implementations.

Since I can't keep much in my head without it turning to soup, I write
down sample values. Here is an example for the comparison function:

Let's assume that ints are 4 bytes each and that pointers are addresses
of memory. Assume, for this example, that there is a declaration

struct mystruct ms[5] = {{1812,1,1}, <more initializations> };

to allocate the array to be sorted and that ms has the address 1000.
Assume that struct mystruct has no padding, so sizeof (ms[0]) = 12.
Assume further that mystructcmp was called to compare ms[0] and ms[1].
Assume that parameters p1 and p2 have the address 2000 and 2004 and sp1
has the address 3000.

Variable Address Value Type
ms[0] 1000 struct mystruct
ms[0].year 1000 1812 int
ms[1] 1012
ms[4] 1048
p1 2000 1000 const void*
p2 2004 1012 const void*

If we initialize sp1 by
const struct mystruct *sp1 = p1;

we get

sp1 3000 1000 const struct mystruct *

Then when we access sp1->year, the offset 0 is added to 1000, the value
of the pointer, and we read address 1000, giving the int value 1812,
which is ms[0].year, exactly what we want.

If, instead, sp1 is initialized by
const struct mystruct *sp1 = &p1;

we get

sp1 3000 2000 const struct mystruct *

When the code accesses sp1->year, it reads the contents of 2000, giving
the value 1000, which is an address, not the intended value of 1812.

In general, things get a lot worse when using the wrong pointer value,
including attempting to read addresses that aren't even assigned to the
program.

Playing computer with sample values, writing down results as statements
are executed, helps me to see whether the declarations and logic makes
sense. I do this when I am using pointers a lot, such as working with
linked lists, but also works well with other computation.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Similar Threads

Drawing missing in bitmap in a pure C win32 program 4
Getting a bad input error, not sure why. 2
Copy string from 2D array to a 1D array in C 1
The following code is not working properly need assistance 2
Lexical Analysis on C++ 1
A question about program logic... program provided 20
Collect Excel Data from Website 5
How can I view / open / render / display a pdf file with c code? 0

Members online

No members online now.
Total: 38 (members: 0, guests: 38)
Robots: 254

Forum statistics

Threads
473,763
Messages
2,569,563
Members
45,039
Latest member
CasimiraVa

Latest Threads

Top