summaryrefslogtreecommitdiff
path: root/src/lib/libc/stdlib/qsort.c (follow)
Commit message (Collapse)AuthorAgeFilesLines
* Don't fall back to heapsort() if we would otherwise switch tomillert2017-05-301-7/+7
| | | | insertion sort (when the number of elements is < 7).
* Support swapping 32-bit aligned elements on 64-bit platforms.millert2017-05-241-22/+63
| | | | | Previously they would be swapped a byte at a time when sizeof(int) != sizeof(long). Idea from FreeBSD.
* Use David Musser's introsort algorithm to fall back to heapsort(3)millert2017-05-201-13/+43
| | | | | | when the recursion depth reaches 2*lg(n + 1). This avoids quicksort's quadratic behavior for pathological input without appreciably changing the average run time.
* The BSD qsort() performs tail recursion elimination on the secondmillert2017-05-171-10/+25
| | | | | | | | 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. OK otto@ schwarze@
* Remove unnecessary casts of 'a' to char * since 'a' is already char *.millert2017-01-041-10/+10
| | | | | This is a remnant from the original 4.4BSD code that had 'a' as void * in the function args. No binary change. OK bluhm@
* Wrap <stdlib.h> so that calls go direct and the symbols not in theguenther2015-09-131-1/+2
| | | | | | C standard are all weak. Apply __{BEGIN,END}_HIDDEN_DECLS to gdtoa{,imp}.h, hiding the arch-specific __strtorx, __ULtox_D2A, __strtorQ, __ULtoQ_D2A symbols.
* Disable the "switch to insertion sort" optimization to avoid quadraticmillert2014-06-121-13/+2
| | | | behavior for certain inputs. From NetBSD. OK tedu@
* Use size_t in appropriate places; fixes sorting of big arrays;otto2010-02-081-9/+10
| | | | | after the diff was written, I made it similar to the freebsd fix of the same code; pr6287 ok millert@ guenther@
* zap remaining rcsid.espie2005-08-081-4/+1
| | | | | | Kill old files that are no longer compiled. okay theo
* ansi + de-registerpat2005-03-301-16/+9
| | | | ok otto deraadt
* Remove the advertising clause in the UCB license which Berkeleymillert2003-06-021-6/+2
| | | | rescinded 22 July 1999. Proofed by myself and Theo.
* Manual cleanup of remaining userland __P use (excluding packages maintained ↵millert2002-02-171-2/+2
| | | | outside the tree)
* Part one of userland __P removal. Done with a simple regexp with some minor ↵millert2002-02-161-2/+2
| | | | hand editing to make comments line up correctly. Another pass is forthcoming that handles the cases that could not be done automatically.
* typecastoramaderaadt1997-06-201-10/+10
|
* Fix RCS idstholo1996-08-191-2/+1
| | | | Make sure everything uses {SYS,}LIBC_SCCS properly
* Cannot do operations on a void pointertholo1996-03-251-3/+4
|
* Add prototypes for internal functionstholo1996-03-251-5/+5
| | | | Change inline to __inline
* initial import of NetBSD treederaadt1995-10-181-0/+175
generated by cgit v1.2.3-55-g6feb (git 2.39.1) at 2025-04-26 16:36:59 +0000