MFC r334928:
libc qsort(3): stop aliasing.

PR: 228780

Revert r330897:

This was intended to be a non-functional change. It wasn't. The commit
message was thus wrong. In addition it broke arm, and merged crypto
related code.

Revert with prejudice.

This revert skips files touched in r316370 since that commit was since
MFCed. This revert also skips files that require $FreeBSD$ property
changes.

Thank you to those who helped me get out of this mess including but not
limited to gonzo, kevans, rgrimes.

Requested by: gjb (re)

Partial merge of the SPDX changes

These changes are incomplete but are making it difficult
to determine what other changes can/should be merged.

No objections from: pfg

MFC r318514-r318515, r318517, r318917

r318514:
Use size_t.

Inspired by: OpenBSD src/lib/libc/stdlib/qsort.c,v 1.11

r318515:
The current qsort(3) implementation ignores the sizes of partitions, and
always perform recursion on the left partition, then use a tail call to
handle the right partition. In the worst case this could require O(N)
levels of recursions.

Reduce the possible recursion level to log2(N) by always recursing on the
smaller partition instead.

Obtained from: PostgreSQL 9d6077abf9d6efd992a59f05ef5aba981ea32096

r318517:
Sync qsort.c with userland r318515.

(Note that MIN macro is removed in favor of sys/param.h's version).

PR: 213922

r318917:
Disconnect heimdal version of qsort.c from build because we are already
using libc's version of qsort.

PR: bin/213922

Copy head@r302406 to stable/11 as part of the 11.0-RELEASE cycle.
Prune svn:mergeinfo from the new branch, as nothing has been merged
here.

Additional commits post-branch will follow.

Approved by: re (implicit)
Sponsored by: The FreeBSD Foundation

Use ANSI C prototypes. Eliminates -Wold-style-definition warnings.

qsort(3): small style(9) cleanups.

Basically spaces vs. tabs.
No functional change.

qsort(3): enhance to handle 32-bit aligned data on 64-bit systems

Implement a small enhancement to the original qsort implementation:
If the data is 32 bit aligned we can side-step the long type
version and use int instead.

The change brings a modest but significant improvement in
32 bit workloads.

Relnotes: yes

PR: 135718
Taken from: ache

Renumber clauses to reduce diffs to other versions

NetBSD, OpenBSD, and Android's Bionic number the clauses 1 through 3,
so follow suit to make comparison easier.

Changing 'r' to a size_t in the previous commit turned quicksort
into slowsort for some sequences because different parts of the
code used 'r' to store two different things, one of which was
signed. Clean things up by splitting 'r' into two variables, and
use a more meaningful name.

Use size_t to avoid overflow when sorting arrays larger than 2 GB.

PR: 111085
MFC after: 2 weeks

Per Regents of the University of Calfornia letter, remove advertising
clause.

# If I've done so improperly on a file, please let me know.

Implement C99's _Exit() interface.
Implement a version of qsort that provides a thunk to the comparison function.

Update manual pages.

Fix the style of the SCM ID's.
I believe have made all of libc .c's as consistent as possible.

Remove __P() usage.

Remove 'register' keyword.

$Id$ -> $FreeBSD$

Revert $FreeBSD$ to $Id$

Make the long-awaited change from $Id$ to $FreeBSD$

This will make a number of things easier in the future, as well as (finally!)
avoiding the Id-smashing problem which has plagued developers for so long.

Boy, I'm glad we're not using sup anymore. This update would have been
insane otherwise.

Don't depend in the kernel on the gcc feature of doing arithmetic on
pointers of type `void *'. Warn about this in future.

Don't include <sys/types.h> when it isn't used.

This commit covers most of the ANSI library functions. Many others only
need <sys/types.h> because they use u_xxx.

Added prototypes.

Remove trailing whitespace.

This commit was generated by cvs2svn to compensate for changes in r1573,
which included commits to RCS files with non-trunk default branches.

BSD 4.4 Lite Lib Sources