I have two different linked lists that each use nodes of different structs.
However the principle of my adding to the linked lists and removing them is
the same. So will it work to have these functions accept a void pointer as
an argument for the list and a void pointer as an argument to a node like
this:
void add_to_tail(void * list, voic * new_node)
{
(list->tail)->next = new_node;
etc...
}
I have two different kinds of "nodes" (structs). Will assigning the void *
new_node to either kind of node automatically cast it to that kind of node
(struct)?
No, but you are in luck, at least with C99: C99 says that all
"struct S *" pointers (regardless of S) use the same representation.
(C89 does *not* say this but in practice it is true anyway.)
I am just thinking of ways to have one function that serves a generic
purpose to be used by different kinds of structs.
You *can* do this, but it requires a bit more work. For instance,
suppose "add_to_tail" works with a structure with two "struct S *"
objects (for some arbitrary structure type S) whose names might as
well be "head" and "tail":
struct S_Header {
struct S *head;
struct S *tail;
};
/* add the given new "struct S *" to the tail of the given list,
using the given S_Header. */
void add_to_tail_using_S_Header(struct S_Header *sh, struct S *new) {
if (sh->head == NULL)
sh->head = sh->tail = new;
else {
sh->tail->next = new;
sh->tail = new;
}
}
Of course, add_to_tail_using_S_Header() works only with an S_Header
and S, and you would like a variant that works regardless of what
the *name* of the two structures is -- and meanwhile we will hope
and pray that nobody calls the "genericized" add_to_tail() incorrectly:
/* "generic" version of add_to_tail_using_S_Header. */
void add_to_tail(void *sh0, void *new0) {
struct S_Header *sh;
struct S *new;
/* these two steps *are* required for portability */
sh = sh0;
new = new0;
/* the rest is as before */
if (sh->head == NULL)
sh->head = sh->tail = new;
else {
sh->tail->next = new;
sh->tail = new;
}
}
Note that the types "struct S_Header" and "struct S" are assumed
to exist here; if they do not already exist you can simply define
them within add_to_tail(). The "sh = sh0" and "new = new0"
assignments above are crucial on word-oriented machines (such as
the Data General Eclipse); these assignments may actually convert
from "byte pointers" (in "void *") to "word pointers".
You can then later have:
struct T_Header { struct T *head, *tail; };
struct T { struct T *next; ... };
struct T_header th;
...
struct T *new = new_t(...);
add_to_tail(&th, new_t);
and the C99 Standard's guarantee that "all struct pointers smell
the same" (as the saying goes) will -- presumably -- mean that the
only difference between a T_Header and T, and an S_Header and S,
is the type name, not any underlying representation in storage.
Thus, even if the call (inefficiently) converts the two word pointers
&th and new_t to byte pointers, just so that add_to_tail() can
convert them back from byte pointers to word pointers, it will
all work.
Unfortunately, an incorrect call like:
struct T *a, *b;
...
add_to_tail(a, b);
will *not* get a diagnostic (unless your compiler goes way beyond
the requirements of the standard, deep into the "telepathic" range
of "I sense what you really meant instead of what you wrote"
),
because "void *" is TOO compatible here. Ideally, what you would
really want is a way to say "the first parameter must be a pointer
to an object comprising two consecutive pointer objects of the same
type, both being `pointer to struct X' for some X, and the second
parameter must then be a `pointer to struct X' for the same X" --
but there is no way to do this in C.
If you have access to a BSD machine (or current BSD sources) you
might look at the BSD <sys/queue.h> macros. These achieve the
desired effect using compile-time macros that are fully type-checked
by any conforming C compiler.
