In article <slrnbpl2k0.k30.news@tuls.pauken.co.uk>
Stig Brautaset <news@brautaset.org> writes:[color=blue]
>... The program at the bottom of this post illustrates what
>I want to do: the declaration of `struct node2' would exist only in the
>library source file. When using the library I would be able to define
>multiple lists of different types of elements. The only requirement
>would be that the ->next member would be the first member in the
>structure.
>
>I'm not 100% certain that it doesn't rely on undefined behaviour though.[/color]
It does.
[color=blue]
>The weak spot is the pop() function, that needs to take a pointer to a
>pointer to the root node. The c-faq states (q: 4.9) that you can _not_
>rely on void ** as a generic pointer to pointer. However, this post (by
>Ben Pfaff in this group) seem to indicate that there _are_ uses of `void
>**' that are acceptable:
>
>
http://tinyurl.com/sbem [0]
>
>Therefore, I ask: is it okay to use `void **' for my use in this case?[/color]
There are indeed uses for "void **", but this is not one of them.
What "void **" can do is point to actual objects of type "void *".
There is a way to think about this that should generally get you
the right answer; I will get to that in a moment.
[color=blue]
>The argument is that I wouldn't be using it as a pointer to pointer to
>any type but for structures only.[/color]
In at least one actual implementation, "void *" (and "char *") are
"byte pointers", while all other pointers -- short *, int *, float *,
double *, and importantly, struct S * for any "S" -- are "word
pointers".
[color=blue]
>The standard (C89, A6.8) states that any pointer to an object can be
>converted to a pointer to void * and back. But can `void *' be thought
>of as an object on its own which can be pointer to?[/color]
Yes. But you must have an actual instance of such an object.
The way to think about this is:
- A cast always produces a conversion, as if by assignment to
a temporary. The only real differences between casting and
ordinary assignment (to just such a temporary) are that
(a) if you had an actual temporary, you could take its
address, and (b) casts involving pointers can remove the
requirement for, and usually the actual issuing of, diagnostic
messages in "dodgy cases".
- Ordinary assignment to or from "void *" variables also
produces a conversion.
The conversions you get when mixing "void *" and other pointer
types are, at least in principle, just like those you get when
converting between integral and floating-point types. On today's
typical 32-bit-integer 32-bit-IEEE-float machine, if you have:
int i;
float f;
then sizeof i == sizeof f, yet in operations like:
i = f; /* or */
f = i; /* after assigning values to them, of course */
nobody expects these to be simple "copy the bits" operations, at
least not after examining how floating-point works or looking at
the actual machine code produced by the compiler. (The machine
code involved may be a single "convert FP to int" or "convert int
to FP" instruction, or even a whole series of instructions, depending
on the CPU.) In any case, the change from something like 3.14159
(a float) to 3 (an int) actually changes the bit pattern in memory,
so that a memory-dump of the bits stored in "i" and those stored
in "f" look nothing alike. Moreover, doing:
i = f, f = i;
or even:
f = (int)f;
drops any digits past the decimal point, changing f from 3.14159
to 3.0. Clearly ordinary assignment is not a bitwise copy!
The key here is that, in the "C virtual machine" defined by the
standard, THE SAME THING HAPPENS WITH POINTERS. Changing "pointer
to T", for some type T, to "pointer to unspecified byte(s)" -- the
special "void *" thing in C -- is allowed to change the bits, even
when sizeof(T *) == sizeof(void *). On a few rare systems, it
really does change the bits. (On a few even-rarer systems, the
sizeof()s may even differ.)
Thus, if a routine takes a pointer to a "void *" object, you must
pass it the address of an actual "void *" object -- just as a
routine that takes a "float *" needs the address of an actual
float, not the address of an int cast to "float *". That is,
just as you would do:
result = set_a_float(&f);
i = f; /* we only want the integer part -- do a conversion
to discard the fractional part of f. */
you can do the equivalent with "void *" and other pointers:
struct S *x;
void *tmp;
result = set_a_voidstar(&tmp);
x = tmp; /* we know that the value in tmp is valid after conversion
(back) to "struct S *", so do the conversion. */
[color=blue]
>The alternative is to declare all functions to take/return a `struct
>mynode *' instead (and `struct mynode **' for the problematic pop()
>function).[/color]
There are other alternatives (although for my part, I think of
linked lists -- whether used as stacks or not -- as so simple that
you might as well just do them in line in many cases). One is the
one outlined above: have an actual temporary variable of type
"void *", pass its address, and convert the result stored in it.
Another is to return a structure containing two "void *"s:
struct list {
struct list *next;
};
struct uglyval {
void *head;
void *rest;
};
struct uglyval ugly(void *head) {
struct popval ret;
struct list *tmp;
tmp = head;
ret.head = tmp; /* or ret.head = head */
ret.rest = tmp->next;
return ret;
}
This second version illustrates the real problem with both
approaches, because now the stack-pop sequence goes from:
[color=blue]
> while ((p = pop((void **)&root))) {
> printf("p->val: %d\n", p->val);
> free(p);
> }[/color]
(where "p" and "root" are both "struct node1 *") to:
struct node1 *p, *root;
struct uglyval tmp;
...
for (;;) {
tmp = ugly(root);
if ((p = tmp.head) == NULL)
break;
root = tmp.rest;
printf("p->val: %d\n", p->val);
free(p);
}
and you might as well just inline the whole thing, giving:
while (root != NULL) {
p = root;
root = p->next;
...
}
getting rid of both the temporary and function ugly(). The
version with a single "void *" temporary is not QUITE as bad:
struct node1 *p, *root;
void *tmp;
...
while (tmp = root, p = pop(&tmp), root = tmp, p != NULL) {
...
}
which is just a comma-operator-ized variant of the ugly() loop.
We can do the same with ugly():
while (tmp = ugly(root), p = tmp.head, root = tmp.rest, p != NULL)
but the result remains, well, ugly. :-)
There is one last technique that uses the "all structure pointers
smell the same" idea that, comp.std.c folks assure us, is true even
though it is not literally spelled out in the C standard. This
method is horrible enough that I decided not to illustrate it after
all.
--
In-Real-Life: Chris Torek, Wind River Systems
Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
email: forget about it
http://67.40.109.61/torek/index.html (for the moment)
Reading email is like searching for food in the garbage, thanks to spammers.
