Generic list manipulation function in C?

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?

Answers


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++).


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

Need Your Help

Does HTTP/1.1 allow delimiting end of request by half-closing the connection?

http tcp half-close

RFC2616 part 4.4 specifies how the end of the message is determined in HTTP/1.1. Item 5 in that section specifies that the server may close the connection to indicate the response is finished.

Android: Keeping track of checked values in multi select dialog

android dialog multi-select

I have a button, on click of which i display a multi-select dialog. I load the dialog with values from the database. i wanna track the values in the dialog that are checked. How do i do that?? And ...

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.