# Generic Linked List in C

## Recommended Posts

Hello, Is there a way to make a data structure in C, more specifically a doubly linked list, truly generic? My current implementation consists of the following modules(one source and one header file): 1. DataType_LinkedList 2. DataType_ListNode 3. DataType where "DataType" can be any name (i.e. Vertex, Texture, etc) When I want to write a list for a new data type, I simply make copies of the first two(2) modules, open them with a text editor and substitute my data type's name in the first part. Also, the data type I've selected must provide a minimum set of functions to interface with the DataType_ListNode such as a constructor, a destructor and a copy constructor. Does anyone know of a better solution?

##### Share on other sites
Quote:
 Original post by bahHello,Is there a way to make a data structure in C, more specifically a doubly linked list, truly generic?*** SNIPPED ***

Yes - do some research on template programming.

Here's a link to get you started

##### Share on other sites
maybe taking void* as a parameter but i don't know is the conversion would be safe or not.

i take it since you are using C that the constructor, copy constructor, and destructor are all actually procedural functions and not member functions.

##### Share on other sites
Quote:
Original post by DJHoy
Quote:
 Original post by bahIs there a way to make a data structure in C, more specifically a doubly linked list, truly generic?

Yes - do some research on template programming.

Here's a link to get you started
He said C.

OP, take a look at glib.

##### Share on other sites
The page for the linked list is at

and the source for the library at

http://cvs.gnome.org/viewcvs/glib/

I had look at the code, it's more or less like my implementation.

Thanks for the help

##### Share on other sites
If you want it to be type-safe, I suppose you could use some macro nastiness to do it
#define INSTANTIATE_LIST_TYPE(TYPE)              \     typedef struct                               \     {                                            \         ListNode_##TYPE* prev, next;             \         TYPE* item;                              \     } ListNode_##TYPE;#define INSTANTIATE_LIST_FUNCS(TYPE)             \                                                  \     ListNode_##TYPE* createList_##TYPE()         \     {                                            \         ListNode_##TYPE *head;                   \         head = (ListNode_##TYPE*)malloc(sizeof(ListNode_##TYPE)); \         head->next = head->next = NULL;          \     }

And so on for each list function. and then when you want to use it
INSTANTIATE_LIST_TYPE(Vertex)INSTANTIATE_LIST_FUNCS(Vertex)void func(){    ListNode_Vertex* vertices = createList_Vertex();}

Of course, you'd have to make sure you only every instantiated your list for a type once. You could place all the INSTANTIATE_LIST_TYPE() and INSTANTIATE_LIST_FUNCS() 'instantiations' in a single .h/.cpp pair.

##### Share on other sites
Quote:
 Original post by joanusdmentiaIf you want it to be type-safe, I suppose you could use some macro nastiness to do it*** Source Snippet Removed ***And so on for each list function. and then when you want to use it*** Source Snippet Removed ***Of course, you'd have to make sure you only every instantiated your list for a type once. You could place all the INSTANTIATE_LIST_TYPE() and INSTANTIATE_LIST_FUNCS() 'instantiations' in a single .h/.cpp pair.

You know how shitty to debug code like that is ?

##### Share on other sites
Quote:
 Original post by George2You know how shitty to debug code like that is ?

I did say macro nastiness [grin]

Actually, it's not *too* bad. Write it once with a fixed type, go nuts debugging it (hint: determine a thorough set of test cases before-hand) and then put it into the macros.

##### Share on other sites
The easiest way is to write a set of list fn()'s that manipulate data via callbacks.

//The api could looks something likenode *AddNode(){  yourdata_t *p = malloc(sizeof(yourdata_t));  // fill data .... p->????  return p;}void DelNode(void *node){  yourdata_t *p = (yourdata_t)node;  free(p->????);  // if you need to}InsertLL(AddNode);DeleteLL(DelNode);

You get the idea - its just list manipulation that uses callbacks (fn ptrs) to do the all the generic stuff.

If you want i could email you complete working code. You can then edit it at will for your requirements

##### Share on other sites
Quote:
 Original post by George2You know how shitty to debug code like that is ?

Yeah, just like debugging templated c++ code.

##### Share on other sites
Quote:
 Original post by leehairyThe easiest way is to write a set of list fn()'s that manipulate data via callbacks.

leehairy, I don't quite understand the concept and would be grateful if you posted a few code segments in this thread.

##### Share on other sites
Either macros or you be really crude and require the user to set a #define prior to including the header file.

#define LIST_DATA_TYPE int
#include "list.h"

##### Share on other sites
Quote:
 Original post by Magmai Kai HolmlorEither macros or you be really crude and require the user to set a #define prior to including the header file.#define LIST_DATA_TYPE int#include "list.h"

It's a shame you can't put pre-processor directives inside macros, then you could do have the following list.h
#define INSTANTIATE_LIST_TYPE(TYPE)  \     #define LIST_DATA_TYPE TYPE      \     #include "list_impl.h"           \     #undef LIST_DATA_TYPE#define INSTANTIATE_LIST_FUNCS(TYPE) \     #define LIST_DATA_TYPE TYPE      \     #include "list_impl.c"           \     #undef LIST_DATA_TYPE

##### Share on other sites
Er, what are you smoking that you want type-safety with C?

C is all about eschewing the type system. If you wish to program procedurally with type-safety, then use C++. And if you're going to use C++, might as well use templates.

##### Share on other sites
Quote:
 originally posted by Magmai Kai HolmlorEither macros or you be really crude and require the user to set a #define prior to including the header file.#define LIST_DATA_TYPE int#include "list.h"

Could you be more specific?

Quote:
 originally posted by antareusEr, what are you smoking that you want type-safety with C?C is all about eschewing the type system. If you wish to program procedurally with type-safety, then use C++. And if you're going to use C++, might as well use templates

Apart from being a tad offensive, you haven't contributed to the discussion.

I am simply investigating ways to make a data structure in C truly generic. That's all. If I used C++, then I could either write my own templatized data structures or use STL's.

Next time do read the initial post and all subsequent posts before replying.

##### Share on other sites
To the OP, check out hashlib at
it's a hashtable library that uses (if I remember correctly) callbacks to be generic.

Another technique is to use void pointers with a size_t variable to keep track of the element size (e.g. qsort(), bsearch()).

Yet another technique is to just slap the "next" pointer in the data structure.

Yet another technique is to create a set of macro's that do the work.

Which you use depends on what you intend to do.

Quote:
 Original post by antareusEr, what are you smoking that you want type-safety with C?C is all about eschewing the type system. If you wish to program procedurally with type-safety, then use C++. And if you're going to use C++, might as well use templates.

Antareus, I thought you knew better. That's inflamatory for no good reason. I also have my reservations about C++'s type system, but this isn't the thread for that.

##### Share on other sites
Quote:
Original post by bah
Quote:
 originally posted by Magmai Kai HolmlorEither macros or you be really crude and require the user to set a #define prior to including the header file.#define LIST_DATA_TYPE int#include "list.h"

Could you be more specific?

He's referring to your list.h being something like this:

#define LIST_NODE_TYPE ListNode_##LIST_DATA_TYPE#define LIST_FUNC(name) name##_##LIST_DATA_TYPEtypedef struct{    // ...} LIST_NODE_TYPE;LIST_NODE_TYPE* LIST_FUNC(createList)(){    // ...}// All your other list functions#undef LIST_NODE_TYPE#undef LIST_FUNC

##### Share on other sites
bah

Email me at mrpeg at hot mail dot com and i will send you some source code.

Put a descriptive subject line the email or it will be auto-deleted as junk

##### Share on other sites
I remember reading about a C linked list that was generic and type-safe without the use of any preprocessor directives, but now I have no clue where to find it, and I remember the code being incredibly horrifying.

Just thinking out loud here, the code my start with something like this
struct gen_type{   void* data;   int data_size;};struct node{   gen_type* here;   gen_type* next;};node* make_node(void* dat, int sz){   node* cur_node = malloc(sizeof(node));   gen_type* ptr = malloc(sizeof(gen_type));   node->here = ptr;   return cur_node;}//and then, to use make_nodeint some_data = 314159;float other_data = 3.14159;node* ptr_inode = make_node((void*)(&some_data), sizeof(int));node* ptr_fnode = make_node((void*)(&other_data), sizeof(float));

##### Share on other sites
Wow, I'm an ass sometimes.

midnight: How would they do it in a typesafe way without the preprocessor? I thought void* was the extent of generic-ness for C. (Thats what I was stabbing at however brusquely earlier. Well, that and the fact that type safety isn't a strength of C.)

For a big project one could look at code generators to do this sort of thing for you.

##### Share on other sites
Quote:
 Original post by antareusWow, I'm an ass sometimes.midnight: How would they do it in a typesafe way without the preprocessor? I thought void* was the extent of generic-ness for C. (Thats what I was stabbing at however brusquely earlier. Well, that and the fact that type safety isn't a strength of C.) For a big project one could look at code generators to do this sort of thing for you.
I don't remember much from the article.

##### Share on other sites
I don't think you can enforce typesafety in C. antareus is correct, void* is the most generic type you can ever have.
typedef{   void* data;   Node* prev;   Node* next;} Node;typedef{   Node* front;   Node* back;} LinkedList;

If you want to create a linked list of int, then do something like:
Node* newnode = malloc( sizeof(Node) );int var = 10;newnode->data = (void*)&var;  // ornewnode->data = malloc( sizeof(int) );newnode->prev = 0;newnode->next = 0;LinkedList intLL;intLL.front = newnode;

Everything just have done via pointers and typecasting everything.
If you want to automate the process, then you can create a function that generates a node:

Node* genNode( int type_size )
{
Node* newnode = malloc( sizeof(Node) );
newnode->data = malloc( type_size );
newnode->prev = 0;
newnode->next = 0;

return newnode;
}

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628330
• Total Posts
2982112

• 22
• 9
• 9
• 13
• 11