Jump to content
  • Advertisement
Sign in to follow this  
bah

Generic Linked List in C

This topic is 5029 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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
Advertisement
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 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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!