Bug 173

Summary: please consider a qsort_r function, similar to BSD
Product: glibc Reporter: Steven G. Johnson <stevenj>
Component: libcAssignee: GOTO Masanori <gotom>
Severity: enhancement CC: glibc-bugs
Priority: P2 Flags: fweimer: security-
Version: unspecified   
Target Milestone: ---   
Host: Target:
Build: Last reconfirmed:

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

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>
  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:


Comment 6 Ulrich Drepper 2008-06-25 18:03:58 UTC
Such a function has been added some time ago.