]> CyberLeo.Net >> Repos - FreeBSD/stable/10.git/commit
MFC r318514-r318515, r318517, r318917
authordelphij <delphij@ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f>
Wed, 31 May 2017 06:26:37 +0000 (06:26 +0000)
committerdelphij <delphij@ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f>
Wed, 31 May 2017 06:26:37 +0000 (06:26 +0000)
commit1e9d313b895c6630c6dbf532a07cb5712ff0d960
tree9f5388eeaa7cca71ef7d56fe90aa47d61739668c
parentd37b402f6905d41f847a077cc97c0b7dcdab25c7
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

git-svn-id: svn://svn.freebsd.org/base/stable/10@319291 ccf9f872-aa2e-dd11-9fc8-001c23d0bc1f
kerberos5/lib/libroken/Makefile
lib/libc/stdlib/qsort.c
sys/libkern/qsort.c