Modular data structure in C with dynamic data type

问题:

For my upcoming university C project, I'm requested to have modular code as C allows it. Basically, I'll have .c file and a corresponding .h file for some data structure, like a linked list, binary tree, hash table, whatever...

Using a linked list as an example, I have this:

typedef struct sLinkedList {
    int value;
    struct sLinkedList *next;
} List;

But this forces value to be of type int and the user using this linked list library would be forced to directly change the source code of the library. I want to avoid that, I want to avoid the need to change the library, to make the code as modular as possible.

My project may need to use a linked list for a list of integers, or maybe a list of some structure. But I'm not going to duplicate the library files/code and change the code accordingly.

How can I solve this?

回答1:

Unfortunately, there is no simple way to solve this. The most common, pure C approach to this type of situation is to use a void*, and to copy the value into memory allocated by you into the pointer. This makes usage tricky, though, and is very error prone.

回答2:

Another alternative no one has mentioned yet can be found in the Linux kernel's list.h generic linked list implementation. The principle is this:

/* generic definition */
struct list {
  strict list *next, *prev;
};

// some more code

/* specific version */
struct intlist {
  struct list list;
  int i;
};

If you make struct intlist* pointers, they can safely be cast (in C) to struct list* pointers, thus allowing you to write genericized functions that operate on struct list* and have them work regardless of datatype.

The list.h implementation uses some macro trickery to support arbitrary placement of the struct list inside your specific list, but I prefer to rely on the struct-cast-to-first-member trick myself. It makes the calling code much easier to read. Granted, it disables "multiple inheritance" (assuming you consider this to be some kind of inheritance) but next(mylist) looks nicer than next(mylist, list). Plus, if you can avoid delving into offsetof hackery, you're probably going to end up in better shape.

回答3:

Since this is a university project, we can't just give you the answer. Instead, I'd invite you to meditate on two C features: the void pointer (which you've likely encountered before), and the token pasting operator (which you may not have).

回答4:

You can avoid this by defining value as void* value;. You can assign a pointer to any type of data this way, but the calling code is required to cast and dereference the pointer to the correct type. One way to keep track of this would be to add a short char array to the struct to note the type name.

回答5:

This problem is precisely the reason why templates were developed for C++. The approach I've used once or twice in C is to have the value field be a void*, and cast the values thereto on insertion and cast them back on retrieval. This is far from type-safe, of course. For extra modularity, I might write insert_int(), get_mystruct() etc. functions for each type you use this for, and do the casting there.

回答6:

You can use Void* instead of int. This allows the data to be of any type. But the user should be aware of the type of data.

For that, optionally you can have another member which represents Type. which is of enum {INT,CHAR,float...}

回答7:

Unlike C++ where one can use template, void * is the de-facto C solution.

Also, you can put the elements of the linked list in a separate struct, e.g:

typedef struct sLinkedListElem {
    int value; /* or "void * value" */
} ListElem;

typedef struct sLinkedList {
    ListElem data;
    struct sLinkedList *next;
} List;

so that the elements can be changed without affecting the link-ing code.

回答8:

Here is an example of linked list utilities in C:

struct Single_List_Node
{
    struct Single_List * p_next;
    void *               p_data;
};

struct Double_List_Node
{
    struct Double_List *    p_next;
    struct Double_List *    p_prev; // pointer to previous node
    void *                  p_data;
};

struct Single_List_Data_Type
{
    size_t                         size; // Number of elements in list
    struct Single_List_Node *      p_first_node;
    struct Single_List_Node *      p_last_node; // To make appending faster.
};

Some generic functions:

void    Single_List_Create(struct Single_List_Data_Type * p_list)
{
    if (p_list)
    {
        p_list->size = 0;
        p_list->first_node = 0;
        p_list->last_node = p_list->first_node;
    }
    return;
}


void    Single_List_Append(struct Single_List_Data_Type *   p_list,
                           void *                           p_data)
{
    if (p_list)
    {
        struct Single_List_Node * p_new_node = malloc(sizeof(struct Single_List_Node));
        if (p_new_node)
        {
            p_new_node->p_data = p_data;
            p_new_node->p_next = 0;
            if (p_list->last_node)
            {
                p_list->last_node->p_next = p_new_node;
            }
            else
            {
                if (p_list->first_node == 0)
                {
                    p_list->first_node = p_new_node;
                    p_list->last_node = p_new_node;
                }
                else
                {
                    struct Single_List_Node * p_last_node = 0;
                    p_last_node = p_list->first_node;
                    while (p_last_node->p_next)
                    {
                        p_last_node = p_last_node->p_next;
                    }
                    p_list->last_node->p_next = p_new_node;
                    p_list->last_node = p_new_node;
                }
            }
            ++(p_list->size);
        }
    }
    return;
}

You can put all these functions into a single source file and the function declarations into a header file. This will allow you to use the functions with other programs and not have to recompile all the time. The void * for the pointer to data will allow you to use the list with many different data types.

(The above code comes as-is and has not been tested with any compiler. The responsibility of bug fixing is up to the user of the examples.)