Generic Programming in C?

[bvkim]

As you know that GNU-C provides qsort() function in <cstdlib> in this prototype

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

You may know about Selection Sort Algorithm already, I want to write a function to perform Selection Sort but it can apply generally for many type: int, long, float, double... like qsort() above.
How can I do that?

[Ronix]

The function should have the same signature as qsort. In order to access the i'th element, you cast the void* to a char*, and move it by i * `size' (Where `size' is the third parameter of the function). The function pointer `comparator' is used to determine whether an element compares equal, less or greater to another one (< 0, = 0 and >0 respectively).

[bvkim]

The function should have the same signature as qsort. In order to access the i'th element, you cast the void* to a char*, and move it by i * `size' (Where `size' is the third parameter of the function). The function pointer `comparator' is used to determine whether an element compares equal, less or greater to another one (< 0, = 0 and >0 respectively).

Something I'm curious

1. why do i need to cast from void* to char*?
2. how can I compare the values in those `base` memory while I don't know what kind of type they are?
3. Would you mind giving me some samples?

Thanks for your responses.

[Ronix]

Something I'm curious
1. why do i need to cast from void* to char*?

Because you cannot move a void pointer. For example, if p is a void*, then the compiler cannot evaluate the expression `p + i', because it has no information on p, and thus it would not know how many bytes to move.

On the other hand, char* represents a byte pointer. Therefore, you can move it exactly as many bytes as you need it. That's why you need to pass the size of the data type as the third parameter in qsort. It moves a byte pointer in multiples of `size' to access a particular element.

2. how can I compare the values in those `base` memory while I don't know what kind of type they are?

The user supplies a function to perform the comparison (Fourth argument in qsort). The function takes 2 void pointers and returns an integer: 0 if both arguments compare equal, a negative value if the first argument compares less than the second and a positive, non-zero value if the first argument compares greater than the second.

3. Would you mind giving me some samples?

Sure.

#include <stdio.h>

void compare_first_to_rest(void *ptr, size_t nelem, 
   size_t size, int (*cmp)(const void*, const void*)) {
    unsigned i;
    for(i = 1; i < nelem; ++i)
        {
        int res = cmp(ptr, (char*)ptr + i * size);
        if(res < 0)
            printf("First element is less than element at %u\n", i);
        else if(res > 0)
            printf("First element is greater than element at %u\n", i);
        else
            printf("First element is equal to element at %u\n", i);
        }
}

int icmp(const void *x, const void *y) {
   return *(int*)x - *(int*)y;
}

int main()
{
   int x[] = { 5, 3, 6, 2, 4, 8, -1, 10 };
   compare_first_to_rest(x, 8, sizeof(int), icmp);
}

As you can see, `compare_first_to_rest' doesn't know about the type of the elements it receives in its first argument. But knowing the size of each one, it can get a pointer to every one of them, and let the function pointer do the job.

[bvkim]

wow, u're such a great teacher just lighted up my mind for knowledge )

But I'm still having 2 more questions to ask if you don't mind ^^!

1. Base on your explanation above, I guess the compare_first_to_rest() should perform comparison to all kinds of datatype such as int, float, long, double, char, char* (string-equivalent), and even any user-defined structures, through the comparator interface icmp(), should it not?

2. Considering i'm writing the piece of code for selection sort

void selsort( void *base, size_t num, size_t size, int (*comparator)(const void *, const void *)
{
	unsigned int i, j;
	for( i = 0; i < num - 1; ++i ) {
		for( j = i + 1; j < num; ++j ) {
			// (1)
		}
	}
}

At position (1), how can I perform my comparator and swap based on the return value of comparator() ?

[quzah]

1. You'd really make a compare function for each type you want to compare, when you need it. Just like qsort expects you to do.

2. You just do something like:

if( comparator( this, that ) < or > or whatever )
{
    temp = this
    this = that
    that = temp
}

Quzah.

[bvkim]

Oh, I've figured it out ...
Problem solved!