Creating and using generic methods in C

Question

I wrote a Linked List ADT for a class I am in originally for a list of ints. Now I am going to use the same list for chars and ints. I know how to rewrite the code for chars to just have basically two List ADTs, one for the ints and the other for the chars.

I don't want to do that however, I want to write it for a generic variable so that in the future I can use this ADT with other code without worrying about types to much.

Initially I went into this with void*, but I am running into an error with it that I am just have a hard time understanding how to fix.

 typedef struct NodePtr {

void* data; 
struct NodePtr*next;
struct NodePtr*prev;
} NodePtr;

typedef struct ListStruct {

NodePtr* first;
NodePtr* last;
NodePtr* current;
} ListStruct;

Then some other code and fun stuff, and then my insert method to insert at the front of the list:

void insert(listhndl L, void* data)
{
 ...inserting of the node here.
}

This code throws no error, but then when I run a driver to test it:

 ListHndl test = NULL;
  test = newList();
  insert(test, 1);

I get the error message:

 warning: passing argument 2 of 'insert' makes pointer from integer without a cast [enabled by default]
   insert(test, 1);
   ^
     error: expected 'void *' but argument is of type 'int'
 void insert(ListHndl L, void* data);

I am confused here because how can it throw an error saying it's not the type it expected, if void* is a generic type?

What am I doing wrong?

I saw on here some people recommend using enum and unions for generics instead of void*, but I could not get that to work ether as I don't really understand what to do with them. If somebody wanted to also answer how to do generics with the enums/unions method I would greatly appreciate it.

Answer 1

Your list addition parameter is a void* so naturally you'll be flagged with an implicit conversion warning (or error if you're compiling with -Wall -Werror like you should be). Generic implementations of any node management algorithms isn' a trivial as it may seem, and much has been written/coded on the subject.

In your case, you could dynamically allocate the data being added yourself (i.e. allocate an int and send the resulting address as the void*, or create additional parameterization of your list interface functions and make them smart enough to figure out what to allocate (if anything)

In general, a generic linked list is eventually not going to escape ownership and sizing information if you're planning on using pointers (and all of the samples linked below go to some lengths to accommodate this). An elaborate enough interface capable of constituting this information into a reasonable node architecture that is generic enough is tedious, but that is the price you pay for generics. Performance is likewise a factor, and again, pay the piper. Type information for a list that holds different data types may also be a consideration, in particular if you're inclined in your algorithms to minimize memory management usage.

There are a multitude of generic linked lists sourced all over this grand illusion we call the World Wide Web. Here are a few such implementations:

• PseudoMuto Generic Linked List : Assumes all items are the same size, maintains dynamic storage to them via internal memory management.

• CMU Generic Linked List: lecture notes on generics development.

• Uncredited Generic List (circa 1999): Another fixed size dynamically managed linked list. Not particularly impressive, but at least functional.

• Atachil's Generic Linked List: Yet another generic implementation, this one implemented as a double-linked list.

• Plenty more where that came from (google and 10 minutes of filtering out junk).

---

You needn't reinvent the wheel, but if you want to there are plenty of examples out there that can assist you. A challenge would be implementing a list that

• Takes user-provided allocation/deallocation functions for any memory management requirements
• Uses a union internal to the list_node that supports all the fundamental data types as well as a void* and size_t for blob or string data, and of course, a type-identifier so you know what member is the member.
• Provides dynamic ownership semantics (i.e. allows the client to specify a dynamic node pointer is "owned" by the client and to not store a duplicate; just use the provided data pointer.
• Bi-directional management (i.e. a double linked list)

Just a few things to consider when embarking on your quest. I wish you the best of luck.

Answer 2

You can make the type of data to be handled more opaque by encapsulating it into a typedef:

typedef struct my_opaque_data {
      int item;      /* example opaque data */
} DATA;


struct NodePtr {
     DATA data; 
     struct NodePtr *next, *prev;
 } NodePtr;

So far, all I have done is replace void * with DATA.

Then you will probably want to declare some basic operations to be implemented elsewhere to handle the type:

 extern int data_compare (const DATA *left, const DATA *right); /* return < 0 if left < 0, 0 if equal, etc. */
 extern void data_set (DATA *dest, const DATA *src);   /* *dest = *src */
 extern void data_swap (DATA *d1, DATA *d2); /* exchange *d1 and *d2 */
 extern size_t data_size (const DATA *d);    /* return size (bytes) of *d */
 ...

Each of these is almost certainly trivial to implement, but by substituting different data types, even complex data types, in DATA, the source code can remain complete generic and oblivious to what is in DATA. With this one could easily implement list operations, sorting, searching, etc., etc.