diff options
Diffstat (limited to 'nuttx/libc/stdlib')
| -rw-r--r-- | nuttx/libc/stdlib/Make.defs | 44 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_abort.c | 121 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_abs.c | 54 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_imaxabs.c | 54 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_labs.c | 54 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_llabs.c | 57 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_qsort.c | 238 | ||||
| -rw-r--r-- | nuttx/libc/stdlib/lib_rand.c | 277 |
8 files changed, 899 insertions, 0 deletions
diff --git a/nuttx/libc/stdlib/Make.defs b/nuttx/libc/stdlib/Make.defs new file mode 100644 index 000000000..dcc4dab26 --- /dev/null +++ b/nuttx/libc/stdlib/Make.defs @@ -0,0 +1,44 @@ +############################################################################ +# libc/stdlib/Make.defs +# +# Copyright (C) 2012 Gregory Nutt. All rights reserved. +# Author: Gregory Nutt <gnutt@nuttx.org> +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions +# are met: +# +# 1. Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# 2. Redistributions in binary form must reproduce the above copyright +# notice, this list of conditions and the following disclaimer in +# the documentation and/or other materials provided with the +# distribution. +# 3. Neither the name NuttX nor the names of its contributors may be +# used to endorse or promote products derived from this software +# without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS +# FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE +# COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, +# INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, +# BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS +# OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED +# AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN +# ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +# POSSIBILITY OF SUCH DAMAGE. +# +############################################################################ + +# Add the stdlib C files to the build + +CSRCS += lib_abs.c lib_abort.c lib_imaxabs.c lib_labs.c lib_llabs.c \ + lib_rand.c lib_qsort.c + +# Add the stdlib directory to the build + +DEPPATH += --dep-path stdlib +VPATH += :stdlib diff --git a/nuttx/libc/stdlib/lib_abort.c b/nuttx/libc/stdlib/lib_abort.c new file mode 100644 index 000000000..1c7442c7f --- /dev/null +++ b/nuttx/libc/stdlib/lib_abort.c @@ -0,0 +1,121 @@ +/************************************************************************ + * libc/stdlib/lib_abort.c + * + * Copyright (C) 2007, 2009, 2011-2012 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name NuttX nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ************************************************************************/ + +/************************************************************************ + * Included Files + ************************************************************************/ + +#include <nuttx/config.h> + +#include <stdlib.h> +#include <pthread.h> + +/************************************************************************ + * Pre-processor Definitions + ************************************************************************/ + +/************************************************************************ + * Private Type Declarations + ************************************************************************/ + +/************************************************************************ + * Global Variables + ************************************************************************/ + +/************************************************************************ + * Private Variables + ************************************************************************/ + +/************************************************************************ + * Private Function Prototypes + ************************************************************************/ + +/************************************************************************ + * Private Functions + ************************************************************************/ + +/************************************************************************ + * Public Functions + ************************************************************************/ + +/************************************************************************ + * Name: Abort + * + * Description: + * The abort() first unblocks the SIGABRT signal, and then raises that + * signal for the calling process. This results in the abnormal + * termination of the process unless the SIGABRT signal is caught and + * the signal handler does not return. + * + * If the abort() function causes process termination, all open + * streams are closed and flushed. + * + * If the SIGABRT signal is ignored, or caught by a handler that + * returns, the abort() function will still terminate the process. + * It does this by restoring the default disposition for SIGABRT and + * then raising the signal for a second time. + * + * Input parameters: + * None + * + * Returned Value: + * This function does not return, + * + ************************************************************************/ + +void abort(void) +{ + /* NuttX does not support standard signal functionality (like the + * behavior of the SIGABRT signal). So no attempt is made to provide + * a conformant version of abort() at this time. This version does not + * signal the calling thread all. + * + * Note that pthread_exit() is called instead of exit(). That is because + * we do no know if abort was called from a pthread or a normal thread + * (we could find out, of course). If abort() is called from a non-pthread, + * then pthread_exit() should fail and fall back to call exit() anyway. + * + * If exit() is called (either below or via pthread_exit()), then exit() + * will flush and close all open files and terminate the thread. If this + * function was called from a pthread, then pthread_exit() will complete + * any joins, but will not flush or close any streams. + */ + +#ifdef CONFIG_DISABLE_PTHREAD + exit(EXIT_FAILURE); +#else + pthread_exit(NULL); +#endif +} diff --git a/nuttx/libc/stdlib/lib_abs.c b/nuttx/libc/stdlib/lib_abs.c new file mode 100644 index 000000000..a4e4ec669 --- /dev/null +++ b/nuttx/libc/stdlib/lib_abs.c @@ -0,0 +1,54 @@ +/************************************************************************ + * libc/stdlib/lib_abs.c + * + * Copyright (C) 2010-2011 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name NuttX nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ************************************************************************/ + +/************************************************************************ + * Included Files + ************************************************************************/ + +#include <nuttx/config.h> +#include <stdlib.h> + +/************************************************************************ + * Global Functions + ************************************************************************/ + +int abs(int j) +{ + if (j < 0) + { + j = -j; + } + return j; +} diff --git a/nuttx/libc/stdlib/lib_imaxabs.c b/nuttx/libc/stdlib/lib_imaxabs.c new file mode 100644 index 000000000..d36504372 --- /dev/null +++ b/nuttx/libc/stdlib/lib_imaxabs.c @@ -0,0 +1,54 @@ +/************************************************************************ + * libc/stdlib//lib_abs.c + * + * Copyright (C) 2010-2011 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name NuttX nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ************************************************************************/ + +/************************************************************************ + * Included Files + ************************************************************************/ + +#include <nuttx/config.h> +#include <inttypes.h> + +/************************************************************************ + * Global Functions + ************************************************************************/ + +intmax_t imaxabs(intmax_t j) +{ + if (j < 0) + { + j = -j; + } + return j; +} diff --git a/nuttx/libc/stdlib/lib_labs.c b/nuttx/libc/stdlib/lib_labs.c new file mode 100644 index 000000000..7cf92a0a1 --- /dev/null +++ b/nuttx/libc/stdlib/lib_labs.c @@ -0,0 +1,54 @@ +/************************************************************************ + * libc/stdlib/lib_labs.c + * + * Copyright (C) 2010-2011 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name NuttX nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ************************************************************************/ + +/************************************************************************ + * Included Files + ************************************************************************/ + +#include <nuttx/config.h> +#include <stdlib.h> + +/************************************************************************ + * Global Functions + ************************************************************************/ + +long int labs(long int j) +{ + if (j < 0) + { + j = -j; + } + return j; +} diff --git a/nuttx/libc/stdlib/lib_llabs.c b/nuttx/libc/stdlib/lib_llabs.c new file mode 100644 index 000000000..3630d1716 --- /dev/null +++ b/nuttx/libc/stdlib/lib_llabs.c @@ -0,0 +1,57 @@ +/************************************************************************ + * libc/stdlib/lib_llabs.c + * + * Copyright (C) 2010-2011 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name NuttX nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ************************************************************************/ + +/************************************************************************ + * Included Files + ************************************************************************/ + +#include <nuttx/config.h> +#include <nuttx/compiler.h> +#include <stdlib.h> + +/************************************************************************ + * Global Functions + ************************************************************************/ + +#ifdef CONFIG_HAVE_LONG_LONG +long long int llabs(long long int j) +{ + if (j < 0) + { + j = -j; + } + return j; +} +#endif diff --git a/nuttx/libc/stdlib/lib_qsort.c b/nuttx/libc/stdlib/lib_qsort.c new file mode 100644 index 000000000..021e782d4 --- /dev/null +++ b/nuttx/libc/stdlib/lib_qsort.c @@ -0,0 +1,238 @@ +/**************************************************************************** + * libc/stdlib/lib_qsort.c + * + * Copyright (C) 2007, 2009, 2011 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Leveraged from: + * + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <nuttx/config.h> + +#include <sys/types.h> +#include <stdlib.h> + +/**************************************************************************** + * Preprocessor Definitions + ****************************************************************************/ + +#define min(a, b) (a) < (b) ? a : b + +#define swapcode(TYPE, parmi, parmj, n) \ + { \ + long i = (n) / sizeof (TYPE); \ + register TYPE *pi = (TYPE *) (parmi); \ + register TYPE *pj = (TYPE *) (parmj); \ + do { \ + register TYPE t = *pi; \ + *pi++ = *pj; \ + *pj++ = t; \ + } while (--i > 0); \ + } + +#define SWAPINIT(a, size) \ + swaptype = ((char *)a - (char *)0) % sizeof(long) || \ + size % sizeof(long) ? 2 : size == sizeof(long)? 0 : 1; + +#define swap(a, b) \ + if (swaptype == 0) \ + { \ + long t = *(long *)(a); \ + *(long *)(a) = *(long *)(b); \ + *(long *)(b) = t; \ + } \ + else \ + { \ + swapfunc(a, b, size, swaptype); \ + } + +#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) + +/**************************************************************************** + * Private Function Prototypes + ****************************************************************************/ + +static inline void swapfunc(char *a, char *b, int n, int swaptype); +static inline char *med3(char *a, char *b, char *c, + int (*compar)(const void *, const void *)); + +/**************************************************************************** + * Private Functions + ****************************************************************************/ + +static inline void swapfunc(char *a, char *b, int n, int swaptype) +{ + if(swaptype <= 1) + { + swapcode(long, a, b, n) + } + else + { + swapcode(char, a, b, n) + } +} + +static inline char *med3(char *a, char *b, char *c, + int (*compar)(const void *, const void *)) +{ + return compar(a, b) < 0 ? + (compar(b, c) < 0 ? b : (compar(a, c) < 0 ? c : a )) + :(compar(b, c) > 0 ? b : (compar(a, c) < 0 ? a : c )); +} + +/**************************************************************************** + * Public Function + ****************************************************************************/ + +/**************************************************************************** + * Name: qsort + * + * Description: + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". + * + ****************************************************************************/ + +void qsort(void *base, size_t nmemb, size_t size, + int(*compar)(const void *, const void *)) +{ + char *pa, *pb, *pc, *pd, *pl, *pm, *pn; + int d, r, swaptype, swap_cnt; + +loop: + SWAPINIT(base, size); + swap_cnt = 0; + if (nmemb < 7) + { + for (pm = (char *) base + size; pm < (char *) base + nmemb * size; pm += size) + { + for (pl = pm; pl > (char *) base && compar(pl - size, pl) > 0; pl -= size) + { + swap(pl, pl - size); + } + } + return; + } + + pm = (char *) base + (nmemb / 2) * size; + if (nmemb > 7) + { + pl = base; + pn = (char *) base + (nmemb - 1) * size; + if (nmemb > 40) + { + d = (nmemb / 8) * size; + pl = med3(pl, pl + d, pl + 2 * d, compar); + pm = med3(pm - d, pm, pm + d, compar); + pn = med3(pn - 2 * d, pn - d, pn, compar); + } + pm = med3(pl, pm, pn, compar); + } + swap(base, pm); + pa = pb = (char *) base + size; + + pc = pd = (char *) base + (nmemb - 1) * size; + for (;;) + { + while (pb <= pc && (r = compar(pb, base)) <= 0) + { + if (r == 0) + { + swap_cnt = 1; + swap(pa, pb); + pa += size; + } + pb += size; + } + while (pb <= pc && (r = compar(pc, base)) >= 0) + { + if (r == 0) + { + swap_cnt = 1; + swap(pc, pd); + pd -= size; + } + pc -= size; + } + + if (pb > pc) + { + break; + } + + swap(pb, pc); + swap_cnt = 1; + pb += size; + pc -= size; + } + + if (swap_cnt == 0) + { + /* Switch to insertion sort */ + + for (pm = (char *) base + size; pm < (char *) base + nmemb * size; pm += size) + { + for (pl = pm; pl > (char *) base && compar(pl - size, pl) > 0; pl -= size) + { + swap(pl, pl - size); + } + } + return; + } + + pn = (char *) base + nmemb * size; + r = min(pa - (char *)base, pb - pa); + vecswap(base, pb - r, r); + r = min(pd - pc, pn - pd - size); + vecswap(pb, pn - r, r); + + if ((r = pb - pa) > size) + { + qsort(base, r / size, size, compar); + } + + if ((r = pd - pc) > size) + { + /* Iterate rather than recurse to save stack space */ + base = pn - r; + nmemb = r / size; + goto loop; + } +} + diff --git a/nuttx/libc/stdlib/lib_rand.c b/nuttx/libc/stdlib/lib_rand.c new file mode 100644 index 000000000..453a4537a --- /dev/null +++ b/nuttx/libc/stdlib/lib_rand.c @@ -0,0 +1,277 @@ +/**************************************************************************** + * libc/stdlib/lib_rand.c + * + * Copyright (C) 2007, 2011 Gregory Nutt. All rights reserved. + * Author: Gregory Nutt <gnutt@nuttx.org> + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in + * the documentation and/or other materials provided with the + * distribution. + * 3. Neither the name NuttX nor the names of its contributors may be + * used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, + * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS + * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED + * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN + * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + * + ****************************************************************************/ + +/**************************************************************************** + * Included Files + ****************************************************************************/ + +#include <sys/types.h> +#include <stdlib.h> + +/**************************************************************************** + * Pre-processor Definitions + ****************************************************************************/ +/* First, second, and thired order congruential generators are supported */ + +#ifndef CONFIG_LIB_RAND_ORDER +# define CONFIG_LIB_RAND_ORDER 1 +#endif + +#if CONFIG_LIB_RAND_ORDER > 3 +# undef CONFIG_LIB_RAND_ORDER +# define CONFIG_LIB_RAND_ORDER 3 +#endif + +/* Values needed by the random number generator */ + +#define RND1_CONSTK 470001 +#define RND1_CONSTP 999563 +#define RND2_CONSTK1 366528 +#define RND2_CONSTK2 508531 +#define RND2_CONSTP 998917 +#define RND3_CONSTK1 360137 +#define RND3_CONSTK2 519815 +#define RND3_CONSTK3 616087 +#define RND3_CONSTP 997783 + +/**************************************************************************** + * Private Function Prototypes + ****************************************************************************/ + +static unsigned int nrand(unsigned int nLimit); + +/* First order congruential generators */ + +static inline unsigned long fgenerate1(void); +#if (CONFIG_LIB_RAND_ORDER == 1) +static double_t frand1(void); +#endif + +/* Second order congruential generators */ + +#if (CONFIG_LIB_RAND_ORDER > 1) +static inline unsigned long fgenerate2(void); +#if (CONFIG_LIB_RAND_ORDER == 2) +static double_t frand2(void); +#endif + +/* Third order congruential generators */ + +#if (CONFIG_LIB_RAND_ORDER > 2) +static inline unsigned long fgenerate3(void); +static double_t frand3(void); +#endif +#endif + +/**************************************************************************** + * Private Data + ****************************************************************************/ + +static unsigned long g_randint1; +#if (CONFIG_LIB_RAND_ORDER > 1) +static unsigned long g_randint2; +#if (CONFIG_LIB_RAND_ORDER > 2) +static unsigned long g_randint3; +#endif +#endif + +/**************************************************************************** + * Private Functions + ****************************************************************************/ + +static unsigned int nrand(unsigned int nLimit) +{ + unsigned long result; + double_t ratio; + + /* Loop to be sure a legal random number is generated */ + + do + { + /* Get a random integer in the requested range */ + +#if (CONFIG_LIB_RAND_ORDER == 1) + ratio = frand1(); +#elif (CONFIG_LIB_RAND_ORDER == 2) + ratio = frand2(); +#else /* if (CONFIG_LIB_RAND_ORDER > 2) */ + ratio = frand3(); +#endif + + /* Then, produce the return-able value */ + + result = (unsigned long)(((double_t)nLimit) * ratio); + } + while (result >= (unsigned long)nLimit); + + return (unsigned int)result; +} + +/* First order congruential generators */ + +static inline unsigned long fgenerate1(void) +{ + unsigned long randint; + + /* First order congruential generator. One may be added to the result of the + * generated value to avoid the value zero. This would be fatal for the + * first order random number generator. + */ + + randint = (RND1_CONSTK * g_randint1) % RND1_CONSTP; + g_randint1 = (randint == 0 ? 1 : randint); + return randint; +} + +#if (CONFIG_LIB_RAND_ORDER == 1) +static double_t frand1(void) +{ + /* First order congruential generator. */ + + unsigned long randint = fgenerate1(); + + /* Construct an floating point value in the range from 0.0 up to 1.0 */ + + return ((double_t)randint) / ((double_t)RND1_CONSTP); +} +#endif + +/* Second order congruential generators */ + +#if (CONFIG_LIB_RAND_ORDER > 1) +static inline unsigned long fgenerate2(void) +{ + unsigned long randint; + + /* Second order congruential generator. */ + + randint = (RND2_CONSTK1 * g_randint1 + + RND2_CONSTK2 * g_randint2) % RND2_CONSTP; + + g_randint2 = g_randint1; + g_randint1 = randint; + + /* We cannot permit both values to become zero. That would be fatal for the + * second order random number generator. + */ + + if (g_randint2 == 0 && g_randint1 == 0) + { + g_randint2 = 1; + } + + return randint; +} + +#if (CONFIG_LIB_RAND_ORDER == 2) +static double_t frand2(void) +{ + /* Second order congruential generator */ + + unsigned long randint = fgenerate2(); + + /* Construct an floating point value in the range from 0.0 up to 1.0 */ + + return ((double_t)randint) / ((double_t)RND2_CONSTP); +} +#endif + +/* Third order congruential generators */ + +#if (CONFIG_LIB_RAND_ORDER > 2) +static inline unsigned long fgenerate3(void) +{ + unsigned long randint; + + /* Third order congruential generator. */ + + randint = (RND3_CONSTK1 * g_randint1 + + RND3_CONSTK2 * g_randint2 + + RND3_CONSTK2 * g_randint3) % RND3_CONSTP; + + g_randint3 = g_randint2; + g_randint2 = g_randint1; + g_randint1 = randint; + + /* We cannot permit all three values to become zero. That would be fatal for the + * third order random number generator. + */ + + if (g_randint3 == 0 && g_randint2 == 0 && g_randint1 == 0) + { + g_randint3 = 1; + } + + return randint; +} + +static double_t frand3(void) +{ + /* Third order congruential generator */ + + unsigned long randint = fgenerate3(); + + /* Construct an floating point value in the range from 0.0 up to 1.0 */ + + return ((double_t)randint) / ((double_t)RND3_CONSTP); +} +#endif +#endif + +/**************************************************************************** + * Public Functions + ****************************************************************************/ + +/**************************************************************************** + * Function: srand, rand + ****************************************************************************/ + +void srand(unsigned int seed) +{ + g_randint1 = seed; +#if (CONFIG_LIB_RAND_ORDER > 1) + g_randint2 = seed; + (void)fgenerate1(); +#if (CONFIG_LIB_RAND_ORDER > 2) + g_randint3 = seed; + (void)fgenerate2(); +#endif +#endif +} + +int rand(void) +{ + return (int)nrand(32768); +} |