Pass extra parameter to comparator for qsort

Question

I'm just wondering if there's a way for me to pass an extra parameter to my comparator which will then be used in my qsort function?

For example I have these 2 comparators (one in ascending order, and one in descending)

qsort(entries, 3, sizeof(struct entry), compare_desc);

int compare_asc(const void *elem1, const void *elem2)
{
     return strcmp(elem1.name.last, elem2.name.last);
}


int compare_desc(const void *elem1, const void *elem2)
{
     return strcmp(elem2.name.last, elem1.name.last);
}

Is there a way so I can do something like this instead:

int compare(const void *elem1, const void *elem2, const char *order)
{
     if (strcmp(order, "asc") == 0)
         return strcmp(elem1.name.last, elem2.name.last);
     else if (strcmp(order, "desc") == 0)
         return strcmp(elem2.name.last, elem1.name.last);
}

Reason I ask is that my sort program has to take switches and if I have 2 different switches (+a, -a) for ascending and descending respectively, then I have to make 2 different comparator functions. If I add more, it gets more complicated. Is there a way to improve the design of this program?

EDIT: No global & extern variables allowed.

Answer 1

Old question, but in case someone stumbles upon it...

There are non-standard versions of qsort() that let you pass an extra parameter to the callback function. glib offers qsort_r() while VC gives you qsort_s().

Answer 2

In your example case it is better to have two different comparators. If you had just the one, every comparison would unnecessarily have to determine the sort order, which you couldn't change mid-sort anyhow for any meaningful results. So instead of putting the if (ascending_sort) { } else { } inside the comparator, put it at your qsort call:

qsort(e, n, sizeof(*e), (strcmp(order, "asc") ? compare_desc : compare_asc));

Edit: Some tips if you add more comparators:

– remember that you don't need to re-write every comparator; you can have them call one another if you are sorting on multiple fields (and you can always invert the result of a comparator with -, e.g., compare_asc(a, b) can return -compare_desc(a, b)).

– it's easy to reverse the order of the entire array in the end so you don't need to double your number of comparators for supporting an option to reverse the entire sort order

– you can replace the trinary operator (? :) in my example with a function that returns the appropriate comparator as suggested in the comments below

Answer 3

qsort_r() and qsort_s()

There are functions called qsort_r() or qsort_s() available in some implementations that do what you want — take a pointer to extra data that is passed to the comparator functions.

The BSD variant implementations (including macOS or Mac OS X) provide a version of qsort_r(), and so does the GNU C library. Unfortunately, the two variants have different signatures. That doesn't stop them being useful, but it does mean that the same source code cannot be used on the two platforms, and further that you have to make sure you understand which variant of qsort_r() is available on any machine where you try to use it.

Similarly, Microsoft provides a version of qsort_s() and the C11 standard defines a version of qsort_s() (as an optional function in Annex K, based on TR-24731), but the two differ in the signature again. Maybe it is fortunate that the Annex K functions are not widely implemented.

BSD qsort_r()

void qsort_r(void *base, size_t nel, size_t width, void *thunk,
             int (*compar)(void *, const void *, const void *));

GNU C library qsort_r()

void qsort_r(void *base, size_t nmemb, size_t size,
             int (*compar)(const void *, const void *, void *),
             void *arg);

Note that in BSD, the 'thunk' is equivalent to 'arg' in GNU, but these arguments appear in different places in the calling sequence to the qsort_r() function (before and after the comparator function pointer). Further, note that the 'thunk' is passed as argument 1 to the BSD comparator functions, but the 'arg' is passed as argument 3 to the GNU comparator functions.

Mnemonic for qsort_r: the context data is specified in relation to the comparator in the calling sequence in the same relation as the context is passed to the comparators in relation to the two values being compared. Context before pointer to comparator means context before values in call to comparator; context after pointer to comparator means context after values in call to comparator.

Annex K qsort_s()

errno_t qsort_s(void *base, rsize_t nmemb, rsize_t size,
               int (*compar)(const void *x, const void *y, void *context),
               void *context);

The Annex K qsort_s() is unique in returning a value; all the other variants do not return any value. Otherwise, for most practical purposes, it matches the GNU qsort_r() function.

Microsoft qsort_s()

void qsort_s(void *base, size_t num, size_t width,
             int (__cdecl *compare )(void *, const void *, const void *),
             void * context);

The rsize_t and size_t distinction is not very important when comparing the Annex K and Microsoft variants of qsort_s(), but in the Annex K qsort_s(), the context is passed as argument 3 to the comparator, but in the Microsoft qsort_s(), the context is passed as argument 1 to the comparator.

Summary

Functions called qsort_r() or qsort_s() provide the required functionality. However, you must check the platform specification for which function is present, and for the correct calling sequence for the arguments to the sorting function, and the correct calling sequence for the arguments to the comparators.

Nominally, you should check for the return type of the function too, but few programs would consider checking it, mainly because most variants of qsort() return no value.

Answer 4

Without using a global variable, AFAIK in general you can't, you have to provide two different functions for the two sorting methods. Actually this is one of the reasons why in C++ functors (objects that provide an overloaded function-call operator) are often used.

Answer 5

What you should do is switch the arguments to qsort so that you pass a function pointer as appropriate.

Given your scenario, it might be something like

// selectively invoke qsort:
if(strcmp(var, "+a")){
    qsort(entries, 3, sizeof(struct entry), compare_asc);
}else{
    qsort(entries, 3, sizeof(struct entry), compare_desc);
}

Or alternatively you can do something like:

// declare a function pointer
int (*func)(const void*, const void*);

// sometime later decide which function to assign
// to the function pointer
if(strcmp(var, "+a")){
    func = compare_asc;
}else{
    func = compare_Desc;
}

// sometime later invoke qsort
qsort(entries, 3, sizeof(struct entry), compare_desc);

Answer 6

> Is there a way to improve the design of this program?

Don't do this -- this is not a design improvement, it's just an experiment.

#include <stdio.h>
#include <stdlib.h>

int comparefx(const void *a, const void *b) {
    static int extra = 0;
    if (a == NULL) {
        extra = (int)b;
        return 0;
    }
    switch (extra) {
        case 24: puts("24"); return *(const int*)a + *(const int*)b; break;
        case 42: puts("42"); return *(const int*)b - *(const int*)a; break;
        default: puts("--"); return *(const int*)a - *(const int*)b; break;
    }
}

int main(void) {
    int entries[] = {4, 2, 8};

    qsort(entries, 3, sizeof *entries, comparefx);
    printf("%d %d %d\n", entries[0], entries[1], entries[2]);

    comparefx(NULL, (void*)42); /* set 'extra' parameter */
    qsort(entries, 3, sizeof *entries, comparefx);
    printf("%d %d %d\n", entries[0], entries[1], entries[2]);

    return 0;
}

It compiles "cleanly" with 3 compilers

$ gcc -std=c89 -pedantic -Wall 4210689.c
4210689.c: In function 'comparefx':
4210689.c:7: warning: cast from pointer to integer of different size

$ clang -std=c89 -pedantic -Wall 4210689.c
$ tcc -Wall 4210689.c
$ 

And it runs as expected

$ ./a.out
--
--
--
2 4 8
42
42
42
8 4 2

Answer 7

In simple cases, you can use a global variable.

Answer 8

A lack of classes and closures pretty much means that you're stuck with writing a separate comparator for each different type of comparison you want.

One thing you could do is have each element of the array be a struct, containing value and sort_order fields. All the sort_order fields would be the same... but that's worse than just having 2 comparators.

Think of it this way: you end up writing all the same comparator code anyway. But instead of having a complex nested if/else with 8 cases, you have 8 functions. The difference is some extra function declarations.

EDIT: To reply to R's comments.. that's a good point. I had this before but I deleted it:

You can create a framework similar to Python's list.sort() function. Pretty much:

• Create a struct with value and sortvalue fields.
• Put initial values in value.
• Write whatever code to transform the items into the sortvalue field.
• Use a standard comparator on that, along with qsort.
• When you're done, just take the elements out of value fields. They'll be sorted according to sortvalue but the values will be correct.

This is used in Python for example, where if you want to sort by say the 4th item in a tuple, you don't write a whole comparator (like lambda v1,v2: v1[3]-v2[3]), but instead just transform the inputs with a key function (lambda k: k[3]) and use a standard sort method. It would work in the case of the "billions of sorts", since your code can do whatever complicated operation with however many inputs to transform the values.

Answer 9

Just use a lambda function for closure. Something like this C++ code:

string sortOrder="asc";   
qsort(entries, 3, sizeof(struct entry),    
[=](const void *elem1, const void *elem2) -> int{
        myCompare(elem1,elem2,sortOrde)             

});