qsort needs one more argument

[jacob navia]

Within the context of the container library, sorting needs a callback
with more than just the two elements to be compared. The standard
qsort function has a callback that takes only two arguments.

This wasn't a big problem since I just adapted the code of lcc-win's
C library to receive one more argument and the problem was gone.

I wonder now, if my problem could be maybe more widespread than I
think. I named the new function: "qsortEx" with the prototype:

void qsortEx(void *base,
size_t num,
size_t width,
int(*cmp) (const void *elem1,
const void *elem2,
void *ExtraArgs),
void *ExtraArgs);

The ExtraArgs aren't "const" since precisely the callbacks could modify
it during the sort.

All this avoids global variables, that are the only solution here.

Has anyone of you seen a function like this?
Is there a C library that provides this?

Thanks in advance.

jacob

 

[Nick]

Within the context of the container library, sorting needs a callback
with more than just the two elements to be compared. The standard
qsort function has a callback that takes only two arguments.

This wasn't a big problem since I just adapted the code of lcc-win's
C library to receive one more argument and the problem was gone.

I wonder now, if my problem could be maybe more widespread than I
think. I named the new function: "qsortEx" with the prototype:

void qsortEx(void *base,
size_t num,
size_t width,
int(*cmp) (const void *elem1,
const void *elem2,
void *ExtraArgs),
void *ExtraArgs);

The ExtraArgs aren't "const" since precisely the callbacks could modify
it during the sort.

All this avoids global variables, that are the only solution here.

Has anyone of you seen a function like this?
Is there a C library that provides this?

One popular library that does this is expat - xml parsing. It passes a
void pointer ("data") all over the place for you to use in whatever way
you want.

I bit myself with this one a while ago, and now always include that
extra pointer - it only adds a couple of lines to the code, and making
it NULL is painless when you don't need it.

 

[jacob navia]

Richard Heathfield a écrit :

That's why, a long time ago, I added
side-channel pointers into my container library. I can't do anything
about qsort, bsearch or *alloc/free, though.

How did you call your qsort routine? Did it have the same interface?

 

[Paul N]

jacob navia wrote:

Well, obviously I don't call it qsort. The interface is basically the
same, except for an additional void * parameter at the end, which is
either a pointer to side channel data or a null pointer.

English is a funny language. "How did you call your qsort routine?"
and "What did you call your qsort routine?" have completely different
meanings.

 

[Seebs]

All this avoids global variables, that are the only solution here.

Not quite, they aren't.

Has anyone of you seen a function like this?
Is there a C library that provides this?

It's a fairly common idiom for callbacks. That said, you can do
it without a global -- through the magic of file scope.

/* begin mycmpEx.c */

static void *aux;

int mycmp(struct foo *a, struct foo *b) {
/* manipulate aux, also compare a and b */
}

int mycmp_aux(void *v) {
aux = v;
}

/* begin use of mycmp */

mycmp_aux(callback_value);
qsort(blah blah, mycmp);

/* see? */

Basically, you can take advantage of static file scope to introduce a
variable which you can access from your comparator, but which is not
visble to anything else. You don't have to worry about this preventing
inlining, because I'm pretty sure no one is inlining qsort comparators,
and you even reduce the number of arguments being passed around.

Christmas was saved!

-s
p.s.: Which isn't to say I wouldn't have preferred qsort's cmp function
to take an aux argument.

 

[Nobody]

Within the context of the container library, sorting needs a callback
with more than just the two elements to be compared. The standard
qsort function has a callback that takes only two arguments.

I wonder now, if my problem could be maybe more widespread than I
think.

Has anyone of you seen a function like this?
Is there a C library that provides this?

Both the GNU and BSD libc provide qsort_r():

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

The first two hits for qsort_r on Google:

BSD http://www.ipnom.com/FreeBSD-Man-Pages/qsort_r.3.html
GNU http://www.digipedia.pl/man/doc/view/qsort_r.3.html

 

[jacob navia]

Seebs a écrit :

Not quite, they aren't.


It's a fairly common idiom for callbacks. That said, you can do
it without a global -- through the magic of file scope.

/* begin mycmpEx.c */

static void *aux;

int mycmp(struct foo *a, struct foo *b) {
/* manipulate aux, also compare a and b */
}

int mycmp_aux(void *v) {
aux = v;
}

/* begin use of mycmp */

mycmp_aux(callback_value);
qsort(blah blah, mycmp);

/* see? */

Basically, you can take advantage of static file scope to introduce a
variable which you can access from your comparator, but which is not
visble to anything else. You don't have to worry about this preventing
inlining, because I'm pretty sure no one is inlining qsort comparators,
and you even reduce the number of arguments being passed around.

Christmas was saved!

-s
p.s.: Which isn't to say I wouldn't have preferred qsort's cmp function
to take an aux argument.

Thanks. The problem with your solution is that in a multithreading
environment it would be a bit messy: you would have to protect the file
scoped variable from other threads.

The whole multithreading stuff is not done yet, but I have it in mind
so that later it is fairly easy to implement.

 

[jacob navia]

Nobody a écrit :

Both the GNU and BSD libc provide qsort_r():

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

The first two hits for qsort_r on Google:

BSD http://www.ipnom.com/FreeBSD-Man-Pages/qsort_r.3.html
GNU http://www.digipedia.pl/man/doc/view/qsort_r.3.html

Thanks.

Once you know about qsort_r it is easy to find of course

 

[Seebs]

Thanks. The problem with your solution is that in a multithreading
environment it would be a bit messy: you would have to protect the file
scoped variable from other threads.

True that.

Your next option over, which is Clearly Very Bad, is to ensure that
every object you're comparing has a pointer to the aux object.

The whole multithreading stuff is not done yet, but I have it in mind
so that later it is fairly easy to implement.

Good thinking.

-s