summaryrefslogtreecommitdiff
path: root/src/stdlib
AgeCommit message (Collapse)AuthorFilesLines
2022-05-06fix constraint violation in qsort wrapper around qsort_rRich Felker1-1/+1
function pointer types do not implicitly convert to void *. a cast is required here.
2021-12-09fix mismatched signatures for strtod_l familyRich Felker1-7/+0
strtod_l, strtof_l, and strtold_l originally existed only as glibc-ABI-compat symbols. as noted in the commit which added them, 17a60f9d327c6f8b5707a06f9497d846e75c01f2, making them aliases for the non-_l functions was a hack and not appropriate if they ever became public API. unfortunately, commit 35eb1a1a9b97577e113240cd65bf9fc44b8df030 did make them public without undoing the hack. fix that now by moving the the _l functions to their own file as wrappers that just throw away the locale_t argument.
2021-09-23add qsort_r and make qsort a wrapper around itÉrico Nogueira2-17/+34
we make qsort a wrapper by providing a wrapper_cmp function that uses the extra argument as a function pointer. should be optimized to a tail call on most architectures, as long as it's built with -fomit-frame-pointer, so the performance impact should be minimal. to keep the git history clean, for now qsort_r is implemented in qsort.c and qsort is implemented in qsort_nr.c. qsort.c also received a few trivial cleanups, including replacing (*cmp)() calls with cmp(). qsort_nr.c contains only wrapper_cmp and qsort as a qsort_r wrapper itself.
2020-04-24fix undefined behavior in wcsto[ld] family functionsRich Felker2-4/+2
analogous to commit b287cd745c2243f8e5114331763a5a9813b5f6ee but for the custom FILE stream type the wcstol and wcstod family use. __toread could be used here as well, but there's a simple direct fix to make the buffer pointers initially valid for subtraction, so just do that to avoid pulling in stdio exit code in programs that don't use stdio.
2018-09-15fix undefined behavior in strto* via FILE buffer pointer abuseRich Felker2-12/+3
in order to produce FILE objects to pass to the intscan/floatscan backends without any (prohibitively costly) extra buffering layer, the strto* functions set the FILE's rend (read end) buffer pointer to an invalid value at the end of the address space, or SIZE_MAX/2 past the beginning of the string. this led to undefined behavior comparing and subtracting the end pointer with the buffer position pointer (rpos). the comparison issue is easily eliminated by using != instead of <. however the subtractions require nontrivial changes: previously, f->shcnt stored the count that would have been read if consuming the whole buffer, which required an end pointer for the buffer. the purpose for this was that it allowed reading it and adding rpos-rend at any time to get the actual count so far, and required no adjustment at the time of __shgetc (actual function call) since the call would only happen when reaching the end of the buffer. to get rid of the dependency on rend, instead offset shcnt by buf-rpos (start of buffer) at the time of last __shlim/__shgetc call. this makes for slightly more work in __shgetc the function, but for the inline macro it's still just as easy to compute the current count. since the scan helper interfaces used here are a big hack, comments are added to document their contracts and what's going on with their implementations.
2018-09-12reduce spurious inclusion of libc.hRich Felker2-2/+0
libc.h was intended to be a header for access to global libc state and related interfaces, but ended up included all over the place because it was the way to get the weak_alias macro. most of the inclusions removed here are places where weak_alias was needed. a few were recently introduced for hidden. some go all the way back to when libc.h defined CANCELPT_BEGIN and _END, and all (wrongly implemented) cancellation points had to include it. remaining spurious users are mostly callers of the LOCK/UNLOCK macros and files that use the LFS64 macro to define the awful *64 aliases. in a few places, new inclusion of libc.h is added because several internal headers no longer implicitly include libc.h. declarations for __lockfile and __unlockfile are moved from libc.h to stdio_impl.h so that the latter does not need libc.h. putting them in libc.h made no sense at all, since the macros in stdio_impl.h are needed to use them correctly anyway.
2018-07-23bsearch: simplify and optimizeFangrui Song1-6/+6
maintainer's note: the key observation here is that the compared element is the first slot of the second ceil(half) of the array, and thus can be removed for further comparison when it does not match, so that we descend into the second ceil(half)-1 rather than ceil(half) elements. this change ensures that nel strictly decreases with each iteration, so that the case of != but nel==1 does not need to be special-cased anymore.
2018-02-25add public interface headers to implementation filesRich Felker3-0/+6
general policy is that all source files defining a public API or an ABI mechanism referenced by a public header should include the public header that declares the interface, so that the compiler or analysis tools can check the consistency of the declarations. Alexander Monakov pointed out a number of violations of this principle a few years back. fix them now.
2017-08-11qsort: add a short comment about the algorithmLeah Neukirchen1-0/+3
2013-12-12include cleanups: remove unused headers and add feature test macrosSzabolcs Nagy3-0/+3
2013-08-07make fcvt decimal point location for zero make more senseRich Felker1-1/+1
the (obsolete) standard allows either 0 or 1 for the decimal point location in this case, but since the number of zero digits returned in the output string (in this implementation) is one more than the number of digits the caller requested, it makes sense for the decimal point to be logically "after" the first digit. in a sense, this change goes with the previous commit which fixed the value of the decimal point location for non-zero inputs.
2013-08-07fix ecvt/fcvt decimal point position outputRich Felker1-1/+1
these functions are obsolete and have no modern standard. the text in SUSv2 is highly ambiguous, specifying that "negative means to the left of the returned digits", which suggested to me that 0 would mean to the right of the first digit. however, this does not agree with historic practice, and the Linux man pages are more clear, specifying that a negative value means "that the decimal point is to the left of the start of the string" (in which case, 0 would mean the start of the string, in accordance with historic practice).
2013-07-26add ABI symbols for strtol family functionsRich Felker1-0/+8
these odd names are actually generated by mess in glibc's stdlib.h, so any glibc-linked program using strtol needs them to run against musl.
2013-07-24add _l versions of strtod family functions, purely as aliasesRich Felker1-0/+8
this is a cheat since the _l versions take an extra argument, but since these functions are only here for ABI purposes, it doesn't really matter as long as the ABI matches. if the non-__-prefixed versions are eventually made public, they should proabably be real functions rather than hacks like this.
2012-11-08clean up stdio_impl.hRich Felker3-0/+8
this header evolved to facilitate the extremely lazy practice of omitting explicit includes of the necessary headers in individual stdio source files; not only was this sloppy, but it also increased build time. now, stdio_impl.h is only including the headers it needs for its own use; any further headers needed by source files are included directly where needed.
2012-09-06use restrict everywhere it's required by c99 and/or posix 2008Rich Felker4-18/+18
to deal with the fact that the public headers may be used with pre-c99 compilers, __restrict is used in place of restrict, and defined appropriately for any supported compiler. we also avoid the form [restrict] since older versions of gcc rejected it due to a bug in the original c99 standard, and instead use the form *restrict.
2012-04-19further fixes to leading space issue (forgot the wide versions)Rich Felker2-5/+9
2012-04-19fix really bad breakage in strtol, etc.: failure to accept leading spacesRich Felker1-5/+3
2012-04-16implement wcstod and familyRich Felker1-0/+61
not heavily tested but these functions appear to work correctly
2012-04-16avoid hitting eof in wcstolRich Felker1-2/+3
shunget cannot unget eof status, causing wcstol to leave endptr pointing to the wrong place when scanning, for example, L"0x". cheap fix is to make the read function provide an infinite stream of bogus characters rather than eof. really this is something of a design flaw in how the shgetc system is used for strto* and wcsto*; in the long term, I believe multi-character unget should be scrapped and replaced with a function that can subtract from the f->shcnt counter.
2012-04-16use the new integer parser (FILE/shgetc based) for strtol, wcstol, etc.Rich Felker12-278/+120
2012-04-10add "scan helper getc" and rework strtod, etc. to use itRich Felker1-2/+4
the immediate benefit is a significant debloating of the float parsing code by moving the responsibility for keeping track of the number of characters read to a different module. by linking shgetc with the stdio buffer logic, counting logic is defered to buffer refill time, keeping the calls to shgetc fast and light. in the future, shgetc will also be useful for integrating the new float code with scanf, which needs to not only count the characters consumed, but also limit the number of characters read based on field width specifiers. shgetc may also become a useful tool for simplifying the integer parsing code.
2012-04-10unify strtof/strtod/strtold wrappers and fix initial whitespace issueRich Felker3-34/+21
2012-04-10new floating point parser/converterRich Felker3-94/+31
this version is intended to be fully conformant to the ISO C, POSIX, and IEEE standards for conversion of decimal/hex floating point strings to float, double, and long double (ld64 or ld80 only at present) values. in particular, all results are intended to be rounded correctly according to the current rounding mode. further, this implementation aims to set the floating point underflow, overflow, and inexact flags to reflect the conversion performed. a moderate amount of testing has been performed (by nsz and myself) prior to integration of the code in musl, but it still may have bugs. so far, only strto(d|ld|f) use the new code. scanf integration will be done as a separate commit, and i will add implementations of the wide character functions later.
2012-03-13first commit of the new libm!Rich Felker3-83/+0
thanks to the hard work of Szabolcs Nagy (nsz), identifying the best (from correctness and license standpoint) implementations from freebsd and openbsd and cleaning them up! musl should now fully support c99 float and long double math functions, and has near-complete complex math support. tgmath should also work (fully on gcc-compatible compilers, and mostly on any c99 compiler). based largely on commit 0376d44a890fea261506f1fc63833e7a686dca19 from nsz's libm git repo, with some additions (dummy versions of a few missing long double complex functions, etc.) by me. various cleanups still need to be made, including re-adding (if they're correct) some asm functions that were dropped.
2012-02-06add deprecated (removed from posix) [efg]cvt() functionsRich Felker3-0/+52
these have not been heavily tested, but they should work as described in the old standards. probably broken for non-finite values...
2011-11-10fix signed overflows at most-negative values in ato(i|l|ll)Rich Felker3-6/+9
patch by Pascal Cuoq (with minor tweaks to comments)
2011-09-19fix incorrect long double parameters on arm (and other future ports)Rich Felker1-0/+12
this was the cause of crashes in printf when attempting to print floating point values.
2011-09-05fix incorrect overflow errors on strtoul, etc.Rich Felker4-8/+20
2011-07-14fix various bugs in new integer parser frameworkRich Felker4-6/+8
1. my interpretation of subject sequence definition was wrong. adjust parser to conform to the standard. 2. some code for handling tail overflow case was missing (forgot to finish writing it). 3. typo (= instead of ==) caused ERANGE to wrongly behave like EINVAL
2011-07-14fix wcsto[iu]max with high charactersRich Felker2-4/+2
stopping without letting the parser see a stop character prevented getting a result. so treat all high chars as the null character and pass them into the parser. also eliminated ugly tmp var using compound literals.
2011-07-14new restartable integer parsing framework.Rich Felker4-156/+81
this fixes a number of bugs in integer parsing due to lazy haphazard wrapping, as well as some misinterpretations of the standard. the new parser is able to work character-at-a-time or on whole strings, making it easy to support the wide functions without unbounded space for conversion. it will also be possible to update scanf to use the new parser.
2011-04-29avoid crashing when nel==0 is passed to qsortRich Felker1-2/+6
2011-04-27replace heap sort with smoothsort implementation by Valentin OchsRich Felker1-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 Felker1-1/+1
2011-04-03fix various bugs in strtold:Rich Felker1-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 Felker2-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 Felker1-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 Felker3-2/+4
2011-02-12initial check-in, version 0.5.0v0.5.0Rich Felker32-0/+688