How C programmers write generic functions?

Short answer: By using void pointers.

The void pointer holds an address but doesn’t interpret it, instead the programmer use explicit cast to give hint to compiler to interpret the the address pointed by void pointer.

Consider the function below:

void printGeneric(const void *something, const size_t size){
	if(sizeof(int) == size)
		printf("%d", *(int*)something);
	if(sizeof(double) == size)
		printf("%lf", *(double*)something);
	if(sizeof(float) == size)
		printf("%f", *(float*)something);
}

When I call this function I need 2 variables

  1. a void pointer
  2. size of the type compiler needs to interpret the data
double f = 3.14;
void *p = &f;

printGeneric(p,sizeof(double));
int i = 3;
void *p = &i;

printGeneric(p,sizeof(int));

Of course function is not portable due to system dependent size of the integral types but I think it’s good enough to describe consept.

Take a look at the quick sort in standard library:

void qsort(void *ptr, size_t count, size_t size,
	   int (*comp)(const void *, const void *));

it takes 4 parameters and returns void.

  • First argument is pointer the void, ptr
  • Second argumet is an unsigned int count, is number of element we want to sort.
  • Third one is size of the every single element in array, in bytes.
  • the last one is predicate function that compared the element, a function pointer takes 2 const void pointer and returns an integer. The return value of the function usually one of -1, 0, -1, as in stmcmp() a negative, zero and positive integer.

Let’s see it in action:

static int compInt(const void *x, const void *y) {
	const int first = *(const int *)x;
	const int second = *(const int *)y;

	if (first < second) return -1;
	if (first > second) return +1;
	else return 0;
}

The function names in C, just like arrays, is a pointer. So we can pass the with or without & operator.

int i[3] = {1, -1, 0};
qsort(i, 3, sizeof(int), compInt);

or

qsort(&i, 3, sizeof(int), &compInt);
Output:
-1 0 1

But how actually this qsort function works? Implementing something similar but simple may be helpful to understand better. A quick target is bubble sort!

here is the pseudocode:

func bubbleSort( var a as array )
1    for i from 1 to N
2        for j from 0 to N - i
3           if a[j] > a[j + 1]
4              swap( a[j], a[j + 1] )
end func

I want same API with the qsort:

void bubbleSort(void *base, size_t num, size_t size,
		      int (*cmp)(const void *, const void *));

Implementing line 1 in pseudocode is trivial:

void bubbleSort(void *base, size_t num, size_t size,
		      int (*cmp)(const void *, const void *)) {
	for (size_t i = 0; i < num; i++)

line 2 is the same:

void bubbleSort(void *base, size_t num, size_t size,
		      int (*cmp)(const void *, const void *)) {
	for (size_t i = 0; i < num; i++)
		for (size_t j = 0; j < num - i; j++)

line 3 has a comparision, that means we have to access memory location of the array elements and to pass it to comparision predicate, interpreting the data is its job.

How can we make it? We need to work on byte-wise. char data type in guaranteed to be 1 byte (ie. 8 bit) and can hold -128..127 and unsigned char can hold 0..255, we can use one of these. But we can also use uint8_t which defined in <stdint>. chars are also an integer after all.

typedef uint8_t byte;

To break it into pieces, I want to demostrate a small example:

int i[3] = {1, -1, 0};

byte *pii = (byte *)i;

Above we assign a pointer to another, nothing interesting, but how to access second element of this int array?

 *(pii + 1 * sizeof(int))
         ^

array index starts from 0 so second element index is 1.

 *(pii + 1 * sizeof(int))
                   ^ 

we need to multiply index value with the sizeof of int, because that’s an int array.

 *(pii + 1 * sizeof(int))
 ^

Finally we need to to dereference to pointer to access its value

printf("%d %d %d",
	 *(pii + 0 * sizeof(int)),
	 *(pii + 1 * sizeof(int)),
	 *(pii + 2 * sizeof(int)));
Output:
1 -1 0

Now turn back and finish the line 3:

void bubbleSort(void *base, size_t num, size_t size,
		int (*cmp)(const void *, const void *)) {
	byte *pbBase = (byte *)base;  // pbBase: pointer to byte base

	for (size_t i = 0; i < num; i++)
		for (size_t j = 0; j < num - i; j++)
			if (cmp(pbBase + (j + 1) * size, pbBase + j * size) < 0)

line 4 has a swap operation, which needs to copy a group of bytes to another, so we need to work on byte-wise operations.

void swap(byte *x, byte *y, size_t size) {
    while (size-- > 0) {
	byte tmp = *x;
	*x++ = *y;
	*y++ = tmp;
    }
}

Almost there but we need some more steps to complete.

void bubbleSort(void *base, size_t num, size_t size,
		int (*cmp)(const void *, const void *)) {
	byte *pbBase = (byte *)base;  // pbBase: pointer to byte base

	for (size_t i = 0; i < num; i++)
		for (size_t j = 0; j < num - i; j++)
			if (cmp(pbBase + (j + 1) * size, pbBase + j * size) < 0)
				swap(pbBase + (j + 1) * size, pbBase + j * size,
				     size);
}

That’s looks all right but when I try to call the function the last element is not where it should be, there is a off by one error that I couldn’t figure out but when I decrement the number of elements by one, the problem solved.

void bubbleSort(void *base, size_t num, size_t size,
		int (*cmp)(const void *, const void *)) {

	byte *pbBase = (byte *)base;  // pbBase: pointer to byte base
	num -= 1;

	if (num)
		for (size_t i = 0; i < num; i++)
			for (size_t j = 0; j < num - i; j++)
				if (cmp(pbBase + (j + 1) * size,
					pbBase + j * size) < 0)
					swap(pbBase + (j + 1) * size,
					     pbBase + j * size, size);
}

I also add an additional check for the number of elements to prevent passing negative arguments.

const int SIZE = 3;

int i[SIZE] = {0, 1, -1};
double d[SIZE] = {1.2, -3.4, 5.6};

bubbleSort(i, SIZE, sizeof(int), compInt);
printf("%d %d %d\n", i[0], i[1], i[2]);

bubbleSort(d, SIZE, sizeof(double), compDouble);
printf("%lf %lf %lf\n", d[0], d[1], d[2]);
Output:
-1 0 1
-3.400000 1.200000 5.600000

You can find source of this post from here, and a few more implementation from here.


CC++

1089 Words

2018-09-19 03:00 +0300