]>
Commit | Line | Data |
---|---|---|
320054e8 DG |
1 | // Copyright (c) 2015-2017 Nuxi, https://nuxi.nl/ |
2 | // | |
3 | // Redistribution and use in source and binary forms, with or without | |
4 | // modification, are permitted provided that the following conditions | |
5 | // are met: | |
6 | // 1. Redistributions of source code must retain the above copyright | |
7 | // notice, this list of conditions and the following disclaimer. | |
8 | // 2. Redistributions in binary form must reproduce the above copyright | |
9 | // notice, this list of conditions and the following disclaimer in the | |
10 | // documentation and/or other materials provided with the distribution. | |
11 | // | |
12 | // THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND | |
13 | // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | |
14 | // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE | |
15 | // ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE | |
16 | // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL | |
17 | // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS | |
18 | // OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) | |
19 | // HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT | |
20 | // LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY | |
21 | // OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF | |
22 | // SUCH DAMAGE. | |
23 | ||
24 | // <stdlib.h> - standard library definitions | |
25 | // | |
26 | // Extensions: | |
27 | // - MB_CUR_MAX_L(), mblen_l(), mbstowcs_l(), mbtowc_l(), wcstombs_l() | |
28 | // and wctomb_l(): | |
29 | // Regular functions always use the C locale. Available on many other | |
30 | // operating systems. | |
31 | // - alloca(): | |
32 | // Present on most other operating systems. | |
33 | // - arc4random(), arc4random_buf() and arc4random_uniform(): | |
34 | // Secure random number generator. Available on many other operating | |
35 | // systems. | |
36 | // - l64a_r(): | |
37 | // Thread-safe replacement for l64a(). Part of the SVID, 4th edition. | |
38 | // - qsort_r(): | |
39 | // Available on many other operating systems, although the prototype | |
40 | // is not consistent. This implementation is compatible with glibc. | |
41 | // It is expected that this version will be standardized in the future. | |
42 | // - reallocarray(): | |
43 | // Allows for reallocation of buffers without integer overflows. | |
44 | // | |
45 | // Features missing: | |
46 | // - initstate(), lcong48(), seed48(), setstate(), srand(), srand48() | |
47 | // and srandom(): | |
48 | // Randomizer is seeded securely by default. There is no need to seed | |
49 | // manually. | |
50 | // - WEXITSTATUS(), WIFEXITED(), WIFSIGNALED(), WIFSTOPPED(), WNOHANG, | |
51 | // WSTOPSIG(), WTERMSIG(), WUNTRACED: | |
52 | // Only useful if system() would actually work. | |
53 | // - l64a(): | |
54 | // Not thread-safe. Use l64a_r() instead. | |
55 | // - putenv(), setenv() and unsetenv(): | |
56 | // Environment variables are not available. | |
57 | // - grantpt(), posix_openpt(), ptsname() and unlockpt(): | |
58 | // Pseudo-terminals are not available. | |
59 | // - mkdtemp(), mkstemp() and realpath(): | |
60 | // Requires global filesystem namespace. | |
61 | // - setkey(): | |
62 | // Password database and encryption schemes not available. | |
63 | // - system(): | |
64 | // Requires a command shell. | |
65 | ||
66 | #ifndef _STDLIB_H_ | |
67 | #define _STDLIB_H_ | |
68 | ||
69 | #include <_/limits.h> | |
70 | #include <_/types.h> | |
71 | ||
72 | #ifdef __wasilibc_unmodified_upstream | |
73 | #define EXIT_FAILURE 1 | |
74 | #define EXIT_SUCCESS 0 | |
75 | ||
76 | #define RAND_MAX _INT_MAX | |
77 | ||
78 | #define NULL _NULL | |
79 | ||
80 | typedef struct { | |
81 | int quot; | |
82 | int rem; | |
83 | } div_t; | |
84 | ||
85 | typedef struct { | |
86 | long quot; | |
87 | long rem; | |
88 | } ldiv_t; | |
89 | ||
90 | typedef struct { | |
91 | long long quot; | |
92 | long long rem; | |
93 | } lldiv_t; | |
94 | ||
95 | #ifndef _SIZE_T_DECLARED | |
96 | typedef __size_t size_t; | |
97 | #define _SIZE_T_DECLARED | |
98 | #endif | |
99 | #ifndef _WCHAR_T_DECLARED | |
100 | typedef __wchar_t wchar_t; | |
101 | #define _WCHAR_T_DECLARED | |
102 | #endif | |
103 | ||
104 | #ifdef __wasilibc_unmodified_upstream | |
105 | // Process wide locale always uses ASCII. | |
106 | #define MB_CUR_MAX ((size_t)1) | |
107 | #endif | |
108 | ||
109 | // Keep existing code happy that assumes that MB_CUR_MAX_L is a macro. | |
110 | #define MB_CUR_MAX_L MB_CUR_MAX_L | |
111 | ||
112 | #define alloca(size) __builtin_alloca(size) | |
afbf94c3 | 113 | #endif |
320054e8 DG |
114 | |
115 | __BEGIN_DECLS | |
116 | _Noreturn void _Exit(int); | |
afbf94c3 | 117 | #ifdef __wasilibc_unmodified_upstream |
320054e8 DG |
118 | size_t MB_CUR_MAX_L(__locale_t); |
119 | long a64l(const char *); | |
120 | #endif | |
121 | _Noreturn void abort(void); | |
122 | #ifdef __wasilibc_unmodified_upstream | |
123 | int abs(int) __pure2; | |
124 | int at_quick_exit(void (*)(void)); | |
125 | int atexit(void (*)(void)); | |
126 | void *aligned_alloc(size_t, size_t); | |
127 | __uint32_t arc4random(void); | |
128 | void arc4random_buf(void *, size_t); | |
129 | __uint32_t arc4random_uniform(__uint32_t); | |
130 | double atof(const char *); | |
131 | int atoi(const char *); | |
132 | long atol(const char *); | |
133 | long long atoll(const char *); | |
134 | void *bsearch(const void *, const void *, size_t, size_t, | |
135 | int (*)(const void *, const void *)); | |
136 | #endif | |
137 | void *calloc(size_t, size_t); | |
138 | #ifdef __wasilibc_unmodified_upstream | |
139 | div_t div(int, int) __pure2; | |
140 | double drand48(void); | |
141 | double erand48(__uint16_t *); | |
142 | _Noreturn void exit(int); | |
143 | #endif | |
144 | void free(void *); | |
145 | #ifdef __wasilibc_unmodified_upstream | |
146 | char *getenv(const char *); | |
147 | int getsubopt(char **, char *const *, char **); | |
148 | long jrand48(__uint16_t *); | |
149 | int l64a_r(long, char *, int); | |
150 | long labs(long) __pure2; | |
151 | ldiv_t ldiv(long, long) __pure2; | |
152 | long long llabs(long long) __pure2; | |
153 | lldiv_t lldiv(long long, long long) __pure2; | |
154 | long lrand48(void); | |
155 | #endif | |
156 | void *malloc(size_t); | |
157 | #ifdef __wasilibc_unmodified_upstream | |
158 | int mblen(const char *, size_t); | |
159 | int mblen_l(const char *, size_t, __locale_t); | |
160 | size_t mbstowcs(wchar_t *__restrict, const char *__restrict, size_t); | |
161 | size_t mbstowcs_l(wchar_t *__restrict, const char *__restrict, size_t, | |
162 | __locale_t); | |
163 | int mbtowc(wchar_t *__restrict, const char *__restrict, size_t); | |
164 | int mbtowc_l(wchar_t *__restrict, const char *__restrict, size_t, __locale_t); | |
165 | long mrand48(void); | |
166 | long nrand48(__uint16_t *); | |
167 | int posix_memalign(void **, size_t, size_t); | |
168 | #endif | |
169 | void qsort(void *, size_t, size_t, int (*)(const void *, const void *)); | |
170 | #ifdef __wasilibc_unmodified_upstream | |
171 | void qsort_r(void *, size_t, size_t, | |
172 | int (*)(const void *, const void *, void *), void *); | |
173 | _Noreturn void quick_exit(int); | |
174 | int rand(void); | |
175 | long random(void); | |
176 | #endif | |
177 | void *realloc(void *, size_t); | |
178 | #ifdef __wasilibc_unmodified_upstream | |
179 | void *reallocarray(void *, size_t, size_t); | |
180 | double strtod(const char *__restrict, char **__restrict); | |
181 | double strtod_l(const char *__restrict, char **__restrict, __locale_t); | |
182 | float strtof(const char *__restrict, char **__restrict); | |
183 | float strtof_l(const char *__restrict, char **__restrict, __locale_t); | |
184 | long strtol(const char *__restrict, char **__restrict, int); | |
185 | long strtol_l(const char *__restrict, char **__restrict, int, __locale_t); | |
186 | long double strtold(const char *__restrict, char **__restrict); | |
187 | long double strtold_l(const char *__restrict, char **__restrict, __locale_t); | |
188 | long long strtoll(const char *__restrict, char **__restrict, int); | |
189 | long long strtoll_l(const char *__restrict, char **__restrict, int, __locale_t); | |
190 | unsigned long strtoul(const char *__restrict, char **__restrict, int); | |
191 | unsigned long strtoul_l(const char *__restrict, char **__restrict, int, | |
192 | __locale_t); | |
193 | unsigned long long strtoull(const char *__restrict, char **__restrict, int); | |
194 | unsigned long long strtoull_l(const char *__restrict, char **__restrict, int, | |
195 | __locale_t); | |
196 | size_t wcstombs(char *__restrict, const wchar_t *__restrict, size_t); | |
197 | size_t wcstombs_l(char *__restrict, const wchar_t *__restrict, size_t, | |
198 | __locale_t); | |
199 | int wctomb(char *, wchar_t); | |
200 | int wctomb_l(char *, wchar_t, __locale_t); | |
320054e8 | 201 | #endif |
afbf94c3 | 202 | __END_DECLS |
320054e8 DG |
203 | |
204 | #if _CLOUDLIBC_INLINE_FUNCTIONS | |
205 | #ifdef __wasilibc_unmodified_upstream | |
206 | static __inline double __atof(const char *__str) { | |
207 | return strtod(__str, NULL); | |
208 | } | |
209 | #define atof(str) __atof(str) | |
210 | ||
211 | static __inline int __atoi(const char *__str) { | |
212 | return (int)strtol(__str, NULL, 10); | |
213 | } | |
214 | #define atoi(str) __atoi(str) | |
215 | ||
216 | static __inline long __atol(const char *__str) { | |
217 | return strtol(__str, NULL, 10); | |
218 | } | |
219 | #define atol(str) __atol(str) | |
220 | ||
221 | static __inline long long __atoll(const char *__str) { | |
222 | return strtoll(__str, NULL, 10); | |
223 | } | |
224 | #define atoll(str) __atoll(str) | |
225 | ||
226 | static __inline int __abs(int __i) { | |
227 | return __i < 0 ? -__i : __i; | |
228 | } | |
229 | #define abs(i) __abs(i) | |
230 | ||
231 | static __inline long __labs(long __i) { | |
232 | return __i < 0 ? -__i : __i; | |
233 | } | |
234 | #define labs(i) __labs(i) | |
235 | ||
236 | static __inline long long __llabs(long long __i) { | |
237 | return __i < 0 ? -__i : __i; | |
238 | } | |
239 | #define llabs(i) __llabs(i) | |
240 | ||
241 | static __inline div_t __div(int __numer, int __denom) { | |
242 | div_t __res = {__numer / __denom, __numer % __denom}; | |
243 | return __res; | |
244 | } | |
245 | #define div(numer, denom) __div(numer, denom) | |
246 | ||
247 | static __inline ldiv_t __ldiv(long __numer, long __denom) { | |
248 | ldiv_t __res = {__numer / __denom, __numer % __denom}; | |
249 | return __res; | |
250 | } | |
251 | #define ldiv(numer, denom) __ldiv(numer, denom) | |
252 | ||
253 | static __inline lldiv_t __lldiv(long long __numer, long long __denom) { | |
254 | lldiv_t __res = {__numer / __denom, __numer % __denom}; | |
255 | return __res; | |
256 | } | |
257 | #define lldiv(numer, denom) __lldiv(numer, denom) | |
258 | ||
259 | static __inline void *__bsearch(const void *__key, const void *__base, | |
260 | size_t __nel, size_t __width, | |
261 | int (*__compar)(const void *, const void *)) { | |
262 | const char *__basep, *__obj; | |
263 | size_t __mid, __skip; | |
264 | int __cmp; | |
265 | ||
266 | __basep = (const char *)__base; | |
267 | while (__nel > 0) { | |
268 | // Pick pivot. | |
269 | __mid = __nel / 2; | |
270 | __obj = __basep + __mid * __width; | |
271 | __cmp = __compar(__key, (const void *)__obj); | |
272 | if (__cmp < 0) { | |
273 | // key < obj. Restrict search to top of the list. | |
274 | __nel = __mid; | |
275 | } else if (__cmp > 0) { | |
276 | // key > obj. Restrict search to bottom of the list. | |
277 | __skip = __mid + 1; | |
278 | __basep += __skip * __width; | |
279 | __nel -= __skip; | |
280 | } else { | |
281 | return (void *)__obj; | |
282 | } | |
283 | } | |
284 | return NULL; | |
285 | } | |
286 | #define bsearch(key, base, nel, width, compar) \ | |
287 | __preserve_const(void, __bsearch, base, key, base, nel, width, compar) | |
288 | #endif | |
289 | ||
290 | // qsort_r() implementation from Bentley and McIlroy's | |
291 | // "Engineering a Sort Function". | |
292 | // | |
293 | // This sorting function is inlined into this header, so that the | |
294 | // compiler can create an optimized version that takes the alignment and | |
295 | // size of the elements into account. It also reduces the overhead of | |
296 | // indirect function calls. | |
297 | ||
298 | static __inline void __qsort_r(void *, size_t, size_t, | |
299 | int (*)(const void *, const void *, void *), | |
300 | void *); | |
301 | ||
302 | static __inline size_t __qsort_min(size_t __a, size_t __b) { | |
303 | return __a < __b ? __a : __b; | |
304 | } | |
305 | ||
306 | // Swaps the contents of two buffers. | |
307 | static __inline void __qsort_swap(char *__a, char *__b, size_t __n) { | |
308 | char __t; | |
309 | ||
310 | while (__n-- > 0) { | |
311 | __t = *__a; | |
312 | *__a++ = *__b; | |
313 | *__b++ = __t; | |
314 | } | |
315 | } | |
316 | ||
317 | // Implementation of insertionsort for small lists. | |
318 | static __inline void __qsort_insertionsort( | |
319 | char *__a, size_t __nel, size_t __width, | |
320 | int (*__cmp)(const void *, const void *, void *), void *__thunk) { | |
321 | char *__pm, *__pl; | |
322 | ||
323 | for (__pm = __a + __width; __pm < __a + __nel * __width; __pm += __width) | |
324 | for (__pl = __pm; __pl > __a && __cmp(__pl - __width, __pl, __thunk) > 0; | |
325 | __pl -= __width) | |
326 | __qsort_swap(__pl, __pl - __width, __width); | |
327 | } | |
328 | ||
329 | // Returns the median of three elements. | |
330 | static __inline char *__qsort_med3(char *__a, char *__b, char *__c, | |
331 | int (*__cmp)(const void *, const void *, | |
332 | void *), | |
333 | void *__thunk) { | |
334 | return __cmp(__a, __b, __thunk) < 0 | |
335 | ? (__cmp(__b, __c, __thunk) < 0 | |
336 | ? __b | |
337 | : __cmp(__a, __c, __thunk) < 0 ? __c : __a) | |
338 | : (__cmp(__b, __c, __thunk) > 0 | |
339 | ? __b | |
340 | : __cmp(__a, __c, __thunk) > 0 ? __c : __a); | |
341 | } | |
342 | ||
343 | // Picks a pivot based on a pseudo-median of three or nine. | |
344 | // TODO(ed): Does this still guarantee an O(n log n) running time? | |
345 | static __inline char *__qsort_pickpivot(char *__a, size_t __nel, size_t __width, | |
346 | int (*__cmp)(const void *, const void *, | |
347 | void *), | |
348 | void *__thunk) { | |
349 | char *__pl, *__pm, *__pn; | |
350 | size_t __s; | |
351 | ||
352 | __pl = __a; | |
353 | __pm = __a + (__nel / 2) * __width; | |
354 | __pn = __a + (__nel - 1) * __width; | |
355 | if (__nel > 40) { | |
356 | __s = (__nel / 8) * __width; | |
357 | __pl = __qsort_med3(__pl, __pl + __s, __pl + 2 * __s, __cmp, __thunk); | |
358 | __pm = __qsort_med3(__pm - __s, __pm, __pm + __s, __cmp, __thunk); | |
359 | __pn = __qsort_med3(__pn - 2 * __s, __pn - __s, __pn, __cmp, __thunk); | |
360 | } | |
361 | return __qsort_med3(__pl, __pm, __pn, __cmp, __thunk); | |
362 | } | |
363 | ||
364 | // Implementation of quicksort for larger lists. | |
365 | static __inline void __qsort_quicksort(char *__a, size_t __nel, size_t __width, | |
366 | int (*__cmp)(const void *, const void *, | |
367 | void *), | |
368 | void *__thunk) { | |
369 | char *__pa, *__pb, *__pc, *__pd, *__pn; | |
370 | int __r; | |
371 | size_t __s; | |
372 | ||
373 | // Select pivot and move it to the head of the list. | |
374 | __qsort_swap(__a, __qsort_pickpivot(__a, __nel, __width, __cmp, __thunk), | |
375 | __width); | |
376 | ||
377 | // Perform partitioning. | |
378 | __pa = __pb = __a; | |
379 | __pc = __pd = __a + (__nel - 1) * __width; | |
380 | for (;;) { | |
381 | while (__pb <= __pc && (__r = __cmp(__pb, __a, __thunk)) <= 0) { | |
382 | if (__r == 0) { | |
383 | __qsort_swap(__pa, __pb, __width); | |
384 | __pa += __width; | |
385 | } | |
386 | __pb += __width; | |
387 | } | |
388 | while (__pc >= __pb && (__r = __cmp(__pc, __a, __thunk)) >= 0) { | |
389 | if (__r == 0) { | |
390 | __qsort_swap(__pc, __pd, __width); | |
391 | __pd -= __width; | |
392 | } | |
393 | __pc -= __width; | |
394 | } | |
395 | if (__pb > __pc) | |
396 | break; | |
397 | __qsort_swap(__pb, __pc, __width); | |
398 | __pb += __width; | |
399 | __pc -= __width; | |
400 | } | |
401 | ||
402 | // Store pivot between the two partitions. | |
403 | __pn = __a + __nel * __width; | |
404 | __s = __qsort_min((size_t)(__pa - __a), (size_t)(__pb - __pa)); | |
405 | __qsort_swap(__a, __pb - __s, __s); | |
406 | __s = __qsort_min((size_t)(__pd - __pc), (size_t)(__pn - __pd) - __width); | |
407 | __qsort_swap(__pb, __pn - __s, __s); | |
408 | ||
409 | // Sort the two partitions. | |
410 | __s = (size_t)(__pb - __pa); | |
411 | __qsort_r(__a, __s / __width, __width, __cmp, __thunk); | |
412 | __s = (size_t)(__pd - __pc); | |
413 | __qsort_r(__pn - __s, __s / __width, __width, __cmp, __thunk); | |
414 | } | |
415 | ||
416 | static __inline void __qsort_r(void *__base, size_t __nel, size_t __width, | |
417 | int (*__cmp)(const void *, const void *, void *), | |
418 | void *__thunk) { | |
419 | char *__a; | |
420 | ||
421 | __a = (char *)__base; | |
422 | if (__nel < 8) { | |
423 | __qsort_insertionsort(__a, __nel, __width, __cmp, __thunk); | |
424 | } else { | |
425 | __qsort_quicksort(__a, __nel, __width, __cmp, __thunk); | |
426 | } | |
427 | } | |
428 | #define qsort_r(base, nel, width, compar, thunk) \ | |
429 | __qsort_r(base, nel, width, compar, thunk) | |
430 | ||
431 | // qsort(): Call into qsort_r(), providing the callback as the thunk. | |
432 | // We assume that the optimizer is smart enough to simplify. | |
433 | ||
434 | static __inline int __qsort_cmp(const void *__a, const void *__b, | |
435 | void *__thunk) { | |
436 | return ((int (*)(const void *, const void *))__thunk)(__a, __b); | |
437 | } | |
438 | ||
439 | static __inline void __qsort(void *__base, size_t __nel, size_t __width, | |
440 | int (*__cmp)(const void *, const void *)) { | |
441 | qsort_r(__base, __nel, __width, __qsort_cmp, (void *)__cmp); | |
442 | } | |
443 | #define qsort(base, nel, width, compar) __qsort(base, nel, width, compar) | |
444 | #endif | |
445 | ||
446 | #endif |