summaryrefslogtreecommitdiff
path: root/src/stdlib
AgeCommit message (Collapse)AuthorLines
2011-04-29avoid crashing when nel==0 is passed to qsortRich Felker-2/+6
2011-04-27replace heap sort with smoothsort implementation by Valentin OchsRich Felker-32/+193
Smoothsort is an adaptive variant of heapsort. This version was written by Valentin Ochs (apo) specifically for inclusion in musl. I worked with him to get it working in O(1) memory usage even with giant array element widths, and to optimize it heavily for size and speed. It's still roughly 4 times as large as the old heap sort implementation, but roughly 20 times faster given an almost-sorted array of 1M elements (20 being the base-2 log of 1M), i.e. it really does reduce O(n log n) to O(n) in the mostly-sorted case. It's still somewhat slower than glibc's Introsort for random input, but now considerably faster than glibc when the input is already sorted, or mostly sorted.
2011-04-07fix broken unsigned comparison in wcstoumaxRich Felker-1/+1
2011-04-03fix various bugs in strtold:Rich Felker-10/+13
0e10000000000000000000000000000000 was setting ERANGE exponent char e/p was considered part of the match even if not followed by a valid decimal value "1e +10" was parsed as "1e+10" hex digits were misinterpreted as 0..5 instead of 10..15
2011-03-25fix all implicit conversion between signed/unsigned pointersRich Felker-4/+4
sadly the C language does not specify any such implicit conversion, so this is not a matter of just fixing warnings (as gcc treats it) but actual errors. i would like to revisit a number of these changes and possibly revise the types used to reduce the number of casts required.
2011-02-17don't compare elements with themselves during qsort.Rich Felker-1/+1
this is actually a workaround for a bug in gcc, whereby it asserts inequality of the keys being compared...
2011-02-14more header fixes, minor warning fixRich Felker-2/+4
2011-02-12initial check-in, version 0.5.0v0.5.0Rich Felker-0/+688