general use struct

[cs32]

I'd like to create a general, type agnostic Node structure that will be used to represent a node in a linked list. The idea with this is to be able to define the node value as an arbitrary type.

Example:

typedef struct Node {
	<arbitrary type> item;
	struct Node *next;
} node;

How do I define my struct in a manner that would allow me to do this? Would I define <arbitrary type> as type void *, or is there a better way to represent a type that would be determined at implementation time, and not restrict the node item type to a certain type (i.e. an int)?

[Salem]

Well using void* is one way, but that relies on an additional allocation, which would be wasteful for small items such as int.

Or you could do something like

typedef struct {
    struct Node *next;
    // more
} data1;
typedef struct {
    struct Node *next;
    // more
} data2;

Where you assume that the linked list node is right at the start of any struct needing to be on a linked list. But then you get into all sorts of casting hackery to make it all work. Plus, if you need two lists, the whole idea is sunk.

There isn't a good way in C which is good for all cases.

[whiteflags]

You could look for and use a third party C list library. A lot of people come up with interesting solutions to this need. One which I remember was gluing together an implementation which relied on macros to define the type for the data inside.

[cs32]

Well using void* is one way, but that relies on an additional allocation, which would be wasteful for small items such as int.

How much of an additional allocation are we talking about here?

[Salem]

Depends on your implementation.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int *p1, *p2, *p3;
    p1 = malloc( sizeof(int) );
    p2 = malloc( sizeof(int) );
    p3 = malloc( sizeof(int) );
    printf( "&#37;p %p %p\n", (void*)p1, (void*)p2, (void*)p3 );
    return 0;
}

$ gcc -W -Wall -ansi -pedantic foo.c
$ ./a.exe
0x660160 0x660170 0x660180

> cl /nologo foo.c
foo.c

> foo.exe
00320758 00320770 00320788

16 for cygwin/gcc, 24 for VC6.

The amount allocated is can be aligned to some boundary.
There is also the memory pool management overhead which keeps track of all the blocks.