Arthur J. O'Dwyer wrote:
On Wed, 7 Jul 2004, Roman Ziak wrote: I started to search internet and found few links, and the following
proposal
http://www.open-std.org/jtc1/sc22/wg...docs/n1031.pdf
[...] The 'bsearch_s' function is interesting, but of course it doesn't
add any functionality to the library that didn't already exist in C99
(I don't know whether C90 guaranteed that 'key' would always be the
first argument to 'compar').
It did.
The 'qsort_s' function is no better than the existing 'qsort'; it
guarantees neither O(NlgN) sorting time nor stable sorting. What
it *does* do is add unnecessary complexity; perhaps the 'context'
argument is an alternative to "locales" in C99? I don't know. It's
certainly not any improvement on the existing C99 functions.
I agree with much of what you wrote, but I think you've overlooked the
usefulness of the `context' argument. In my experience, a `context'
argument is an essential part of any properly-designed interface
involving a callback function, allowing customization of the behaviour
of the comparison function at runtime. The lack of it is, I think,
the one major defect in the specification of qsort().
An example is perhaps the easiest way to show this: suppose you want
to sort an array of elements of structure type:
struct element {
int id;
char strings[3];
} elements[] = { ... };
Further, you want to allow sorting by a particular member, say
strings[0], strings[1] or strings[2], and to provide the option of
sorting in forward or reverse. One way to do this is to provide two
separate comparison functions for each possibility:
int compare_zero(co nst void *l, const void *r)
{
const struct element *left = l, *right = r;
return strcmp(left->strings[0], right->strings[0]);
}
int compare_one(con st void *l, const void *r)
{
const struct element *left = l, *right = r;
return strcmp(left->strings[1], right->strings[1]);
}
int compare_two(con st void *l, const void *r)
{
const struct element *left = l, *right = r;
return strcmp(left->strings[2], right->strings[2]);
}
int compare_r_zero( const void *l, const void *r)
{
const struct element *left = l, *right = r;
return - strcmp(left->strings[0], right->strings[0]);
}
int compare_r_one(c onst void *l, const void *r)
{
const struct element *left = l, *right = r;
return - strcmp(left->strings[1], right->strings[1]);
}
int compare_r_two(c onst void *l, const void *r)
{
const struct element *left = l, *right = r;
return - strcmp(left->strings[2], right->strings[2]);
}
The appropriate comparison function can then be selected at runtime by
an if-else ladder, or an array of pointers to the functions, etc.
Duplicating the comparison code in this way is pretty inelegant,
though, besides being a maintenance burden. Obviously, it's desirable
to replace the almost-identical functions above with a single
function, and parameterize the hard-coded indexes and minus operator.
int compare(const void *l, const void *r)
{
const struct element *left = l, *right = r;
return sign * strcmp(left->strings[index], right->strings[index]);
}
The question, of course, is "Where do `sign' and `index' come from?
They could be global variables, but this is undesirable for a number
of reasons: giving up thread safety, re-entrancy, modularity, etc.
The ideal thing would be to pass them as parameters, but qsort()
provides no mechanism for doing this: the signature of the comparison
function is fixed, and only allows two arguments to be passed. Now, I
hope, the purpose of the `context' parameter starts to become clear.
We can pass data of any type through `context', so the single function
becomes easy to write:
struct context
{
int sign;
int index;
};
int compare_ctxt(co nst void *l, const void *r, void *context)
{
const struct element *left = l, *right = r;
return context->sign * strcmp(left->strings[context->index],
right->strings[context->index]);
}
Having dispensed with the plethora of functions, there's no longer any
need for a runtime selection of comparison function, so the code that
invokes qsort() (or rather, qsort_s()) becomes much simpler as well.
Borrowing some syntax from C99:
qsort_s(element s,
sizeof elements / sizeof elements[0],
sizeof elements[0],
&(struct context){direct ion, index});
This is essentially the same as the concept of a "closure" in more
functionally-inclined languages, albeit quite a bit more explicit.
Jeremy.
