void pointers

[John Hanley]

I working in C. I haven't paid much attention to void pointers in the past,
but I am wondering if I can use them for my various linked lists to save
work.

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)?

I am just thinking of ways to have one function that serves a generic
purpose to be used by different kinds of structs. If this was C++ or Java,
it wouldn't be much of a problem.

Ideas?

Thanks again!

John

[Emmanuel Delahaye]

John Hanley wrote on 01/08/04 :

> I working in C. I haven't paid much attention to void pointers in the past,
> but I am wondering if I can use them for my various linked lists to save
> work.

Yes, void pointers are useful for generic programming. OTOH, the
programmer must exactly know what is he doing, because the compiler
doesn't check the types anymore.

It is highly recommended that the user is kept away from such gory
details. Abstraction is not a option.

--
Emmanuel
The C-FAQ: http://www.eskimo.com/~scs/C-faq/faq.html

"C is a sharp tool"

[Chris Torek]

In article <10913322...@proxy2.srv.ualberta.ca>

John Hanley <jdha...@telusplanet.net> writes:
>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.
--
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://web.torek.net/torek/index.html
Reading email is like searching for food in the garbage, thanks to spammers.

[Malcolm]

"John Hanley" <jdha...@telusplanet.net> wrote

As you say, C++ has a template mechanism that offers compile-time binding by
name. Thus the same code can operate on two unrelated structs that happen to
have a member called "next".

void * is useful for creating generic functions, but it is not as powerful
as C++ templates. Generally you use void * for passing data of an unknown
type

eg struct linkedlistnode
{
struct linkedlistnode *prev;
struct linkedlistnode *next;
void *data;
};

would be a generic node, but you would have to know the size and layout of
the data pointed to by the last member in other areas of the program.

[Stig Brautaset]

John Hanley <jdha...@telusplanet.net> wrote:
> 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.

Have a look at http://brautaset.org/projects/sl/ for an example
implementation of generic linked lists using void pointers. It exploits
the notion that one struct pointer smells like another, even though the
structs might be different.

Additionally, instead of using container nodes with pointers to your
data it uses a pointer to the next item directly in the datastructure
you want to create lists (or stacks) of. In addition to significant
memory savings, this allows for very fast push and pop operations since
there is no need to allocate/free memory for the container nodes. It
also means that a push can't fail because memory couldn't be allocated
for the container node.

PS: thanks to all the people here on comp.lang.c that helped me get the
understanding that enabled me to write the above mentioned library.

Stig

[pete]

John Hanley wrote:
>
> I working in C. I haven't paid much attention to
> void pointers in the past,
> but I am wondering if I can use them for my
> various linked lists to save work.
>
> 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.

I wind up writing nearly identical functions when working
with list of different type nodes.
Sometimes, things, like concatenation of lists, are exactly the same.

void cl_cat(cn_type *head, cn_type *tail)
{
cn_type *old;

if (head != NULL) {
do {
old = head;
head = head -> c_NEXT;
} while (head != NULL);
old -> c_NEXT = tail;
}
}

void pl_cat(pn_type *head, pn_type *tail)
{
pn_type *old;

if (head != NULL) {
do {
old = head;
head = head -> p_NEXT;
} while (head != NULL);
old -> p_NEXT = tail;
}
}

Sometimes, things, like freeing the lists, aren't exactly the same.

void pl_free(pn_type *node)
{
pn_type *next;

while (node != NULL) {
next = node -> p_NEXT;
free(node);
node = next;
}
}

void cl_free(cn_type *node)
{
cn_type *next;

while (node != NULL) {
pl_free(node -> car.part_list);
next = node -> c_NEXT;
free(node);
node = next;
}
}

--
pete

[CBFalconer]

pete wrote:
> John Hanley wrote:
>>
>> I working in C. I haven't paid much attention to void pointers
>> in the past, but I am wondering if I can use them for my
>> various linked lists to save work.
>>
>> 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.
>
> I wind up writing nearly identical functions when working
> with list of different type nodes. Sometimes, things, like
> concatenation of lists, are exactly the same.

Define the essence of a singly linked list with:

typedef struct slinklist {
struct slinklist *next;
void *data;
} slinklist;

and similarly for a doubly linked list:

typedef struct dlinklist {
struct dlinklist *next, *prev;
void *data;
} dlinklist;

Now you can write universal functions to do the list
manipulations, and functions to handle the list data that are
customized to that data.

whatever dataop(void *data, otherparams)
{
datatype datap = data;

/* code as needed, using the well typed datap */
}

and call it with:

dataop(mylistitem->data, otherparams);

--
"I'm a war president. I make decisions here in the Oval Office
in foreign policy matters with war on my mind." - Bush.
"Churchill and Bush can both be considered wartime leaders, just
as Secretariat and Mr Ed were both horses." - James Rhodes.

[pete]

That's interesting. I'll look into it.

--
pete

[Mark F. Haigh]

Chris Torek wrote:
<snip>

>
> 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.)
>

In C99, they have the same representation. In C89, they may not, but
they sure do smell alike!

:-)

Mark F. Haigh
mfh...@sbcglobal.net