|Summary:||please consider a qsort_r function, similar to BSD|
|Product:||glibc||Reporter:||Steven G. Johnson <stevenj>|
|Component:||libc||Assignee:||GOTO Masanori <gotom>|
Description Steven G. Johnson 2004-05-19 07:25:38 UTC
As you know, qsort has a deficiency in that, if you need to pass additional state to the comparison function, you must do so through global variables. This means that qsort cannot be called from a library function that is intended to be re-entrant. As you probably know, some BSD variants have a qsort_r function in which the comparison function takes an extra void* argument, which solves the problem. (A similar problem and solution would apply to bsearch etc.) Perhaps you've already considered and rejected this possibility (fearing code bloat?), but I couldn't find any record of such a discussion on Google, so I thought I'd file a bug here. Thanks for your consideration.
Comment 1 Petter Reinholdtsen 2004-05-21 17:41:55 UTC
The FreeBSD manual page for qsort_r() is available from <URL: http://www.freebsd.org/cgi/man.cgi?query=qsort >. It specifies #include <stdlib.h> [...] void qsort_r(void *base, size_t nmemb, size_t size, void *thunk, int (*compar)(void *, const void *, const void *)); [...] The qsort_r() function behaves identically to qsort(), except that it takes an additional argument, thunk, which is passed unchanged as the first argument to function pointed to compar. This allows the comparison function to access additional data without using global variables, and thus qsort_r() is suitable for use in functions which must be reentrant.
Comment 2 Jakub Jelinek 2004-05-25 20:43:36 UTC
There are already now ways how to do that even without qsort_r: a) store the state to __thread variables b) use GCC nested functions c) use pthread_getspecific d) use locking around the qsort invocation
Comment 3 Ulrich Drepper 2004-08-09 07:45:01 UTC
I'll suspend this bug. I haven't seen any interest in this code ever and as Jakub pointed out, there are plenty of methods to make things work with qsort. Especially on reasonable systems which have __thread support. If there should be more interest (which can be demonstrated!) the bug can be activated again. Alternatively, you can try to get the function standardized by POSIX.
Comment 4 Enrique Metzel 2008-05-04 00:55:11 UTC
I think this should be re-opened. Contrary to the argument presented in this bug, it is actually really hard to properly implement qsort_r on top of qsort (short of using a trampoline or entirely re-coding quicksort). Rationale against the arguments presented: >There are already now ways how to do that even without qsort_r: >a) store the state to __thread variables This may be thread safe, but it is not re-entrant, which is what the original poster needed (and what I find myself needing as well) >b) use GCC nested functions This obliges you to write GCC specific code. As elegant as this solution may be, and as much as we all like GCC, this is a non standard feature and makes your code unportable to non-GCC environments. >c) use pthread_getspecific Again an ugly band-aid (in this case a global variable hidden in a posix thread function). Depending on your OS and implementation of posix threads, this might also very well be dog slow. Finally: this is again not reentrant. d) use locking around the qsort invocation Again: not re-entrant. If the compare function finds itself in need of sorting against a second key to get an answer, you're dead in the water. Please, please, please re-consider making qsort_r part of glibc.
Comment 5 Enrique Metzel 2008-05-04 01:13:42 UTC
Also, re-reading the comment Ulrich made about why there should be interest in this function, you may want to take a look at how glib had to solve the problem. They basically had no choice but to re-implement quicksort: http://www.google.com/codesearch?hl=en&q=+g_qsort_with_data+show:KCTGLOhTfYQ:Un7Mc9xTPvU:xo7tCazfQxw&sa=N&cd=1&ct=rc&cs_p=ftp://ftp.gtk.org/pub/gtk/v2.4/glib-2.4.1.tar.bz2&cs_f=glib-2.4.1/glib/gqsort.c#first
Comment 6 Ulrich Drepper 2008-06-25 18:03:58 UTC
Such a function has been added some time ago.