Modular data structure in C with dynamic data type

Question

For my upcoming C university project, I am invited to have a modular code that allows C. In principle, I will have a .c file and a corresponding .h file for some data structure, such as a linked list, binary tree, hash table, whatever .. .

Using the linked list as an example, I have the following:

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

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

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

How can i solve this?

Answer 1

Unfortunately, there is no easy way to solve this problem. The most common, clean C approach to this type of situation is to use void* and copy the value into the memory you allocated to the pointer. This makes use difficult, although very error prone.

Answer 2

Another alternative that no one has mentioned can be found in the Linux kernel list.h implementation of a common list of links. The principle is as follows:

 /* generic definition */ struct list { strict list *next, *prev; }; // some more code /* specific version */ struct intlist { struct list list; int i; }; 

If you create struct intlist* pointers, you can safely map them (from C) to struct list* pointers, which allows you to write generic functions that work on struct list* and make them work regardless of the data type.

The implementation of list.h uses some macro trickery to support the arbitrary placement of a struct list inside your specific list, but I prefer to rely on the trick struct-cast-to-first-member. This makes the calling code a lot easier to read. Of course, this disables "multiple inheritance" (if you consider this a kind of inheritance), but next(mylist) looks better than next(mylist, list) . Also, if you can't get into the offsetof hacking, you'll probably be in better shape.

Answer 3

Since this is a university project, we cannot just give you an answer. Instead, I invite you to reflect on two C functions: the void pointer (which you most likely have seen before), and the token labeling operator (which you may not have).

Answer 4

You can avoid this by specifying the value as void* value; . Thus, you can assign a pointer to any data type, but the calling code is necessary in order to set and dereference a pointer to the correct type. One way to keep track of this would be to add a short char array to the struct to mark the type name.

Answer 5

This problem is exactly why the templates were developed for C ++. The approach that I used once or twice in C is to have the value field as empty *, and enter the values ​​into it when pasting and discard them when retrieving. Of course, this is far from safe. For additional modularity, I could write the functions insert_int (), get_mystruct (), etc. For each type for which you use this, and perform a listing.

Answer 6

You can use Void * instead of int. This allows you to use any type of data. But the user must know the data type.

For this, optionally, you may have another member that represents Type. which has an enumeration {INT, CHAR, float ...}

Answer 7

Unlike C ++, where you can use template , void * is a de facto C solution.

In addition, you can put items in a linked list in a separate structure, for example:

 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 communication code.

Answer 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 common features:

 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 in one source file and function declarations in a header file. This will allow you to use functions with other programs and not recompile all the time. void * for a data pointer allows you to use a list with many different data types.

(The above code is delivered as is and has not been tested with any compiler. The responsibility for fixing errors depends on the user of the examples.)