Can i use memcmp with qsort?

Question

I am creating a C dynamic array library, sort of. Please note that I do this for fun in my free time, so please do not recommend millions of existing libraries.

I started to sort. An array has the size of an arbitrary element, defined as a struct:

typedef struct { //[PRIVATE] Pointer to array data void *array; //[READONLY] How many elements are in array size_t length; //[PRIVATE] How many elements can further fit in array (allocated memory) size_t size; //[PRIVATE] Bytes per element size_t elm_size; } Array; 

I originally prepared this to start with the sort function:

 /** sorts the array using provided comparator method * if metod not provided, memcmp is used * Comparator signature * int my_comparator ( const void * ptr1, const void * ptr2, size_t type_size ); **/ void array_sort(Array* a, int(*comparator)(const void*, const void*, size_t)) { if(comparator == NULL) comparator = &memcmp; // Sorting algorithm should follow } 

However, I found out about qsort :

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

Apparently, I could just pass my internal array to qsort . I could just call it:

 qsort (a->array, a->length, a->elm_size, comparator_callback); 

But there is a signature for the catch comparator, qsort , which reads:

 int (*compar)(const void*,const void*) 

So far, memcmp signature:

 int memcmp ( const void * ptr1, const void * ptr2, size_t type_size ); 

The element size is missing in the qsort callback, that is, I can no longer have a general comparator function when NULL is passed as a callback. I could manually create comparators up to X bytes in element size, but that sounds ugly.

Can qsort (or other built-in sorting) be used with memcpy ? Or do I need to choose between the built-in comparator and the built-in sort function?

Answer 1

A non-potential way is to use a private global variable to pass size.

 static size_t compareSize = 0; int defaultComparator(const void *p1, const void *p2) { return memcmp(p1, p2, compareSize); } void array_sort(Array* a, int(*comparator)(const void*, const void*, size_t)) { if(comparator == NULL) { compareSize = a->elm_size; comparator = &defaultComparator; } // Sorting algorithm should follow } 

You can make it thread safe by making compareSize thread-local variable ( __thread )

Answer 2

C11 provides you (admittedly optional) qsort_s function that is designed to address this particular situation. It allows you to pass the user-supplied value void * - a context pointer - from the calling code to the comparator function. The comparator callback in this case has the following signature

 int (*compar)(const void *x, const void *y, void *context) 

In the simplest case, you can pass a pointer to a size value as a context

 #define __STDC_WANT_LIB_EXT1__ 1 #include <stdlib.h> ... int comparator_callback(const void *x, const void *y, void *context) { size_t elm_size = *(const size_t *) context; return memcmp(x, y, elm_size); } ... qsort_s(a->array, a->length, a->elm_size, comparator_callback, &a->elm_size); 

Or it might make sense to pass a pointer to the entire array object as a context.

Some nix-based implementations have been providing a similar qsort_r function for some time, although it is non-standard.

Answer 3

The qsort() API is a legacy of simpler times. There must be an additional “environment” pointer passed unanswered from the qsort() call for each comparison. This will allow you to transfer the size of the object and any other necessary context in streaming safe mode.

But this is not so. The @BryanChen method is the only reasonable one.

The main reason I write this answer is to indicate that there are very few cases where memcmp will do something useful. There are not many kinds of objects where a lexicographic comparison of the unsigned char component makes sense.

Of course, comparing a struct in this way is dangerous because padding byte values ​​are not set. Even part of the equality can fail. In other words,

 struct foo { int i; }; void bar(void) { struct foo a, b; ai = bi = 0; if (memcmp(&a, &b, sizeof a) == 0) printf("equal!"); } 

maybe - according to the C standard - nothing to print!

Another example: for something as simple as unsigned int s, you will get different sort orders for a large storage order in storage order.

 unsigned a = 0x0102; unsigned b = 0x0201; printf("%s", memcmp(&a, &b, sizeof a) < 0 ? "Less! : "More!"); 

will print Less or More depending on the machine it is running on.

Indeed, the only type of object I can imagine that makes sense to compare with memcmp is equal-sized blocks of unsigned bytes. This is not a very common sorting option.

In general, a library that offers memcmp as a comparison function is doomed to be error prone. Someone will try to use it as a substitute for specialized comparison, which is really the only way to get the desired result.