void pointer arithmetic

[Alex Fraser]

From searching Google Groups, I understand that void pointer arithmetic is a
constraint violation, which is understandable. However, generic functions
like qsort() and bsearch() must in essence do exactly this, and similarly
generic functions seem to have useful applications.

In a few posts I read, it was suggested to avoid void pointer arithmetic by
casting to a char pointer, and performing arithmetic on that (in multiples
of sizeof(original_type)). Thus the pointer is cast through the sequence
original_type* -> void* -> char* -> void* -> original_type*.

I am quite sure this would work on many implementations (where the casts are
no-ops), but the threads I saw containing the above suggestion did not make
clear whether or not it was undefined (or implementation defined)
behaviour - is it? If so, is there any way to achieve the desired effect
while strictly conforming to the standards?

TIA,
Alex

 

[Hallvard B Furuseth]

From searching Google Groups, I understand that void pointer
arithmetic is a constraint violation, which is understandable.
Yup.

However, generic functions like qsort() and bsearch() must in essence
do exactly this,

No, what these functions do to compare the objects depends on the
original data type of the objects and their semantics. See below.

In a few posts I read, it was suggested to avoid void pointer
arithmetic by casting to a char pointer, and performing arithmetic on
that (in multiples of sizeof(original_type)).

You could, but it's usually cleaner to just cast to pointers the
original type and let the compiler do the sizeof for you.

As for doing pointer arithmetic on the results: If all the pointers
point into the same array, and you really want to sort the pointers by
their index into that array, yes, then you can do that. However,
usually you'll want to do something quite else, e.g.:

static int str_qcmp(const void *a, const void *b)
{
char *const *ap = a;
char *const *bp = b;
return strcmp(*ap, *bp);
}
....
char *arr[] = { "foo", "bar", "baz" };
qsort(arr, sizeof(arr)/sizeof(*arr), sizeof(*arr), str_qcmp);
/* arr = { "bar", "baz", "foo" } */

I am quite sure this would work on many implementations (where the
casts are no-ops),

Never mind that. If casts are not no-ops, the casts will modify the
representations of the pointer as appropriate. Unless you make
the mistake of telling the compiler that some data has another type
than it really has, for example by casting the _function pointer_
to another type. For example, I've seen programs that did this:

static int foo_qcmp(struct foo *a, struct foo *b);
...
qsort(..., (int (*)(const void*, const void*)) foo_qcmp);

Now qsort will pass void pointers to foo_qcmp, but foo_qcmp thinks it is
receives struct foo pointers, so it doesn't convert them from void* to
struct foo*. That fails if void* and struct foo* have different
representations or are passed in different ways to functions.

Thus the pointer is cast through the sequence
original_type* -> void* -> char* -> void* -> original_type*.

The standard allows this, because char* and void* have the same
representation and alignment requirements. However,
original_type* -> void* -> original_type* is quite enough.

 

[Alex Fraser]

Alex Fraser wrote: [snip]

However, generic functions like qsort() and bsearch() must in essence
do exactly this,

No, what these functions do to compare the objects [...]

Sorry, but you totally missed the point, which was the implementation. The
cast sequence I described seems unavoidable. For an equivalent to qsort()
(for example), the first cast happens before you call it, the middle two
within it (with the pointer arithmetic inbetween), and the last in the
comparison function.

The standard allows this, because char* and void* have the same
representation and alignment requirements.

That's what I needed to know . Thankyou.

Alex

 

[Richard Heathfield]

Alex Fraser wrote: [snip]

However, generic functions like qsort() and bsearch() must in essence
do exactly this,

No, what these functions do to compare the objects [...]

Sorry, but you totally missed the point, which was the implementation. The
cast sequence I described seems unavoidable.

Well, you don't need a cast. You can assign a void * to a char * without
casting. But yes, the conversion is unavoidable, and legal.

 

[Alex Fraser]

Well, you don't need a cast. You can assign a void * to a char * without
casting.

Indeed, and the reverse. In fact, all the conversions are to/from void *, so
there's no casting at all.

But yes, the conversion is unavoidable, and legal.

Thanks for the confirmation (that I'm not missing something too).

Alex

 

[Jack Klein]

Indeed, and the reverse. In fact, all the conversions are to/from void *, so
there's no casting at all.

No, this is not true. In some cases there is a difference between
casting between a pointer to void and a pointer to some non-character
object type, although not on today's common desktop systems.

There are some systems where the minimum word size addressable by the
processor is large. I have used digital signal processors from
vendors like Texas Instruments and Analog Devices where there is no
direct hardware support for 8-bit types, that is nothing smaller than
16-bit (TI) or 32-bit (AD).

DSPs in general are used almost entirely in what are called
free-standing environments, and their compilers do not bother to
provide an 8-bit type.

But there are other processors without small integer support that do
feel the need to provide more familiar sized characters.

On some such implementations, a pointer to any object type except void
and the character types is the same size as a machine address, but a
pointer to a character type must be larger. It must contain the
address of a machine word and some additional bits to specify what
sub-word field of the word contains the character of interest.

That is why the standard specifically guarantees that a pointer to
void must have the same representation as pointers to the character
types, and does not place the same requirement on pointers to other
data types.

So all pointers are the same size and representation on your
particular platform, and in fact on most platforms, but not on all
platforms.

Thanks for the confirmation (that I'm not missing something too).

Alex

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Chris Torek]

No, this is not true. In some cases there is a difference between
casting between a pointer to void and a pointer to some non-character
object type, although not on today's common desktop systems. ...[/QUOTE]

[more about byte vs non-byte pointers, snipped]

I do not believe this is what Alex Fraser meant. The quotes I
retained above have to do with the means of achieving the various
pointer conversions. The Standard's constraints on "char *"
imply that any valid data pointer value can be stored in an
object of type "char *", with conversions to and fro giving back
the original pointer (or one that compares equal and is equally
useful, in any case). That is:

char *cp;
double *dp;
... assign some valid value to "dp" ...
cp = (char *)dp;
... any code here that leaves both cp and dp alone ...
*(double *)cp /* has the same effect as *dp */
... code here that modifies "dp"
dp = (double *)cp; /* restores "dp" to the saved value */

Here, the conversions from "double *" to "char *" and back *must*
be done via casts. (As Jack Klein notes, this conversion may indeed
change the underlying bits, so that, e.g., a memory dump of the
memory or registers holding cp and dp would show different values.
If there *is* a change in representation, the one from "double *"
to "char *" is reversible, and "char *" to "double *" reverses it,
except possibly for "padding" bits.)

On the other hand, if we replace "cp" with:

void *vp;

then we can write:

vp = dp;

and later:

dp = vp;

all without casts. (But note that the conversion requested via
*(double *)cp requires either an auxiliary variable such as
"double *dp2", or another cast.) Any actual machine code needed
to convert the "double *" pointer to "void *", and then reverse
that conversion, will still be there, and there is no reason for
code to differ from that for "char *cp".

What Alex Fraser and Richard Heathfield are noting -- correctly --
is that all the intermediate conversions can be written without
the syntactic construct called a "cast". What Jack Klein is noting
-- correctly -- is that they are still conversions. The casts are
"just" syntax by which one can request a conversion; the conversions
are always conversions; and using "void *" allows you to achieve
the desired conversions without the syntax of casts.

The last -- conversions without casts -- can be considered desirable
because casts are very powerful: they not only perform the requested
conversion, but also generally tell a C compiler to shut up and do
it no matter how wrong it looks. In other words, casts suppress
useful diagnostics. The fewer casts you use, the more likely it
is that your C compiler can catch errors in conversions. Or, to
steal a line from Stan Lee and Spider-Man, "with great power comes
great responsibility".

 

[Jack Klein]

No, this is not true. In some cases there is a difference between
casting between a pointer to void and a pointer to some non-character
object type, although not on today's common desktop systems. ...

[more about byte vs non-byte pointers, snipped]

I do not believe this is what Alex Fraser meant.[/QUOTE]

You're absolutely right, I read something in Alex's post that wasn't
actually written there. I'm not sure how I managed to do that, but
thanks for pointing it out!

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Hallvard B Furuseth]

Alex Fraser wrote: [snip]

However, generic functions like qsort() and bsearch() must in essence
do exactly this,

No, what these functions do to compare the objects [...]

Sorry, but you totally missed the point, which was the implementation. The
cast sequence I described seems unavoidable.

Read my article again. I explained that you were wrong, and why.

For an equivalent to qsort() (for example), the first cast happens
before you call it, the middle two within it (with the pointer
arithmetic inbetween), and the last in the comparison function.

Not so. Look at my example using qsort: No pointer arithmetic. No
casts to or from char*. If you disagree, test and then post actual
code which does what you said above, so we can see what you mean.

If you want to _implement_ qsort, you need to cast to char* and do
pointer arithmetic on the result. If you want to _use_ it, you almost
certainly need not.

 

[Dan Pop]

Alex Fraser wrote: [snip]
However, generic functions like qsort() and bsearch() must in essence
do exactly this,

No, what these functions do to compare the objects [...]

Sorry, but you totally missed the point, which was the implementation. The ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
cast sequence I described seems unavoidable.

Read my article again. I explained that you were wrong, and why.

For an equivalent to qsort() (for example), the first cast happens
before you call it, the middle two within it (with the pointer
arithmetic inbetween), and the last in the comparison function.

Not so. Look at my example using qsort: No pointer arithmetic. No
casts to or from char*. If you disagree, test and then post actual
code which does what you said above, so we can see what you mean.

If you want to _implement_ qsort, you need to cast to char* and do
pointer arithmetic on the result. If you want to _use_ it, you almost
certainly need not.

Are you reading impaired, or what? He explicitly told you that he was
talking about the *implementation* of qsort and bsearch and, as you
agree, the casts are unavoidable. So, where is he wrong?

Dan

 

[Richard Heathfield]

In <[email protected]> Hallvard B Furuseth



Are you reading impaired, or what? He explicitly told you that he was
talking about the *implementation* of qsort and bsearch and, as you
agree, the casts are unavoidable. So, where is he wrong?

A small nit: the /conversions/ are unavoidable. They can, however, be
implicit conversions. They do not need to be casts. All you need is a spare
char * to hold the relevant pointer value. (Or possibly more than one. I
haven't checked.)

 

[Dan Pop]

A small nit: the /conversions/ are unavoidable. They can, however, be
implicit conversions. They do not need to be casts. All you need is a spare
char * to hold the relevant pointer value. (Or possibly more than one. I
haven't checked.)

But that's the point: the casts (which are effectively no-ops in terms of
generated code) avoid the need of temporary pointers that serve no other
purpose than avoiding the casts.

Dan

 

[Richard Heathfield]

In <[email protected]> Richard Heathfield


But that's the point: the casts (which are effectively no-ops in terms of
generated code) avoid the need of temporary pointers that serve no other
purpose than avoiding the casts.

You missed the *primary* purpose of the temporary pointers, which is that
they make the code easier to read.

 

[karl malbrain]

You missed the *primary* purpose of the temporary pointers, which is that
they make the code easier to read.

It also makes for a disciplined evaluation of NULL pointers, as in:

MyStruct *my;
void *voidmyptr;

if( my = voidmyptr )
continue ok;
else
return errpunt ("My struct doesn't exist"

SO, I'm with you on this one, 100%. karl m

 

[Richard Heathfield]

It also makes for a disciplined evaluation of NULL pointers, as in:

MyStruct *my;
void *voidmyptr;

if( my = voidmyptr )
continue ok;
else
return errpunt ("My struct doesn't exist"

SO, I'm with you on this one, 100%. karl m

Nevertheless, I stand by what I said.

 

[Dan Pop]

You missed the *primary* purpose of the temporary pointers, which is that
they make the code easier to read.

That's not automatically true in my experience. It heavily depends on the
context.

Dan

 

[Richard Bos]

You missed the *primary* purpose of the temporary pointers, which is that
they make the code easier to read.

Says you. In some often-occurring cases (e.g., qsort()ing strings using
a wrapper for strcpy()), the cast version is, IMO, easier to read than
the extra-object version.

Richard

 

[Al Bowers]

Says you. In some often-occurring cases (e.g., qsort()ing strings using
a wrapper for strcpy()), the cast version is, IMO, easier to read than
the extra-object version.

What is this often-occuring case (qsort()ing strings using a
wrapper for strcpy()?

 

[Dan Pop]

What is this often-occuring case (qsort()ing strings using a
wrapper for strcpy()?

Obvious typo: he meant strcmp(). Consider the case when the comparison
has to omit a fixed length header, that might contain binary data:

int compare(const void *s1, const void *s2)
{
return strcmp((char *)s1 + OFFSET, (char *)s2 + OFFSET);
}

Dan

 

[Jeremy Yallop]

Obvious typo: he meant strcmp(). Consider the case when the comparison
has to omit a fixed length header, that might contain binary data:

int compare(const void *s1, const void *s2)
{
return strcmp((char *)s1 + OFFSET, (char *)s2 + OFFSET);
}

I think this needs to be something like:

int compare(const void *s1, const void *s2)
{
return strcmp(*(char **)s1 + OFFSET, *(char **)s2 + OFFSET);
}

Jeremy.