Generic programming is a style in computer programming in which the implementation of data structures and algorithms is decorrelated from the type of the data they manipulates. For example, implementing an array and the functions to manipulate it independently of the type of the data in the array. The implementation of data structures and algorithms in C requires the type of the data to be set at compile time. For example, there should be one implementation for arrays of integer: struct ArrayInt {int* data;};, int ArrayIntGet(struct ArrayInt* array, int idx); and one for arrays of float: struct ArrayFloat {float* data;};, float ArrayFloatGet(struct ArrayFloat* array, int idx);. The code in the 'Get' functions is exactly the same: return array->data[idx];, and if we later need an array of another type we have to implement it too and duplicate once again the exact same code. Then, it seems at first glance not possible to do generic programming in C. In this article I'll explore ways to bring genericity into C, through the examples of generic arrays and generic linked list.

Using void*.

A well known solution to achieve genericity is to use pointers to void. A void* typed variable contains the address of a location in memory without precising the type of the data at this location. It's the responsibility of the programmer to cast the pointed data into a non-void type before using it. Knowing which type means the void pointer is accompanied with some kind of identification indicating which type it should be cast into. To illustrate this, below is a dummy example of a function taking a void pointer and an identifier as arguments, casting the void pointer as necessary and printing it.

void GenericPrint(void* val, int id) { // Switch on the identifier, cast accordingly and print the value switch(id) { case 0: // integer case printf("%d\n", *(int*)val); break; case 1: // float case printf("%f\n", *(float*)val); break; } } int main() { ... // Values of different type to print int integerVal = 1; float floatVal = 2.0; // Print the values GenericPrint(&integerVal, 0); GenericPrint(&floatVal, 1); ... }

Using void* it is possible to create a generic array as follow:

struct GenericArray { void* data; // Identifier to memorise the type of the data pointed to by the // void pointer int dataType; };

An enumeration could be a better choice compare to an integer for dataType as it would prevent reuse of the same value for different types and clarify the code thanks to names instead of numbers.

// Type identifiers enum GenericArrayType { GenericArrayType_int, GenericArrayType_float, // ... }; struct GenericArray { void* data; enum GenericArrayType dataType; };

And a generic linked list:

// Type identifiers enum GenericLinkedListType { GenericListType_int, GenericListType_float, // ... }; struct GenericLinkListElem; struct GenericLinkListElem { // List element containing a pointer to void void* data; struct GenericLinkListElem* next; }; struct GenericLinkList { struct GenericLinkListElem* head; // Identifier to memorise the type of the data pointed to by the // void pointer in the list's elements enum GenericLinkedListType dataType; };

The array and list themselves are somehow generics but you can't define much functions to manipulate them. Even a 'Get' function would be impractical: its return type would need to be set to void*, raising the question of how other functions would use it. void* are dangerous because the compiler can't check any more if you're using variables of the correct type, and they limit the genericity to pointers only. It isn't possible to have a list of, for example, integer, only a list of pointer to integer. To extend genericity to base types, a solution is to use an union instead:

enum GenericValueType { GenericValueType_int, GenericValueType_float, GenericValueType_ptrInt, GenericValueType_ptrFloat, ... }; // Union to memorise any type of data in a single variable union GenericValue { int intVal; float floatVal; ... void* ptrVal; }; struct GenericLinkListElem; struct GenericLinkListElem { // Use the union to create a generic element union GenericValue data; struct GenericLinkListElem* next; }; struct GenericLinkList { struct GenericLinkListElem* head; // Identifier to memorise the type of the data in the elements' union // and convert it as needed enum GenericValueType dataType; };

Which would be used as, for example:

void GenericLinkListPrintHead(struct GenericLinkList* list) { // Switch on the identifier, cast accordingly and print the value of the // head element switch(list->dataType) { case GenericValueType_int: printf("%d\n", list->head->data.intVal); break; case GenericValueType_float: printf("%f\n", list->head->data.floatVal); break; case GenericValueType_ptrInt: printf("%d\n", *(int*)(list->head->data.ptrVal)); break; case GenericValueType_ptrFloat: printf("%f\n", *(float*)(list->head->data.ptrVal)); break; ... } }

Base types and pointers are then both available, at the cost of memory: the size of the union is the size of its biggest type. A linked list of char would use as much memory (per element) as a linked list of long long int. If the usage of memory is not critical this isn't a problem but in some case it may not be acceptable, and the user should use that kind of generic structure carefully based on its needs.

Another heavy downside of using void pointer and/or union is the need to maintain the enumeration of possible data types and the switch in the functions' body. If they are intended to be provided through a library, when the user data types are unknown at time of implementation, it isn't possible for the user to extend them himself with its own types.

Using _Generic.

The _Generic keyword has been introduced in C11. It allows to switch at compile time between several expressions based on the type of another one. It is introduced as a way to achieve genericity and can be used as follow:

// Definition of the array for each type struct ArrayInt { int* data; }; struct ArrayFloat { float* data; }; // Definition of the get function for each typed array int ArrayIntGet(struct ArrayInt* arr, int idx) { return arr->data[idx]; } float ArrayFloatGet(struct ArrayFloat* arr, int idx) { return arr->data[idx]; } // Wrap the get function into a generic one with _Generic #define ArrayGet(arr, idx) _Generic(arr, \ struct ArrayInt*: ArrayIntGet, \ struct ArrayFloat*: ArrayFloatGet)(arr, idx) int main() { ... // Use the single generic interface on various array type struct ArrayInt arrInt; struct ArrayFloat arrFloat; ... int a = ArrayGet(&arrInt, 0); float b = ArrayGet(&arrFloat, 0); ... }

From the point of view of the user it effectively looks like ArrayGet is a generic function, but to me it is very unsatisfying. Behind the scene, the structure and get function are implemented for each type, hence the goal of genericity (implement it only once) is not achieved. It is still necessary to maintain the list of supported types and add the corresponding functions for any new type, Meaning that the user can't extend the genericity to its own types if the code is burried into a library.

Using the preprocessor.

_Generic hints toward the use of the preprocessor to try to solve the genericity problem. Here the solution is to create macros that expand to the implementation of data structures and functions given a type in argument. This could be achieved as follow:

// Declaration of the generic structure for a given type and its // related functions. Use two arguments, 'type' and 'name', to be // able to generate a valid struct name for types like 'unsigned int'. // Split the macro into definition and declaration as they would // probably be called one in a header file and the other in a body file. #define DeclareGenericArray(type, name) \ struct GenericArray ## name { \ type* data; \ }; \ type GenericArray ## name ## Get(struct GenericArray ## name* arr, int idx); // Definition of the functions #define DefineGenericArray(type, name) \ type GenericArray ## name ## Get(struct GenericArray ## name* arr, int idx) { \ return arr->data[idx]; \ } // Declare and define the generic array and its get function for // integer and float DeclareGenericArray(int, Int) DeclareGenericArray(float, Float) DefineGenericArray(int, Int) DefineGenericArray(float, Float) int main() { struct GenericArrayInt arrInt; struct GenericArrayFloat arrFloat; int a = GenericArrayIntGet(&arrInt, 0); float b = GenericArrayFloatGet(&arrFloat, 0); }

And for generic linked lists:

#define DeclareGenericList(type, name) \ struct GenericListElem ## name; \ struct GenericListElem ## name { \ type data; \ struct GenericListElem ## name* next; \ }; \ struct GenericList ## name { \ struct GenericListElem ## name* head; \ }; \ type GenericList ## name ## Get(struct GenericList ## name* list, int idx); #define DefineGenericList(type, name) \ type GenericList ## name ## Get(struct GenericList ## name* list, int idx) { \ struct GenericListElem ## name* ptr = list->head; \ while (idx-- > 0) ptr = ptr->next; \ return ptr->data; \ } DeclareGenericList(int, Int) DeclareGenericList(float, Float) DefineGenericList(int, Int) DefineGenericList(float, Float) int main() { ... struct GenericListInt listInt; struct GenericListFloat listFloat; ... int a = GenericListIntGet(&listInt, 0); float b = GenericListFloatGet(&listFloat, 0); ... }

Now, we have data structures and functions truly implemented only once, any type available, no need to maintain lists of type identifier or _Generic, and with the macros exposed in a header file, an eventual user could add arrays and lists of any other types. That looks very promising !

However there are inconvenients here too. First, everything being defined in a macro, it must be on one single line, or split using the \ character. This makes editing these macros annoying, generates confusing debug message (a problem wherever in the macro is reported as if it was at the #define line), and worst of all prevents from writing comments in the functions created by these macros. Second, having to use a different name for each type (GenericArrayIntGet(), GenericArrayFloatGet(), ...) doesn't make it look very generic.

The "macros are one line" problem can be mitigated by splitting the declare/define macros into several submacros:

#define DefineGenericArray_Get(type, name) \ type GenericArray ## name ## Get(struct GenericArray ## name, int idx) { \ ... \ } #define DefineGenericArray_Set(type, name, val) \ void GenericArray ## name ## Get( \ struct GenericArray ## name, int idx, type val) { \ ... \ } #define DefineGenericArray(type, name) \ DefineGenericArray_Get(type, name) \ DefineGenericArray_Set(type, name)

These line splitters are still a bit cumbersome but it's better, it gives room for comments at the beginning of each submacro, and no pain no gain !

Separate names have also their work around: object oriented programming.

Using OOP.

If you haven't read my article about OOP methods in C, read it first, you'll need it to understand the rest of this article.

Do you remember how methods help to resolve nicely name conflicts ? It's handy too to make the previous solution friendlier. Instead of having one function name per type, if you use methods, from the user point of view it becomes only one shared name accross all types. For example, using LibCapy for the method framework:

#define DeclareGenericArray(type, name) \ struct GenericArray ## name { \ type* data; \ type (*get)(int idx); \ }; \ struct GenericArray ## name GenericArray ## name ## Create(void); \ type GenericArray ## name ## Get(int idx); #define DefineGenericArray(type, name) \ struct GenericArray ## name GenericArray ## name ## Create(void) { \ return (struct GenericArray ## name){.get = GenericArray ## name ## Get}; \ } \ type GenericArray ## name ## Get(int idx) { \ struct GenericArray ## name* that = (struct GenericArray ## name*)capyThat; \ return that->data[idx]; \ } DeclareGenericArray(int, Int) DeclareGenericArray(float, Float) DefineGenericArray(int, Int) DefineGenericArray(float, Float) int main() { ... struct GenericArrayInt arrInt = GenericArrayIntCreate(); struct GenericArrayFloat arrFloat = GenericArrayFloatCreate(); ... int a = $(&arrInt, get)(0); float b = $(&arrFloat, get)(0); ... }

This brings us to a solution to the genericity problem which I find very interesting. No code duplication, extandable to any type (including not yet defined ones), non occlusive to type checking by the compiler, simple and intuitive usage for the user, and relatively simple to implement for the developer.

Using casting.

In the examples above I was only defining the get function to keep things short and simple. In reality these structures would have also functions to set, add, find, remove, count, etc... What about a function to sort ? It's a common operation on such structures so it sounds legitimate. However, if you think about it, you realise that sorting algorithms do not depend on the type of the containers they sort. Quick sort is conceptually the same for a generic array and a generic list. Hence, if you've implemented it as a method of a generic array, you'll need to implement it again as a method of a generic list. Considering we are interested in genericity here that's pity. Wouldn't it be possible to apply the same solution described above to implement a generic sorting function ? The code below gives an example (skipping the code for the generic array and list which has been given in the previous sections):

... // Declaration and definition of the generic sorting function #define DeclareGenericSort(type, name) \ void GenericSort ## name(type* container, int (*cmp)()); // The body of the function expects all the container to have a 'size', // 'getPtr', 'swap' propoerty/method to generalise the sorting implementation // over all the types. #define DefineGenericSort(type, name) \ void GenericSort ## name(type* container, int (*cmp)()) { \ for (int i = 0; i < container->size - 1; ++i) \ for (int j = i + 1; j < container->size; ++j) \ if (cmp($(container, getPtr)(i), $(container, getPtr)(j)) > 0) \ $(container, swap)( \ $(container, getPtr)(i), \ $(container, getPtr)(j)); \ } // Create the sorting function for an array of int and a list of float, for // example DeclareGenericSort(struct GenericArrayInt, ArrInt) DefineGenericSort(struct GenericArrayInt, ArrInt) DeclareGenericSort(struct GenericListFloat, ListFloat) DefineGenericSort(struct GenericListFloat, ListFloat) // The sorting criteria int cmpInt(int* a, int* b) {return *a > *b ? 1 : 0;} int cmpFloat(float* a, float* b) {return *a > *b ? 1 : 0;} int main() { ... // Declare the generic array and list to be sorted struct GenericArrayInt arrInt = GenericArrayIntCreate(); struct GenericListFloat listFloat = GenericListFloatCreate(); ... // Sort the generic array and list with the generic sorting function GenericSortArrInt(&arrInt, cmpInt); GenericSortListFloat(&listFloat, cmpFloat); ... }

Note the unspecified arguments for the cmp pointer to function in the generic sorting function. This allows to pass cmpInt or cmpFloat as necessary.

It works has desired, but can be improved. The generic function relies on the shared name for the method getPtr and swap. This creates an unnecessary constraint on the data structure acceptable as type. Also, the cmp function is a bit of a burden. We want to let the user to choose upon which criteria the container is sorted, but it would be handy if a default criteria could be used without having to be specified. Lastly, the name of the generic function, including the type of container, is quite long. Using the OOP approach we can again improve on all these points. The previous solution, relying on shared name for the necessary methods, points toward another object of higher conceptual level, whose interface is the one needed to implement the sorting algorithm. I'll call this object here a SortableContainer. To sort a generic array or list, first cast it into a SortableContainer, then use this new object to execute the sorting. The code below shows how to implement it:

// The SortableContainer structure used to cast any other container into a // sortable generic object struct SortableContainer { void* container; int (*getSize)(void); void* (*getPtr)(int idx); int (*cmp)(); void (*swap)(); void (*sort)(void); }; // The sorting algorithm. SortableContainer could also implement several // sorting methods: 'sortBubble', 'sortQuick', ... void SortableContainerSort(void) { struct SortableContainer* that = (struct SortableContainer*)capyThat; for (int i = 0; i < $$(that, that->container, getSize)() - 1; ++i) for (int j = i + 1; j < $$(that, that->container, getSize)(); ++j) { void* valI = $$(that, that->container, getPtr)(i); void* valJ = $$(that, that->container, getPtr)(j); if ($$(that, that->container, cmp)(valI, valJ) > 0) $$(that, that->container, swap)(valI, valJ); } } struct SortableContainer SortableContainerCreate( void* container, int (*getSize)(void), void* (*getPtr)(int idx), int (*cmp)(), void (*swap)()) { struct SortableContainer that = { .container = container, // The related container (array, list, ...) .getSize = getSize, // Inherit methods from the related container .getPtr = getPtr, // ... .swap = swap, // ... .cmp = cmp, // Sorting criteria defining the SortableContainer .sort = SortableContainerSort}; // SortableContainer's own method return that; }

Here I introduce an operator which I haven't spoken about in my article about OOP: #define $$(instance, actor, method) ((capyThat=(actor)) ? (instance)->method : NULL). It allows to execute the method of the instance as if actor was the instance.

Then I add to the generic array and list a method to cast into a SortableContainer and use it as follow:

#define DeclareGenericArray(type, name) \ struct GenericArray ## name { \ ... \ struct SortableContainer (*asSortableContainer)(int (*cmp)()); \ }; \ ... #define DefineGenericArray(type, name) \ ... \ struct SortableContainer GenericArray ## name ## AsSortableContainer( \ int (*cmp)()) { \ struct GenericArray ## name* that = (struct GenericArray ## name*)capyThat; \ return SortableContainerCreate( \ that, that->getSize, (void* (*)())(that->getPtr), cmp, that->swap); \ } \ ... #define DeclareGenericList(type, name) \ ... \ struct GenericList ## name { \ ... \ struct SortableContainer (*asSortableContainer)(int (*cmp)()); \ }; \ #define DefineGenericList(type, name) \ ... \ struct SortableContainer GenericList ## name ## AsSortableContainer( \ int (*cmp)()) { \ struct GenericList ## name* that = (struct GenericList ## name*)capyThat; \ return SortableContainerCreate( \ that, that->getSize, (void* (*)())(that->getPtr), cmp, that->swap); \ } \ ... int main() { // Declare a generic array and generic list struct GenericArrayInt arrInt = GenericArrayIntCreate(); struct GenericListFloat listFloat = GenericListFloatCreate(); // Cast the array and list into SortableContainer struct SortableContainer sortArrInt = $(&arrInt, asSortableContainer)(cmpInt); struct SortableContainer sortListFloat = $(&listFloat, asSortableContainer)(cmpFloat); // Sort the array and list through their SortableContainer $(&sortArrInt, sort)(); $(&sortListFloat, sort)(); }

Conclusion.

In this article I have introduced solutions to the problem of genericity in C. In particular, using the preprocessor, OOP's method and void* pointers it is possible to implement truly generic data structures and functions, written only once and later extendable to any applicable data type in a rather simple way, even for complex scenario as the sorting functionality. The only downside is the edition of the preprocessor commands. If the developper accept this burden, he can provide to the user very easy to use generic code and benefit from the advantages of genericity: faster development, easier maintanability and more readable code.

Finally, here is a minimal listing for a generic array and list, and their sorting with a generic sorter:

#include <LibCapy/capy.h> // The SortableContainer structure used to cast any other container into a // sortable generic object struct SortableContainer { void* container; int (*getSize)(void); void* (*getPtr)(int idx); int (*cmp)(); void (*swap)(); void (*sort)(void); }; // The sorting algorithm. SortableContainer could also implement several // sorting methods: 'sortBubble', 'sortQuick', ... void SortableContainerSort(void) { struct SortableContainer* that = (struct SortableContainer*)capyThat; for (int i = 0; i < $$(that, that->container, getSize)() - 1; ++i) for (int j = i + 1; j < $$(that, that->container, getSize)(); ++j) { void* valI = $$(that, that->container, getPtr)(i); void* valJ = $$(that, that->container, getPtr)(j); if ($$(that, that->container, cmp)(valI, valJ) > 0) $$(that, that->container, swap)(valI, valJ); } } // Create a SortableContainer struct SortableContainer SortableContainerCreate( void* container, int (*getSize)(void), void* (*getPtr)(int idx), int (*cmp)(), void (*swap)()) { struct SortableContainer that = { .container = container, .getSize = getSize, .getPtr = getPtr, .cmp = cmp, .swap = swap, .sort = SortableContainerSort}; return that; } // Generic array declaration // (force the size to 5 elements to simplify this example) #define DeclareGenericArray(type, name) \ struct GenericArray ## name { \ type data[5]; \ int size; \ int (*getSize)(void); \ type* (*getPtr)(int idx); \ void (*swap)(type* valA, type* valB); \ struct SortableContainer (*asSortableContainer)(int (*cmp)()); \ }; \ struct GenericArray ## name GenericArray ## name ## Create(void); \ int GenericArray ## name ## GetSize(void); \ type* GenericArray ## name ## GetPtr(int idx); \ struct SortableContainer GenericArray ## name ## AsSortableContainer( \ int (*cmp)()); \ void GenericArray ## name ## Swap(type* valA, type* valB); // Generic array definition #define DefineGenericArray(type, name) \ struct GenericArray ## name GenericArray ## name ## Create(void) { \ return (struct GenericArray ## name){ \ .size = 5, \ .getSize = GenericArray ## name ## GetSize, \ .getPtr = GenericArray ## name ## GetPtr, \ .asSortableContainer = GenericArray ## name ## AsSortableContainer, \ .swap = GenericArray ## name ## Swap}; \ } \ int GenericArray ## name ## GetSize(void) { \ struct GenericArray ## name* that = (struct GenericArray ## name*)capyThat; \ return that->size; \ } \ struct SortableContainer GenericArray ## name ## AsSortableContainer( \ int (*cmp)()) { \ struct GenericArray ## name* that = (struct GenericArray ## name*)capyThat; \ return SortableContainerCreate( \ that, that->getSize, (void* (*)())(that->getPtr), cmp, that->swap); \ } \ type* GenericArray ## name ## GetPtr(int idx) { \ struct GenericArray ## name* that = (struct GenericArray ## name*)capyThat; \ return that->data + idx; \ } \ void GenericArray ## name ## Swap(type* valA, type* valB) { \ type tmp = *valA; *valA = *valB; *valB = tmp; \ } // Create arrays of integer DeclareGenericArray(int, Int) DefineGenericArray(int, Int) // Declaration of a generic list #define DeclareGenericList(type, name) \ struct GenericListElem ## name; \ struct GenericListElem ## name { \ type data; \ struct GenericListElem ## name* next; \ }; \ struct GenericList ## name { \ struct GenericListElem ## name* head; \ int size; \ int (*getSize)(void); \ type* (*getPtr)(int idx); \ void (*swap)(type* valA, type* valB); \ struct SortableContainer (*asSortableContainer)(int (*cmp)()); \ }; \ struct GenericList ## name GenericList ## name ## Create(void); \ int GenericList ## name ## GetSize(void); \ type* GenericList ## name ## GetPtr(int idx); \ struct SortableContainer GenericList ## name ## AsSortableContainer( \ int (*cmp)()); \ void GenericList ## name ## Swap(type* valA, type* valB); // Definition of a generic list #define DefineGenericList(type, name) \ struct GenericList ## name GenericList ## name ## Create(void) { \ return (struct GenericList ## name){ \ .head = NULL, \ .size = 5, \ .getSize = GenericList ## name ## GetSize, \ .getPtr = GenericList ## name ## GetPtr, \ .asSortableContainer = GenericList ## name ## AsSortableContainer, \ .swap = GenericList ## name ## Swap}; \ } \ int GenericList ## name ## GetSize(void) { \ struct GenericList ## name* that = (struct GenericList ## name*)capyThat; \ return that->size; \ } \ struct SortableContainer GenericList ## name ## AsSortableContainer( \ int (*cmp)()) { \ struct GenericList ## name* that = (struct GenericList ## name*)capyThat; \ return SortableContainerCreate( \ that, that->getSize, (void* (*)())(that->getPtr), cmp, that->swap); \ } \ type* GenericList ## name ## GetPtr(int idx) { \ struct GenericList ## name* that = (struct GenericList ## name*)capyThat; \ struct GenericListElem ## name* ptr = that->head; \ while (idx-- > 0) ptr = ptr->next; \ return &(ptr->data); \ } \ void GenericList ## name ## Swap(type* valA, type* valB) { \ type tmp = *valA; *valA = *valB; *valB = tmp; \ } // Create arrays of float DeclareGenericList(float, Float) DefineGenericList(float, Float) // Comparison function to sort the array and list in increasing order int cmpInt(int* a, int* b) {return *a > *b ? 1 : 0;} int cmpFloat(float* a, float* b) {return *a > *b ? 1 : 0;} int main() { // Create the array and list struct GenericArrayInt arrInt = GenericArrayIntCreate(); struct GenericListFloat listFloat = GenericListFloatCreate(); // Add 5 elements to each to test the generic sorting loop (i, 5) arrInt.data[i] = 4 - i; struct GenericListElemFloat elems[5]; loop (i, 5) { elems[i].data = i; elems[i].next = listFloat.head; listFloat.head = elems + i; } // Cast the array and list into SortableContainer to sort them struct SortableContainer sortArrInt = $(&arrInt, asSortableContainer)(cmpInt); struct SortableContainer sortListFloat = $(&listFloat, asSortableContainer)(cmpFloat); // Print the content of the array and list before sorting println("Before sorting"); loop (i, 5) printf("%d ", arrInt.data[i]); printf("\n"); struct GenericListElemFloat* elem = listFloat.head; while (elem) {printf("%f ", elem->data); elem = elem->next;} printf("\n"); // Sort the array and list through their SortableContainer $(&sortArrInt, sort)(); $(&sortListFloat, sort)(); // Print the content of the array and list after sorting println("After sorting"); loop (i, 5) printf("%d ", arrInt.data[i]); printf("\n"); elem = listFloat.head; while (elem) {printf("%f ", elem->data); elem = elem->next;} printf("\n"); } // Compile without warning with // gcc -std=c18 -Wall -Wextra -o main main.c -lcapy // Output: // Before sorting // 4 3 2 1 0 // 4.000000 3.000000 2.000000 1.000000 0.000000 // After sorting // 0 1 2 3 4 // 0.000000 1.000000 2.000000 3.000000 4.000000

If this article was interesting to you, you may also want to read: OOP in C - Methods, OOP in C - Inheritance.