Generic list manipulation function in C?

Question

What is a generic list manipulation function in C? (I saw this when I was going through some materials.)

What is the difference between this function and a function which can accept elements of any kind?

Are they same...? How can we implement them individually if they are not same?

Answer 1

A generic list is likely to be singly-linked, and probably assumes that the items in the list have a structure like this:

typedef struct list_item list_item;

struct list_item
{
    list_item *next;
    ...data for node...
};

Using this layout, you can write functions to manipulate lists using just the next pointers.

Sometimes, the '...data for node...' will be a simple 'void *'; that is, the list items will contain pointers to the next node in the list (or NULL if there is no next node) and pointers to the data.

typedef struct list list;

struct list
{
    list *next;
    void *data;
};

Since you can cast any pointer to 'void *', you can have any mix of data types in the list - but your code must know how to handle them.

You ask about 'a' generic list function, but there probably isn't a single one-function-does-all design, and certainly not a simple one. There are a number of possible sets of functions that could make generic list functions. One set, inspired by Lisp, would consist of:

void *car(list *lp);    // Return the data for the first item on the list
list *cdr(list *lp);    // Return the tail of the list
list *cons(list *lp1, list *lp2);   // Construct a list from lists lp1 and lp2

list *cond(list *lp, void *data);  // Append data item to list

You probably want to provide the ability to test whether the list is empty, and a few other items.

One good exposition, admittedly in C++, is found in Koenig's "Ruminations on C++". The ideas can be adapted into C quite easily - it isn't dreadfully hard (though the storage management in C is harder than in C++).

Answer 2

C has no concept of "generic" pointers or objects - the closest you can get is using a void* pointer. If you want one piece of code to be able to handle any data type, you pretty much have to use void* pointers. For data types with sizes no larger than a pointer, you can cast between the type and void*; for larger data types, you'll have to use dynamic memory and have the void* member point to the dynamic memory. Just watch out for memory leaks!

typedef struct list_node {
  struct list_node *next;
  void *data;
} list_node;

void list_insert(list_node *node, void *data) {
  // ...
}

On the other hand, if you want to generate code for each possible data type, you'll have to do it with macros, and then instantiate the macros for each data type you might use. For example:

#define DEFINE_LIST(type) \
  typedef struct list_node_##type { \
    struct list_node_##type *next; \
    type data; \
  }

#define IMPLEMENT_LIST_INSERT(type) \
  void list_##type##_insert(list_node_##type *node, type data) { \
    ... \
  }

DEFINE_LIST(int);     // defines struct list_node_int
DEFINE_LIST(double);  // defines struct list_node_double
IMPLEMENT_LIST_INSERT(int);    // defines list_int_insert
IMPLEMENT_LIST_INSERT(double); // defines list_double_insert

Answer 3

The Linux kernel has an interesting implementation of a generic linked list in C on its linux/list.h header. It is a doubly-linked list with a head node, used like this:

struct mystruct {
    ...
    /* Contains the next and prev pointers */
    struct list_head mylist;
    ...
    /* A single struct can be in several lists */
    struct list_head another_list;
    ...
};

struct list_head mylist_head;
struct list_head another_list_head;

Some interesting things in this small example:

• The list node is embedded within the target struct, needing no data pointer.
• The list node does not have to come at the beginning of the target struct.
• A single struct can be in several linked lists at the same time.
• The next and prev pointers within the list point to the struct list_head, not to the target structure (on the example above, they point to &(foo->mylist) for the first list and &(foo->another_list) for the second list).

All the list manipulation functions take pointers to struct list_head (and most do not care at all whether it is the separate head node or one of the embedded nodes). To get from the struct list_head to the target struct, you use the list_entry macro (which is the same as the containter_of macro from the linux/kernel.h header), which expands into a simple pointer subtraction.

Since it is a doubly-linked list with a head node, you can in O(1):

• Check if the list is empty, or if a node is not on any list.
• Get the node after or before any other node (if the node is the head, you get the first or last element of the list).
• Insert a node after or before any other node (if the node is the head, you insert at the beginning or end of the list).
• Remove a node from the list (you need only the pointer to the node itself to do this).
• Several other operations.

Answer 4

C and its standard library don't offer any list specific functions.

But there are libraries with many useful functions for C that support data types known from other programming languages: http://library.gnome.org/devel/glib/2.18/glib-data-types.html