<template> replacement for C linkedList

Question

Hi All

Just finished small linked list in C, and realized that I got a problem :) There is no template arguments for C, so at the start of the file I declaring my data type for list, something like:

typedef int LData; So far so good, but I cant use this Linked list for 2(or more) different data types in one program.

I can define LData as void* and manually convert it to specific datatype according to context. But I wonder if there are more elegant solutions?

Thanks a lot

Answer 1

The union was invented for this purpose, although it is not a very safe construct.

Answer 2

Or, use the opaque pointer idiom:

struct datum;
typedef struct datum datum;
typedef datum *LData;

struct datum {
   int whatever;
};

Answer 3

You could have a bunch of #defines defining the type stored in the "link"?

ie.

 #define TYPE_INT   0
 #define TYPE_FLOAT 1
 // etc

Then define each entry as something like this:

 struct LinkedListLink
 {
      int    type;
      LData  data;
 };

Now by checking "type" you know what sort of data was added (Provided you set it appropriately when you set up the LinkedListLink struct).

Answer 4

Define your LData type as a void*. The user of the linked list has to know what sort of data it contains, so they can cast to and from void* whenever they're pulling data in or out.

Answer 5

Thanks

But how its going to work with getters. ?

LData* getElementAt(LinkedList* list, int n);

Answer 6

When I want to use a generalized set of linked list (or in my case, queue) code, I embed the linked list pointer inside the larger structure that I want to use it with. Then use the link field name when passing arguments to the linked list functions. And have a function that can convert from a linked list pointer to the larger struct pointer for when I get pointers back from my linked list. Something like the code you see below.

This idiom doesn't give you the type safety of C++, but the code is pretty clean, with the casting is localized into just a few functions.

// some representative bits of my linked list API
//
typedef void* PLINK;

extern PLINK LLAddToList(PLINK head, PLINK new);
extern PLINK LLNextItem(PLINK current); 

// the structure I want to use it with

typedef struct _foo {
   PLINK  pLink;
   int    data1; 
   int    data2;
} FOO;

// to allow for the link pointers to be some other than the first field
// we use this to go from link pointer to structure pointer.
FOO * FooFromPLink(PLINK current) {
    return (FOO *)((char *)&current - FIELD_OFFSET(FOO, pLink));
}

void MyFunction()
{
   // this idiom to use the linklist code with a FOO struct
   //
   FOO * pfoo = // allocate and initialize a foo
   LLAddToList(head, &pfoo->pLink);


   // this idiom to traverse a list of FOOs, etc.
   //
   PLINK next = LLNextItem(head);
   while (next)
      {
      pfoo = FooFromPLink(next);
      // operate on foo.
      next = LLNextItem(next);
      }

}