qsort needs one more argument

[jacob navia]

It would be nice to be able to pass to qsort an extra argument to allow
some context in the comparison.

This need is shared by several other people. I added to the c library of
the lcc-win compiler:

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 to store private data.

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

The same could be done to bsearch --> bsearchEx.

Any possibility of adding this to the new standard?

Happy new year.

jacob

[Kalle Olavi Niemitalo]

jacob navia <ja...@spamsink.net> writes:

> It would be nice to be able to pass to qsort an extra argument to
> allow some context in the comparison.

GNU libc has had a qsort_r since 2007-11-13. Like in your
qsortEx, ExtraArgs is the last parameter of qsort_r and the last
argument of the comparison function:
http://repo.or.cz/w/glibc.git/commitdiff/e458144c99ddc00769ffa6bd367c21d37e879d83

FreeBSD got its qsort_r on 2002-09-10. This one differs from
yours by making ExtraArgs the fourth parameter of qsort_r and
the first argument of the comparison function. Likewise Apple:
http://www.freebsd.org/cgi/cvsweb.cgi/src/include/stdlib.h.diff?r1=1.41;r2=1.42
http://developer.apple.com/mac/library/documentation/Darwin/Reference/ManPages/man3/qsort.3.html

Microsoft apparently added qsort_s in Visual Studio 2005. There,
ExtraArgs is the last parameter of qsort_r and the first argument
of the comparison function. This variant also has more strictly
specified error handling (IIRC you generally prefer that):
http://msdn.microsoft.com/en-us/library/4xc60xas(VS.80).aspx

> The same could be done to bsearch --> bsearchEx.

That would be useful if one wants to sort an array with
qsortEx/qsort_r/qsort_s and then search in it with the same
comparison function. Microsoft has bsearch_s:
http://msdn.microsoft.com/en-us/library/2w9185b8(VS.80).aspx

However, if you make the comparison function just for bsearch and
don't use it for any variant of qsort, then you can pass the
context data via the key pointer, because bsearch always gives
that to the comparison function as the first argument; the key
pointer need not point to the same kind of data structure as you
have in the array. It's a bit of a hack though.

If you're extending bsearch, then it might also make sense to
provide something like C++'s std::lower_bound and
std::upper_bound, for finding the place where an element should
be inserted. Those are pretty simple to implement though, so C
programs that need such features and are intended to be portable
would probably keep providing their own code for the next 15
years or so.

> Any possibility of adding this to the new standard?

qsort_s and bsearch_s are in TR 24731-1. I don't know whether
they are going to be added to ISO 9899 itself. They seem easier
to standardize than qsort_r, which has incompatible variants.

[jacob navia]

Kalle Olavi Niemitalo a �crit :

(snip very useful and detailed answer)

Thank you.

I will follow the qsort_s line then.