Home | History | Annotate | Download | only in stdlib
History log of /src/lib/libc/stdlib/qsort.c
RevisionDateAuthorComments
 1.24  02-Mar-2025  riastradh libc: New _r variants of heapsort, mergesort, qsort.

Also kheapsort_r for kernel/standalone use.

These variants allow the caller to pass a cookie through to the
comparison function, e.g. if you want to sort an array of indices
into a buffer.

qsort_r is new in POSIX.1-2024; the others are obvious analogues of
our nonstandard extensions for heapsort and mergesort.

PR lib/58931: qsort_r() missing
 1.23  19-May-2017  christos branches: 1.23.22;
The BSD qsort() performs tail recursion elimination on the second
side of the array being partitioned to save on stack space. Greater
savings can be gained by choosing recursion for the smaller side
of the partition and eliminating recursion for the larger side.
This also results in a small but measurable performance gain.
(From OpenBSD)
 1.22  26-May-2012  christos don't trigger diagassert for a null array with 0 elements or 0 elementsize.
 1.21  18-May-2011  dsl branches: 1.21.4;
Remove __P()
 1.20  01-Jun-2009  yamt qsort: remove the "switch to insertion sort" optimization because it
causes catastrophic performance for certain inputs.
 1.19  30-Jan-2009  lukem sign-compare fix
 1.18  11-Jan-2009  christos merge christos-time_t
 1.17  16-Nov-2008  ad Our qsort() is inappropriate for kernel use because it makes recursive
calls. Replace it with a kheapsort() function in kernel. Pointed out
by tron@.
 1.16  16-Nov-2008  ad Make qsort() available in libkern.
 1.15  11-Mar-2008  rmind branches: 1.15.10;
Use size_t to avoid overflow when sorting large arrays. While here, ANSIfy.
Obtained from FreeBSD (das@).
 1.14  24-Dec-2005  perry branches: 1.14.10; 1.14.16;
Remove leading __ from __(const|inline|signed|volatile) -- it is obsolete.
 1.13  07-Aug-2003  agc Move UCB-licensed code from 4-clause to 3-clause licence.

Patches provided by Joel Baker in PR 22280, verified by myself.
 1.12  20-Sep-1999  lukem back out the #ifdef _DIAGNOSTIC argument checks; too many people complained.
_DIAGASSERT() is still retained.
 1.11  16-Sep-1999  lukem * use _DIAGASSERT() to check pointer arguments against NULL and file
descriptors against -1 (as appropriate).
* add actual checks which to detect stuff that would trigger_DIAGASSERT(),
and attempt to return a sane error condition.
* knf some code
* remove some `register' decls.

the first two items result in the addition of code similar to the
following in various functions:

_DIAGASSERT(path != NULL)
#ifdef _DIAGNOSTIC
if (path == NULL) {
errno = EFAULT;
return (-1);
}
#endif
 1.10  15-Nov-1998  christos delint
 1.9  03-Feb-1998  perry remove obsolete register declarations
 1.8  13-Jul-1997  christos Add local.h for local prototypes.
Fix namespace issues for strtoq and strtouq
Fix gcc warnings.
Fix RCSID's
 1.7  19-Jun-1997  mikel avoid unportable arithmetic on void pointers
 1.6  19-Dec-1996  cgd use __inline and __asm, rather than inline and asm. By default (without -g)
lint won't accept the latter two, but will accept the former two as valid.
As far as gcc's concerned, they're the same.
 1.5  28-Dec-1995  thorpej New-style RCS ids.
 1.4  16-Jun-1994  mycroft Add RCS ids.
 1.3  26-Aug-1993  jtc Declare rcsid strings so they are stored in text segment.
 1.2  01-Aug-1993  mycroft Add RCS identifiers.
 1.1  21-Mar-1993  cgd branches: 1.1.1;
Initial revision
 1.1.1.2  16-Jun-1994  mycroft Import from 4.4-Lite.
 1.1.1.1  21-Mar-1993  cgd initial import of 386bsd-0.1 sources
 1.14.16.1  24-Mar-2008  keiichi sync with head.
 1.14.10.1  23-Mar-2008  matt sync with HEAD
 1.15.10.1  04-Jan-2009  christos merge with head.
 1.21.4.1  30-Oct-2012  yamt sync with head
 1.23.22.1  02-Aug-2025  perseant Sync with HEAD

RSS XML Feed