Polymorphism is something usually associated with Object Oriented Programming, not with classic C. However, the notion of Polymorphic behavior definitely exists in C in a “lighter” form. You will not automatically get all the back-stage mechanisms OOP languages give you, but there are still time in which you can get a lot of code cleanness by manually applying some polymorphic principles.
The first thing that comes to my mind when thinking about Polymorphism in the context of C programming is pointers to functions. It sometimes allow you to trade-off data with code such that the same general code can handle different tasks without hard-coding the differences. A great (and classic) example to that will be sorting functions. Similar to the OOP Design Pattern in which a general algorithm can be implemented without binding to a specific type as long as it implements the “Comparable” Interface, you can use a similar pattern in C, even if in a slightly more primitive way. Consider the following Bubble Sort implementation working only on ‘int’ arrays.
Bubble sort restricted to arrays of ‘int’
void swap(int * p_a, int * p_b)
{
int tmp = *p_a;
*p_a = *p_b;
*p_b = tmp;
}
void int_bubble_sort(int array[], unsigned int num_elements)
{
unsigned int i;
unsigned int j;
for(i = 0; i < num_elements; ++i)
{
for(j = 0; j < num_elements; ++j)
{
if(array[i] > array[j])
{
swap( &(array[i]), &(array[j]) );
}
else
{
break; //Don’t continue the inner loop
}
}
}
}
Assume the array:
int array[] = {3,4,0,2,1};
One can call the sorting function simply by:
int_bubble_sort(array, sizeof(array)/sizeof(array[0]) );
This implementation works only on ‘int’, but with some modifications it can work on any comparable type, as follows.
Bubble sort, suitable to any comparable type using Polymorphic-like behavior
in order to support any comparable type, we need to apply this transformation to the code above:
- The “swap” function has to be generalized to be able to swap any type. Obviously it will need more information about the type.
- The array of elements is now with arbitrarily sized cells, so we need to generalize how we iterate over it.
- We can no longer compare with ‘>’. We need a generelized way to compare elemets
The core of the implementation stays the same. Note that the focus of the code below is not to be the best code for the task, but rather to neatly show the transformation.
// A function that swaps any two elements with identical size
void swap(void * p_a, void * p_b, unsigned int element_size)
{
// NOTE: to easily stick to the point, I used C99 dynamic array
// syntax here and not malloc(), which is not always recommended.
char tmp_buffer[element_size];
memcpy(tmp_buffer , p_a , element_size);
memcpy(p_a , p_b , element_size);
memcpy(p_b , tmp_buffer , element_size);
}
// Defines a functionthat receives two elements and returns a positive
// number if a>b, zero if a==b, a negative number if a<b
typedef int (*COMPARE_FUNCTION)(void * a, void * b);
void bubble_sort(char * p_array, unsigned int num_elements,
unsigned int element_size,
COMPARE_FUNCTION p_compare_function)
{
int i,j;
for(i = 0; i < (num_elements * element_size); i += element_size)
{
for(j = 0; j < (num_elements * element_size); j += element_size)
{
if(p_compare_function( &(array[i]) , &(array[j]) ) > 0)
{
swap( &(array[i]), &(array[j]) );
}
else
{
break; //Don’t continue the inner loop
}
}
}
}
Now, assume this employee data structure, employees record (array) and compare function:
#define EMPLOYEE_MAX_NAME_SIZE
typedef struct
{
char name[EMPLOYEE_MAX_NAME_SIZE + 1];
unsigned int salary;
}EMPLOYEE;
EMPLOYEE employees[] = {
{“Judy”, 60000},
{“John”, 50000},
{“Sarah”, 90000},
{“Michael”, 80000}
};
int compare_employees(void * a, void * b)
{
// Make sure you call the right compare function,
// C will not automatically protect you…
return ((EMPLOYEE*)a)->salary – ((EMPLOYEE*)b)->salary;
}
With those in place, one can call the general bubble sort function like this:
bubble_sort(employees,
sizeof(employees)/sizeof(employees[0]),
sizeof(employees[0]),
compare_employees);
This is indeed a classic usage of function pointers, used for example in GNU’s quick sort (see the qsort() man page).
A discussion about the “Polymorphic” C
First, you can see that the degree of “Polymorphism” given here is not what you will get from real OOP languages. There is still a lot of manual labor you have to do, like correctly select the compare function, with no real time protection. In real OOP, identifying the handeled type is given automatically as part of the Polymorphism infrastructure. This is not necessarily bad, since a “real” Polymorphism infrastructure takes its toll in size and speed. If you are writing in C and not C++ for example, maybe there is a good reason for that, for example the simplicity of the resulting binary and its leanness.
However, it is definitely possible to up the Polymorphism game in C and create higher degrees of automation, for a price. I will give an example of a higher degree of C Polymorphism in the second part of that post.
2 Comments
1ku3to
Greetings! Very useful advice in this particular article! Its the little changes that will make the biggest changes. Thanks for sharing!