c comparator best practice for when more arguments needed

Question

I intend to sort an array of multidimentional points each time by another coordinate. I want to use c qsort() method but in order to do so I have to use comparator function which its input is only two pointers, so I can't send it the desired coordinate to sort by. Therefore I figured out two solutions and I am struggling choosing the best one of them :

Use a static variable - an int in this example - initialize it to a -1, and before calling the qsort function set it to the wanted coordinate. In addition, make my comparator, access this variable and compare based on it.
Build a new struct to hold a pointer to the point and the desired coordinate, then make the comparator to sort two pointers to such struct and use the additional info from the struct.

The first sounds like a quick solution though it might be loop hole, while the second sounds like an overkill for such a simple task. I would be glad to hear any better solution if there is to the problem.

Why not show some code instead of describing it? How you store the points matters a great deal to the solution you can get. — StoryTeller - Unslander Monica, Mar 22 '17 at 10:47
@Bathsheba option 2 could get very expensive for large arrays of points. — JeremyP, Mar 22 '17 at 11:13
there is possibly a 3rd option - have different comparators for each of the coordinates? — Chris Turner, Mar 22 '17 at 11:15
If so, then either use `qsort_r` as you detail in your fine answer, or nick the source for `qsort_r` if your platform doesn't have it. — Bathsheba, Mar 22 '17 at 11:16

score 2 · Answer 1 · edited May 23 '17 at 12:00

2

If your system has qsort_r, you can use that. qsort_r has an extra parameter that you can use to pass your coordinate in.

int comparator(const void *l, const void *r, void *param)
{
    Point* lPoint = (Point*) l;
    Point* rPoint = (Point*) r;
    Coordinate* coord = (Coordinate*) param;

    // Do your comparison ....
}

void mySort(Point* list, size_t listSize, Coordinate sortCoord)
{
    qsort_r(list, listSize, sizeof(Point), comparator, &sortCoord);
}

It's definitely available if you are using glibc (e.g. on Linux) and on OS X. However, it is not officially portable. See this answer on portability

How portable is the re-entrant qsort_r function compared to qsort?

My code example is written for the Linux version. With OS X, the comparator must be declared as

 int comparator( void *param, const void *l, const void *r)

and the qsort_r call is

qsort_r(list, listSize, sizeof(Point), &sortCoord, comparator);

edited May 23 '17 at 12:00

Community

1
1

answered Mar 22 '17 at 11:08

JeremyP

84,577
15
123
161

Nice. Have an upvote. It's probably juvenile to suggest pinching the source if your platform doesn't have `qsort_r`, but I would be tempted. – Bathsheba Mar 22 '17 at 11:17
@Bathsheba There's an implementation of qsort_r in glibc and another in OS X's libc. Both of these are open source, therefore using their source code is not only not pinching but encouraged (provided you comply with the licence terms, of course). – JeremyP Mar 22 '17 at 11:20
Note that the specification of `qsort_r` differs on Linux and Mac. The placement of the extra parameter is different, IIRC. – Jonathan Leffler Mar 22 '17 at 11:40
@JonathanLeffler Thanks. In fact, my answer as written is wrong for both OS X and Linux! I'll edit it. – JeremyP Mar 22 '17 at 11:42
Note http://stackoverflow.com/q/39560773/15168 for info about Mac vs Linux. – Jonathan Leffler Mar 22 '17 at 11:48

score 0 · Answer 2 · answered Mar 22 '17 at 11:57

The most portable version would probably indeed be to encapsulate the comparsion object(s) ("functors") in a separate file, then use a static file scope variable to change the behavior of the function.

something.h

void set_something (something_t s);

int compare_something (const void* obj1, const void* obj2);

something.c

#include "something.h"

static something_t someting = 0;

void set_something (something_t s)
{
  something = s;
}

int compare_something (const void* obj1, const void* obj2)
{
  const coord_t* c1 = obj1;
  const coord_t* c2 = obj2;

  // do stuff with c1, c2 based on something
}

The only down-side with this is that you can't have multiple threads performing different kinds of sorting at the same time, but that's not likely to be an issue. (If it is, design some way to pass a "something" variable as parameter to each thread callback instead.)

score 0 · Answer 3 · edited May 23 '17 at 12:10

I suggest an option #3

C11 presents qsort_s() which provides the needed context parameter. This is in Annex K (normative) and so may not be included in C11 compliant compiler.
The availability of this function may not be wide.

K.3.6.3.2 The qsort_s function

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 third argument to the comparison function is the context argument passed to qsort_s. The sole use of context by qsort_s is to pass it to the comparison function

If this function is not available, consider an alternative that mimics this interface.

This idea is similar to the @JeremyP which suggest qsort_r. The two functions are similar, except for argument order amongst qsort_r() variants the return type.

c comparator best practice for when more arguments needed

3 Answers3