'Multipurpose' linked list implementation in pure C

Question

This is not exactly a technical question, since I know C kind of enough to do the things I need to (I mean, in terms of not 'letting the language get in your way'), so this question is basically a 'what direction to take' question.

Situation is: I am currently taking an advanced algorithms course, and for the sake of 'growing up as programmers', I am required to use pure C to implement the practical assignments (it works well: pretty much any small mistake you make actually forces you to understand completely what you're doing in order to fix it). In the course of implementing, I obviously run into the problem of having to implement the 'basic' data structures from the ground up: actually not only linked lists, but also stacks, trees, et cetera.

I am focusing on lists in this topic because it's typically a structure I end up using a lot in the program, either as a 'main' structure or as a 'helper' structure for other bigger ones (for example, a hash tree that resolves conflicts by using a linked list).

This requires that the list stores elements of lots of different types. I am assuming here as a premise that I don't want to re-code the list for every type. So, I can come up with these alternatives:

• Making a list of void pointers (kinda inelegant; harder to debug)
• Making only one list, but having a union as 'element type', containing all element types I will use in the program (easier to debug; wastes space if elements are not all the same size)
• Using a preprocessor macro to regenerate the code for every type, in the style of SGLIB, 'imitating' C++'s STL (creative solution; doesn't waste space; elements have the explicit type they actually are when they are returned; any change in list code can be really dramatic)
• Your idea/solution

To make the question clear: which one of the above is best?

PS: Since I am basically in an academic context, I am also very interested in the view of people working with pure C out there in the industry. I understand that most pure C programmers are in the embedded devices area, where I don't think this kind of problem I am facing is common. However, if anyone out there knows how it's done 'in the real world', I would be very interested in your opinion.

Answer 1

A void * is a bit of a pain in a linked list since you have to manage it's allocation separately to the list itself. One approach I've used in the past is to have a 'variable sized' structure like:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

Now I realize that doesn't look variable sized but let's allocate a structure thus:

typedef struct {
    char Name[30];
    char Addr[50];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

Now you have a node that, for all intents and purposes, looks like this:

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

or, in graphical form (where [n] means n bytes):

+----------------+
|    prev[4]     |
+----------------+
|    next[4]     |
+----------------+
| payloadType[4] |                
+----------------+                +----------+
|   payload[1]   | <- overlap ->  | Name[30] |
+----------------+                +----------+
                                  | Addr[50] |
                                  +----------+

That is, assuming you know how to address the payload correctly. This can be done as follows:

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

That cast line simply casts the address of the payload character (in the tNode type) to be an address of the actual tPerson payload type.

Using this method, you can carry any payload type you want in a node, even different payload types in each node, without the wasted space of a union. This wastage can be seen with the following:

union {
    int x;
    char y[100];
} u;

where 96 bytes are wasted every time you store an integer type in the list (for a 4-byte integer).

The payload type in the tNode allows you to easily detect what type of payload this node is carrying, so your code can decide how to process it. You can use something along the lines of:

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

or (probably better):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

Answer 2

My $.002:

• Making a list of void pointers (kinda diselegant; harder to debug)

This isn't such a bad choice, IMHO, if you must write in C. You might add API methods to allow the application to supply a print() method for ease of debugging. Similar methods could be invoked when (e.g.) items get added to or removed from the list. (For linked lists, this is usually not necessary, but for more complex data structures -- hash tables, for example) -- it can sometimes be a lifesaver.)

• Making only one list, but having a union as 'element type', containing all element types I will use in the program (easier to debug; wastes space if elements are not all the same size)

I would avoid this like the plague. (Well, you did ask.) Having a manually-configured, compile-time dependency from the data structure to its contained types is the worst of all worlds. Again, IMHO.

• Using a preprocessor macro to regenerate the code for every type, in the style of SGLIB (sglib.sourceforge.net), 'imitating' C++'s STL (creative solution; doesn't waste space; elements have the explicit type they actually are when they are returned; any change in list code can be really dramatic)

Intriguing idea, but since I don't know SGLIB, I can't say much more than that.

• Your idea/solution

I'd go with the first choice.

Answer 3

I've done this in the past, in our code (which has since been converted to C++), and at the time, decided on the void* approach. I just did this for flexibility - we were almost always storing a pointer in the list anyways, and the simplicity of the solution, and usability of it outweighed (for me) the downsides to the other approaches.

That being said, there was one time where it caused some nasty bug that was difficult to debug, so it's definitely not a perfect solution. I think it's still the one I'd take, though, if I was doing this again now.

Answer 4

Using a preprocessor macro is the best option. The Linux kernel linked list is a excellent a eficient implementation of a circularly-linked list in C. Is very portable and easy to use. Here a standalone version of linux kernel 2.6.29 list.h header.

The FreeBSD/OpenBSD sys/queue is another good option for a generic macro based linked list

Answer 5

I haven't coded C in years but GLib claims to provide "a large set of utility functions for strings and common data structures", among which are linked lists.

Answer 6

Although It's tempting to think about solving this kind of problem using the techniques of another language, say, generics, in practice it's rarely a win. There are probably some canned solutions that get it right most of the time (and tell you in their documentation when they get it wrong), using that might miss the point of the assignment, So i'd think twice about it. For a very few number of cases, It might be feasable to roll your own, but for a project of any reasonable size, Its not likely to be worth the debugging effort.

Rather, When programming in language x, you should use the idioms of language x. Don't write java when you're using python. Don't write C when you're using scheme. Don't write C++ when you're using C99.

Myself, I'd probably end up using something like Pax's suggestion, but actually use a union of char[1] and void* and int, to make the common cases convenient (and an enumed type flag)

(I'd also probably end up implementing a fibonacci tree, just cause that sounds neat, and you can only implement RB Trees so many times before it loses it's flavor, even if that is better for the common cases it'd be used for.)

edit: based on your comment, it looks like you've got a pretty good case for using a canned solution. If your instructor allows it, and the syntax it offers feels comfortable, give it a whirl.

Answer 7

This is a good problem. There are two solutions I like:

• Dave Hanson's C Interfaces and Implementations uses a list of void * pointers, which is good enough for me.

• For my students, I wrote an awk script to generate type-specific list functions. Compared to preprocessor macros, it requires an extra build step, but the operation of the system is much more transparent to programmers without a lot of experience. And it really helps make the case for parametric polymorphism, which they see later in their curriculum.

  Here's what one set of functions looks like:

  int      lengthEL (Explist *l);
  Exp*     nthEL    (Explist *l, unsigned n);
  Explist *mkEL     (Exp *hd, Explist *tl);
  

  The awk script is a 150-line horror; it searches C code for typedefs and generates a set of list functions for each one. It's very old; I could probably do better now :-)

I wouldn't give a list of unions the time of day (or space on my hard drive). It's not safe, and it's not extensible, so you may as well just use void * and be done with it.

Answer 8

One improvement over making it a list of void* would be making it a list of structs that contain a void* and some meta-data about what the void* points to, including its type, size, etc.

Other ideas: embed a Perl or Lisp interpreter.

Or go halfway: link with the Perl library and make it a list of Perl SVs or something.

Answer 9

I'd probably go with the void* approach myself, but it occurred to me that you could store your data as XML. Then the list can just have a char* for data (which you would parse on demand for whatever sub elements you need)....