Sign in to follow this  
bah

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 this post


Link to post
Share on other sites
The page for the linked list is at
http://developer.gnome.org/doc/API/2.0/glib/glib-Doubly-Linked-Lists.html

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by joanusdmentia
If 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 this post


Link to post
Share on other sites
Quote:
Original post by George2
You 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 this post


Link to post
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 like

node *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 this post


Link to post
Share on other sites
Guest Anonymous Poster
Quote:
Original post by George2
You know how shitty to debug code like that is ?


Yeah, just like debugging templated c++ code.

Share this post


Link to post
Share on other sites
Quote:
Original post by leehairy
The 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 this post


Link to post
Share on other sites
Quote:
Original post by Magmai Kai Holmlor
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"

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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
originally posted by Magmai Kai Holmlor
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"


Could you be more specific?

Quote:
originally posted by antareus
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


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 this post


Link to post
Share on other sites
To the OP, check out hashlib at
http://cbfalconer.home.att.net/download/
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 antareus
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.


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 this post


Link to post
Share on other sites
Quote:
Original post by bah
Quote:
originally posted by Magmai Kai Holmlor
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"


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_TYPE

typedef struct
{
// ...
} LIST_NODE_TYPE;

LIST_NODE_TYPE* LIST_FUNC(createList)()
{
// ...
}

// All your other list functions

#undef LIST_NODE_TYPE
#undef LIST_FUNC

Share this post


Link to post
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_node
int 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 this post


Link to post
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 this post


Link to post
Share on other sites
Quote:
Original post by antareus
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.
I don't remember much from the article.

Share this post


Link to post
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; // or
newnode->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;
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this