diff options
Diffstat (limited to 'lib/libc/stdlib')
62 files changed, 9451 insertions, 0 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc new file mode 100644 index 0000000..5298202 --- /dev/null +++ b/lib/libc/stdlib/Makefile.inc @@ -0,0 +1,25 @@ +# @(#)Makefile.inc 8.2 (Berkeley) 2/16/94 + +# machine-independent stdlib sources +.PATH: ${.CURDIR}/${MACHINE}/stdlib ${.CURDIR}/stdlib + +SRCS+= abort.c atexit.c atof.c atoi.c atol.c bsearch.c calloc.c div.c \ + exit.c getenv.c getopt.c getsubopt.c heapsort.c labs.c ldiv.c \ + malloc.c merge.c putenv.c qsort.c radixsort.c rand.c random.c \ + realpath.c setenv.c strtod.c strtol.c strtoq.c strtoul.c \ + strtouq.c system.c + +# machine-dependent stdlib sources +.include "${.CURDIR}/${MACHINE}/stdlib/Makefile.inc" + +MAN3+= abort.0 abs.0 alloca.0 atexit.0 atof.0 atoi.0 atol.0 bsearch.0 \ + calloc.0 div.0 exit.0 free.0 getenv.0 getopt.0 getsubopt.0 labs.0 \ + ldiv.0 malloc.0 memory.0 qsort.0 radixsort.0 rand.0 random.0 \ + realloc.0 realpath.0 strtod.0 strtol.0 strtoul.0 system.0 + +MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3 +MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 +MLINKS+=rand.3 srand.3 +MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 +MLINKS+=strtol.3 strtoq.3 +MLINKS+=strtoul.3 strtouq.3 diff --git a/lib/libc/stdlib/abort.3 b/lib/libc/stdlib/abort.3 new file mode 100644 index 0000000..83b4e04 --- /dev/null +++ b/lib/libc/stdlib/abort.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)abort.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ABORT 3 +.Os +.Sh NAME +.Nm abort +.Nd cause abnormal program termination +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn abort void +.Sh DESCRIPTION +The +.Fn abort +function causes abnormal program termination to occur, unless the +signal +.Dv SIGABRT +is being caught and the signal handler does not return. +.Pp +No open streams are closed or flushed. +.Sh RETURN VALUES +The +.Nm abort +function +never returns. +.Sh SEE ALSO +.Xr sigaction 2 , +.Xr exit 2 +.Sh STANDARDS +The +.Fn abort +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/abort.c b/lib/libc/stdlib/abort.c new file mode 100644 index 0000000..e56e7e9 --- /dev/null +++ b/lib/libc/stdlib/abort.c @@ -0,0 +1,65 @@ +/* + * Copyright (c) 1985, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)abort.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/signal.h> +#include <stdlib.h> +#include <stddef.h> +#include <unistd.h> + +void +abort() +{ + sigset_t mask; + + sigfillset(&mask); + /* + * don't block SIGABRT to give any handler a chance; we ignore + * any errors -- X311J doesn't allow abort to return anyway. + */ + sigdelset(&mask, SIGABRT); + (void)sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); + (void)kill(getpid(), SIGABRT); + + /* + * if SIGABRT ignored, or caught and the handler returns, do + * it again, only harder. + */ + (void)signal(SIGABRT, SIG_DFL); + (void)sigprocmask(SIG_SETMASK, &mask, (sigset_t *)NULL); + (void)kill(getpid(), SIGABRT); + exit(1); +} diff --git a/lib/libc/stdlib/abs.3 b/lib/libc/stdlib/abs.3 new file mode 100644 index 0000000..e12f798 --- /dev/null +++ b/lib/libc/stdlib/abs.3 @@ -0,0 +1,73 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)abs.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ABS 3 +.Os +.Sh NAME +.Nm abs +.Nd integer absolute value function +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn abs "int j" +.Sh DESCRIPTION +The +.Fn abs +function +computes +the absolute value of the integer +.Ar j . +.Sh RETURN VALUES +The +.Fn abs +function +returns +the absolute value. +.Sh SEE ALSO +.Xr floor 3 , +.Xr labs 3 +.Xr cabs 3 +.Xr hypot 3 +.Xr math 3 +.Sh STANDARDS +The +.Fn abs +function conforms to +.St -ansiC . +.Sh BUGS +The absolute value of the most negative integer remains negative. diff --git a/lib/libc/stdlib/abs.c b/lib/libc/stdlib/abs.c new file mode 100644 index 0000000..013fe53 --- /dev/null +++ b/lib/libc/stdlib/abs.c @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)abs.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> + +int +abs(j) + int j; +{ + return(j < 0 ? -j : j); +} diff --git a/lib/libc/stdlib/alloca.3 b/lib/libc/stdlib/alloca.3 new file mode 100644 index 0000000..ad5aaf69 --- /dev/null +++ b/lib/libc/stdlib/alloca.3 @@ -0,0 +1,78 @@ +.\" Copyright (c) 1980, 1991, 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. +.\" +.\" @(#)alloca.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ALLOCA 3 +.Os BSD 4 +.Sh NAME +.Nm alloca +.Nd memory allocator +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn alloca "size_t size" +.Sh DESCRIPTION +The +.Fn alloca +function +allocates +.Fa size +bytes of space in the stack frame of the caller. +This temporary space is automatically freed on +return. +.Sh RETURN VALUES +The +.Fn alloca +function returns a pointer to the beginning of the allocated space. +If the allocation failed, a +.Dv NULL +pointer is returned. +.Sh SEE ALSO +.Xr brk 2 , +.Xr pagesize 2 +.Xr calloc 3 , +.Xr malloc 3 , +.Xr realloc 3 , +.Sh BUGS +The +.Fn alloca +function +is machine dependent; its use is discouraged. +.\" .Sh HISTORY +.\" The +.\" .Fn alloca +.\" function appeared in +.\" .Bx ?? . +.\" The function appeared in 32v, pwb and pwb.2 and in 3bsd 4bsd +.\" The first man page (or link to a man page that I can find at the +.\" moment is 4.3... diff --git a/lib/libc/stdlib/atexit.3 b/lib/libc/stdlib/atexit.3 new file mode 100644 index 0000000..d50d57c --- /dev/null +++ b/lib/libc/stdlib/atexit.3 @@ -0,0 +1,77 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)atexit.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ATEXIT 3 +.Os +.Sh NAME +.Nm atexit +.Nd register a function to be called on exit +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn atexit "void (*function)(void)" +.Sh DESCRIPTION +The +.Fn atexit +function +registers the given +.Ar function +to be called at program exit, whether via +.Xr exit 3 +or via return from the program's +.Em main . +Functions so registered are called in reverse order; +no arguments are passed. +At least 32 functions can always be registered, +and more are allowed as long as sufficient memory can be allocated. +.Sh RETURN VALUES +.Rv -std atexit +.Sh ERRORS +.Bl -tag -width [ENOMEM] +.It Bq Er ENOMEM +No memory was available to add the function to the list. +The existing list of functions is unmodified. +.El +.Sh SEE ALSO +.Xr exit 3 +.Sh STANDARDS +The +.Fn atexit +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/atexit.c b/lib/libc/stdlib/atexit.c new file mode 100644 index 0000000..9c4caed --- /dev/null +++ b/lib/libc/stdlib/atexit.c @@ -0,0 +1,66 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atexit.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> +#include "atexit.h" + +/* + * Register a function to be performed at exit. + */ +int +atexit(fn) + void (*fn)(); +{ + static struct atexit __atexit0; /* one guaranteed table */ + register struct atexit *p; + + if ((p = __atexit) == NULL) + __atexit = p = &__atexit0; + else if (p->ind >= ATEXIT_SIZE) { + if ((p = malloc(sizeof(*p))) == NULL) + return (-1); + p->ind = 0; + p->next = __atexit; + __atexit = p; + } + p->fns[p->ind++] = fn; + return (0); +} diff --git a/lib/libc/stdlib/atexit.h b/lib/libc/stdlib/atexit.h new file mode 100644 index 0000000..3067e8d --- /dev/null +++ b/lib/libc/stdlib/atexit.h @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990, 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. + * + * @(#)atexit.h 8.1 (Berkeley) 6/4/93 + */ + +/* must be at least 32 to guarantee ANSI conformance */ +#define ATEXIT_SIZE 32 + +struct atexit { + struct atexit *next; /* next in list */ + int ind; /* next index in this table */ + void (*fns[ATEXIT_SIZE])(); /* the table itself */ +}; + +struct atexit *__atexit; /* points to head of LIFO stack */ diff --git a/lib/libc/stdlib/atof.3 b/lib/libc/stdlib/atof.3 new file mode 100644 index 0000000..978d3f4 --- /dev/null +++ b/lib/libc/stdlib/atof.3 @@ -0,0 +1,87 @@ +.\" Copyright (c) 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)atof.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ATOF 3 +.Os +.Sh NAME +.Nm atof +.Nd convert +.Tn ASCII +string to double +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft double +.Fn atof "const char *nptr" +.Sh DESCRIPTION +The +.Fn atof +function converts the initial portion of the string pointed to by +.Ar nptr +to +.Ar double +representation. +.Pp +It is equivalent to: +.Bd -literal -offset indent +strtod(nptr, (char **)NULL); +.Ed +.Sh SEE ALSO +.Xr atoi 3 , +.Xr atol 3 , +.Xr strtod 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn atof +function conforms to +.St -ansiC . +.Sh BUGS +This manual page represents intent instead of actual practice. +While it is intended that +.Fn atof +be implemented using +.Xr strtod 3 , +this has not yet happened. +In the current system, +.Fn atof +translates a string in the following form to a double: a string of +leading white space, possibly followed by a sign (``+'' or ``-''), +followed by a digit string which may contain one decimal point (``.''), +which may be followed by either of the exponent flags (``E'' or ``e''), +and lastly, followed by a signed or unsigned integer. diff --git a/lib/libc/stdlib/atof.c b/lib/libc/stdlib/atof.c new file mode 100644 index 0000000..130e285 --- /dev/null +++ b/lib/libc/stdlib/atof.c @@ -0,0 +1,46 @@ +/* + * Copyright (c) 1988, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atof.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <stddef.h> + +double +atof(ascii) + const char *ascii; +{ + return (strtod(ascii, NULL)); +} diff --git a/lib/libc/stdlib/atoi.3 b/lib/libc/stdlib/atoi.3 new file mode 100644 index 0000000..a39779f --- /dev/null +++ b/lib/libc/stdlib/atoi.3 @@ -0,0 +1,73 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)atoi.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ATOI 3 +.Os +.Sh NAME +.Nm atoi +.Nd convert +.Tn ASCII +string to integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn atoi "const char *nptr" +.Sh DESCRIPTION +The +.Fn atoi +function converts the initial portion of the string pointed to by +.Em nptr +to +.Em integer +representation. +.Pp +It is equivalent to: +.Bd -literal -offset indent +(int)strtol(nptr, (char **)NULL, 10); +.Ed +.Sh SEE ALSO +.Xr atof 3 , +.Xr atol 3 , +.Xr strtod 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn atoi +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/atoi.c b/lib/libc/stdlib/atoi.c new file mode 100644 index 0000000..a13c0e2 --- /dev/null +++ b/lib/libc/stdlib/atoi.c @@ -0,0 +1,45 @@ +/* + * Copyright (c) 1988, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atoi.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <stddef.h> + +atoi(str) + const char *str; +{ + return((int)strtol(str, (char **)NULL, 10)); +} diff --git a/lib/libc/stdlib/atol.3 b/lib/libc/stdlib/atol.3 new file mode 100644 index 0000000..6b12cc9 --- /dev/null +++ b/lib/libc/stdlib/atol.3 @@ -0,0 +1,74 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)atol.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt ATOL 3 +.Os +.Sh NAME +.Nm atol +.Nd convert +.Tn ASCII +string to long integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft long +.Fn atol "const char *nptr" +.Sh DESCRIPTION +The +.Fn atol +function converts the initial portion of the string pointed to by +.Ar nptr +to +.Em long integer +representation. +.Pp +It is equivalent to: +.Bd -literal -offset indent +strtol(nptr, (char **)NULL, 10); +.Ed +.Sh SEE ALSO +.Xr atof 3 , +.Xr atoi 3 , +.Xr strtod 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn atol +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/atol.c b/lib/libc/stdlib/atol.c new file mode 100644 index 0000000..31bcaa6 --- /dev/null +++ b/lib/libc/stdlib/atol.c @@ -0,0 +1,46 @@ +/* + * Copyright (c) 1988, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)atol.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> + +long +atol(str) + const char *str; +{ + return(strtol(str, (char **)NULL, 10)); +} diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3 new file mode 100644 index 0000000..e4cf49f --- /dev/null +++ b/lib/libc/stdlib/bsearch.3 @@ -0,0 +1,90 @@ +.\" Copyright (c) 1990, 1991, 1993, 1994 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)bsearch.3 8.3 (Berkeley) 4/19/94 +.\" +.Dd April 19, 1994 +.Dt BSEARCH 3 +.Os +.Sh NAME +.Nm bsearch +.Nd binary search of a sorted table +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn bsearch "const void *key" "const void *base" "size_t nmemb" "size_t size" "int (*compar) (const void *, const void *)" +.Sh DESCRIPTION +The +.Fn bsearch +function searches an array of +.Fa nmemb +objects, the initial member of which is +pointed to by +.Fa base , +for a member that matches the object pointed to by +.Fa key . +The size of each member of the array is specified by +.Fa size . +.Pp +The contents of the array should be in ascending sorted order according +to the comparison function referenced by +.Fa compar . +The +.Fa compar +routine +is expected to have +two arguments which point to the +.Fa key +object and to an array member, in that order, and should return an integer +less than, equal to, or greater than zero if the +.Fa key +object is found, respectively, to be less than, to match, or be +greater than the array member. +.Sh RETURN VALUES +The +.Fn bsearch +function returns a pointer to a matching member of the array, or a null +pointer if no match is found. +If two members compare as equal, which member is matched is unspecified. +.Sh SEE ALSO +.Xr db 3 , +.Xr lsearch 3 , +.Xr qsort 3 , +.\" .Xr tsearch 3 +.Sh STANDARDS +The +.Fn bsearch +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/bsearch.c b/lib/libc/stdlib/bsearch.c new file mode 100644 index 0000000..4cee9de --- /dev/null +++ b/lib/libc/stdlib/bsearch.c @@ -0,0 +1,81 @@ +/* + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)bsearch.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> + +/* + * Perform a binary search. + * + * The code below is a bit sneaky. After a comparison fails, we + * divide the work in half by moving either left or right. If lim + * is odd, moving left simply involves halving lim: e.g., when lim + * is 5 we look at item 2, so we change lim to 2 so that we will + * look at items 0 & 1. If lim is even, the same applies. If lim + * is odd, moving right again involes halving lim, this time moving + * the base up one item past p: e.g., when lim is 5 we change base + * to item 3 and make lim 2 so that we will look at items 3 and 4. + * If lim is even, however, we have to shrink it by one before + * halving: e.g., when lim is 4, we still looked at item 2, so we + * have to make lim 3, then halve, obtaining 1, so that we will only + * look at item 3. + */ +void * +bsearch(key, base0, nmemb, size, compar) + register const void *key; + const void *base0; + size_t nmemb; + register size_t size; + register int (*compar) __P((const void *, const void *)); +{ + register const char *base = base0; + register size_t lim; + register int cmp; + register const void *p; + + for (lim = nmemb; lim != 0; lim >>= 1) { + p = base + (lim >> 1) * size; + cmp = (*compar)(key, p); + if (cmp == 0) + return ((void *)p); + if (cmp > 0) { /* key > p: move right */ + base = (char *)p + size; + lim--; + } /* else move left */ + } + return (NULL); +} diff --git a/lib/libc/stdlib/calloc.3 b/lib/libc/stdlib/calloc.3 new file mode 100644 index 0000000..0ca15e5 --- /dev/null +++ b/lib/libc/stdlib/calloc.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)calloc.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt CALLOC 3 +.Os +.Sh NAME +.Nm calloc +.Nd allocate clean memory (zero initialized space) +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn calloc "size_t nmemb" "size_t size" +.Sh DESCRIPTION +The +.Fn calloc +function allocates space for an array of +.Fa nmemb +objects, each of whose size is +.Fa size . +The space is initialized to all bits zero. +.Sh RETURN VALUES +The +.Fn calloc +function returns +a pointer to the +the allocated space if successful; otherwise a null pointer is returned. +.Sh SEE ALSO +.Xr malloc 3 , +.Xr realloc 3 , +.Xr free 3 , +.Sh STANDARDS +The +.Fn calloc +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/calloc.c b/lib/libc/stdlib/calloc.c new file mode 100644 index 0000000..d7c8e07 --- /dev/null +++ b/lib/libc/stdlib/calloc.c @@ -0,0 +1,52 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)calloc.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <string.h> + +void * +calloc(num, size) + size_t num; + register size_t size; +{ + register void *p; + + size *= num; + if (p = malloc(size)) + bzero(p, size); + return(p); +} diff --git a/lib/libc/stdlib/div.3 b/lib/libc/stdlib/div.3 new file mode 100644 index 0000000..f09e818 --- /dev/null +++ b/lib/libc/stdlib/div.3 @@ -0,0 +1,67 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek. +.\" 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. +.\" +.\" @(#)div.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt DIV 3 +.Os +.Sh NAME +.Nm div +.Nd return quotient and remainder from division +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft div_t +.Fn div "int num" "int denom" +.Sh DESCRIPTION +The +.Fn div +function +computes the value +.Fa num/denom +and returns the quotient and remainder in a structure named +.Fa div_t +that contains two +.Em int +members named +.Fa quot +and +.Fa rem . +.Sh SEE ALSO +.Xr ldiv 3 +.Sh STANDARDS +The +.Fn div +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/div.c b/lib/libc/stdlib/div.c new file mode 100644 index 0000000..d7bde163 --- /dev/null +++ b/lib/libc/stdlib/div.c @@ -0,0 +1,79 @@ +/* + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)div.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> /* div_t */ + +div_t +div(num, denom) + int num, denom; +{ + div_t r; + + r.quot = num / denom; + r.rem = num % denom; + /* + * The ANSI standard says that |r.quot| <= |n/d|, where + * n/d is to be computed in infinite precision. In other + * words, we should always truncate the quotient towards + * 0, never -infinity. + * + * Machine division and remainer may work either way when + * one or both of n or d is negative. If only one is + * negative and r.quot has been truncated towards -inf, + * r.rem will have the same sign as denom and the opposite + * sign of num; if both are negative and r.quot has been + * truncated towards -inf, r.rem will be positive (will + * have the opposite sign of num). These are considered + * `wrong'. + * + * If both are num and denom are positive, r will always + * be positive. + * + * This all boils down to: + * if num >= 0, but r.rem < 0, we got the wrong answer. + * In that case, to get the right answer, add 1 to r.quot and + * subtract denom from r.rem. + */ + if (num >= 0 && r.rem < 0) { + r.quot++; + r.rem -= denom; + } + return (r); +} diff --git a/lib/libc/stdlib/exit.3 b/lib/libc/stdlib/exit.3 new file mode 100644 index 0000000..43ee3c0 --- /dev/null +++ b/lib/libc/stdlib/exit.3 @@ -0,0 +1,83 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)exit.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt EXIT 3 +.Os +.Sh NAME +.Nm exit +.Nd perform normal program termination +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn exit "int status" +.Sh DESCRIPTION +.Fn Exit +terminates a process. +.Pp +Before termination it performs the following functions in the +order listed: +.Bl -enum -offset indent +.It +Call the functions registered with the +.Xr atexit 3 +function, in the reverse order of their registration. +.It +Flush all open output streams. +.It +Close all open streams. +.It +Unlink all files created with the +.Xr tmpfile 3 +function. +.El +.Sh RETURN VALUES +The +.Fn exit +function +never returns. +.Sh SEE ALSO +.Xr _exit 2 , +.Xr atexit 3 , +.Xr intro 3 , +.Xr tmpfile 3 +.Sh STANDARDS +The +.Fn exit +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/exit.c b/lib/libc/stdlib/exit.c new file mode 100644 index 0000000..a8f6e24 --- /dev/null +++ b/lib/libc/stdlib/exit.c @@ -0,0 +1,60 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)exit.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <unistd.h> +#include "atexit.h" + +void (*__cleanup)(); + +/* + * Exit, flushing stdio buffers if necessary. + */ +void +exit(status) + int status; +{ + register struct atexit *p; + register int n; + + for (p = __atexit; p; p = p->next) + for (n = p->ind; --n >= 0;) + (*p->fns[n])(); + if (__cleanup) + (*__cleanup)(); + _exit(status); +} diff --git a/lib/libc/stdlib/free.3 b/lib/libc/stdlib/free.3 new file mode 100644 index 0000000..17d99eb --- /dev/null +++ b/lib/libc/stdlib/free.3 @@ -0,0 +1,81 @@ +.\" Copyright (c) 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)free.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt FREE 3 +.Os +.Sh NAME +.Nm free +.Nd free up memory allocated with malloc, calloc or realloc +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn free "void *ptr" +.Sh DESCRIPTION +The +.Fn free +function causes the space pointed to by +.Fa ptr +to be deallocated, that is, made available +for further allocation. +If +.Fa ptr +is a null pointer, no action occurs. +Otherwise, if the argument does not match a pointer earlier +returned by the +.Xr calloc , +.Xr malloc , +or +.Xr realloc +function, or if the space has been deallocated by a call to +.Fn free +or +.Xr realloc , +general havoc may occur. +.Sh RETURN VALUES +The +.Fn free +function returns no value. +.Sh SEE ALSO +.Xr calloc 3 , +.Xr malloc 3 , +.Xr realloc 3 +.Sh STANDARDS +The +.Fn free +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/getenv.3 b/lib/libc/stdlib/getenv.3 new file mode 100644 index 0000000..f552d3d --- /dev/null +++ b/lib/libc/stdlib/getenv.3 @@ -0,0 +1,151 @@ +.\" Copyright (c) 1988, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)getenv.3 8.2 (Berkeley) 12/11/93 +.\" +.Dd December 11, 1993 +.Dt GETENV 3 +.Os +.Sh NAME +.Nm getenv , +.Nm putenv , +.Nm setenv , +.Nm unsetenv +.Nd environment variable functions +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft char * +.Fn getenv "const char *name" +.Ft int +.Fn setenv "const char *name" "const char *value" "int overwrite" +.Ft int +.Fn putenv "const char *string" +.Ft void +.Fn unsetenv "const char *name" +.Sh DESCRIPTION +These functions set, unset and fetch environment variables from the +host +.Em environment list . +For compatibility with differing environment conventions, +the given arguments +.Ar name +and +.Ar value +may be appended and prepended, +respectively, +with an equal sign +.Dq Li \&= . +.Pp +The +.Fn getenv +function obtains the current value of the environment variable, +.Ar name . +If the variable +.Ar name +is not in the current environment, +a null pointer is returned. +.Pp +The +.Fn setenv +function inserts or resets the environment variable +.Ar name +in the current environment list. +If the variable +.Ar name +does not exist in the list, +it is inserted with the given +.Ar value. +If the variable does exist, the argument +.Ar overwrite +is tested; if +.Ar overwrite is +zero, the +variable is not reset, otherwise it is reset +to the given +.Ar value . +.Pp +The +.Fn putenv +function takes an argument of the form ``name=value'' and is +equivalent to: +.Bd -literal -offset indent +setenv(name, value, 1); +.Ed +.Pp +The +.Fn unsetenv +function +deletes all instances of the variable name pointed to by +.Fa name +from the list. +.Sh RETURN VALUES +The functions +.Fn setenv +and +.Fn putenv +return zero if successful; otherwise the global variable +.Va errno +is set to indicate the error and a +\-1 is returned. +.Sh ERRORS +.Bl -tag -width [ENOMEM] +.It Bq Er ENOMEM +The function +.Fn setenv +or +.Fn putenv +failed because they were unable to allocate memory for the environment. +.El +.Sh SEE ALSO +.Xr csh 1 , +.Xr sh 1 , +.Xr execve 2 , +.Xr environ 7 +.Sh STANDARDS +The +.Fn getenv +function conforms to +.St -ansiC . +.Sh HISTORY +The functions +.Fn setenv +and +.Fn unsetenv +appeared in +.At v7 . +The +.Fn putenv +function appeared in +.Bx 4.3 Reno . diff --git a/lib/libc/stdlib/getenv.c b/lib/libc/stdlib/getenv.c new file mode 100644 index 0000000..7407e0b --- /dev/null +++ b/lib/libc/stdlib/getenv.c @@ -0,0 +1,87 @@ +/* + * Copyright (c) 1987, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)getenv.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <stddef.h> +#include <string.h> + +char *__findenv __P((const char *, int *)); + +/* + * getenv -- + * Returns ptr to value associated with name, if any, else NULL. + */ +char * +getenv(name) + const char *name; +{ + int offset; + + return (__findenv(name, &offset)); +} + +/* + * __findenv -- + * Returns pointer to value associated with name, if any, else NULL. + * Sets offset to be the offset of the name/value combination in the + * environmental array, for use by setenv(3) and unsetenv(3). + * Explicitly removes '=' in argument name. + * + * This routine *should* be a static; don't use it. + */ +char * +__findenv(name, offset) + register const char *name; + int *offset; +{ + extern char **environ; + register int len; + register const char *np; + register char **p, *c; + + if (name == NULL || environ == NULL) + return (NULL); + for (np = name; *np && *np != '='; ++np) + continue; + len = np - name; + for (p = environ; (c = *p) != NULL; ++p) + if (strncmp(c, name, len) == 0 && c[len] == '=') { + *offset = p - environ; + return (c + len + 1); + } + return (NULL); +} diff --git a/lib/libc/stdlib/getopt.3 b/lib/libc/stdlib/getopt.3 new file mode 100644 index 0000000..95ff6e6 --- /dev/null +++ b/lib/libc/stdlib/getopt.3 @@ -0,0 +1,252 @@ +.\" Copyright (c) 1988, 1991, 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. +.\" +.\" @(#)getopt.3 8.4 (Berkeley) 4/19/94 +.\" +.Dd April 19, 1994 +.Dt GETOPT 3 +.Os BSD 4.3 +.Sh NAME +.Nm getopt +.Nd get option character from command line argument list +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Vt extern char *optarg; +.Vt extern int optind; +.Vt extern int optopt; +.Vt extern int opterr; +.Vt extern int optreset; +.Ft int +.Fn getopt "int argc" "char * const *argv" "const char *optstring" +.Sh DESCRIPTION +The +.Fn getopt +function incrementally parses a command line argument list +.Fa argv +and returns the next +.Em known +option character. +An option character is +.Em known +if it has been specified in the string of accepted option characters, +.Fa optstring . +.Pp +The option string +.Fa optstring +may contain the following elements: individual characters, and +characters followed by a colon to indicate an option argument +is to follow. +For example, an option string +.Li "\&""x"" +recognizes an option +.Dq Fl x , +and an option string +.Li "\&""x:"" +recognizes an option and argument +.Dq Fl x Ar argument . +It does not matter to +.Fn getopt +if a following argument has leading white space. +.Pp +On return from +.Fn getopt , +.Va optarg +points to an option argument, if it is anticipated, +and the variable +.Va optind +contains the index to the next +.Fa argv +argument for a subsequent call +to +.Fn getopt . +The variable +.Va optopt +saves the last +.Em known +option character returned by +.Fn getopt . +.Pp +The variable +.Va opterr +and +.Va optind +are both initialized to 1. +The +.Va optind +variable may be set to another value before a set of calls to +.Fn getopt +in order to skip over more or less argv entries. +.Pp +In order to use +.Fn getopt +to evaluate multiple sets of arguments, or to evaluate a single set of +arguments multiple times, +the variable +.Va optreset +must be set to 1 before the second and each additional set of calls to +.Fn getopt , +and the variable +.Va optind +must be reinitialized. +.Pp +The +.Fn getopt +function +returns an +.Dv EOF +when the argument list is exhausted, or a non-recognized +option is encountered. +The interpretation of options in the argument list may be cancelled +by the option +.Ql -- +(double dash) which causes +.Fn getopt +to signal the end of argument processing and return an +.Dv EOF . +When all options have been processed (i.e., up to the first non-option +argument), +.Fn getopt +returns +.Dv EOF . +.Sh DIAGNOSTICS +If the +.Fn getopt +function encounters a character not found in the string +.Va optarg +or detects +a missing option argument it writes an error message and returns +.Ql ? +to the +.Em stderr . +Setting +.Va opterr +to a zero will disable these error messages. +If +.Va optstring +has a leading +.Ql \&: +then a missing option argument causes a +.Ql \&: +to be returned in addition to suppressing any error messages. +.Pp +Option arguments are allowed to begin with +.Dq Li \- ; +this is reasonable but +reduces the amount of error checking possible. +.Sh EXTENSIONS +The +.Va optreset +variable was added to make it possible to call the +.Fn getopt +function multiple times. +This is an extension to the +.St -p1003.2 +specification. +.Sh EXAMPLE +.Bd -literal -compact +extern char *optarg; +extern int optind; +int bflag, ch, fd; + +bflag = 0; +while ((ch = getopt(argc, argv, "bf:")) != EOF) + switch(ch) { + case 'b': + bflag = 1; + break; + case 'f': + if ((fd = open(optarg, O_RDONLY, 0)) < 0) { + (void)fprintf(stderr, + "myname: %s: %s\en", optarg, strerror(errno)); + exit(1); + } + break; + case '?': + default: + usage(); +} +argc -= optind; +argv += optind; +.Ed +.Sh HISTORY +The +.Fn getopt +function appeared +.Bx 4.3 . +.Sh BUGS +A single dash +.Dq Li - +may be specified as an character in +.Fa optstring , +however it should +.Em never +have an argument associated with it. +This allows +.Fn getopt +to be used with programs that expect +.Dq Li - +as an option flag. +This practice is wrong, and should not be used in any current development. +It is provided for backward compatibility +.Em only . +By default, a single dash causes +.Fn getopt +to return +.Dv EOF . +This is, we believe, compatible with System V. +.Pp +It is also possible to handle digits as option letters. +This allows +.Fn getopt +to be used with programs that expect a number +.Pq Dq Li \&-\&3 +as an option. +This practice is wrong, and should not be used in any current development. +It is provided for backward compatibility +.Em only . +The following code fragment works in most cases. +.Bd -literal -offset indent +int length; +char *p; + +while ((c = getopt(argc, argv, "0123456789")) != EOF) + switch (c) { + case '0': case '1': case '2': case '3': case '4': + case '5': case '6': case '7': case '8': case '9': + p = argv[optind - 1]; + if (p[0] == '-' && p[1] == ch && !p[2]) + length = atoi(++p); + else + length = atoi(argv[optind] + 1); + break; + } +} +.Ed diff --git a/lib/libc/stdlib/getopt.c b/lib/libc/stdlib/getopt.c new file mode 100644 index 0000000..994d757 --- /dev/null +++ b/lib/libc/stdlib/getopt.c @@ -0,0 +1,117 @@ +/* + * Copyright (c) 1987, 1993, 1994 + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)getopt.c 8.2 (Berkeley) 4/2/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +int opterr = 1, /* if error message should be printed */ + optind = 1, /* index into parent argv vector */ + optopt, /* character checked for validity */ + optreset; /* reset getopt */ +char *optarg; /* argument associated with option */ + +#define BADCH (int)'?' +#define BADARG (int)':' +#define EMSG "" + +/* + * getopt -- + * Parse argc/argv argument vector. + */ +int +getopt(nargc, nargv, ostr) + int nargc; + char * const *nargv; + const char *ostr; +{ + extern char *__progname; + static char *place = EMSG; /* option letter processing */ + char *oli; /* option letter list index */ + + if (optreset || !*place) { /* update scanning pointer */ + optreset = 0; + if (optind >= nargc || *(place = nargv[optind]) != '-') { + place = EMSG; + return (EOF); + } + if (place[1] && *++place == '-') { /* found "--" */ + ++optind; + place = EMSG; + return (EOF); + } + } /* option letter okay? */ + if ((optopt = (int)*place++) == (int)':' || + !(oli = strchr(ostr, optopt))) { + /* + * if the user didn't specify '-' as an option, + * assume it means EOF. + */ + if (optopt == (int)'-') + return (EOF); + if (!*place) + ++optind; + if (opterr && *ostr != ':') + (void)fprintf(stderr, + "%s: illegal option -- %c\n", __progname, optopt); + return (BADCH); + } + if (*++oli != ':') { /* don't need argument */ + optarg = NULL; + if (!*place) + ++optind; + } + else { /* need an argument */ + if (*place) /* no white space */ + optarg = place; + else if (nargc <= ++optind) { /* no arg */ + place = EMSG; + if (*ostr == ':') + return (BADARG); + if (opterr) + (void)fprintf(stderr, + "%s: option requires an argument -- %c\n", + __progname, optopt); + return (BADCH); + } + else /* white space */ + optarg = nargv[optind]; + place = EMSG; + ++optind; + } + return (optopt); /* dump back option letter */ +} diff --git a/lib/libc/stdlib/getsubopt.3 b/lib/libc/stdlib/getsubopt.3 new file mode 100644 index 0000000..e1040d7 --- /dev/null +++ b/lib/libc/stdlib/getsubopt.3 @@ -0,0 +1,145 @@ +.\" Copyright (c) 1990, 1991, 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. +.\" +.\" @(#)getsubopt.3 8.1 (Berkeley) 6/9/93 +.\" +.Dd June 9, 1993 +.Dt GETSUBOPT 3 +.Os +.Sh NAME +.Nm getsubopt +.Nd get sub options from an argument +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Vt extern char *suboptarg +.Ft int +.Fn getsubopt "char **optionp" "char * const *tokens" "char **valuep" +.Sh DESCRIPTION +The +.Fn getsubopt +function +parses a string containing tokens delimited by one or more tab, space or +comma +.Pq Ql \&, +characters. +It is intended for use in parsing groups of option arguments provided +as part of a utility command line. +.Pp +The argument +.Fa optionp +is a pointer to a pointer to the string. +The argument +.Fa tokens +is a pointer to a +.Dv NULL Ns -terminated +array of pointers to strings. +.Pp +The +.Fn getsubopt +function +returns the zero-based offset of the pointer in the +.Fa tokens +array referencing a string which matches the first token +in the string, or, \-1 if the string contains no tokens or +.Fa tokens +does not contain a matching string. +.Pp +If the token is of the form ``name=value'', the location referenced by +.Fa valuep +will be set to point to the start of the ``value'' portion of the token. +.Pp +On return from +.Fn getsubopt , +.Fa optionp +will be set to point to the start of the next token in the string, +or the null at the end of the string if no more tokens are present. +The external variable +.Fa suboptarg +will be set to point to the start of the current token, or +.Dv NULL +if no +tokens were present. +The argument +.Fa valuep +will be set to point to the ``value'' portion of the token, or +.Dv NULL +if no ``value'' portion was present. +.Sh EXAMPLE +.Bd -literal -compact +char *tokens[] = { + #define ONE 0 + "one", + #define TWO 1 + "two", + NULL +}; + +\&... + +extern char *optarg, *suboptarg; +char *options, *value; + +while ((ch = getopt(argc, argv, "ab:")) != \-1) { + switch(ch) { + case 'a': + /* process ``a'' option */ + break; + case 'b': + options = optarg; + while (*options) { + switch(getsubopt(&options, tokens, &value)) { + case ONE: + /* process ``one'' sub option */ + break; + case TWO: + /* process ``two'' sub option */ + if (!value) + error("no value for two"); + i = atoi(value); + break; + case \-1: + if (suboptarg) + error("illegal sub option %s", + suboptarg); + else + error("missing sub option"); + break; + } + break; + } +.Ed +.Sh SEE ALSO +.Xr getopt 3 , +.Xr strsep 3 +.Sh HISTORY +The +.Fn getsubopt +function first appeared in 4.4BSD. diff --git a/lib/libc/stdlib/getsubopt.c b/lib/libc/stdlib/getsubopt.c new file mode 100644 index 0000000..d0ebde2 --- /dev/null +++ b/lib/libc/stdlib/getsubopt.c @@ -0,0 +1,98 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#ifndef lint +static char sccsid[] = "@(#)getsubopt.c 8.1 (Berkeley) 6/4/93"; +#endif /* not lint */ + +#include <unistd.h> +#include <stdlib.h> + +/* + * The SVID interface to getsubopt provides no way of figuring out which + * part of the suboptions list wasn't matched. This makes error messages + * tricky... The extern variable suboptarg is a pointer to the token + * which didn't match. + */ +char *suboptarg; + +getsubopt(optionp, tokens, valuep) + register char **optionp, **valuep; + register char * const *tokens; +{ + register int cnt; + register char *p; + + suboptarg = *valuep = NULL; + + if (!optionp || !*optionp) + return(-1); + + /* skip leading white-space, commas */ + for (p = *optionp; *p && (*p == ',' || *p == ' ' || *p == '\t'); ++p); + + if (!*p) { + *optionp = p; + return(-1); + } + + /* save the start of the token, and skip the rest of the token. */ + for (suboptarg = p; + *++p && *p != ',' && *p != '=' && *p != ' ' && *p != '\t';); + + if (*p) { + /* + * If there's an equals sign, set the value pointer, and + * skip over the value part of the token. Terminate the + * token. + */ + if (*p == '=') { + *p = '\0'; + for (*valuep = ++p; + *p && *p != ',' && *p != ' ' && *p != '\t'; ++p); + if (*p) + *p++ = '\0'; + } else + *p++ = '\0'; + /* Skip any whitespace or commas after this token. */ + for (; *p && (*p == ',' || *p == ' ' || *p == '\t'); ++p); + } + + /* set optionp for next round. */ + *optionp = p; + + for (cnt = 0; *tokens; ++tokens, ++cnt) + if (!strcmp(suboptarg, *tokens)) + return(cnt); + return(-1); +} diff --git a/lib/libc/stdlib/heapsort.c b/lib/libc/stdlib/heapsort.c new file mode 100644 index 0000000..d800064 --- /dev/null +++ b/lib/libc/stdlib/heapsort.c @@ -0,0 +1,184 @@ +/*- + * Copyright (c) 1991, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Ronnie Kon at Mindcraft Inc., Kevin Lew and Elmer Yglesias. + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)heapsort.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <errno.h> +#include <stdlib.h> +#include <stddef.h> + +/* + * Swap two areas of size number of bytes. Although qsort(3) permits random + * blocks of memory to be sorted, sorting pointers is almost certainly the + * common case (and, were it not, could easily be made so). Regardless, it + * isn't worth optimizing; the SWAP's get sped up by the cache, and pointer + * arithmetic gets lost in the time required for comparison function calls. + */ +#define SWAP(a, b, count, size, tmp) { \ + count = size; \ + do { \ + tmp = *a; \ + *a++ = *b; \ + *b++ = tmp; \ + } while (--count); \ +} + +/* Copy one block of size size to another. */ +#define COPY(a, b, count, size, tmp1, tmp2) { \ + count = size; \ + tmp1 = a; \ + tmp2 = b; \ + do { \ + *tmp1++ = *tmp2++; \ + } while (--count); \ +} + +/* + * Build the list into a heap, where a heap is defined such that for + * the records K1 ... KN, Kj/2 >= Kj for 1 <= j/2 <= j <= N. + * + * There two cases. If j == nmemb, select largest of Ki and Kj. If + * j < nmemb, select largest of Ki, Kj and Kj+1. + */ +#define CREATE(initval, nmemb, par_i, child_i, par, child, size, count, tmp) { \ + for (par_i = initval; (child_i = par_i * 2) <= nmemb; \ + par_i = child_i) { \ + child = base + child_i * size; \ + if (child_i < nmemb && compar(child, child + size) < 0) { \ + child += size; \ + ++child_i; \ + } \ + par = base + par_i * size; \ + if (compar(child, par) <= 0) \ + break; \ + SWAP(par, child, count, size, tmp); \ + } \ +} + +/* + * Select the top of the heap and 'heapify'. Since by far the most expensive + * action is the call to the compar function, a considerable optimization + * in the average case can be achieved due to the fact that k, the displaced + * elememt, is ususally quite small, so it would be preferable to first + * heapify, always maintaining the invariant that the larger child is copied + * over its parent's record. + * + * Then, starting from the *bottom* of the heap, finding k's correct place, + * again maintianing the invariant. As a result of the invariant no element + * is 'lost' when k is assigned its correct place in the heap. + * + * The time savings from this optimization are on the order of 15-20% for the + * average case. See Knuth, Vol. 3, page 158, problem 18. + * + * XXX Don't break the #define SELECT line, below. Reiser cpp gets upset. + */ +#define SELECT(par_i, child_i, nmemb, par, child, size, k, count, tmp1, tmp2) { \ + for (par_i = 1; (child_i = par_i * 2) <= nmemb; par_i = child_i) { \ + child = base + child_i * size; \ + if (child_i < nmemb && compar(child, child + size) < 0) { \ + child += size; \ + ++child_i; \ + } \ + par = base + par_i * size; \ + COPY(par, child, count, size, tmp1, tmp2); \ + } \ + for (;;) { \ + child_i = par_i; \ + par_i = child_i / 2; \ + child = base + child_i * size; \ + par = base + par_i * size; \ + if (child_i == 1 || compar(k, par) < 0) { \ + COPY(child, k, count, size, tmp1, tmp2); \ + break; \ + } \ + COPY(child, par, count, size, tmp1, tmp2); \ + } \ +} + +/* + * Heapsort -- Knuth, Vol. 3, page 145. Runs in O (N lg N), both average + * and worst. While heapsort is faster than the worst case of quicksort, + * the BSD quicksort does median selection so that the chance of finding + * a data set that will trigger the worst case is nonexistent. Heapsort's + * only advantage over quicksort is that it requires little additional memory. + */ +int +heapsort(vbase, nmemb, size, compar) + void *vbase; + size_t nmemb, size; + int (*compar) __P((const void *, const void *)); +{ + register int cnt, i, j, l; + register char tmp, *tmp1, *tmp2; + char *base, *k, *p, *t; + + if (nmemb <= 1) + return (0); + + if (!size) { + errno = EINVAL; + return (-1); + } + + if ((k = malloc(size)) == NULL) + return (-1); + + /* + * Items are numbered from 1 to nmemb, so offset from size bytes + * below the starting address. + */ + base = (char *)vbase - size; + + for (l = nmemb / 2 + 1; --l;) + CREATE(l, nmemb, i, j, t, p, size, cnt, tmp); + + /* + * For each element of the heap, save the largest element into its + * final slot, save the displaced element (k), then recreate the + * heap. + */ + while (nmemb > 1) { + COPY(k, base + nmemb * size, cnt, size, tmp1, tmp2); + COPY(base + nmemb * size, base + size, cnt, size, tmp1, tmp2); + --nmemb; + SELECT(i, j, nmemb, t, p, size, k, cnt, tmp1, tmp2); + } + free(k); + return (0); +} diff --git a/lib/libc/stdlib/labs.3 b/lib/libc/stdlib/labs.3 new file mode 100644 index 0000000..ef9ba80 --- /dev/null +++ b/lib/libc/stdlib/labs.3 @@ -0,0 +1,66 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)labs.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt LABS 3 +.Os +.Sh NAME +.Nm labs +.Nd return the absolute value of a long integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft long +.Fn labs "long j" +.Sh DESCRIPTION +The +.Fn labs +function +returns the absolute value of the long integer +.Ar j . +.Sh SEE ALSO +.Xr abs 3 , +.Xr floor 3 , +.Xr cabs 3 , +.Xr math 3 +.Sh STANDARDS +The +.Fn labs +function +conforms to +.St -ansiC . +.Sh BUGS +The absolute value of the most negative integer remains negative. diff --git a/lib/libc/stdlib/labs.c b/lib/libc/stdlib/labs.c new file mode 100644 index 0000000..4adc398 --- /dev/null +++ b/lib/libc/stdlib/labs.c @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)labs.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> + +long +labs(j) + long j; +{ + return(j < 0 ? -j : j); +} diff --git a/lib/libc/stdlib/ldiv.3 b/lib/libc/stdlib/ldiv.3 new file mode 100644 index 0000000..a68952f --- /dev/null +++ b/lib/libc/stdlib/ldiv.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)ldiv.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt LDIV 3 +.Os +.Sh NAME +.Nm ldiv +.Nd return quotient and remainder from division +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft ldiv_t +.Fn ldiv "int num" "int denom" +.Sh DESCRIPTION +The +.Fn ldiv +function +computes the value +.Ar num/denom +and returns the quotient and remainder in a structure named +.Ar ldiv_t +that contains two +.Em long integer +members named +.Ar quot +and +.Ar rem . +.Sh SEE ALSO +.Xr div 3 , +.Xr math 3 +.Sh STANDARDS +The +.Fn ldiv +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/ldiv.c b/lib/libc/stdlib/ldiv.c new file mode 100644 index 0000000..d458efd --- /dev/null +++ b/lib/libc/stdlib/ldiv.c @@ -0,0 +1,58 @@ +/* + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Chris Torek. + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)ldiv.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> /* ldiv_t */ + +ldiv_t +ldiv(num, denom) + long num, denom; +{ + ldiv_t r; + + /* see div.c for comments */ + + r.quot = num / denom; + r.rem = num % denom; + if (num >= 0 && r.rem < 0) { + r.quot++; + r.rem -= denom; + } + return (r); +} diff --git a/lib/libc/stdlib/malloc.3 b/lib/libc/stdlib/malloc.3 new file mode 100644 index 0000000..98ebadc --- /dev/null +++ b/lib/libc/stdlib/malloc.3 @@ -0,0 +1,90 @@ +.\" Copyright (c) 1980, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)malloc.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt MALLOC 3 +.Os BSD 4 +.Sh NAME +.Nm malloc , +.Nd general memory allocation function +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn malloc "size_t size" +.Sh DESCRIPTION +The +.Fn malloc +function allocates uninitialized space for an object whose +size is specified by +.Fa size . +The +.Fn malloc +function maintains multiple lists of free blocks according to size, allocating +space from the appropriate list. +.Pp +The allocated space is +suitably aligned (after possible pointer +coercion) for storage of any type of object. If the space is of +.Em pagesize +or larger, the memory returned will be page-aligned. +.Sh RETURN VALUES +The +.Fn malloc +function returns +a pointer to the allocated space if successful; otherwise +a null pointer is returned. +.Sh SEE ALSO +.Xr brk 2 , +.Xr pagesize 2 , +.Xr free 3 , +.Xr calloc 3 , +.Xr alloca 3 , +.Xr realloc 3 , +.Xr memory 3 +.Sh STANDARDS +The +.Fn malloc +function conforms to +.St -ansiC . +.Sh BUGS +The current implementation of +.Xr malloc +does not always fail gracefully when system +memory limits are approached. +It may fail to allocate memory when larger free blocks could be broken +up, or when limits are exceeded because the size is rounded up. +It is optimized for sizes that are powers of two. diff --git a/lib/libc/stdlib/malloc.c b/lib/libc/stdlib/malloc.c new file mode 100644 index 0000000..ea8f092 --- /dev/null +++ b/lib/libc/stdlib/malloc.c @@ -0,0 +1,420 @@ +/* + * Copyright (c) 1983, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)malloc.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +/* + * malloc.c (Caltech) 2/21/82 + * Chris Kingsley, kingsley@cit-20. + * + * This is a very fast storage allocator. It allocates blocks of a small + * number of different sizes, and keeps free lists of each size. Blocks that + * don't exactly fit are passed up to the next larger size. In this + * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long. + * This is designed for use in a virtual memory environment. + */ + +#include <sys/types.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#define NULL 0 + +static void morecore(); +static int findbucket(); + +/* + * The overhead on a block is at least 4 bytes. When free, this space + * contains a pointer to the next free block, and the bottom two bits must + * be zero. When in use, the first byte is set to MAGIC, and the second + * byte is the size index. The remaining bytes are for alignment. + * If range checking is enabled then a second word holds the size of the + * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC). + * The order of elements is critical: ov_magic must overlay the low order + * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern. + */ +union overhead { + union overhead *ov_next; /* when free */ + struct { + u_char ovu_magic; /* magic number */ + u_char ovu_index; /* bucket # */ +#ifdef RCHECK + u_short ovu_rmagic; /* range magic number */ + u_int ovu_size; /* actual block size */ +#endif + } ovu; +#define ov_magic ovu.ovu_magic +#define ov_index ovu.ovu_index +#define ov_rmagic ovu.ovu_rmagic +#define ov_size ovu.ovu_size +}; + +#define MAGIC 0xef /* magic # on accounting info */ +#define RMAGIC 0x5555 /* magic # on range info */ + +#ifdef RCHECK +#define RSLOP sizeof (u_short) +#else +#define RSLOP 0 +#endif + +/* + * nextf[i] is the pointer to the next free block of size 2^(i+3). The + * smallest allocatable block is 8 bytes. The overhead information + * precedes the data area returned to the user. + */ +#define NBUCKETS 30 +static union overhead *nextf[NBUCKETS]; +extern char *sbrk(); + +static int pagesz; /* page size */ +static int pagebucket; /* page size bucket */ + +#ifdef MSTATS +/* + * nmalloc[i] is the difference between the number of mallocs and frees + * for a given block size. + */ +static u_int nmalloc[NBUCKETS]; +#include <stdio.h> +#endif + +#if defined(DEBUG) || defined(RCHECK) +#define ASSERT(p) if (!(p)) botch("p") +#include <stdio.h> +static +botch(s) + char *s; +{ + fprintf(stderr, "\r\nassertion botched: %s\r\n", s); + (void) fflush(stderr); /* just in case user buffered it */ + abort(); +} +#else +#define ASSERT(p) +#endif + +void * +malloc(nbytes) + size_t nbytes; +{ + register union overhead *op; + register int bucket, n; + register unsigned amt; + + /* + * First time malloc is called, setup page size and + * align break pointer so all data will be page aligned. + */ + if (pagesz == 0) { + pagesz = n = getpagesize(); + op = (union overhead *)sbrk(0); + n = n - sizeof (*op) - ((int)op & (n - 1)); + if (n < 0) + n += pagesz; + if (n) { + if (sbrk(n) == (char *)-1) + return (NULL); + } + bucket = 0; + amt = 8; + while (pagesz > amt) { + amt <<= 1; + bucket++; + } + pagebucket = bucket; + } + /* + * Convert amount of memory requested into closest block size + * stored in hash buckets which satisfies request. + * Account for space used per block for accounting. + */ + if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) { +#ifndef RCHECK + amt = 8; /* size of first bucket */ + bucket = 0; +#else + amt = 16; /* size of first bucket */ + bucket = 1; +#endif + n = -(sizeof (*op) + RSLOP); + } else { + amt = pagesz; + bucket = pagebucket; + } + while (nbytes > amt + n) { + amt <<= 1; + if (amt == 0) + return (NULL); + bucket++; + } + /* + * If nothing in hash bucket right now, + * request more memory from the system. + */ + if ((op = nextf[bucket]) == NULL) { + morecore(bucket); + if ((op = nextf[bucket]) == NULL) + return (NULL); + } + /* remove from linked list */ + nextf[bucket] = op->ov_next; + op->ov_magic = MAGIC; + op->ov_index = bucket; +#ifdef MSTATS + nmalloc[bucket]++; +#endif +#ifdef RCHECK + /* + * Record allocated size of block and + * bound space with magic numbers. + */ + op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); + op->ov_rmagic = RMAGIC; + *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; +#endif + return ((char *)(op + 1)); +} + +/* + * Allocate more memory to the indicated bucket. + */ +static void +morecore(bucket) + int bucket; +{ + register union overhead *op; + register int sz; /* size of desired block */ + int amt; /* amount to allocate */ + int nblks; /* how many blocks we get */ + + /* + * sbrk_size <= 0 only for big, FLUFFY, requests (about + * 2^30 bytes on a VAX, I think) or for a negative arg. + */ + sz = 1 << (bucket + 3); +#ifdef DEBUG + ASSERT(sz > 0); +#else + if (sz <= 0) + return; +#endif + if (sz < pagesz) { + amt = pagesz; + nblks = amt / sz; + } else { + amt = sz + pagesz; + nblks = 1; + } + op = (union overhead *)sbrk(amt); + /* no more room! */ + if ((int)op == -1) + return; + /* + * Add new memory allocated to that on + * free list for this hash bucket. + */ + nextf[bucket] = op; + while (--nblks > 0) { + op->ov_next = (union overhead *)((caddr_t)op + sz); + op = (union overhead *)((caddr_t)op + sz); + } +} + +void +free(cp) + void *cp; +{ + register int size; + register union overhead *op; + + if (cp == NULL) + return; + op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); +#ifdef DEBUG + ASSERT(op->ov_magic == MAGIC); /* make sure it was in use */ +#else + if (op->ov_magic != MAGIC) + return; /* sanity */ +#endif +#ifdef RCHECK + ASSERT(op->ov_rmagic == RMAGIC); + ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC); +#endif + size = op->ov_index; + ASSERT(size < NBUCKETS); + op->ov_next = nextf[size]; /* also clobbers ov_magic */ + nextf[size] = op; +#ifdef MSTATS + nmalloc[size]--; +#endif +} + +/* + * When a program attempts "storage compaction" as mentioned in the + * old malloc man page, it realloc's an already freed block. Usually + * this is the last block it freed; occasionally it might be farther + * back. We have to search all the free lists for the block in order + * to determine its bucket: 1st we make one pass thru the lists + * checking only the first block in each; if that fails we search + * ``__realloc_srchlen'' blocks in each list for a match (the variable + * is extern so the caller can modify it). If that fails we just copy + * however many bytes was given to realloc() and hope it's not huge. + */ +int __realloc_srchlen = 4; /* 4 should be plenty, -1 =>'s whole list */ + +void * +realloc(cp, nbytes) + void *cp; + size_t nbytes; +{ + register u_int onb; + register int i; + union overhead *op; + char *res; + int was_alloced = 0; + + if (cp == NULL) + return (malloc(nbytes)); + op = (union overhead *)((caddr_t)cp - sizeof (union overhead)); + if (op->ov_magic == MAGIC) { + was_alloced++; + i = op->ov_index; + } else { + /* + * Already free, doing "compaction". + * + * Search for the old block of memory on the + * free list. First, check the most common + * case (last element free'd), then (this failing) + * the last ``__realloc_srchlen'' items free'd. + * If all lookups fail, then assume the size of + * the memory block being realloc'd is the + * largest possible (so that all "nbytes" of new + * memory are copied into). Note that this could cause + * a memory fault if the old area was tiny, and the moon + * is gibbous. However, that is very unlikely. + */ + if ((i = findbucket(op, 1)) < 0 && + (i = findbucket(op, __realloc_srchlen)) < 0) + i = NBUCKETS; + } + onb = 1 << (i + 3); + if (onb < pagesz) + onb -= sizeof (*op) + RSLOP; + else + onb += pagesz - sizeof (*op) - RSLOP; + /* avoid the copy if same size block */ + if (was_alloced) { + if (i) { + i = 1 << (i + 2); + if (i < pagesz) + i -= sizeof (*op) + RSLOP; + else + i += pagesz - sizeof (*op) - RSLOP; + } + if (nbytes <= onb && nbytes > i) { +#ifdef RCHECK + op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1); + *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC; +#endif + return(cp); + } else + free(cp); + } + if ((res = malloc(nbytes)) == NULL) + return (NULL); + if (cp != res) /* common optimization if "compacting" */ + bcopy(cp, res, (nbytes < onb) ? nbytes : onb); + return (res); +} + +/* + * Search ``srchlen'' elements of each free list for a block whose + * header starts at ``freep''. If srchlen is -1 search the whole list. + * Return bucket number, or -1 if not found. + */ +static +findbucket(freep, srchlen) + union overhead *freep; + int srchlen; +{ + register union overhead *p; + register int i, j; + + for (i = 0; i < NBUCKETS; i++) { + j = 0; + for (p = nextf[i]; p && j != srchlen; p = p->ov_next) { + if (p == freep) + return (i); + j++; + } + } + return (-1); +} + +#ifdef MSTATS +/* + * mstats - print out statistics about malloc + * + * Prints two lines of numbers, one showing the length of the free list + * for each size category, the second showing the number of mallocs - + * frees for each size category. + */ +mstats(s) + char *s; +{ + register int i, j; + register union overhead *p; + int totfree = 0, + totused = 0; + + fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s); + for (i = 0; i < NBUCKETS; i++) { + for (j = 0, p = nextf[i]; p; p = p->ov_next, j++) + ; + fprintf(stderr, " %d", j); + totfree += j * (1 << (i + 3)); + } + fprintf(stderr, "\nused:\t"); + for (i = 0; i < NBUCKETS; i++) { + fprintf(stderr, " %d", nmalloc[i]); + totused += nmalloc[i] * (1 << (i + 3)); + } + fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n", + totused, totfree); +} +#endif diff --git a/lib/libc/stdlib/memory.3 b/lib/libc/stdlib/memory.3 new file mode 100644 index 0000000..9bc600b --- /dev/null +++ b/lib/libc/stdlib/memory.3 @@ -0,0 +1,70 @@ +.\" Copyright (c) 1991, 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. +.\" +.\" @(#)memory.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt MEMORY 3 +.Os BSD 4 +.Sh NAME +.Nm malloc , +.Nm free , +.Nm realloc , +.Nm calloc , +.Nm alloca +.Nd general memory allocation operations +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn malloc "size_t size" +.Ft void +.Fn free "void *ptr" +.Ft void * +.Fn realloc "void *ptr" "size_t size" +.Ft void * +.Fn calloc "size_t nelem" "size_t elsize" +.Ft void * +.Fn alloca "size_t size" +.Sh DESCRIPTION +These functions allocate and free memory for the calling process. +They are described in the +individual manual pages. +.Sh SEE ALSO +.Xr calloc 3 , +.Xr free 3 , +.Xr malloc 3 , +.Xr realloc 3 , +.Xr alloca 3 , +.Sh STANDARDS +These functions, with the exception of +.Fn alloca +conform to +.St -ansiC . diff --git a/lib/libc/stdlib/merge.c b/lib/libc/stdlib/merge.c new file mode 100644 index 0000000..7d00844 --- /dev/null +++ b/lib/libc/stdlib/merge.c @@ -0,0 +1,347 @@ +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Peter McIlroy. + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)merge.c 8.2 (Berkeley) 2/14/94"; +#endif /* LIBC_SCCS and not lint */ + +/* + * Hybrid exponential search/linear search merge sort with hybrid + * natural/pairwise first pass. Requires about .3% more comparisons + * for random data than LSMS with pairwise first pass alone. + * It works for objects as small as two bytes. + */ + +#define NATURAL +#define THRESHOLD 16 /* Best choice for natural merge cut-off. */ + +/* #define NATURAL to get hybrid natural merge. + * (The default is pairwise merging.) + */ + +#include <sys/types.h> + +#include <errno.h> +#include <stdlib.h> +#include <string.h> + +static void setup __P((u_char *, u_char *, size_t, size_t, int (*)())); +static void insertionsort __P((u_char *, size_t, size_t, int (*)())); + +#define ISIZE sizeof(int) +#define PSIZE sizeof(u_char *) +#define ICOPY_LIST(src, dst, last) \ + do \ + *(int*)dst = *(int*)src, src += ISIZE, dst += ISIZE; \ + while(src < last) +#define ICOPY_ELT(src, dst, i) \ + do \ + *(int*) dst = *(int*) src, src += ISIZE, dst += ISIZE; \ + while (i -= ISIZE) + +#define CCOPY_LIST(src, dst, last) \ + do \ + *dst++ = *src++; \ + while (src < last) +#define CCOPY_ELT(src, dst, i) \ + do \ + *dst++ = *src++; \ + while (i -= 1) + +/* + * Find the next possible pointer head. (Trickery for forcing an array + * to do double duty as a linked list when objects do not align with word + * boundaries. + */ +/* Assumption: PSIZE is a power of 2. */ +#define EVAL(p) (u_char **) \ + ((u_char *)0 + \ + (((u_char *)p + PSIZE - 1 - (u_char *) 0) & ~(PSIZE - 1))) + +/* + * Arguments are as for qsort. + */ +int +mergesort(base, nmemb, size, cmp) + void *base; + size_t nmemb; + register size_t size; + int (*cmp) __P((const void *, const void *)); +{ + register int i, sense; + int big, iflag; + register u_char *f1, *f2, *t, *b, *tp2, *q, *l1, *l2; + u_char *list2, *list1, *p2, *p, *last, **p1; + + if (size < PSIZE / 2) { /* Pointers must fit into 2 * size. */ + errno = EINVAL; + return (-1); + } + + /* + * XXX + * Stupid subtraction for the Cray. + */ + iflag = 0; + if (!(size % ISIZE) && !(((char *)base - (char *)0) % ISIZE)) + iflag = 1; + + if ((list2 = malloc(nmemb * size + PSIZE)) == NULL) + return (-1); + + list1 = base; + setup(list1, list2, nmemb, size, cmp); + last = list2 + nmemb * size; + i = big = 0; + while (*EVAL(list2) != last) { + l2 = list1; + p1 = EVAL(list1); + for (tp2 = p2 = list2; p2 != last; p1 = EVAL(l2)) { + p2 = *EVAL(p2); + f1 = l2; + f2 = l1 = list1 + (p2 - list2); + if (p2 != last) + p2 = *EVAL(p2); + l2 = list1 + (p2 - list2); + while (f1 < l1 && f2 < l2) { + if ((*cmp)(f1, f2) <= 0) { + q = f2; + b = f1, t = l1; + sense = -1; + } else { + q = f1; + b = f2, t = l2; + sense = 0; + } + if (!big) { /* here i = 0 */ +LINEAR: while ((b += size) < t && cmp(q, b) >sense) + if (++i == 6) { + big = 1; + goto EXPONENTIAL; + } + } else { +EXPONENTIAL: for (i = size; ; i <<= 1) + if ((p = (b + i)) >= t) { + if ((p = t - size) > b && + (*cmp)(q, p) <= sense) + t = p; + else + b = p; + break; + } else if ((*cmp)(q, p) <= sense) { + t = p; + if (i == size) + big = 0; + goto FASTCASE; + } else + b = p; +SLOWCASE: while (t > b+size) { + i = (((t - b) / size) >> 1) * size; + if ((*cmp)(q, p = b + i) <= sense) + t = p; + else + b = p; + } + goto COPY; +FASTCASE: while (i > size) + if ((*cmp)(q, + p = b + (i >>= 1)) <= sense) + t = p; + else + b = p; +COPY: b = t; + } + i = size; + if (q == f1) { + if (iflag) { + ICOPY_LIST(f2, tp2, b); + ICOPY_ELT(f1, tp2, i); + } else { + CCOPY_LIST(f2, tp2, b); + CCOPY_ELT(f1, tp2, i); + } + } else { + if (iflag) { + ICOPY_LIST(f1, tp2, b); + ICOPY_ELT(f2, tp2, i); + } else { + CCOPY_LIST(f1, tp2, b); + CCOPY_ELT(f2, tp2, i); + } + } + } + if (f2 < l2) { + if (iflag) + ICOPY_LIST(f2, tp2, l2); + else + CCOPY_LIST(f2, tp2, l2); + } else if (f1 < l1) { + if (iflag) + ICOPY_LIST(f1, tp2, l1); + else + CCOPY_LIST(f1, tp2, l1); + } + *p1 = l2; + } + tp2 = list1; /* swap list1, list2 */ + list1 = list2; + list2 = tp2; + last = list2 + nmemb*size; + } + if (base == list2) { + memmove(list2, list1, nmemb*size); + list2 = list1; + } + free(list2); + return (0); +} + +#define swap(a, b) { \ + s = b; \ + i = size; \ + do { \ + tmp = *a; *a++ = *s; *s++ = tmp; \ + } while (--i); \ + a -= size; \ + } +#define reverse(bot, top) { \ + s = top; \ + do { \ + i = size; \ + do { \ + tmp = *bot; *bot++ = *s; *s++ = tmp; \ + } while (--i); \ + s -= size2; \ + } while(bot < s); \ +} + +/* + * Optional hybrid natural/pairwise first pass. Eats up list1 in runs of + * increasing order, list2 in a corresponding linked list. Checks for runs + * when THRESHOLD/2 pairs compare with same sense. (Only used when NATURAL + * is defined. Otherwise simple pairwise merging is used.) + */ +void +setup(list1, list2, n, size, cmp) + size_t n, size; + int (*cmp) __P((const void *, const void *)); + u_char *list1, *list2; +{ + int i, length, size2, tmp, sense; + u_char *f1, *f2, *s, *l2, *last, *p2; + + size2 = size*2; + if (n <= 5) { + insertionsort(list1, n, size, cmp); + *EVAL(list2) = (u_char*) list2 + n*size; + return; + } + /* + * Avoid running pointers out of bounds; limit n to evens + * for simplicity. + */ + i = 4 + (n & 1); + insertionsort(list1 + (n - i) * size, i, size, cmp); + last = list1 + size * (n - i); + *EVAL(list2 + (last - list1)) = list2 + n * size; + +#ifdef NATURAL + p2 = list2; + f1 = list1; + sense = (cmp(f1, f1 + size) > 0); + for (; f1 < last; sense = !sense) { + length = 2; + /* Find pairs with same sense. */ + for (f2 = f1 + size2; f2 < last; f2 += size2) { + if ((cmp(f2, f2+ size) > 0) != sense) + break; + length += 2; + } + if (length < THRESHOLD) { /* Pairwise merge */ + do { + p2 = *EVAL(p2) = f1 + size2 - list1 + list2; + if (sense > 0) + swap (f1, f1 + size); + } while ((f1 += size2) < f2); + } else { /* Natural merge */ + l2 = f2; + for (f2 = f1 + size2; f2 < l2; f2 += size2) { + if ((cmp(f2-size, f2) > 0) != sense) { + p2 = *EVAL(p2) = f2 - list1 + list2; + if (sense > 0) + reverse(f1, f2-size); + f1 = f2; + } + } + if (sense > 0) + reverse (f1, f2-size); + f1 = f2; + if (f2 < last || cmp(f2 - size, f2) > 0) + p2 = *EVAL(p2) = f2 - list1 + list2; + else + p2 = *EVAL(p2) = list2 + n*size; + } + } +#else /* pairwise merge only. */ + for (f1 = list1, p2 = list2; f1 < last; f1 += size2) { + p2 = *EVAL(p2) = p2 + size2; + if (cmp (f1, f1 + size) > 0) + swap(f1, f1 + size); + } +#endif /* NATURAL */ +} + +/* + * This is to avoid out-of-bounds addresses in sorting the + * last 4 elements. + */ +static void +insertionsort(a, n, size, cmp) + u_char *a; + size_t n, size; + int (*cmp) __P((const void *, const void *)); +{ + u_char *ai, *s, *t, *u, tmp; + int i; + + for (ai = a+size; --n >= 1; ai += size) + for (t = ai; t > a; t -= size) { + u = t - size; + if (cmp(u, t) <= 0) + break; + swap(u, t); + } +} diff --git a/lib/libc/stdlib/putenv.c b/lib/libc/stdlib/putenv.c new file mode 100644 index 0000000..eb5e805 --- /dev/null +++ b/lib/libc/stdlib/putenv.c @@ -0,0 +1,58 @@ +/*- + * Copyright (c) 1988, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)putenv.c 8.2 (Berkeley) 3/27/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdlib.h> +#include <string.h> + +int +putenv(str) + const char *str; +{ + char *p, *equal; + int rval; + + if ((p = strdup(str)) == NULL) + return (-1); + if ((equal = index(p, '=')) == NULL) { + (void)free(p); + return (-1); + } + *equal = '\0'; + rval = setenv(p, equal + 1, 1); + (void)free(p); + return (rval); +} diff --git a/lib/libc/stdlib/qsort.3 b/lib/libc/stdlib/qsort.3 new file mode 100644 index 0000000..4f449c7 --- /dev/null +++ b/lib/libc/stdlib/qsort.3 @@ -0,0 +1,233 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)qsort.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt QSORT 3 +.Os +.Sh NAME +.Nm qsort, heapsort, mergesort +.Nd sort functions +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn qsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" +.Ft int +.Fn heapsort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" +.Ft int +.Fn mergesort "void *base" "size_t nmemb" "size_t size" "int (*compar)(const void *, const void *)" +.Sh DESCRIPTION +The +.Fn qsort +function is a modified partition-exchange sort, or quicksort. +The +.Fn heapsort +function is a modified selection sort. +The +.Fn mergesort +function is a modified merge sort with exponential search +intended for sorting data with pre-existing order. +.Pp +The +.Fn qsort +and +.Fn heapsort +functions sort an array of +.Fa nmemb +objects, the initial member of which is pointed to by +.Fa base . +The size of each object is specified by +.Fa size . +.Fn Mergesort +behaves similarly, but +.Em requires +that +.Fa size +be greater than +.Dq "sizeof(void *) / 2" . +.Pp +The contents of the array +.Fa base +are sorted in ascending order according to +a comparison function pointed to by +.Fa compar , +which requires two arguments pointing to the objects being +compared. +.Pp +The comparison function must return an integer less than, equal to, or +greater than zero if the first argument is considered to be respectively +less than, equal to, or greater than the second. +.Pp +The functions +.Fn qsort +and +.Fn heapsort +are +.Em not +stable, that is, if two members compare as equal, their order in +the sorted array is undefined. +The function +.Fn mergesort +is stable. +.Pp +The +.Fn qsort +function is an implementation of C.A.R. Hoare's ``quicksort'' algorithm, +a variant of partition-exchange sorting; in particular, see D.E. Knuth's +Algorithm Q. +.Fn Qsort +takes O N lg N average time. +This implementation uses median selection to avoid its +O N**2 worst-case behavior. +.Pp +The +.Fn heapsort +function is an implementation of J.W.J. William's ``heapsort'' algorithm, +a variant of selection sorting; in particular, see D.E. Knuth's Algorithm H. +.Fn Heapsort +takes O N lg N worst-case time. +Its +.Em only +advantage over +.Fn qsort +is that it uses almost no additional memory; while +.Fn qsort +does not allocate memory, it is implemented using recursion. +.Pp +The function +.Fn mergesort +requires additional memory of size +.Fa nmemb * +.Fa size +bytes; it should be used only when space is not at a premium. +.Fn Mergesort +is optimized for data with pre-existing order; its worst case +time is O N lg N; its best case is O N. +.Pp +Normally, +.Fn qsort +is faster than +.Fn mergesort +is faster than +.Fn heapsort . +Memory availability and pre-existing order in the data can make this +untrue. +.Sh RETURN VALUES +The +.Fn qsort +function +returns no value. +.Pp +Upon successful completion, +.Fn heapsort +and +.Fn mergesort +return 0. +Otherwise, they return \-1 and the global variable +.Va errno +is set to indicate the error. +.Sh ERRORS +The +.Fn heapsort +function succeeds unless: +.Bl -tag -width Er +.It Bq Er EINVAL +The +.Fa size +argument is zero, or, +the +.Fa size +argument to +.Fn mergesort +is less than +.Dq "sizeof(void *) / 2" . +.It Bq Er ENOMEM +.Fn Heapsort +or +.Fn mergesort +were unable to allocate memory. +.El +.Sh COMPATIBILITY +Previous versions of +.Fn qsort +did not permit the comparison routine itself to call +.Fn qsort 3 . +This is no longer true. +.Sh SEE ALSO +.Xr sort 1 , +.Xr radixsort 3 +.Rs +.%A Hoare, C.A.R. +.%D 1962 +.%T "Quicksort" +.%J "The Computer Journal" +.%V 5:1 +.%P pp. 10-15 +.Re +.Rs +.%A Williams, J.W.J +.%D 1964 +.%T "Heapsort" +.%J "Communications of the ACM" +.%V 7:1 +.%P pp. 347-348 +.Re +.Rs +.%A Knuth, D.E. +.%D 1968 +.%B "The Art of Computer Programming" +.%V Vol. 3 +.%T "Sorting and Searching" +.%P pp. 114-123, 145-149 +.Re +.Rs +.%A Mcilroy, P.M. +.%T "Optimistic Sorting and Information Theoretic Complexity" +.%J "Fourth Annual ACM-SIAM Symposium on Discrete Algorithms" +.%V January 1992 +.Re +.Rs +.%A Bentley, J.L. +.%T "Engineering a Sort Function" +.%J "bentley@research.att.com" +.%V January 1992 +.Re +.Sh STANDARDS +The +.Fn qsort +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/qsort.c b/lib/libc/stdlib/qsort.c new file mode 100644 index 0000000..1d3aa93 --- /dev/null +++ b/lib/libc/stdlib/qsort.c @@ -0,0 +1,174 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)qsort.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <stdlib.h> + +static inline char *med3 __P((char *, char *, char *, int (*)())); +static inline void swapfunc __P((char *, char *, int, int)); + +#define min(a, b) (a) < (b) ? a : b + +/* + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". + */ +#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, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \ + es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; + +static inline void +swapfunc(a, b, n, swaptype) + char *a, *b; + int n, swaptype; +{ + if(swaptype <= 1) + swapcode(long, a, b, n) + else + swapcode(char, a, b, n) +} + +#define swap(a, b) \ + if (swaptype == 0) { \ + long t = *(long *)(a); \ + *(long *)(a) = *(long *)(b); \ + *(long *)(b) = t; \ + } else \ + swapfunc(a, b, es, swaptype) + +#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n, swaptype) + +static inline char * +med3(a, b, c, cmp) + char *a, *b, *c; + int (*cmp)(); +{ + return cmp(a, b) < 0 ? + (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) + :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); +} + +void +qsort(a, n, es, cmp) + void *a; + size_t n, es; + int (*cmp)(); +{ + char *pa, *pb, *pc, *pd, *pl, *pm, *pn; + int d, r, swaptype, swap_cnt; + +loop: SWAPINIT(a, es); + swap_cnt = 0; + if (n < 7) { + for (pm = a + es; pm < (char *) a + n * es; pm += es) + for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + pm = a + (n / 2) * es; + if (n > 7) { + pl = a; + pn = a + (n - 1) * es; + if (n > 40) { + d = (n / 8) * es; + pl = med3(pl, pl + d, pl + 2 * d, cmp); + pm = med3(pm - d, pm, pm + d, cmp); + pn = med3(pn - 2 * d, pn - d, pn, cmp); + } + pm = med3(pl, pm, pn, cmp); + } + swap(a, pm); + pa = pb = a + es; + + pc = pd = a + (n - 1) * es; + for (;;) { + while (pb <= pc && (r = cmp(pb, a)) <= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pa, pb); + pa += es; + } + pb += es; + } + while (pb <= pc && (r = cmp(pc, a)) >= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pc, pd); + pd -= es; + } + pc -= es; + } + if (pb > pc) + break; + swap(pb, pc); + swap_cnt = 1; + pb += es; + pc -= es; + } + if (swap_cnt == 0) { /* Switch to insertion sort */ + for (pm = a + es; pm < (char *) a + n * es; pm += es) + for (pl = pm; pl > (char *) a && cmp(pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + + pn = a + n * es; + r = min(pa - (char *)a, pb - pa); + vecswap(a, pb - r, r); + r = min(pd - pc, pn - pd - es); + vecswap(pb, pn - r, r); + if ((r = pb - pa) > es) + qsort(a, r / es, es, cmp); + if ((r = pd - pc) > es) { + /* Iterate rather than recurse to save stack space */ + a = pn - r; + n = r / es; + goto loop; + } +/* qsort(pn - r, r / es, es, cmp);*/ +} diff --git a/lib/libc/stdlib/radixsort.3 b/lib/libc/stdlib/radixsort.3 new file mode 100644 index 0000000..ce30378 --- /dev/null +++ b/lib/libc/stdlib/radixsort.3 @@ -0,0 +1,160 @@ +.\" Copyright (c) 1990, 1991, 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. +.\" +.\" @(#)radixsort.3 8.2 (Berkeley) 1/27/94 +.\" +.Dd January 27, 1994 +.Dt RADIXSORT 3 +.Os +.Sh NAME +.Nm radixsort +.Nd radix sort +.Sh SYNOPSIS +.Fd #include <limits.h> +.Fd #include <stdlib.h> +.Ft int +.Fn radixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" +.Ft int +.Fn sradixsort "u_char **base" "int nmemb" "u_char *table" "u_int endbyte" +.Sh DESCRIPTION +The +.Fn radixsort +and +.Fn sradixsort +functions +are implementations of radix sort. +.Pp +These functions sort an array of pointers to byte strings, the initial +member of which is referenced by +.Fa base . +The byte strings may contain any values; the end of each string +is denoted by the user-specified value +.Fa endbyte . +.Pp +Applications may specify a sort order by providing the +.Fa table +argument. +If +.Pf non- Dv NULL , +.Fa table +must reference an array of +.Dv UCHAR_MAX ++ 1 bytes which contains the sort +weight of each possible byte value. +The end-of-string byte must have a sort weight of 0 or 255 +(for sorting in reverse order). +More than one byte may have the same sort weight. +The +.Fa table +argument +is useful for applications which wish to sort different characters +equally, for example, providing a table with the same weights +for A-Z as for a-z will result in a case-insensitive sort. +If +.Fa table +is NULL, the contents of the array are sorted in ascending order +according to the +.Tn ASCII +order of the byte strings they reference and +.Fa endbyte +has a sorting weight of 0. +.Pp +The +.Fn sradixsort +function is stable, that is, if two elements compare as equal, their +order in the sorted array is unchanged. +The +.Fn sradixsort +function uses additional memory sufficient to hold +.Fa nmemb +pointers. +.Pp +The +.Fn radixsort +function is not stable, but uses no additional memory. +.Pp +These functions are variants of most-significant-byte radix sorting; in +particular, see D.E. Knuth's Algorithm R and section 5.2.5, exercise 10. +They take linear time relative to the number of bytes in the strings. +.Sh RETURN VALUES +Upon successful completion 0 is returned. +Otherwise, \-1 is returned and the global variable +.Va errno +is set to indicate the error. +.Sh ERRORS +.Bl -tag -width Er +.It Bq Er EINVAL +The value of the +.Fa endbyte +element of +.Fa table +is not 0 or 255. +.El +.Pp +Additionally, the +.Fn sradixsort +function +may fail and set +.Va errno +for any of the errors specified for the library routine +.Xr malloc 3 . +.Sh SEE ALSO +.Xr sort 1 , +.Xr qsort 3 +.Pp +.Rs +.%A Knuth, D.E. +.%D 1968 +.%B "The Art of Computer Programming" +.%T "Sorting and Searching" +.%V Vol. 3 +.%P pp. 170-178 +.Re +.Rs +.%A Paige, R. +.%D 1987 +.%T "Three Partition Refinement Algorithms" +.%J "SIAM J. Comput." +.%V Vol. 16 +.%N No. 6 +.Re +.Rs +.%A McIlroy, P. +.%D 1993 +.%B "Engineering Radix Sort" +.%T "Computing Systems" +.%V Vol. 6:1 +.%P pp. 5-27 +.Re +.Sh HISTORY +The +.Fn radixsort +function first appeared in 4.4BSD. diff --git a/lib/libc/stdlib/radixsort.c b/lib/libc/stdlib/radixsort.c new file mode 100644 index 0000000..d211f3d --- /dev/null +++ b/lib/libc/stdlib/radixsort.c @@ -0,0 +1,318 @@ +/*- + * Copyright (c) 1990, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Peter McIlroy and by Dan Bernstein at New York University, + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)radixsort.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +/* + * Radixsort routines. + * + * Program r_sort_a() is unstable but uses O(logN) extra memory for a stack. + * Use radixsort(a, n, trace, endchar) for this case. + * + * For stable sorting (using N extra pointers) use sradixsort(), which calls + * r_sort_b(). + * + * For a description of this code, see D. McIlroy, P. McIlroy, K. Bostic, + * "Engineering Radix Sort". + */ + +#include <sys/types.h> +#include <stdlib.h> +#include <stddef.h> +#include <errno.h> + +typedef struct { + const u_char **sa; + int sn, si; +} stack; + +static inline void simplesort + __P((const u_char **, int, int, const u_char *, u_int)); +static void r_sort_a __P((const u_char **, int, int, const u_char *, u_int)); +static void r_sort_b __P((const u_char **, + const u_char **, int, int, const u_char *, u_int)); + +#define THRESHOLD 20 /* Divert to simplesort(). */ +#define SIZE 512 /* Default stack size. */ + +#define SETUP { \ + if (tab == NULL) { \ + tr = tr0; \ + for (c = 0; c < endch; c++) \ + tr0[c] = c + 1; \ + tr0[c] = 0; \ + for (c++; c < 256; c++) \ + tr0[c] = c; \ + endch = 0; \ + } else { \ + endch = tab[endch]; \ + tr = tab; \ + if (endch != 0 && endch != 255) { \ + errno = EINVAL; \ + return (-1); \ + } \ + } \ +} + +int +radixsort(a, n, tab, endch) + const u_char **a, *tab; + int n; + u_int endch; +{ + const u_char *tr; + int c; + u_char tr0[256]; + + SETUP; + r_sort_a(a, n, 0, tr, endch); + return (0); +} + +int +sradixsort(a, n, tab, endch) + const u_char **a, *tab; + int n; + u_int endch; +{ + const u_char *tr, **ta; + int c; + u_char tr0[256]; + + SETUP; + if (n < THRESHOLD) + simplesort(a, n, 0, tr, endch); + else { + if ((ta = malloc(n * sizeof(a))) == NULL) + return (-1); + r_sort_b(a, ta, n, 0, tr, endch); + free(ta); + } + return (0); +} + +#define empty(s) (s >= sp) +#define pop(a, n, i) a = (--sp)->sa, n = sp->sn, i = sp->si +#define push(a, n, i) sp->sa = a, sp->sn = n, (sp++)->si = i +#define swap(a, b, t) t = a, a = b, b = t + +/* Unstable, in-place sort. */ +void +r_sort_a(a, n, i, tr, endch) + const u_char **a; + int n, i; + const u_char *tr; + u_int endch; +{ + static int count[256], nc, bmin; + register int c; + register const u_char **ak, *r; + stack s[SIZE], *sp, *sp0, *sp1, temp; + int *cp, bigc; + const u_char **an, *t, **aj, **top[256]; + + /* Set up stack. */ + sp = s; + push(a, n, i); + while (!empty(s)) { + pop(a, n, i); + if (n < THRESHOLD) { + simplesort(a, n, i, tr, endch); + continue; + } + an = a + n; + + /* Make character histogram. */ + if (nc == 0) { + bmin = 255; /* First occupied bin, excluding eos. */ + for (ak = a; ak < an;) { + c = tr[(*ak++)[i]]; + if (++count[c] == 1 && c != endch) { + if (c < bmin) + bmin = c; + nc++; + } + } + if (sp + nc > s + SIZE) { /* Get more stack. */ + r_sort_a(a, n, i, tr, endch); + continue; + } + } + + /* + * Set top[]; push incompletely sorted bins onto stack. + * top[] = pointers to last out-of-place element in bins. + * count[] = counts of elements in bins. + * Before permuting: top[c-1] + count[c] = top[c]; + * during deal: top[c] counts down to top[c-1]. + */ + sp0 = sp1 = sp; /* Stack position of biggest bin. */ + bigc = 2; /* Size of biggest bin. */ + if (endch == 0) /* Special case: set top[eos]. */ + top[0] = ak = a + count[0]; + else { + ak = a; + top[255] = an; + } + for (cp = count + bmin; nc > 0; cp++) { + while (*cp == 0) /* Find next non-empty pile. */ + cp++; + if (*cp > 1) { + if (*cp > bigc) { + bigc = *cp; + sp1 = sp; + } + push(ak, *cp, i+1); + } + top[cp-count] = ak += *cp; + nc--; + } + swap(*sp0, *sp1, temp); /* Play it safe -- biggest bin last. */ + + /* + * Permute misplacements home. Already home: everything + * before aj, and in bin[c], items from top[c] on. + * Inner loop: + * r = next element to put in place; + * ak = top[r[i]] = location to put the next element. + * aj = bottom of 1st disordered bin. + * Outer loop: + * Once the 1st disordered bin is done, ie. aj >= ak, + * aj<-aj + count[c] connects the bins in a linked list; + * reset count[c]. + */ + for (aj = a; aj < an; *aj = r, aj += count[c], count[c] = 0) + for (r = *aj; aj < (ak = --top[c = tr[r[i]]]);) + swap(*ak, r, t); + } +} + +/* Stable sort, requiring additional memory. */ +void +r_sort_b(a, ta, n, i, tr, endch) + const u_char **a, **ta; + int n, i; + const u_char *tr; + u_int endch; +{ + static int count[256], nc, bmin; + register int c; + register const u_char **ak, **ai; + stack s[512], *sp, *sp0, *sp1, temp; + const u_char **top[256]; + int *cp, bigc; + + sp = s; + push(a, n, i); + while (!empty(s)) { + pop(a, n, i); + if (n < THRESHOLD) { + simplesort(a, n, i, tr, endch); + continue; + } + + if (nc == 0) { + bmin = 255; + for (ak = a + n; --ak >= a;) { + c = tr[(*ak)[i]]; + if (++count[c] == 1 && c != endch) { + if (c < bmin) + bmin = c; + nc++; + } + } + if (sp + nc > s + SIZE) { + r_sort_b(a, ta, n, i, tr, endch); + continue; + } + } + + sp0 = sp1 = sp; + bigc = 2; + if (endch == 0) { + top[0] = ak = a + count[0]; + count[0] = 0; + } else { + ak = a; + top[255] = a + n; + count[255] = 0; + } + for (cp = count + bmin; nc > 0; cp++) { + while (*cp == 0) + cp++; + if ((c = *cp) > 1) { + if (c > bigc) { + bigc = c; + sp1 = sp; + } + push(ak, c, i+1); + } + top[cp-count] = ak += c; + *cp = 0; /* Reset count[]. */ + nc--; + } + swap(*sp0, *sp1, temp); + + for (ak = ta + n, ai = a+n; ak > ta;) /* Copy to temp. */ + *--ak = *--ai; + for (ak = ta+n; --ak >= ta;) /* Deal to piles. */ + *--top[tr[(*ak)[i]]] = *ak; + } +} + +static inline void +simplesort(a, n, b, tr, endch) /* insertion sort */ + register const u_char **a; + int n, b; + register const u_char *tr; + u_int endch; +{ + register u_char ch; + const u_char **ak, **ai, *s, *t; + + for (ak = a+1; --n >= 1; ak++) + for (ai = ak; ai > a; ai--) { + for (s = ai[0] + b, t = ai[-1] + b; + (ch = tr[*s]) != endch; s++, t++) + if (ch != tr[*t]) + break; + if (ch >= tr[*t]) + break; + swap(ai[0], ai[-1], s); + } +} diff --git a/lib/libc/stdlib/rand.3 b/lib/libc/stdlib/rand.3 new file mode 100644 index 0000000..f2e3742 --- /dev/null +++ b/lib/libc/stdlib/rand.3 @@ -0,0 +1,84 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)rand.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt RAND 3 +.Os +.Sh NAME +.Nm rand , +.Nm srand +.Nd bad random number generator +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void +.Fn srand "unsigned seed" +.Ft int +.Fn rand void +.Sh DESCRIPTION +.Bf -symbolic +These interfaces are obsoleted by random(3). +.Ef +.Pp +The +.Fn rand +function computes a sequence of pseudo-random integers in the range +of 0 to +.Dv RAND_MAX +(as defined by the header file +.Aq Pa stdlib.h ) . +.Pp +The +.Fn srand +function sets its argument as the seed for a new sequence of +pseudo-random numbers to be returned by +.Fn rand . +These sequences are repeatable by calling +.Fn srand +with the same seed value. +.Pp +If no seed value is provided, the functions are automatically +seeded with a value of 1. +.Sh SEE ALSO +.Xr random 3 +.Sh STANDARDS +The +.Fn rand +and +.Fn srand +functions +conform to +.St -ansiC . diff --git a/lib/libc/stdlib/rand.c b/lib/libc/stdlib/rand.c new file mode 100644 index 0000000..12846c3 --- /dev/null +++ b/lib/libc/stdlib/rand.c @@ -0,0 +1,54 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)rand.c 8.1 (Berkeley) 6/14/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <stdlib.h> + +static u_long next = 1; + +int +rand() +{ + return ((next = next * 1103515245 + 12345) % ((u_long)RAND_MAX + 1)); +} + +void +srand(seed) +u_int seed; +{ + next = seed; +} diff --git a/lib/libc/stdlib/random.3 b/lib/libc/stdlib/random.3 new file mode 100644 index 0000000..84680e2 --- /dev/null +++ b/lib/libc/stdlib/random.3 @@ -0,0 +1,166 @@ +.\" Copyright (c) 1983, 1991, 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. +.\" +.\" @(#)random.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt RANDOM 3 +.Os BSD 4.2 +.Sh NAME +.Nm random , +.Nm srandom , +.Nm initstate , +.Nm setstate +.Nd better random number generator; routines for changing generators +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft long +.Fn random void +.Ft void +.Fn srandom "unsigned seed" +.Ft char * +.Fn initstate "unsigned seed" "char *state" "int n" +.Ft char * +.Fn setstate "char *state" +.Sh DESCRIPTION +The +.Fn random +function +uses a non-linear additive feedback random number generator employing a +default table of size 31 long integers to return successive pseudo-random +numbers in the range from 0 to +.if t 2\u\s731\s10\d\(mi1. +.if n (2**31)\(mi1. +The period of this random number generator is very large, approximately +.if t 16\(mu(2\u\s731\s10\d\(mi1). +.if n 16*((2**31)\(mi1). +.Pp +The +.Fn random Ns / Fn srandom +have (almost) the same calling sequence and initialization properties as +.Xr rand 3 Ns / Xr srand 3 . +The difference is that +.Xr rand +produces a much less random sequence \(em in fact, the low dozen bits +generated by rand go through a cyclic pattern. All the bits generated by +.Fn random +are usable. For example, +.Sq Li random()&01 +will produce a random binary +value. +.Pp +Unlike +.Xr srand , +.Fn srandom +does not return the old seed; the reason for this is that the amount of +state information used is much more than a single word. (Two other +routines are provided to deal with restarting/changing random +number generators). Like +.Xr rand 3 , +however, +.Fn random +will by default produce a sequence of numbers that can be duplicated +by calling +.Fn srandom +with +.Ql 1 +as the seed. +.Pp +The +.Fn initstate +routine allows a state array, passed in as an argument, to be initialized +for future use. The size of the state array (in bytes) is used by +.Fn initstate +to decide how sophisticated a random number generator it should use \(em the +more state, the better the random numbers will be. +(Current "optimal" values for the amount of state information are +8, 32, 64, 128, and 256 bytes; other amounts will be rounded down to +the nearest known amount. Using less than 8 bytes will cause an error.) +The seed for the initialization (which specifies a starting point for +the random number sequence, and provides for restarting at the same +point) is also an argument. +The +.Fn initstate +function +returns a pointer to the previous state information array. +.Pp +Once a state has been initialized, the +.Fn setstate +routine provides for rapid switching between states. +The +.Fn setstate +function +returns a pointer to the previous state array; its +argument state array is used for further random number generation +until the next call to +.Fn initstate +or +.Fn setstate . +.Pp +Once a state array has been initialized, it may be restarted at a +different point either by calling +.Fn initstate +(with the desired seed, the state array, and its size) or by calling +both +.Fn setstate +(with the state array) and +.Fn srandom +(with the desired seed). +The advantage of calling both +.Fn setstate +and +.Fn srandom +is that the size of the state array does not have to be remembered after +it is initialized. +.Pp +With 256 bytes of state information, the period of the random number +generator is greater than +.if t 2\u\s769\s10\d, +.if n 2**69 +which should be sufficient for most purposes. +.Sh AUTHOR +Earl T. Cohen +.Sh DIAGNOSTICS +If +.Fn initstate +is called with less than 8 bytes of state information, or if +.Fn setstate +detects that the state information has been garbled, error +messages are printed on the standard error output. +.Sh SEE ALSO +.Xr rand 3 +.Sh HISTORY +These +functions appeared in +.Bx 4.2 . +.Sh BUGS +About 2/3 the speed of +.Xr rand 3 . diff --git a/lib/libc/stdlib/random.c b/lib/libc/stdlib/random.c new file mode 100644 index 0000000..18babba --- /dev/null +++ b/lib/libc/stdlib/random.c @@ -0,0 +1,363 @@ +/* + * Copyright (c) 1983, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)random.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stdio.h> +#include <stdlib.h> + +/* + * random.c: + * + * An improved random number generation package. In addition to the standard + * rand()/srand() like interface, this package also has a special state info + * interface. The initstate() routine is called with a seed, an array of + * bytes, and a count of how many bytes are being passed in; this array is + * then initialized to contain information for random number generation with + * that much state information. Good sizes for the amount of state + * information are 32, 64, 128, and 256 bytes. The state can be switched by + * calling the setstate() routine with the same array as was initiallized + * with initstate(). By default, the package runs with 128 bytes of state + * information and generates far better random numbers than a linear + * congruential generator. If the amount of state information is less than + * 32 bytes, a simple linear congruential R.N.G. is used. + * + * Internally, the state information is treated as an array of longs; the + * zeroeth element of the array is the type of R.N.G. being used (small + * integer); the remainder of the array is the state information for the + * R.N.G. Thus, 32 bytes of state information will give 7 longs worth of + * state information, which will allow a degree seven polynomial. (Note: + * the zeroeth word of state information also has some other information + * stored in it -- see setstate() for details). + * + * The random number generation technique is a linear feedback shift register + * approach, employing trinomials (since there are fewer terms to sum up that + * way). In this approach, the least significant bit of all the numbers in + * the state table will act as a linear feedback shift register, and will + * have period 2^deg - 1 (where deg is the degree of the polynomial being + * used, assuming that the polynomial is irreducible and primitive). The + * higher order bits will have longer periods, since their values are also + * influenced by pseudo-random carries out of the lower bits. The total + * period of the generator is approximately deg*(2**deg - 1); thus doubling + * the amount of state information has a vast influence on the period of the + * generator. Note: the deg*(2**deg - 1) is an approximation only good for + * large deg, when the period of the shift register is the dominant factor. + * With deg equal to seven, the period is actually much longer than the + * 7*(2**7 - 1) predicted by this formula. + */ + +/* + * For each of the currently supported random number generators, we have a + * break value on the amount of state information (you need at least this + * many bytes of state info to support this random number generator), a degree + * for the polynomial (actually a trinomial) that the R.N.G. is based on, and + * the separation between the two lower order coefficients of the trinomial. + */ +#define TYPE_0 0 /* linear congruential */ +#define BREAK_0 8 +#define DEG_0 0 +#define SEP_0 0 + +#define TYPE_1 1 /* x**7 + x**3 + 1 */ +#define BREAK_1 32 +#define DEG_1 7 +#define SEP_1 3 + +#define TYPE_2 2 /* x**15 + x + 1 */ +#define BREAK_2 64 +#define DEG_2 15 +#define SEP_2 1 + +#define TYPE_3 3 /* x**31 + x**3 + 1 */ +#define BREAK_3 128 +#define DEG_3 31 +#define SEP_3 3 + +#define TYPE_4 4 /* x**63 + x + 1 */ +#define BREAK_4 256 +#define DEG_4 63 +#define SEP_4 1 + +/* + * Array versions of the above information to make code run faster -- + * relies on fact that TYPE_i == i. + */ +#define MAX_TYPES 5 /* max number of types above */ + +static int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; +static int seps [MAX_TYPES] = { SEP_0, SEP_1, SEP_2, SEP_3, SEP_4 }; + +/* + * Initially, everything is set up as if from: + * + * initstate(1, &randtbl, 128); + * + * Note that this initialization takes advantage of the fact that srandom() + * advances the front and rear pointers 10*rand_deg times, and hence the + * rear pointer which starts at 0 will also end up at zero; thus the zeroeth + * element of the state information, which contains info about the current + * position of the rear pointer is just + * + * MAX_TYPES * (rptr - state) + TYPE_3 == TYPE_3. + */ + +static long randtbl[DEG_3 + 1] = { + TYPE_3, + 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, 0xde3b81e0, 0xdf0a6fb5, + 0xf103bc02, 0x48f340fb, 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, + 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, 0xda672e2a, 0x1588ca88, + 0xe369735d, 0x904f35f7, 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, + 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, 0xf5ad9d0e, 0x8999220b, + 0x27fb47b9, +}; + +/* + * fptr and rptr are two pointers into the state info, a front and a rear + * pointer. These two pointers are always rand_sep places aparts, as they + * cycle cyclically through the state information. (Yes, this does mean we + * could get away with just one pointer, but the code for random() is more + * efficient this way). The pointers are left positioned as they would be + * from the call + * + * initstate(1, randtbl, 128); + * + * (The position of the rear pointer, rptr, is really 0 (as explained above + * in the initialization of randtbl) because the state table pointer is set + * to point to randtbl[1] (as explained below). + */ +static long *fptr = &randtbl[SEP_3 + 1]; +static long *rptr = &randtbl[1]; + +/* + * The following things are the pointer to the state information table, the + * type of the current generator, the degree of the current polynomial being + * used, and the separation between the two pointers. Note that for efficiency + * of random(), we remember the first location of the state information, not + * the zeroeth. Hence it is valid to access state[-1], which is used to + * store the type of the R.N.G. Also, we remember the last location, since + * this is more efficient than indexing every time to find the address of + * the last element to see if the front and rear pointers have wrapped. + */ +static long *state = &randtbl[1]; +static int rand_type = TYPE_3; +static int rand_deg = DEG_3; +static int rand_sep = SEP_3; +static long *end_ptr = &randtbl[DEG_3 + 1]; + +/* + * srandom: + * + * Initialize the random number generator based on the given seed. If the + * type is the trivial no-state-information type, just remember the seed. + * Otherwise, initializes state[] based on the given "seed" via a linear + * congruential generator. Then, the pointers are set to known locations + * that are exactly rand_sep places apart. Lastly, it cycles the state + * information a given number of times to get rid of any initial dependencies + * introduced by the L.C.R.N.G. Note that the initialization of randtbl[] + * for default usage relies on values produced by this routine. + */ +void +srandom(x) + u_int x; +{ + register int i, j; + + if (rand_type == TYPE_0) + state[0] = x; + else { + j = 1; + state[0] = x; + for (i = 1; i < rand_deg; i++) + state[i] = 1103515245 * state[i - 1] + 12345; + fptr = &state[rand_sep]; + rptr = &state[0]; + for (i = 0; i < 10 * rand_deg; i++) + (void)random(); + } +} + +/* + * initstate: + * + * Initialize the state information in the given array of n bytes for future + * random number generation. Based on the number of bytes we are given, and + * the break values for the different R.N.G.'s, we choose the best (largest) + * one we can and set things up for it. srandom() is then called to + * initialize the state information. + * + * Note that on return from srandom(), we set state[-1] to be the type + * multiplexed with the current value of the rear pointer; this is so + * successive calls to initstate() won't lose this information and will be + * able to restart with setstate(). + * + * Note: the first thing we do is save the current state, if any, just like + * setstate() so that it doesn't matter when initstate is called. + * + * Returns a pointer to the old state. + */ +char * +initstate(seed, arg_state, n) + u_int seed; /* seed for R.N.G. */ + char *arg_state; /* pointer to state array */ + int n; /* # bytes of state info */ +{ + register char *ostate = (char *)(&state[-1]); + + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = MAX_TYPES * (rptr - state) + rand_type; + if (n < BREAK_0) { + (void)fprintf(stderr, + "random: not enough state (%d bytes); ignored.\n", n); + return(0); + } + if (n < BREAK_1) { + rand_type = TYPE_0; + rand_deg = DEG_0; + rand_sep = SEP_0; + } else if (n < BREAK_2) { + rand_type = TYPE_1; + rand_deg = DEG_1; + rand_sep = SEP_1; + } else if (n < BREAK_3) { + rand_type = TYPE_2; + rand_deg = DEG_2; + rand_sep = SEP_2; + } else if (n < BREAK_4) { + rand_type = TYPE_3; + rand_deg = DEG_3; + rand_sep = SEP_3; + } else { + rand_type = TYPE_4; + rand_deg = DEG_4; + rand_sep = SEP_4; + } + state = &(((long *)arg_state)[1]); /* first location */ + end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ + srandom(seed); + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = MAX_TYPES*(rptr - state) + rand_type; + return(ostate); +} + +/* + * setstate: + * + * Restore the state from the given state array. + * + * Note: it is important that we also remember the locations of the pointers + * in the current state information, and restore the locations of the pointers + * from the old state information. This is done by multiplexing the pointer + * location into the zeroeth word of the state information. + * + * Note that due to the order in which things are done, it is OK to call + * setstate() with the same state as the current state. + * + * Returns a pointer to the old state information. + */ +char * +setstate(arg_state) + char *arg_state; +{ + register long *new_state = (long *)arg_state; + register int type = new_state[0] % MAX_TYPES; + register int rear = new_state[0] / MAX_TYPES; + char *ostate = (char *)(&state[-1]); + + if (rand_type == TYPE_0) + state[-1] = rand_type; + else + state[-1] = MAX_TYPES * (rptr - state) + rand_type; + switch(type) { + case TYPE_0: + case TYPE_1: + case TYPE_2: + case TYPE_3: + case TYPE_4: + rand_type = type; + rand_deg = degrees[type]; + rand_sep = seps[type]; + break; + default: + (void)fprintf(stderr, + "random: state info corrupted; not changed.\n"); + } + state = &new_state[1]; + if (rand_type != TYPE_0) { + rptr = &state[rear]; + fptr = &state[(rear + rand_sep) % rand_deg]; + } + end_ptr = &state[rand_deg]; /* set end_ptr too */ + return(ostate); +} + +/* + * random: + * + * If we are using the trivial TYPE_0 R.N.G., just do the old linear + * congruential bit. Otherwise, we do our fancy trinomial stuff, which is + * the same in all the other cases due to all the global variables that have + * been set up. The basic operation is to add the number at the rear pointer + * into the one at the front pointer. Then both pointers are advanced to + * the next location cyclically in the table. The value returned is the sum + * generated, reduced to 31 bits by throwing away the "least random" low bit. + * + * Note: the code takes advantage of the fact that both the front and + * rear pointers can't wrap on the same call by not testing the rear + * pointer if the front one has wrapped. + * + * Returns a 31-bit random number. + */ +long +random() +{ + long i; + + if (rand_type == TYPE_0) + i = state[0] = (state[0] * 1103515245 + 12345) & 0x7fffffff; + else { + *fptr += *rptr; + i = (*fptr >> 1) & 0x7fffffff; /* chucking least random bit */ + if (++fptr >= end_ptr) { + fptr = state; + ++rptr; + } else if (++rptr >= end_ptr) + rptr = state; + } + return(i); +} diff --git a/lib/libc/stdlib/realloc.3 b/lib/libc/stdlib/realloc.3 new file mode 100644 index 0000000..903825c --- /dev/null +++ b/lib/libc/stdlib/realloc.3 @@ -0,0 +1,99 @@ +.\" Copyright (c) 1991, 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. +.\" +.\" @(#)realloc.3 8.2 (Berkeley) 4/19/94 +.\" +.Dd April 19, 1994 +.Dt REALLOC 3 +.Os +.Sh NAME +.Nm realloc +.Nd reallocation of memory function +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft void * +.Fn realloc "void *ptr" "size_t size" +.Sh DESCRIPTION +The +.Fn realloc +function changes the size of the object pointed to by +.Fa ptr +to the size specified by +.Fa size . +The contents of the object are unchanged up to the lesser +of the new and old sizes. +If the new size is larger, the value of the newly allocated portion +of the object is indeterminate. +If +.Fa ptr +is a null pointer, the +.Fn realloc +function behaves like the +.Xr malloc 3 +function for the specified size. +Otherwise, if +.Fa ptr +does not match a pointer earlier returned by the +.Xr calloc 3 , +.Xr malloc 3 , +or +.Fn realloc +function, or if the space has been deallocated +by a call to the +.Xr free +or +.Fn realloc +function, unpredictable and usually detrimental +behavior will occur. +If the space cannot be allocated, the object +pointed to by +.Fa ptr +is unchanged. +If +.Fa size +is zero and +.Fa ptr +is not a null pointer, the object it points to is freed. +.Pp +The +.Fn realloc +function returns either a null pointer or a pointer +to the possibly moved allocated space. +.Sh SEE ALSO +.Xr alloca 3 , +.Xr calloc 3 , +.Xr free 3 , +.Xr malloc 3 , +.Sh STANDARDS +The +.Fn realloc +function conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/realpath.3 b/lib/libc/stdlib/realpath.3 new file mode 100644 index 0000000..83f4a43 --- /dev/null +++ b/lib/libc/stdlib/realpath.3 @@ -0,0 +1,125 @@ +.\" Copyright (c) 1994 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Jan-Simon Pendry. +.\" +.\" 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. +.\" +.\" @(#)realpath.3 8.2 (Berkeley) 2/16/94 +.\" +.Dd "February 16, 1994" +.Dt REALPATH 3 +.Os +.Sh NAME +.Nm realpath +.Nd returns the canonicalized absolute pathname +.Sh SYNOPSIS +.Fd #include <sys/param.h> +.Fd #include <stdlib.h> +.Ft "char *" +.Fn realpath "const char *pathname" "char resolvedname[MAXPATHLEN]" +.Sh DESCRIPTION +The +.Fn realpath +function resolves all symbolic links, extra +.Dq / +characters and references to +.Pa /./ +and +.Pa /../ +in +.Fa pathname , +and copies the resulting absolute pathname into +the memory referenced by +.Fa resolvedname . +The +.Fa resolvedname +argument +.Em must +refer to a buffer capable of storing at least +.Dv MAXPATHLEN +characters. +.Pp +The +.Fn realpath +function will resolve both absolute and relative paths +and return the absolute pathname corresponding to +.Fa pathname . +All but the last component of +.Fa pathname +must exist when +.Fn realpath +is called. +.Sh "RETURN VALUES" +The +.Fn realpath +function returns +.Fa resolved_name +on success. +If an error occurs, +.Fn realpath +returns +.Dv NULL , +and +.Fa resolved_name +contains the pathname which caused the problem. +.Sh ERRORS +The function +.Fn realpath +may fail and set the external variable +.Va errno +for any of the errors specified for the library functions +.Xr chdir 2 , +.Xr close 2 , +.Xr fchdir 2 , +.Xr lstat 2 , +.Xr open 2 , +.Xr readlink 2 +and +.Xr getcwd 3 . +.Sh CAVEATS +This implementation of +.Fn realpath +differs slightly from the Solaris implementation. +The +.Bx 4.4 +version always returns absolute pathnames, +whereas the Solaris implementation will, +under certain circumstances, return a relative +.Fa resolved_path +when given a relative +.Fa pathname . +.Sh "SEE ALSO" +.Xr getcwd 3 +.Sh HISTORY +The +.Fn realpath +function call first appeared in +.Bx 4.4 . diff --git a/lib/libc/stdlib/realpath.c b/lib/libc/stdlib/realpath.c new file mode 100644 index 0000000..20efabd --- /dev/null +++ b/lib/libc/stdlib/realpath.c @@ -0,0 +1,158 @@ +/* + * Copyright (c) 1994 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Jan-Simon Pendry. + * + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)realpath.c 8.1 (Berkeley) 2/16/94"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/param.h> +#include <sys/stat.h> + +#include <errno.h> +#include <fcntl.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +/* + * char *realpath(const char *path, char resolved_path[MAXPATHLEN]); + * + * Find the real name of path, by removing all ".", ".." and symlink + * components. Returns (resolved) on success, or (NULL) on failure, + * in which case the path which caused trouble is left in (resolved). + */ +char * +realpath(path, resolved) + const char *path; + char *resolved; +{ + struct stat sb; + int fd, n, rootd, serrno; + char *p, *q, wbuf[MAXPATHLEN]; + + /* Save the starting point. */ + if ((fd = open(".", O_RDONLY)) < 0) { + (void)strcpy(resolved, "."); + return (NULL); + } + + /* + * Find the dirname and basename from the path to be resolved. + * Change directory to the dirname component. + * lstat the basename part. + * if it is a symlink, read in the value and loop. + * if it is a directory, then change to that directory. + * get the current directory name and append the basename. + */ + (void)strncpy(resolved, path, MAXPATHLEN - 1); + resolved[MAXPATHLEN - 1] = '\0'; +loop: + q = strrchr(resolved, '/'); + if (q != NULL) { + p = q + 1; + if (q == resolved) + q = "/"; + else { + do { + --q; + } while (q > resolved && *q == '/'); + q[1] = '\0'; + q = resolved; + } + if (chdir(q) < 0) + goto err1; + } else + p = resolved; + + /* Deal with the last component. */ + if (lstat(p, &sb) == 0) { + if (S_ISLNK(sb.st_mode)) { + n = readlink(p, resolved, MAXPATHLEN); + if (n < 0) + goto err1; + resolved[n] = '\0'; + goto loop; + } + if (S_ISDIR(sb.st_mode)) { + if (chdir(p) < 0) + goto err1; + p = ""; + } + } + + /* + * Save the last component name and get the full pathname of + * the current directory. + */ + (void)strcpy(wbuf, p); + if (getcwd(resolved, MAXPATHLEN) == 0) + goto err1; + + /* + * Join the two strings together, ensuring that the right thing + * happens if the last component is empty, or the dirname is root. + */ + if (resolved[0] == '/' && resolved[1] == '\0') + rootd = 1; + else + rootd = 0; + + if (*wbuf) { + if (strlen(resolved) + strlen(wbuf) + rootd + 1 > MAXPATHLEN) { + errno = ENAMETOOLONG; + goto err1; + } + if (rootd == 0) + (void)strcat(resolved, "/"); + (void)strcat(resolved, wbuf); + } + + /* Go back to where we came from. */ + if (fchdir(fd) < 0) { + serrno = errno; + goto err2; + } + + /* It's okay if the close fails, what's an fd more or less? */ + (void)close(fd); + return (resolved); + +err1: serrno = errno; + (void)fchdir(fd); +err2: (void)close(fd); + errno = serrno; + return (NULL); +} diff --git a/lib/libc/stdlib/setenv.c b/lib/libc/stdlib/setenv.c new file mode 100644 index 0000000..b36d673 --- /dev/null +++ b/lib/libc/stdlib/setenv.c @@ -0,0 +1,116 @@ +/* + * Copyright (c) 1987, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)setenv.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <stddef.h> +#include <stdlib.h> +#include <string.h> + +char *__findenv __P((const char *, int *)); + +/* + * setenv -- + * Set the value of the environmental variable "name" to be + * "value". If rewrite is set, replace any current value. + */ +setenv(name, value, rewrite) + register const char *name; + register const char *value; + int rewrite; +{ + extern char **environ; + static int alloced; /* if allocated space before */ + register char *c; + int l_value, offset; + + if (*value == '=') /* no `=' in value */ + ++value; + l_value = strlen(value); + if ((c = __findenv(name, &offset))) { /* find if already exists */ + if (!rewrite) + return (0); + if (strlen(c) >= l_value) { /* old larger; copy over */ + while (*c++ = *value++); + return (0); + } + } else { /* create new slot */ + register int cnt; + register char **p; + + for (p = environ, cnt = 0; *p; ++p, ++cnt); + if (alloced) { /* just increase size */ + environ = (char **)realloc((char *)environ, + (size_t)(sizeof(char *) * (cnt + 2))); + if (!environ) + return (-1); + } + else { /* get new space */ + alloced = 1; /* copy old entries into it */ + p = malloc((size_t)(sizeof(char *) * (cnt + 2))); + if (!p) + return (-1); + bcopy(environ, p, cnt * sizeof(char *)); + environ = p; + } + environ[cnt + 1] = NULL; + offset = cnt; + } + for (c = (char *)name; *c && *c != '='; ++c); /* no `=' in name */ + if (!(environ[offset] = /* name + `=' + value */ + malloc((size_t)((int)(c - name) + l_value + 2)))) + return (-1); + for (c = environ[offset]; (*c = *name++) && *c != '='; ++c); + for (*c++ = '='; *c++ = *value++;); + return (0); +} + +/* + * unsetenv(name) -- + * Delete environmental variable "name". + */ +void +unsetenv(name) + const char *name; +{ + extern char **environ; + register char **p; + int offset; + + while (__findenv(name, &offset)) /* if set multiple times */ + for (p = &environ[offset];; ++p) + if (!(*p = *(p + 1))) + break; +} diff --git a/lib/libc/stdlib/strtod.3 b/lib/libc/stdlib/strtod.3 new file mode 100644 index 0000000..e1d4c39 --- /dev/null +++ b/lib/libc/stdlib/strtod.3 @@ -0,0 +1,132 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)strtod.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt STRTOD 3 +.Os +.Sh NAME +.Nm strtod +.Nd convert +.Tn ASCII +string to double +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft double +.Fn strtod "const char *nptr" "char **endptr" +.Sh DESCRIPTION +The +.Fn strtod +function converts the initial portion of the string +pointed to by +.Fa nptr +to +.Em double +representation. +.Pp +The expected form of the string is an optional plus (``+'') or minus +sign (``\-'') followed by a sequence of digits optionally containing +a decimal-point character, optionally followed by an exponent. +An exponent consists of an ``E'' or ``e'', followed by an optional plus +or minus sign, followed by a sequence of digits. +.Pp +Leading white-space characters in the string (as defined by the +.Xr isspace 3 +function) are skipped. +.Sh RETURN VALUES +The +.Fn strtod +function returns the converted value, if any. +.Pp +If +.Fa endptr +is not +.Dv NULL , +a pointer to the character after the last character used +in the conversion is stored in the location referenced by +.Fa endptr . +.Pp +If no conversion is performed, zero is returned and the value of +.Fa nptr +is stored in the location referenced by +.Fa endptr . +.Pp +If the correct value would cause overflow, plus or minus +.Dv HUGE_VAL +is returned (according to the sign of the value), and +.Dv ERANGE +is stored in +.Va errno . +If the correct value would cause underflow, zero is +returned and +.Dv ERANGE +is stored in +.Va errno . +.Sh ERRORS +.Bl -tag -width [ERANGE] +.It Bq Er ERANGE +Overflow or underflow occurred. +.Sh SEE ALSO +.Xr atof 3 , +.Xr atoi 3 , +.Xr atol 3 , +.Xr strtol 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn strtod +function +conforms to +.St -ansiC . +.Sh AUTHORS +The author of this software is David M. Gay. +.Pp +Copyright (c) 1991 by AT&T. +.Pp +Permission to use, copy, modify, and distribute this software for any +purpose without fee is hereby granted, provided that this entire notice +is included in all copies of any software which is or includes a copy +or modification of this software and in all copies of the supporting +documentation for such software. +.Pp +THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED +WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR AT&T MAKES ANY +REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY +OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. +.Pp +Contact your vendor for a free copy of the source code to +.Fn strtod +and accompanying functions. diff --git a/lib/libc/stdlib/strtod.c b/lib/libc/stdlib/strtod.c new file mode 100644 index 0000000..cd82c73 --- /dev/null +++ b/lib/libc/stdlib/strtod.c @@ -0,0 +1,2447 @@ +/*- + * Copyright (c) 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtod.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +/**************************************************************** + * + * The author of this software is David M. Gay. + * + * Copyright (c) 1991 by AT&T. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose without fee is hereby granted, provided that this entire notice + * is included in all copies of any software which is or includes a copy + * or modification of this software and in all copies of the supporting + * documentation for such software. + * + * THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED + * WARRANTY. IN PARTICULAR, NEITHER THE AUTHOR NOR AT&T MAKES ANY + * REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY + * OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE. + * + ***************************************************************/ + +/* Please send bug reports to + David M. Gay + AT&T Bell Laboratories, Room 2C-463 + 600 Mountain Avenue + Murray Hill, NJ 07974-2070 + U.S.A. + dmg@research.att.com or research!dmg + */ + +/* strtod for IEEE-, VAX-, and IBM-arithmetic machines. + * + * This strtod returns a nearest machine number to the input decimal + * string (or sets errno to ERANGE). With IEEE arithmetic, ties are + * broken by the IEEE round-even rule. Otherwise ties are broken by + * biased rounding (add half and chop). + * + * Inspired loosely by William D. Clinger's paper "How to Read Floating + * Point Numbers Accurately" [Proc. ACM SIGPLAN '90, pp. 92-101]. + * + * Modifications: + * + * 1. We only require IEEE, IBM, or VAX double-precision + * arithmetic (not IEEE double-extended). + * 2. We get by with floating-point arithmetic in a case that + * Clinger missed -- when we're computing d * 10^n + * for a small integer d and the integer n is not too + * much larger than 22 (the maximum integer k for which + * we can represent 10^k exactly), we may be able to + * compute (d*10^k) * 10^(e-k) with just one roundoff. + * 3. Rather than a bit-at-a-time adjustment of the binary + * result in the hard case, we use floating-point + * arithmetic to determine the adjustment to within + * one bit; only in really hard cases do we need to + * compute a second residual. + * 4. Because of 3., we don't need a large table of powers of 10 + * for ten-to-e (just some small tables, e.g. of 10^k + * for 0 <= k <= 22). + */ + +/* + * #define IEEE_8087 for IEEE-arithmetic machines where the least + * significant byte has the lowest address. + * #define IEEE_MC68k for IEEE-arithmetic machines where the most + * significant byte has the lowest address. + * #define Sudden_Underflow for IEEE-format machines without gradual + * underflow (i.e., that flush to zero on underflow). + * #define IBM for IBM mainframe-style floating-point arithmetic. + * #define VAX for VAX-style floating-point arithmetic. + * #define Unsigned_Shifts if >> does treats its left operand as unsigned. + * #define No_leftright to omit left-right logic in fast floating-point + * computation of dtoa. + * #define Check_FLT_ROUNDS if FLT_ROUNDS can assume the values 2 or 3. + * #define RND_PRODQUOT to use rnd_prod and rnd_quot (assembly routines + * that use extended-precision instructions to compute rounded + * products and quotients) with IBM. + * #define ROUND_BIASED for IEEE-format with biased rounding. + * #define Inaccurate_Divide for IEEE-format with correctly rounded + * products but inaccurate quotients, e.g., for Intel i860. + * #define Just_16 to store 16 bits per 32-bit long when doing high-precision + * integer arithmetic. Whether this speeds things up or slows things + * down depends on the machine and the number being converted. + * #define KR_headers for old-style C function headers. + * #define Bad_float_h if your system lacks a float.h or if it does not + * define some or all of DBL_DIG, DBL_MAX_10_EXP, DBL_MAX_EXP, + * FLT_RADIX, FLT_ROUNDS, and DBL_MAX. + */ + +#if defined(i386) || defined(mips) && defined(MIPSEL) +#define IEEE_8087 +#else +#define IEEE_MC68k +#endif + +#ifdef DEBUG +#include "stdio.h" +#define Bug(x) {fprintf(stderr, "%s\n", x); exit(1);} +#endif + +#ifdef __cplusplus +#include "malloc.h" +#include "memory.h" +#else +#ifndef KR_headers +#include "stdlib.h" +#include "string.h" +#else +#include "malloc.h" +#include "memory.h" +#endif +#endif + +#include "errno.h" +#ifdef Bad_float_h +#undef __STDC__ +#ifdef IEEE_MC68k +#define IEEE_ARITHMETIC +#endif +#ifdef IEEE_8087 +#define IEEE_ARITHMETIC +#endif +#ifdef IEEE_ARITHMETIC +#define DBL_DIG 15 +#define DBL_MAX_10_EXP 308 +#define DBL_MAX_EXP 1024 +#define FLT_RADIX 2 +#define FLT_ROUNDS 1 +#define DBL_MAX 1.7976931348623157e+308 +#endif + +#ifdef IBM +#define DBL_DIG 16 +#define DBL_MAX_10_EXP 75 +#define DBL_MAX_EXP 63 +#define FLT_RADIX 16 +#define FLT_ROUNDS 0 +#define DBL_MAX 7.2370055773322621e+75 +#endif + +#ifdef VAX +#define DBL_DIG 16 +#define DBL_MAX_10_EXP 38 +#define DBL_MAX_EXP 127 +#define FLT_RADIX 2 +#define FLT_ROUNDS 1 +#define DBL_MAX 1.7014118346046923e+38 +#endif + +#ifndef LONG_MAX +#define LONG_MAX 2147483647 +#endif +#else +#include "float.h" +#endif +#ifndef __MATH_H__ +#include "math.h" +#endif + +#ifdef __cplusplus +extern "C" { +#endif + +#ifndef CONST +#ifdef KR_headers +#define CONST /* blank */ +#else +#define CONST const +#endif +#endif + +#ifdef Unsigned_Shifts +#define Sign_Extend(a,b) if (b < 0) a |= 0xffff0000; +#else +#define Sign_Extend(a,b) /*no-op*/ +#endif + +#if defined(IEEE_8087) + defined(IEEE_MC68k) + defined(VAX) + defined(IBM) != 1 +Exactly one of IEEE_8087, IEEE_MC68k, VAX, or IBM should be defined. +#endif + +#ifdef IEEE_8087 +#define word0(x) ((unsigned long *)&x)[1] +#define word1(x) ((unsigned long *)&x)[0] +#else +#define word0(x) ((unsigned long *)&x)[0] +#define word1(x) ((unsigned long *)&x)[1] +#endif + +/* The following definition of Storeinc is appropriate for MIPS processors. + * An alternative that might be better on some machines is + * #define Storeinc(a,b,c) (*a++ = b << 16 | c & 0xffff) + */ +#if defined(IEEE_8087) + defined(VAX) +#define Storeinc(a,b,c) (((unsigned short *)a)[1] = (unsigned short)b, \ +((unsigned short *)a)[0] = (unsigned short)c, a++) +#else +#define Storeinc(a,b,c) (((unsigned short *)a)[0] = (unsigned short)b, \ +((unsigned short *)a)[1] = (unsigned short)c, a++) +#endif + +/* #define P DBL_MANT_DIG */ +/* Ten_pmax = floor(P*log(2)/log(5)) */ +/* Bletch = (highest power of 2 < DBL_MAX_10_EXP) / 16 */ +/* Quick_max = floor((P-1)*log(FLT_RADIX)/log(10) - 1) */ +/* Int_max = floor(P*log(FLT_RADIX)/log(10) - 1) */ + +#if defined(IEEE_8087) + defined(IEEE_MC68k) +#define Exp_shift 20 +#define Exp_shift1 20 +#define Exp_msk1 0x100000 +#define Exp_msk11 0x100000 +#define Exp_mask 0x7ff00000 +#define P 53 +#define Bias 1023 +#define IEEE_Arith +#define Emin (-1022) +#define Exp_1 0x3ff00000 +#define Exp_11 0x3ff00000 +#define Ebits 11 +#define Frac_mask 0xfffff +#define Frac_mask1 0xfffff +#define Ten_pmax 22 +#define Bletch 0x10 +#define Bndry_mask 0xfffff +#define Bndry_mask1 0xfffff +#define LSB 1 +#define Sign_bit 0x80000000 +#define Log2P 1 +#define Tiny0 0 +#define Tiny1 1 +#define Quick_max 14 +#define Int_max 14 +#define Infinite(x) (word0(x) == 0x7ff00000) /* sufficient test for here */ +#else +#undef Sudden_Underflow +#define Sudden_Underflow +#ifdef IBM +#define Exp_shift 24 +#define Exp_shift1 24 +#define Exp_msk1 0x1000000 +#define Exp_msk11 0x1000000 +#define Exp_mask 0x7f000000 +#define P 14 +#define Bias 65 +#define Exp_1 0x41000000 +#define Exp_11 0x41000000 +#define Ebits 8 /* exponent has 7 bits, but 8 is the right value in b2d */ +#define Frac_mask 0xffffff +#define Frac_mask1 0xffffff +#define Bletch 4 +#define Ten_pmax 22 +#define Bndry_mask 0xefffff +#define Bndry_mask1 0xffffff +#define LSB 1 +#define Sign_bit 0x80000000 +#define Log2P 4 +#define Tiny0 0x100000 +#define Tiny1 0 +#define Quick_max 14 +#define Int_max 15 +#else /* VAX */ +#define Exp_shift 23 +#define Exp_shift1 7 +#define Exp_msk1 0x80 +#define Exp_msk11 0x800000 +#define Exp_mask 0x7f80 +#define P 56 +#define Bias 129 +#define Exp_1 0x40800000 +#define Exp_11 0x4080 +#define Ebits 8 +#define Frac_mask 0x7fffff +#define Frac_mask1 0xffff007f +#define Ten_pmax 24 +#define Bletch 2 +#define Bndry_mask 0xffff007f +#define Bndry_mask1 0xffff007f +#define LSB 0x10000 +#define Sign_bit 0x8000 +#define Log2P 1 +#define Tiny0 0x80 +#define Tiny1 0 +#define Quick_max 15 +#define Int_max 15 +#endif +#endif + +#ifndef IEEE_Arith +#define ROUND_BIASED +#endif + +#ifdef RND_PRODQUOT +#define rounded_product(a,b) a = rnd_prod(a, b) +#define rounded_quotient(a,b) a = rnd_quot(a, b) +#ifdef KR_headers +extern double rnd_prod(), rnd_quot(); +#else +extern double rnd_prod(double, double), rnd_quot(double, double); +#endif +#else +#define rounded_product(a,b) a *= b +#define rounded_quotient(a,b) a /= b +#endif + +#define Big0 (Frac_mask1 | Exp_msk1*(DBL_MAX_EXP+Bias-1)) +#define Big1 0xffffffff + +#ifndef Just_16 +/* When Pack_32 is not defined, we store 16 bits per 32-bit long. + * This makes some inner loops simpler and sometimes saves work + * during multiplications, but it often seems to make things slightly + * slower. Hence the default is now to store 32 bits per long. + */ +#ifndef Pack_32 +#define Pack_32 +#endif +#endif + +#define Kmax 15 + +#ifdef __cplusplus +extern "C" double strtod(const char *s00, char **se); +extern "C" char *dtoa(double d, int mode, int ndigits, + int *decpt, int *sign, char **rve); +#endif + + struct +Bigint { + struct Bigint *next; + int k, maxwds, sign, wds; + unsigned long x[1]; +}; + + typedef struct Bigint Bigint; + + static Bigint *freelist[Kmax+1]; + + static Bigint * +Balloc +#ifdef KR_headers + (k) int k; +#else + (int k) +#endif +{ + int x; + Bigint *rv; + + if (rv = freelist[k]) { + freelist[k] = rv->next; + } else { + x = 1 << k; + rv = (Bigint *)malloc(sizeof(Bigint) + (x-1)*sizeof(long)); + rv->k = k; + rv->maxwds = x; + } + rv->sign = rv->wds = 0; + return rv; +} + + static void +Bfree +#ifdef KR_headers + (v) Bigint *v; +#else + (Bigint *v) +#endif +{ + if (v) { + v->next = freelist[v->k]; + freelist[v->k] = v; + } +} + +#define Bcopy(x,y) memcpy((char *)&x->sign, (char *)&y->sign, \ +y->wds*sizeof(long) + 2*sizeof(int)) + + static Bigint * +multadd +#ifdef KR_headers + (b, m, a) Bigint *b; int m, a; +#else + (Bigint *b, int m, int a) /* multiply by m and add a */ +#endif +{ + int i, wds; + unsigned long *x, y; +#ifdef Pack_32 + unsigned long xi, z; +#endif + Bigint *b1; + + wds = b->wds; + x = b->x; + i = 0; + do { +#ifdef Pack_32 + xi = *x; + y = (xi & 0xffff) * m + a; + z = (xi >> 16) * m + (y >> 16); + a = (int)(z >> 16); + *x++ = (z << 16) + (y & 0xffff); +#else + y = *x * m + a; + a = (int)(y >> 16); + *x++ = y & 0xffff; +#endif + } while (++i < wds); + if (a) { + if (wds >= b->maxwds) { + b1 = Balloc(b->k+1); + Bcopy(b1, b); + Bfree(b); + b = b1; + } + b->x[wds++] = a; + b->wds = wds; + } + return b; +} + + static Bigint * +s2b +#ifdef KR_headers + (s, nd0, nd, y9) CONST char *s; int nd0, nd; unsigned long y9; +#else + (CONST char *s, int nd0, int nd, unsigned long y9) +#endif +{ + Bigint *b; + int i, k; + long x, y; + + x = (nd + 8) / 9; + for (k = 0, y = 1; x > y; y <<= 1, k++) ; +#ifdef Pack_32 + b = Balloc(k); + b->x[0] = y9; + b->wds = 1; +#else + b = Balloc(k+1); + b->x[0] = y9 & 0xffff; + b->wds = (b->x[1] = y9 >> 16) ? 2 : 1; +#endif + + i = 9; + if (9 < nd0) { + s += 9; + do + b = multadd(b, 10, *s++ - '0'); + while (++i < nd0); + s++; + } else + s += 10; + for (; i < nd; i++) + b = multadd(b, 10, *s++ - '0'); + return b; +} + + static int +hi0bits +#ifdef KR_headers + (x) register unsigned long x; +#else + (register unsigned long x) +#endif +{ + register int k = 0; + + if (!(x & 0xffff0000)) { + k = 16; + x <<= 16; + } + if (!(x & 0xff000000)) { + k += 8; + x <<= 8; + } + if (!(x & 0xf0000000)) { + k += 4; + x <<= 4; + } + if (!(x & 0xc0000000)) { + k += 2; + x <<= 2; + } + if (!(x & 0x80000000)) { + k++; + if (!(x & 0x40000000)) + return 32; + } + return k; +} + + static int +lo0bits +#ifdef KR_headers + (y) unsigned long *y; +#else + (unsigned long *y) +#endif +{ + register int k; + register unsigned long x = *y; + + if (x & 7) { + if (x & 1) + return 0; + if (x & 2) { + *y = x >> 1; + return 1; + } + *y = x >> 2; + return 2; + } + k = 0; + if (!(x & 0xffff)) { + k = 16; + x >>= 16; + } + if (!(x & 0xff)) { + k += 8; + x >>= 8; + } + if (!(x & 0xf)) { + k += 4; + x >>= 4; + } + if (!(x & 0x3)) { + k += 2; + x >>= 2; + } + if (!(x & 1)) { + k++; + x >>= 1; + if (!x & 1) + return 32; + } + *y = x; + return k; +} + + static Bigint * +i2b +#ifdef KR_headers + (i) int i; +#else + (int i) +#endif +{ + Bigint *b; + + b = Balloc(1); + b->x[0] = i; + b->wds = 1; + return b; + } + + static Bigint * +mult +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + Bigint *c; + int k, wa, wb, wc; + unsigned long carry, y, z; + unsigned long *x, *xa, *xae, *xb, *xbe, *xc, *xc0; +#ifdef Pack_32 + unsigned long z2; +#endif + + if (a->wds < b->wds) { + c = a; + a = b; + b = c; + } + k = a->k; + wa = a->wds; + wb = b->wds; + wc = wa + wb; + if (wc > a->maxwds) + k++; + c = Balloc(k); + for (x = c->x, xa = x + wc; x < xa; x++) + *x = 0; + xa = a->x; + xae = xa + wa; + xb = b->x; + xbe = xb + wb; + xc0 = c->x; +#ifdef Pack_32 + for (; xb < xbe; xb++, xc0++) { + if (y = *xb & 0xffff) { + x = xa; + xc = xc0; + carry = 0; + do { + z = (*x & 0xffff) * y + (*xc & 0xffff) + carry; + carry = z >> 16; + z2 = (*x++ >> 16) * y + (*xc >> 16) + carry; + carry = z2 >> 16; + Storeinc(xc, z2, z); + } while (x < xae); + *xc = carry; + } + if (y = *xb >> 16) { + x = xa; + xc = xc0; + carry = 0; + z2 = *xc; + do { + z = (*x & 0xffff) * y + (*xc >> 16) + carry; + carry = z >> 16; + Storeinc(xc, z, z2); + z2 = (*x++ >> 16) * y + (*xc & 0xffff) + carry; + carry = z2 >> 16; + } while (x < xae); + *xc = z2; + } + } +#else + for (; xb < xbe; xc0++) { + if (y = *xb++) { + x = xa; + xc = xc0; + carry = 0; + do { + z = *x++ * y + *xc + carry; + carry = z >> 16; + *xc++ = z & 0xffff; + } while (x < xae); + *xc = carry; + } + } +#endif + for (xc0 = c->x, xc = xc0 + wc; wc > 0 && !*--xc; --wc) ; + c->wds = wc; + return c; +} + + static Bigint *p5s; + + static Bigint * +pow5mult +#ifdef KR_headers + (b, k) Bigint *b; int k; +#else + (Bigint *b, int k) +#endif +{ + Bigint *b1, *p5, *p51; + int i; + static int p05[3] = { 5, 25, 125 }; + + if (i = k & 3) + b = multadd(b, p05[i-1], 0); + + if (!(k >>= 2)) + return b; + if (!(p5 = p5s)) { + /* first time */ + p5 = p5s = i2b(625); + p5->next = 0; + } + for (;;) { + if (k & 1) { + b1 = mult(b, p5); + Bfree(b); + b = b1; + } + if (!(k >>= 1)) + break; + if (!(p51 = p5->next)) { + p51 = p5->next = mult(p5,p5); + p51->next = 0; + } + p5 = p51; + } + return b; +} + + static Bigint * +lshift +#ifdef KR_headers + (b, k) Bigint *b; int k; +#else + (Bigint *b, int k) +#endif +{ + int i, k1, n, n1; + Bigint *b1; + unsigned long *x, *x1, *xe, z; + +#ifdef Pack_32 + n = k >> 5; +#else + n = k >> 4; +#endif + k1 = b->k; + n1 = n + b->wds + 1; + for (i = b->maxwds; n1 > i; i <<= 1) + k1++; + b1 = Balloc(k1); + x1 = b1->x; + for (i = 0; i < n; i++) + *x1++ = 0; + x = b->x; + xe = x + b->wds; +#ifdef Pack_32 + if (k &= 0x1f) { + k1 = 32 - k; + z = 0; + do { + *x1++ = *x << k | z; + z = *x++ >> k1; + } while (x < xe); + if (*x1 = z) + ++n1; + } +#else + if (k &= 0xf) { + k1 = 16 - k; + z = 0; + do { + *x1++ = *x << k & 0xffff | z; + z = *x++ >> k1; + } while (x < xe); + if (*x1 = z) + ++n1; + } +#endif + else + do + *x1++ = *x++; + while (x < xe); + b1->wds = n1 - 1; + Bfree(b); + return b1; +} + + static int +cmp +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + unsigned long *xa, *xa0, *xb, *xb0; + int i, j; + + i = a->wds; + j = b->wds; +#ifdef DEBUG + if (i > 1 && !a->x[i-1]) + Bug("cmp called with a->x[a->wds-1] == 0"); + if (j > 1 && !b->x[j-1]) + Bug("cmp called with b->x[b->wds-1] == 0"); +#endif + if (i -= j) + return i; + xa0 = a->x; + xa = xa0 + j; + xb0 = b->x; + xb = xb0 + j; + for (;;) { + if (*--xa != *--xb) + return *xa < *xb ? -1 : 1; + if (xa <= xa0) + break; + } + return 0; +} + + static Bigint * +diff +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + Bigint *c; + int i, wa, wb; + long borrow, y; /* We need signed shifts here. */ + unsigned long *xa, *xae, *xb, *xbe, *xc; +#ifdef Pack_32 + long z; +#endif + + i = cmp(a,b); + if (!i) { + c = Balloc(0); + c->wds = 1; + c->x[0] = 0; + return c; + } + if (i < 0) { + c = a; + a = b; + b = c; + i = 1; + } else + i = 0; + c = Balloc(a->k); + c->sign = i; + wa = a->wds; + xa = a->x; + xae = xa + wa; + wb = b->wds; + xb = b->x; + xbe = xb + wb; + xc = c->x; + borrow = 0; +#ifdef Pack_32 + do { + y = (*xa & 0xffff) - (*xb & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*xa++ >> 16) - (*xb++ >> 16) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(xc, z, y); + } while (xb < xbe); + while (xa < xae) { + y = (*xa & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*xa++ >> 16) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(xc, z, y); + } +#else + do { + y = *xa++ - *xb++ + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *xc++ = y & 0xffff; + } while (xb < xbe); + while (xa < xae) { + y = *xa++ + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *xc++ = y & 0xffff; + } +#endif + while (!*--xc) + wa--; + c->wds = wa; + return c; +} + + static double +ulp +#ifdef KR_headers + (x) double x; +#else + (double x) +#endif +{ + register long L; + double a; + + L = (word0(x) & Exp_mask) - (P-1)*Exp_msk1; +#ifndef Sudden_Underflow + if (L > 0) { +#endif +#ifdef IBM + L |= Exp_msk1 >> 4; +#endif + word0(a) = L; + word1(a) = 0; +#ifndef Sudden_Underflow + } else { + L = -L >> Exp_shift; + if (L < Exp_shift) { + word0(a) = 0x80000 >> L; + word1(a) = 0; + } else { + word0(a) = 0; + L -= Exp_shift; + word1(a) = L >= 31 ? 1 : 1 << 31 - L; + } + } +#endif + return a; +} + + static double +b2d +#ifdef KR_headers + (a, e) Bigint *a; int *e; +#else + (Bigint *a, int *e) +#endif +{ + unsigned long *xa, *xa0, w, y, z; + int k; + double d; +#ifdef VAX + unsigned long d0, d1; +#else +#define d0 word0(d) +#define d1 word1(d) +#endif + + xa0 = a->x; + xa = xa0 + a->wds; + y = *--xa; +#ifdef DEBUG + if (!y) Bug("zero y in b2d"); +#endif + k = hi0bits(y); + *e = 32 - k; +#ifdef Pack_32 + if (k < Ebits) { + d0 = Exp_1 | y >> Ebits - k; + w = xa > xa0 ? *--xa : 0; + d1 = y << (32-Ebits) + k | w >> Ebits - k; + goto ret_d; + } + z = xa > xa0 ? *--xa : 0; + if (k -= Ebits) { + d0 = Exp_1 | y << k | z >> 32 - k; + y = xa > xa0 ? *--xa : 0; + d1 = z << k | y >> 32 - k; + } else { + d0 = Exp_1 | y; + d1 = z; + } +#else + if (k < Ebits + 16) { + z = xa > xa0 ? *--xa : 0; + d0 = Exp_1 | y << k - Ebits | z >> Ebits + 16 - k; + w = xa > xa0 ? *--xa : 0; + y = xa > xa0 ? *--xa : 0; + d1 = z << k + 16 - Ebits | w << k - Ebits | y >> 16 + Ebits - k; + goto ret_d; + } + z = xa > xa0 ? *--xa : 0; + w = xa > xa0 ? *--xa : 0; + k -= Ebits + 16; + d0 = Exp_1 | y << k + 16 | z << k | w >> 16 - k; + y = xa > xa0 ? *--xa : 0; + d1 = w << k + 16 | y << k; +#endif + ret_d: +#ifdef VAX + word0(d) = d0 >> 16 | d0 << 16; + word1(d) = d1 >> 16 | d1 << 16; +#else +#undef d0 +#undef d1 +#endif + return d; +} + + static Bigint * +d2b +#ifdef KR_headers + (d, e, bits) double d; int *e, *bits; +#else + (double d, int *e, int *bits) +#endif +{ + Bigint *b; + int de, i, k; + unsigned long *x, y, z; +#ifdef VAX + unsigned long d0, d1; + d0 = word0(d) >> 16 | word0(d) << 16; + d1 = word1(d) >> 16 | word1(d) << 16; +#else +#define d0 word0(d) +#define d1 word1(d) +#endif + +#ifdef Pack_32 + b = Balloc(1); +#else + b = Balloc(2); +#endif + x = b->x; + + z = d0 & Frac_mask; + d0 &= 0x7fffffff; /* clear sign bit, which we ignore */ +#ifdef Sudden_Underflow + de = (int)(d0 >> Exp_shift); +#ifndef IBM + z |= Exp_msk11; +#endif +#else + if (de = (int)(d0 >> Exp_shift)) + z |= Exp_msk1; +#endif +#ifdef Pack_32 + if (y = d1) { + if (k = lo0bits(&y)) { + x[0] = y | z << 32 - k; + z >>= k; + } + else + x[0] = y; + i = b->wds = (x[1] = z) ? 2 : 1; + } else { +#ifdef DEBUG + if (!z) + Bug("Zero passed to d2b"); +#endif + k = lo0bits(&z); + x[0] = z; + i = b->wds = 1; + k += 32; + } +#else + if (y = d1) { + if (k = lo0bits(&y)) + if (k >= 16) { + x[0] = y | z << 32 - k & 0xffff; + x[1] = z >> k - 16 & 0xffff; + x[2] = z >> k; + i = 2; + } else { + x[0] = y & 0xffff; + x[1] = y >> 16 | z << 16 - k & 0xffff; + x[2] = z >> k & 0xffff; + x[3] = z >> k+16; + i = 3; + } + else { + x[0] = y & 0xffff; + x[1] = y >> 16; + x[2] = z & 0xffff; + x[3] = z >> 16; + i = 3; + } + } else { +#ifdef DEBUG + if (!z) + Bug("Zero passed to d2b"); +#endif + k = lo0bits(&z); + if (k >= 16) { + x[0] = z; + i = 0; + } else { + x[0] = z & 0xffff; + x[1] = z >> 16; + i = 1; + } + k += 32; + } + while (!x[i]) + --i; + b->wds = i + 1; +#endif +#ifndef Sudden_Underflow + if (de) { +#endif +#ifdef IBM + *e = (de - Bias - (P-1) << 2) + k; + *bits = 4*P + 8 - k - hi0bits(word0(d) & Frac_mask); +#else + *e = de - Bias - (P-1) + k; + *bits = P - k; +#endif +#ifndef Sudden_Underflow + } else { + *e = de - Bias - (P-1) + 1 + k; +#ifdef Pack_32 + *bits = 32*i - hi0bits(x[i-1]); +#else + *bits = (i+2)*16 - hi0bits(x[i]); +#endif + } +#endif + return b; +} +#undef d0 +#undef d1 + + static double +ratio +#ifdef KR_headers + (a, b) Bigint *a, *b; +#else + (Bigint *a, Bigint *b) +#endif +{ + double da, db; + int k, ka, kb; + + da = b2d(a, &ka); + db = b2d(b, &kb); +#ifdef Pack_32 + k = ka - kb + 32*(a->wds - b->wds); +#else + k = ka - kb + 16*(a->wds - b->wds); +#endif +#ifdef IBM + if (k > 0) { + word0(da) += (k >> 2)*Exp_msk1; + if (k &= 3) + da *= 1 << k; + } else { + k = -k; + word0(db) += (k >> 2)*Exp_msk1; + if (k &= 3) + db *= 1 << k; + } +#else + if (k > 0) + word0(da) += k*Exp_msk1; + else { + k = -k; + word0(db) += k*Exp_msk1; + } +#endif + return da / db; +} + + static double +tens[] = { + 1e0, 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, + 1e10, 1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, + 1e20, 1e21, 1e22 +#ifdef VAX + , 1e23, 1e24 +#endif + }; + + static double +#ifdef IEEE_Arith +bigtens[] = { 1e16, 1e32, 1e64, 1e128, 1e256 }; +static double tinytens[] = { 1e-16, 1e-32, 1e-64, 1e-128, 1e-256 }; +#define n_bigtens 5 +#else +#ifdef IBM +bigtens[] = { 1e16, 1e32, 1e64 }; +static double tinytens[] = { 1e-16, 1e-32, 1e-64 }; +#define n_bigtens 3 +#else +bigtens[] = { 1e16, 1e32 }; +static double tinytens[] = { 1e-16, 1e-32 }; +#define n_bigtens 2 +#endif +#endif + + double +strtod +#ifdef KR_headers + (s00, se) CONST char *s00; char **se; +#else + (CONST char *s00, char **se) +#endif +{ + int bb2, bb5, bbe, bd2, bd5, bbbits, bs2, c, dsign, + e, e1, esign, i, j, k, nd, nd0, nf, nz, nz0, sign; + CONST char *s, *s0, *s1; + double aadj, aadj1, adj, rv, rv0; + long L; + unsigned long y, z; + Bigint *bb, *bb1, *bd, *bd0, *bs, *delta; + sign = nz0 = nz = 0; + rv = 0.; + for (s = s00;;s++) switch(*s) { + case '-': + sign = 1; + /* no break */ + case '+': + if (*++s) + goto break2; + /* no break */ + case 0: + s = s00; + goto ret; + case '\t': + case '\n': + case '\v': + case '\f': + case '\r': + case ' ': + continue; + default: + goto break2; + } + break2: + if (*s == '0') { + nz0 = 1; + while (*++s == '0') ; + if (!*s) + goto ret; + } + s0 = s; + y = z = 0; + for (nd = nf = 0; (c = *s) >= '0' && c <= '9'; nd++, s++) + if (nd < 9) + y = 10*y + c - '0'; + else if (nd < 16) + z = 10*z + c - '0'; + nd0 = nd; + if (c == '.') { + c = *++s; + if (!nd) { + for (; c == '0'; c = *++s) + nz++; + if (c > '0' && c <= '9') { + s0 = s; + nf += nz; + nz = 0; + goto have_dig; + } + goto dig_done; + } + for (; c >= '0' && c <= '9'; c = *++s) { + have_dig: + nz++; + if (c -= '0') { + nf += nz; + for (i = 1; i < nz; i++) + if (nd++ < 9) + y *= 10; + else if (nd <= DBL_DIG + 1) + z *= 10; + if (nd++ < 9) + y = 10*y + c; + else if (nd <= DBL_DIG + 1) + z = 10*z + c; + nz = 0; + } + } + } + dig_done: + e = 0; + if (c == 'e' || c == 'E') { + if (!nd && !nz && !nz0) { + s = s00; + goto ret; + } + s00 = s; + esign = 0; + switch(c = *++s) { + case '-': + esign = 1; + case '+': + c = *++s; + } + if (c >= '0' && c <= '9') { + while (c == '0') + c = *++s; + if (c > '0' && c <= '9') { + L = c - '0'; + s1 = s; + while ((c = *++s) >= '0' && c <= '9') + L = 10*L + c - '0'; + if (s - s1 > 8 || L > 19999) + /* Avoid confusion from exponents + * so large that e might overflow. + */ + e = 19999; /* safe for 16 bit ints */ + else + e = (int)L; + if (esign) + e = -e; + } else + e = 0; + } else + s = s00; + } + if (!nd) { + if (!nz && !nz0) + s = s00; + goto ret; + } + e1 = e -= nf; + + /* Now we have nd0 digits, starting at s0, followed by a + * decimal point, followed by nd-nd0 digits. The number we're + * after is the integer represented by those digits times + * 10**e */ + + if (!nd0) + nd0 = nd; + k = nd < DBL_DIG + 1 ? nd : DBL_DIG + 1; + rv = y; + if (k > 9) + rv = tens[k - 9] * rv + z; + if (nd <= DBL_DIG +#ifndef RND_PRODQUOT + && FLT_ROUNDS == 1 +#endif + ) { + if (!e) + goto ret; + if (e > 0) { + if (e <= Ten_pmax) { +#ifdef VAX + goto vax_ovfl_check; +#else + /* rv = */ rounded_product(rv, tens[e]); + goto ret; +#endif + } + i = DBL_DIG - nd; + if (e <= Ten_pmax + i) { + /* A fancier test would sometimes let us do + * this for larger i values. + */ + e -= i; + rv *= tens[i]; +#ifdef VAX + /* VAX exponent range is so narrow we must + * worry about overflow here... + */ + vax_ovfl_check: + word0(rv) -= P*Exp_msk1; + /* rv = */ rounded_product(rv, tens[e]); + if ((word0(rv) & Exp_mask) + > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) + goto ovfl; + word0(rv) += P*Exp_msk1; +#else + /* rv = */ rounded_product(rv, tens[e]); +#endif + goto ret; + } + } +#ifndef Inaccurate_Divide + else if (e >= -Ten_pmax) { + /* rv = */ rounded_quotient(rv, tens[-e]); + goto ret; + } +#endif + } + e1 += nd - k; + + /* Get starting approximation = rv * 10**e1 */ + + if (e1 > 0) { + if (i = e1 & 15) + rv *= tens[i]; + if (e1 &= ~15) { + if (e1 > DBL_MAX_10_EXP) { + ovfl: + errno = ERANGE; +#ifdef __STDC__ + rv = HUGE_VAL; +#else + /* Can't trust HUGE_VAL */ +#ifdef IEEE_Arith + word0(rv) = Exp_mask; + word1(rv) = 0; +#else + word0(rv) = Big0; + word1(rv) = Big1; +#endif +#endif + goto ret; + } + if (e1 >>= 4) { + for (j = 0; e1 > 1; j++, e1 >>= 1) + if (e1 & 1) + rv *= bigtens[j]; + /* The last multiplication could overflow. */ + word0(rv) -= P*Exp_msk1; + rv *= bigtens[j]; + if ((z = word0(rv) & Exp_mask) + > Exp_msk1*(DBL_MAX_EXP+Bias-P)) + goto ovfl; + if (z > Exp_msk1*(DBL_MAX_EXP+Bias-1-P)) { + /* set to largest number */ + /* (Can't trust DBL_MAX) */ + word0(rv) = Big0; + word1(rv) = Big1; + } + else + word0(rv) += P*Exp_msk1; + } + } + } else if (e1 < 0) { + e1 = -e1; + if (i = e1 & 15) + rv /= tens[i]; + if (e1 &= ~15) { + e1 >>= 4; + for (j = 0; e1 > 1; j++, e1 >>= 1) + if (e1 & 1) + rv *= tinytens[j]; + /* The last multiplication could underflow. */ + rv0 = rv; + rv *= tinytens[j]; + if (!rv) { + rv = 2.*rv0; + rv *= tinytens[j]; + if (!rv) { + undfl: + rv = 0.; + errno = ERANGE; + goto ret; + } + word0(rv) = Tiny0; + word1(rv) = Tiny1; + /* The refinement below will clean + * this approximation up. + */ + } + } + } + + /* Now the hard part -- adjusting rv to the correct value.*/ + + /* Put digits into bd: true value = bd * 10^e */ + + bd0 = s2b(s0, nd0, nd, y); + + for (;;) { + bd = Balloc(bd0->k); + Bcopy(bd, bd0); + bb = d2b(rv, &bbe, &bbbits); /* rv = bb * 2^bbe */ + bs = i2b(1); + + if (e >= 0) { + bb2 = bb5 = 0; + bd2 = bd5 = e; + } else { + bb2 = bb5 = -e; + bd2 = bd5 = 0; + } + if (bbe >= 0) + bb2 += bbe; + else + bd2 -= bbe; + bs2 = bb2; +#ifdef Sudden_Underflow +#ifdef IBM + j = 1 + 4*P - 3 - bbbits + ((bbe + bbbits - 1) & 3); +#else + j = P + 1 - bbbits; +#endif +#else + i = bbe + bbbits - 1; /* logb(rv) */ + if (i < Emin) /* denormal */ + j = bbe + (P-Emin); + else + j = P + 1 - bbbits; +#endif + bb2 += j; + bd2 += j; + i = bb2 < bd2 ? bb2 : bd2; + if (i > bs2) + i = bs2; + if (i > 0) { + bb2 -= i; + bd2 -= i; + bs2 -= i; + } + if (bb5 > 0) { + bs = pow5mult(bs, bb5); + bb1 = mult(bs, bb); + Bfree(bb); + bb = bb1; + } + if (bb2 > 0) + bb = lshift(bb, bb2); + if (bd5 > 0) + bd = pow5mult(bd, bd5); + if (bd2 > 0) + bd = lshift(bd, bd2); + if (bs2 > 0) + bs = lshift(bs, bs2); + delta = diff(bb, bd); + dsign = delta->sign; + delta->sign = 0; + i = cmp(delta, bs); + if (i < 0) { + /* Error is less than half an ulp -- check for + * special case of mantissa a power of two. + */ + if (dsign || word1(rv) || word0(rv) & Bndry_mask) + break; + delta = lshift(delta,Log2P); + if (cmp(delta, bs) > 0) + goto drop_down; + break; + } + if (i == 0) { + /* exactly half-way between */ + if (dsign) { + if ((word0(rv) & Bndry_mask1) == Bndry_mask1 + && word1(rv) == 0xffffffff) { + /*boundary case -- increment exponent*/ + word0(rv) = (word0(rv) & Exp_mask) + + Exp_msk1 +#ifdef IBM + | Exp_msk1 >> 4 +#endif + ; + word1(rv) = 0; + break; + } + } else if (!(word0(rv) & Bndry_mask) && !word1(rv)) { + drop_down: + /* boundary case -- decrement exponent */ +#ifdef Sudden_Underflow + L = word0(rv) & Exp_mask; +#ifdef IBM + if (L < Exp_msk1) +#else + if (L <= Exp_msk1) +#endif + goto undfl; + L -= Exp_msk1; +#else + L = (word0(rv) & Exp_mask) - Exp_msk1; +#endif + word0(rv) = L | Bndry_mask1; + word1(rv) = 0xffffffff; +#ifdef IBM + goto cont; +#else + break; +#endif + } +#ifndef ROUND_BIASED + if (!(word1(rv) & LSB)) + break; +#endif + if (dsign) + rv += ulp(rv); +#ifndef ROUND_BIASED + else { + rv -= ulp(rv); +#ifndef Sudden_Underflow + if (!rv) + goto undfl; +#endif + } +#endif + break; + } + if ((aadj = ratio(delta, bs)) <= 2.) { + if (dsign) + aadj = aadj1 = 1.; + else if (word1(rv) || word0(rv) & Bndry_mask) { +#ifndef Sudden_Underflow + if (word1(rv) == Tiny1 && !word0(rv)) + goto undfl; +#endif + aadj = 1.; + aadj1 = -1.; + } else { + /* special case -- power of FLT_RADIX to be */ + /* rounded down... */ + + if (aadj < 2./FLT_RADIX) + aadj = 1./FLT_RADIX; + else + aadj *= 0.5; + aadj1 = -aadj; + } + } else { + aadj *= 0.5; + aadj1 = dsign ? aadj : -aadj; +#ifdef Check_FLT_ROUNDS + switch(FLT_ROUNDS) { + case 2: /* towards +infinity */ + aadj1 -= 0.5; + break; + case 0: /* towards 0 */ + case 3: /* towards -infinity */ + aadj1 += 0.5; + } +#else + if (FLT_ROUNDS == 0) + aadj1 += 0.5; +#endif + } + y = word0(rv) & Exp_mask; + + /* Check for overflow */ + + if (y == Exp_msk1*(DBL_MAX_EXP+Bias-1)) { + rv0 = rv; + word0(rv) -= P*Exp_msk1; + adj = aadj1 * ulp(rv); + rv += adj; + if ((word0(rv) & Exp_mask) >= + Exp_msk1*(DBL_MAX_EXP+Bias-P)) { + if (word0(rv0) == Big0 && word1(rv0) == Big1) + goto ovfl; + word0(rv) = Big0; + word1(rv) = Big1; + goto cont; + } else + word0(rv) += P*Exp_msk1; + } else { +#ifdef Sudden_Underflow + if ((word0(rv) & Exp_mask) <= P*Exp_msk1) { + rv0 = rv; + word0(rv) += P*Exp_msk1; + adj = aadj1 * ulp(rv); + rv += adj; +#ifdef IBM + if ((word0(rv) & Exp_mask) < P*Exp_msk1) +#else + if ((word0(rv) & Exp_mask) <= P*Exp_msk1) +#endif + { + if (word0(rv0) == Tiny0 + && word1(rv0) == Tiny1) + goto undfl; + word0(rv) = Tiny0; + word1(rv) = Tiny1; + goto cont; + } else + word0(rv) -= P*Exp_msk1; + } else { + adj = aadj1 * ulp(rv); + rv += adj; + } +#else + /* Compute adj so that the IEEE rounding rules will + * correctly round rv + adj in some half-way cases. + * If rv * ulp(rv) is denormalized (i.e., + * y <= (P-1)*Exp_msk1), we must adjust aadj to avoid + * trouble from bits lost to denormalization; + * example: 1.2e-307 . + */ + if (y <= (P-1)*Exp_msk1 && aadj >= 1.) { + aadj1 = (double)(int)(aadj + 0.5); + if (!dsign) + aadj1 = -aadj1; + } + adj = aadj1 * ulp(rv); + rv += adj; +#endif + } + z = word0(rv) & Exp_mask; + if (y == z) { + /* Can we stop now? */ + L = aadj; + aadj -= L; + /* The tolerances below are conservative. */ + if (dsign || word1(rv) || word0(rv) & Bndry_mask) { + if (aadj < .4999999 || aadj > .5000001) + break; + } else if (aadj < .4999999/FLT_RADIX) + break; + } + cont: + Bfree(bb); + Bfree(bd); + Bfree(bs); + Bfree(delta); + } + Bfree(bb); + Bfree(bd); + Bfree(bs); + Bfree(bd0); + Bfree(delta); + ret: + if (se) + *se = (char *)s; + return sign ? -rv : rv; +} + + static int +quorem +#ifdef KR_headers + (b, S) Bigint *b, *S; +#else + (Bigint *b, Bigint *S) +#endif +{ + int n; + long borrow, y; + unsigned long carry, q, ys; + unsigned long *bx, *bxe, *sx, *sxe; +#ifdef Pack_32 + long z; + unsigned long si, zs; +#endif + + n = S->wds; +#ifdef DEBUG + /*debug*/ if (b->wds > n) + /*debug*/ Bug("oversize b in quorem"); +#endif + if (b->wds < n) + return 0; + sx = S->x; + sxe = sx + --n; + bx = b->x; + bxe = bx + n; + q = *bxe / (*sxe + 1); /* ensure q <= true quotient */ +#ifdef DEBUG + /*debug*/ if (q > 9) + /*debug*/ Bug("oversized quotient in quorem"); +#endif + if (q) { + borrow = 0; + carry = 0; + do { +#ifdef Pack_32 + si = *sx++; + ys = (si & 0xffff) * q + carry; + zs = (si >> 16) * q + (ys >> 16); + carry = zs >> 16; + y = (*bx & 0xffff) - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*bx >> 16) - (zs & 0xffff) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(bx, z, y); +#else + ys = *sx++ * q + carry; + carry = ys >> 16; + y = *bx - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *bx++ = y & 0xffff; +#endif + } while (sx <= sxe); + if (!*bxe) { + bx = b->x; + while (--bxe > bx && !*bxe) + --n; + b->wds = n; + } + } + if (cmp(b, S) >= 0) { + q++; + borrow = 0; + carry = 0; + bx = b->x; + sx = S->x; + do { +#ifdef Pack_32 + si = *sx++; + ys = (si & 0xffff) + carry; + zs = (si >> 16) + (ys >> 16); + carry = zs >> 16; + y = (*bx & 0xffff) - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + z = (*bx >> 16) - (zs & 0xffff) + borrow; + borrow = z >> 16; + Sign_Extend(borrow, z); + Storeinc(bx, z, y); +#else + ys = *sx++ + carry; + carry = ys >> 16; + y = *bx - (ys & 0xffff) + borrow; + borrow = y >> 16; + Sign_Extend(borrow, y); + *bx++ = y & 0xffff; +#endif + } while (sx <= sxe); + bx = b->x; + bxe = bx + n; + if (!*bxe) { + while (--bxe > bx && !*bxe) + --n; + b->wds = n; + } + } + return q; +} + +/* dtoa for IEEE arithmetic (dmg): convert double to ASCII string. + * + * Inspired by "How to Print Floating-Point Numbers Accurately" by + * Guy L. Steele, Jr. and Jon L. White [Proc. ACM SIGPLAN '90, pp. 92-101]. + * + * Modifications: + * 1. Rather than iterating, we use a simple numeric overestimate + * to determine k = floor(log10(d)). We scale relevant + * quantities using O(log2(k)) rather than O(k) multiplications. + * 2. For some modes > 2 (corresponding to ecvt and fcvt), we don't + * try to generate digits strictly left to right. Instead, we + * compute with fewer bits and propagate the carry if necessary + * when rounding the final digit up. This is often faster. + * 3. Under the assumption that input will be rounded nearest, + * mode 0 renders 1e23 as 1e23 rather than 9.999999999999999e22. + * That is, we allow equality in stopping tests when the + * round-nearest rule will give the same floating-point value + * as would satisfaction of the stopping test with strict + * inequality. + * 4. We remove common factors of powers of 2 from relevant + * quantities. + * 5. When converting floating-point integers less than 1e16, + * we use floating-point arithmetic rather than resorting + * to multiple-precision integers. + * 6. When asked to produce fewer than 15 digits, we first try + * to get by with floating-point arithmetic; we resort to + * multiple-precision integer arithmetic only if we cannot + * guarantee that the floating-point calculation has given + * the correctly rounded result. For k requested digits and + * "uniformly" distributed input, the probability is + * something like 10^(k-15) that we must resort to the long + * calculation. + */ + +char * +__dtoa +#ifdef KR_headers + (d, mode, ndigits, decpt, sign, rve) + double d; int mode, ndigits, *decpt, *sign; char **rve; +#else + (double d, int mode, int ndigits, int *decpt, int *sign, char **rve) +#endif +{ + /* Arguments ndigits, decpt, sign are similar to those + of ecvt and fcvt; trailing zeros are suppressed from + the returned string. If not null, *rve is set to point + to the end of the return value. If d is +-Infinity or NaN, + then *decpt is set to 9999. + + mode: + 0 ==> shortest string that yields d when read in + and rounded to nearest. + 1 ==> like 0, but with Steele & White stopping rule; + e.g. with IEEE P754 arithmetic , mode 0 gives + 1e23 whereas mode 1 gives 9.999999999999999e22. + 2 ==> max(1,ndigits) significant digits. This gives a + return value similar to that of ecvt, except + that trailing zeros are suppressed. + 3 ==> through ndigits past the decimal point. This + gives a return value similar to that from fcvt, + except that trailing zeros are suppressed, and + ndigits can be negative. + 4-9 should give the same return values as 2-3, i.e., + 4 <= mode <= 9 ==> same return as mode + 2 + (mode & 1). These modes are mainly for + debugging; often they run slower but sometimes + faster than modes 2-3. + 4,5,8,9 ==> left-to-right digit generation. + 6-9 ==> don't try fast floating-point estimate + (if applicable). + + Values of mode other than 0-9 are treated as mode 0. + + Sufficient space is allocated to the return value + to hold the suppressed trailing zeros. + */ + + int bbits, b2, b5, be, dig, i, ieps, ilim, ilim0, ilim1, + j, j1, k, k0, k_check, leftright, m2, m5, s2, s5, + spec_case, try_quick; + long L; +#ifndef Sudden_Underflow + int denorm; + unsigned long x; +#endif + Bigint *b, *b1, *delta, *mlo, *mhi, *S; + double d2, ds, eps; + char *s, *s0; + static Bigint *result; + static int result_k; + + if (result) { + result->k = result_k; + result->maxwds = 1 << result_k; + Bfree(result); + result = 0; + } + + if (word0(d) & Sign_bit) { + /* set sign for everything, including 0's and NaNs */ + *sign = 1; + word0(d) &= ~Sign_bit; /* clear sign bit */ + } + else + *sign = 0; + +#if defined(IEEE_Arith) + defined(VAX) +#ifdef IEEE_Arith + if ((word0(d) & Exp_mask) == Exp_mask) +#else + if (word0(d) == 0x8000) +#endif + { + /* Infinity or NaN */ + *decpt = 9999; + s = +#ifdef IEEE_Arith + !word1(d) && !(word0(d) & 0xfffff) ? "Infinity" : +#endif + "NaN"; + if (rve) + *rve = +#ifdef IEEE_Arith + s[3] ? s + 8 : +#endif + s + 3; + return s; + } +#endif +#ifdef IBM + d += 0; /* normalize */ +#endif + if (!d) { + *decpt = 1; + s = "0"; + if (rve) + *rve = s + 1; + return s; + } + + b = d2b(d, &be, &bbits); +#ifdef Sudden_Underflow + i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1)); +#else + if (i = (int)(word0(d) >> Exp_shift1 & (Exp_mask>>Exp_shift1))) { +#endif + d2 = d; + word0(d2) &= Frac_mask1; + word0(d2) |= Exp_11; +#ifdef IBM + if (j = 11 - hi0bits(word0(d2) & Frac_mask)) + d2 /= 1 << j; +#endif + + /* log(x) ~=~ log(1.5) + (x-1.5)/1.5 + * log10(x) = log(x) / log(10) + * ~=~ log(1.5)/log(10) + (x-1.5)/(1.5*log(10)) + * log10(d) = (i-Bias)*log(2)/log(10) + log10(d2) + * + * This suggests computing an approximation k to log10(d) by + * + * k = (i - Bias)*0.301029995663981 + * + ( (d2-1.5)*0.289529654602168 + 0.176091259055681 ); + * + * We want k to be too large rather than too small. + * The error in the first-order Taylor series approximation + * is in our favor, so we just round up the constant enough + * to compensate for any error in the multiplication of + * (i - Bias) by 0.301029995663981; since |i - Bias| <= 1077, + * and 1077 * 0.30103 * 2^-52 ~=~ 7.2e-14, + * adding 1e-13 to the constant term more than suffices. + * Hence we adjust the constant term to 0.1760912590558. + * (We could get a more accurate k by invoking log10, + * but this is probably not worthwhile.) + */ + + i -= Bias; +#ifdef IBM + i <<= 2; + i += j; +#endif +#ifndef Sudden_Underflow + denorm = 0; + } else { + /* d is denormalized */ + + i = bbits + be + (Bias + (P-1) - 1); + x = i > 32 ? word0(d) << 64 - i | word1(d) >> i - 32 + : word1(d) << 32 - i; + d2 = x; + word0(d2) -= 31*Exp_msk1; /* adjust exponent */ + i -= (Bias + (P-1) - 1) + 1; + denorm = 1; + } +#endif + ds = (d2-1.5)*0.289529654602168 + 0.1760912590558 + i*0.301029995663981; + k = (int)ds; + if (ds < 0. && ds != k) + k--; /* want k = floor(ds) */ + k_check = 1; + if (k >= 0 && k <= Ten_pmax) { + if (d < tens[k]) + k--; + k_check = 0; + } + j = bbits - i - 1; + if (j >= 0) { + b2 = 0; + s2 = j; + } else { + b2 = -j; + s2 = 0; + } + if (k >= 0) { + b5 = 0; + s5 = k; + s2 += k; + } else { + b2 -= k; + b5 = -k; + s5 = 0; + } + if (mode < 0 || mode > 9) + mode = 0; + try_quick = 1; + if (mode > 5) { + mode -= 4; + try_quick = 0; + } + leftright = 1; + switch(mode) { + case 0: + case 1: + ilim = ilim1 = -1; + i = 18; + ndigits = 0; + break; + case 2: + leftright = 0; + /* no break */ + case 4: + if (ndigits <= 0) + ndigits = 1; + ilim = ilim1 = i = ndigits; + break; + case 3: + leftright = 0; + /* no break */ + case 5: + i = ndigits + k + 1; + ilim = i; + ilim1 = i - 1; + if (i <= 0) + i = 1; + } + j = sizeof(unsigned long); + for (result_k = 0; sizeof(Bigint) - sizeof(unsigned long) + j < i; + j <<= 1) result_k++; + result = Balloc(result_k); + s = s0 = (char *)result; + + if (ilim >= 0 && ilim <= Quick_max && try_quick) { + + /* Try to get by with floating-point arithmetic. */ + + i = 0; + d2 = d; + k0 = k; + ilim0 = ilim; + ieps = 2; /* conservative */ + if (k > 0) { + ds = tens[k&0xf]; + j = k >> 4; + if (j & Bletch) { + /* prevent overflows */ + j &= Bletch - 1; + d /= bigtens[n_bigtens-1]; + ieps++; + } + for (; j; j >>= 1, i++) + if (j & 1) { + ieps++; + ds *= bigtens[i]; + } + d /= ds; + } else if (j1 = -k) { + d *= tens[j1 & 0xf]; + for (j = j1 >> 4; j; j >>= 1, i++) + if (j & 1) { + ieps++; + d *= bigtens[i]; + } + } + if (k_check && d < 1. && ilim > 0) { + if (ilim1 <= 0) + goto fast_failed; + ilim = ilim1; + k--; + d *= 10.; + ieps++; + } + eps = ieps*d + 7.; + word0(eps) -= (P-1)*Exp_msk1; + if (ilim == 0) { + S = mhi = 0; + d -= 5.; + if (d > eps) + goto one_digit; + if (d < -eps) + goto no_digits; + goto fast_failed; + } +#ifndef No_leftright + if (leftright) { + /* Use Steele & White method of only + * generating digits needed. + */ + eps = 0.5/tens[ilim-1] - eps; + for (i = 0;;) { + L = d; + d -= L; + *s++ = '0' + (int)L; + if (d < eps) + goto ret1; + if (1. - d < eps) + goto bump_up; + if (++i >= ilim) + break; + eps *= 10.; + d *= 10.; + } + } else { +#endif + /* Generate ilim digits, then fix them up. */ + eps *= tens[ilim-1]; + for (i = 1;; i++, d *= 10.) { + L = d; + d -= L; + *s++ = '0' + (int)L; + if (i == ilim) { + if (d > 0.5 + eps) + goto bump_up; + else if (d < 0.5 - eps) { + while (*--s == '0'); + s++; + goto ret1; + } + break; + } + } +#ifndef No_leftright + } +#endif + fast_failed: + s = s0; + d = d2; + k = k0; + ilim = ilim0; + } + + /* Do we have a "small" integer? */ + + if (be >= 0 && k <= Int_max) { + /* Yes. */ + ds = tens[k]; + if (ndigits < 0 && ilim <= 0) { + S = mhi = 0; + if (ilim < 0 || d <= 5*ds) + goto no_digits; + goto one_digit; + } + for (i = 1;; i++) { + L = d / ds; + d -= L*ds; +#ifdef Check_FLT_ROUNDS + /* If FLT_ROUNDS == 2, L will usually be high by 1 */ + if (d < 0) { + L--; + d += ds; + } +#endif + *s++ = '0' + (int)L; + if (i == ilim) { + d += d; + if (d > ds || d == ds && L & 1) { + bump_up: + while (*--s == '9') + if (s == s0) { + k++; + *s = '0'; + break; + } + ++*s++; + } + break; + } + if (!(d *= 10.)) + break; + } + goto ret1; + } + + m2 = b2; + m5 = b5; + mhi = mlo = 0; + if (leftright) { + if (mode < 2) { + i = +#ifndef Sudden_Underflow + denorm ? be + (Bias + (P-1) - 1 + 1) : +#endif +#ifdef IBM + 1 + 4*P - 3 - bbits + ((bbits + be - 1) & 3); +#else + 1 + P - bbits; +#endif + } else { + j = ilim - 1; + if (m5 >= j) + m5 -= j; + else { + s5 += j -= m5; + b5 += j; + m5 = 0; + } + if ((i = ilim) < 0) { + m2 -= i; + i = 0; + } + } + b2 += i; + s2 += i; + mhi = i2b(1); + } + if (m2 > 0 && s2 > 0) { + i = m2 < s2 ? m2 : s2; + b2 -= i; + m2 -= i; + s2 -= i; + } + if (b5 > 0) { + if (leftright) { + if (m5 > 0) { + mhi = pow5mult(mhi, m5); + b1 = mult(mhi, b); + Bfree(b); + b = b1; + } + if (j = b5 - m5) + b = pow5mult(b, j); + } else + b = pow5mult(b, b5); + } + S = i2b(1); + if (s5 > 0) + S = pow5mult(S, s5); + + /* Check for special case that d is a normalized power of 2. */ + + if (mode < 2) { + if (!word1(d) && !(word0(d) & Bndry_mask) +#ifndef Sudden_Underflow + && word0(d) & Exp_mask +#endif + ) { + /* The special case */ + b2 += Log2P; + s2 += Log2P; + spec_case = 1; + } else + spec_case = 0; + } + + /* Arrange for convenient computation of quotients: + * shift left if necessary so divisor has 4 leading 0 bits. + * + * Perhaps we should just compute leading 28 bits of S once + * and for all and pass them and a shift to quorem, so it + * can do shifts and ors to compute the numerator for q. + */ +#ifdef Pack_32 + if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0x1f) + i = 32 - i; +#else + if (i = ((s5 ? 32 - hi0bits(S->x[S->wds-1]) : 1) + s2) & 0xf) + i = 16 - i; +#endif + if (i > 4) { + i -= 4; + b2 += i; + m2 += i; + s2 += i; + } else if (i < 4) { + i += 28; + b2 += i; + m2 += i; + s2 += i; + } + if (b2 > 0) + b = lshift(b, b2); + if (s2 > 0) + S = lshift(S, s2); + if (k_check) { + if (cmp(b,S) < 0) { + k--; + b = multadd(b, 10, 0); /* we botched the k estimate */ + if (leftright) + mhi = multadd(mhi, 10, 0); + ilim = ilim1; + } + } + if (ilim <= 0 && mode > 2) { + if (ilim < 0 || cmp(b,S = multadd(S,5,0)) <= 0) { + /* no digits, fcvt style */ + no_digits: + k = -1 - ndigits; + goto ret; + } + one_digit: + *s++ = '1'; + k++; + goto ret; + } + if (leftright) { + if (m2 > 0) + mhi = lshift(mhi, m2); + + /* Compute mlo -- check for special case + * that d is a normalized power of 2. + */ + + mlo = mhi; + if (spec_case) { + mhi = Balloc(mhi->k); + Bcopy(mhi, mlo); + mhi = lshift(mhi, Log2P); + } + + for (i = 1;;i++) { + dig = quorem(b,S) + '0'; + /* Do we yet have the shortest decimal string + * that will round to d? + */ + j = cmp(b, mlo); + delta = diff(S, mhi); + j1 = delta->sign ? 1 : cmp(b, delta); + Bfree(delta); +#ifndef ROUND_BIASED + if (j1 == 0 && !mode && !(word1(d) & 1)) { + if (dig == '9') + goto round_9_up; + if (j > 0) + dig++; + *s++ = dig; + goto ret; + } +#endif + if (j < 0 || j == 0 && !mode +#ifndef ROUND_BIASED + && !(word1(d) & 1) +#endif + ) { + if (j1 > 0) { + b = lshift(b, 1); + j1 = cmp(b, S); + if ((j1 > 0 || j1 == 0 && dig & 1) + && dig++ == '9') + goto round_9_up; + } + *s++ = dig; + goto ret; + } + if (j1 > 0) { + if (dig == '9') { /* possible if i == 1 */ + round_9_up: + *s++ = '9'; + goto roundoff; + } + *s++ = dig + 1; + goto ret; + } + *s++ = dig; + if (i == ilim) + break; + b = multadd(b, 10, 0); + if (mlo == mhi) + mlo = mhi = multadd(mhi, 10, 0); + else { + mlo = multadd(mlo, 10, 0); + mhi = multadd(mhi, 10, 0); + } + } + } else + for (i = 1;; i++) { + *s++ = dig = quorem(b,S) + '0'; + if (i >= ilim) + break; + b = multadd(b, 10, 0); + } + + /* Round off last digit */ + + b = lshift(b, 1); + j = cmp(b, S); + if (j > 0 || j == 0 && dig & 1) { + roundoff: + while (*--s == '9') + if (s == s0) { + k++; + *s++ = '1'; + goto ret; + } + ++*s++; + } else { + while (*--s == '0'); + s++; + } + ret: + Bfree(S); + if (mhi) { + if (mlo && mlo != mhi) + Bfree(mlo); + Bfree(mhi); + } + ret1: + Bfree(b); + if (s == s0) { /* don't return empty string */ + *s++ = '0'; + k = 0; + } + *s = 0; + *decpt = k + 1; + if (rve) + *rve = s; + return s0; + } +#ifdef __cplusplus +} +#endif diff --git a/lib/libc/stdlib/strtol.3 b/lib/libc/stdlib/strtol.3 new file mode 100644 index 0000000..4ebf069 --- /dev/null +++ b/lib/libc/stdlib/strtol.3 @@ -0,0 +1,168 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)strtol.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt STRTOL 3 +.Os +.Sh NAME +.Nm strtol, strtoq +.Nd convert string value to a long or quad_t integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Fd #include <limits.h> +.Ft long +.Fn strtol "char *nptr" "char **endptr" "int base" + +.Fd #include <sys/types.h> +.Fd #include <stdlib.h> +.Fd #include <limits.h> +.Ft quad_t +.Fn strtoq "char *nptr" "char **endptr" "int base" +.Sh DESCRIPTION +The +.Fn strtol +function +converts the string in +.Fa nptr +to a +.Em long +value. +The +.Fn strtoq +function +converts the string in +.Fa nptr +to a +.Em quad_t +value. +The conversion is done according to the given +.Fa base , +which must be between 2 and 36 inclusive, +or be the special value 0. +.Pp +The string may begin with an arbitrary amount of white space +(as determined by +.Xr isspace 3 ) +followed by a single optional +.Ql + +or +.Ql - +sign. +If +.Fa base +is zero or 16, +the string may then include a +.Ql 0x +prefix, +and the number will be read in base 16; otherwise, a zero +.Fa base +is taken as 10 (decimal) unless the next character is +.Ql 0 , +in which case it is taken as 8 (octal). +.Pp +The remainder of the string is converted to a +.Em long +value in the obvious manner, +stopping at the first character which is not a valid digit +in the given base. +(In bases above 10, the letter +.Ql A +in either upper or lower case +represents 10, +.Ql B +represents 11, and so forth, with +.Ql Z +representing 35.) +.Pp +If +.Fa endptr +is non nil, +.Fn strtol +stores the address of the first invalid character in +.Fa *endptr . +If there were no digits at all, however, +.Fn strtol +stores the original value of +.Fa nptr +in +.Fa *endptr . +(Thus, if +.Fa *nptr +is not +.Ql \e0 +but +.Fa **endptr +is +.Ql \e0 +on return, the entire string was valid.) +.Sh RETURN VALUES +The +.Fn strtol +function +returns the result of the conversion, +unless the value would underflow or overflow. +If an underflow occurs, +.Fn strtol +returns +.Dv LONG_MIN . +If an overflow occurs, +.Fn strtol +returns +.Dv LONG_MAX . +In both cases, +.Va errno +is set to +.Er ERANGE . +.Sh ERRORS +.Bl -tag -width [ERANGE] +.It Bq Er ERANGE +The given string was out of range; the value converted has been clamped. +.El +.Sh SEE ALSO +.Xr atof 3 , +.Xr atoi 3 , +.Xr atol 3 , +.Xr strtod 3 , +.Xr strtoul 3 +.Sh STANDARDS +The +.Fn strtol +function +conforms to +.St -ansiC . +.Sh BUGS +Ignores the current locale. diff --git a/lib/libc/stdlib/strtol.c b/lib/libc/stdlib/strtol.c new file mode 100644 index 0000000..1a7f7b3 --- /dev/null +++ b/lib/libc/stdlib/strtol.c @@ -0,0 +1,129 @@ +/*- + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtol.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <limits.h> +#include <ctype.h> +#include <errno.h> +#include <stdlib.h> + + +/* + * Convert a string to a long integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +long +strtol(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s = nptr; + register unsigned long acc; + register int c; + register unsigned long cutoff; + register int neg = 0, any, cutlim; + + /* + * Skip white space and pick up leading +/- sign if any. + * If base is 0, allow 0x for hex and 0 for octal, else + * assume decimal; if base is already 16, allow 0x. + */ + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else if (c == '+') + c = *s++; + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + + /* + * Compute the cutoff value between legal numbers and illegal + * numbers. That is the largest legal value, divided by the + * base. An input number that is greater than this value, if + * followed by a legal input character, is too big. One that + * is equal to this value may be valid or not; the limit + * between valid and invalid numbers is then based on the last + * digit. For instance, if the range for longs is + * [-2147483648..2147483647] and the input base is 10, + * cutoff will be set to 214748364 and cutlim to either + * 7 (neg==0) or 8 (neg==1), meaning that if we have accumulated + * a value > 214748364, or equal but the next digit is > 7 (or 8), + * the number is too big, and we will return a range error. + * + * Set any if any `digits' consumed; make it negative to indicate + * overflow. + */ + cutoff = neg ? -(unsigned long)LONG_MIN : LONG_MAX; + cutlim = cutoff % (unsigned long)base; + cutoff /= (unsigned long)base; + for (acc = 0, any = 0;; c = *s++) { + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + any = -1; + else { + any = 1; + acc *= base; + acc += c; + } + } + if (any < 0) { + acc = neg ? LONG_MIN : LONG_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/lib/libc/stdlib/strtoq.c b/lib/libc/stdlib/strtoq.c new file mode 100644 index 0000000..b31cca4 --- /dev/null +++ b/lib/libc/stdlib/strtoq.c @@ -0,0 +1,136 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtoq.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include <limits.h> +#include <errno.h> +#include <ctype.h> +#include <stdlib.h> + +/* + * Convert a string to a quad integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +quad_t +strtoq(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s; + register u_quad_t acc; + register int c; + register u_quad_t qbase, cutoff; + register int neg, any, cutlim; + + /* + * Skip white space and pick up leading +/- sign if any. + * If base is 0, allow 0x for hex and 0 for octal, else + * assume decimal; if base is already 16, allow 0x. + */ + s = nptr; + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else { + neg = 0; + if (c == '+') + c = *s++; + } + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + + /* + * Compute the cutoff value between legal numbers and illegal + * numbers. That is the largest legal value, divided by the + * base. An input number that is greater than this value, if + * followed by a legal input character, is too big. One that + * is equal to this value may be valid or not; the limit + * between valid and invalid numbers is then based on the last + * digit. For instance, if the range for quads is + * [-9223372036854775808..9223372036854775807] and the input base + * is 10, cutoff will be set to 922337203685477580 and cutlim to + * either 7 (neg==0) or 8 (neg==1), meaning that if we have + * accumulated a value > 922337203685477580, or equal but the + * next digit is > 7 (or 8), the number is too big, and we will + * return a range error. + * + * Set any if any `digits' consumed; make it negative to indicate + * overflow. + */ + qbase = (unsigned)base; + cutoff = neg ? -(u_quad_t)QUAD_MIN : QUAD_MAX; + cutlim = cutoff % qbase; + cutoff /= qbase; + for (acc = 0, any = 0;; c = *s++) { + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + any = -1; + else { + any = 1; + acc *= qbase; + acc += c; + } + } + if (any < 0) { + acc = neg ? QUAD_MIN : QUAD_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/lib/libc/stdlib/strtoul.3 b/lib/libc/stdlib/strtoul.3 new file mode 100644 index 0000000..5d6b050 --- /dev/null +++ b/lib/libc/stdlib/strtoul.3 @@ -0,0 +1,163 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" Chris Torek and the American National Standards Committee X3, +.\" on Information Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)strtoul.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt STRTOUL 3 +.Os +.Sh NAME +.Nm strtoul, strtouq +.Nd convert a string to an unsigned long or uquad_t integer +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Fd #include <limits.h> +.Ft unsigned long +.Fn strtoul "const char *nptr" "char **endptr" "int base" + +.Fd #include <sys/types.h> +.Fd #include <stdlib.h> +.Fd #include <limits.h> +.Ft u_quad_t +.Fn strtouq "const char *nptr" "char **endptr" "int base" +.Sh DESCRIPTION +The +.Fn strtoul +function +converts the string in +.Fa nptr +to an +.Em unsigned long +value. +The +.Fn strtouq +function +converts the string in +.Fa nptr +to a +.Em u_quad_t +value. +The conversion is done according to the given +.Fa base , +which must be between 2 and 36 inclusive, +or be the special value 0. +.Pp +The string may begin with an arbitrary amount of white space +(as determined by +.Xr isspace 3 ) +followed by a single optional +.Ql + +or +.Ql - +sign. +If +.Fa base +is zero or 16, +the string may then include a +.Ql 0x +prefix, +and the number will be read in base 16; otherwise, a zero +.Fa base +is taken as 10 (decimal) unless the next character is +.Ql 0 , +in which case it is taken as 8 (octal). +.Pp +The remainder of the string is converted to an +.Em unsigned long +value in the obvious manner, +stopping at the end of the string +or at the first character that does not produce a valid digit +in the given base. +(In bases above 10, the letter +.Ql A +in either upper or lower case +represents 10, +.Ql B +represents 11, and so forth, with +.Ql Z +representing 35.) +.Pp +If +.Fa endptr +is non nil, +.Fn strtoul +stores the address of the first invalid character in +.Fa *endptr . +If there were no digits at all, however, +.Fn strtoul +stores the original value of +.Fa nptr +in +.Fa *endptr . +(Thus, if +.Fa *nptr +is not +.Ql \e0 +but +.Fa **endptr +is +.Ql \e0 +on return, the entire string was valid.) +.Sh RETURN VALUES +The +.Fn strtoul +function +returns either the result of the conversion +or, if there was a leading minus sign, +the negation of the result of the conversion, +unless the original (non-negated) value would overflow; +in the latter case, +.Fn strtoul +returns +.Dv ULONG_MAX +and sets the global variable +.Va errno +to +.Er ERANGE . +.Sh ERRORS +.Bl -tag -width [ERANGE] +.It Bq Er ERANGE +The given string was out of range; the value converted has been clamped. +.El +.Sh SEE ALSO +.Xr strtol 3 +.Sh STANDARDS +The +.Fn strtoul +function +conforms to +.St -ansiC . +.Sh BUGS +Ignores the current locale. diff --git a/lib/libc/stdlib/strtoul.c b/lib/libc/stdlib/strtoul.c new file mode 100644 index 0000000..e60556c0 --- /dev/null +++ b/lib/libc/stdlib/strtoul.c @@ -0,0 +1,107 @@ +/* + * Copyright (c) 1990, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtoul.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <limits.h> +#include <ctype.h> +#include <errno.h> +#include <stdlib.h> + +/* + * Convert a string to an unsigned long integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +unsigned long +strtoul(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s = nptr; + register unsigned long acc; + register int c; + register unsigned long cutoff; + register int neg = 0, any, cutlim; + + /* + * See strtol for comments as to the logic used. + */ + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else if (c == '+') + c = *s++; + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + cutoff = (unsigned long)ULONG_MAX / (unsigned long)base; + cutlim = (unsigned long)ULONG_MAX % (unsigned long)base; + for (acc = 0, any = 0;; c = *s++) { + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + any = -1; + else { + any = 1; + acc *= base; + acc += c; + } + } + if (any < 0) { + acc = ULONG_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/lib/libc/stdlib/strtouq.c b/lib/libc/stdlib/strtouq.c new file mode 100644 index 0000000..cc62a07 --- /dev/null +++ b/lib/libc/stdlib/strtouq.c @@ -0,0 +1,114 @@ +/*- + * 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)strtouq.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include <limits.h> +#include <errno.h> +#include <ctype.h> +#include <stdlib.h> + +/* + * Convert a string to an unsigned quad integer. + * + * Ignores `locale' stuff. Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +u_quad_t +strtouq(nptr, endptr, base) + const char *nptr; + char **endptr; + register int base; +{ + register const char *s = nptr; + register u_quad_t acc; + register int c; + register u_quad_t qbase, cutoff; + register int neg, any, cutlim; + + /* + * See strtoq for comments as to the logic used. + */ + s = nptr; + do { + c = *s++; + } while (isspace(c)); + if (c == '-') { + neg = 1; + c = *s++; + } else { + neg = 0; + if (c == '+') + c = *s++; + } + if ((base == 0 || base == 16) && + c == '0' && (*s == 'x' || *s == 'X')) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + qbase = (unsigned)base; + cutoff = (u_quad_t)UQUAD_MAX / qbase; + cutlim = (u_quad_t)UQUAD_MAX % qbase; + for (acc = 0, any = 0;; c = *s++) { + if (isdigit(c)) + c -= '0'; + else if (isalpha(c)) + c -= isupper(c) ? 'A' - 10 : 'a' - 10; + else + break; + if (c >= base) + break; + if (any < 0 || acc > cutoff || acc == cutoff && c > cutlim) + any = -1; + else { + any = 1; + acc *= qbase; + acc += c; + } + } + if (any < 0) { + acc = UQUAD_MAX; + errno = ERANGE; + } else if (neg) + acc = -acc; + if (endptr != 0) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/lib/libc/stdlib/system.3 b/lib/libc/stdlib/system.3 new file mode 100644 index 0000000..d89c79e --- /dev/null +++ b/lib/libc/stdlib/system.3 @@ -0,0 +1,93 @@ +.\" Copyright (c) 1990, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. +.\" +.\" @(#)system.3 8.1 (Berkeley) 6/4/93 +.\" +.Dd June 4, 1993 +.Dt SYSTEM 3 +.Os +.Sh NAME +.Nm system +.Nd pass a command to the shell +.Sh SYNOPSIS +.Fd #include <stdlib.h> +.Ft int +.Fn system "const char *string" +.Sh DESCRIPTION +The +.Fn system +function +hands the argument +.Fa string +to the command interpreter +.Xr sh 1 . +The calling process waits for the shell +to finish executing the command, +ignoring +.Dv SIGINT +and +.Dv SIGQUIT , +and blocking +.Dv SIGCHLD . +.Pp +If +.Fa string +is a +.Dv NULL +pointer, +.Fn system +will return non-zero if the command interpreter +.Xr sh 1 +is available, and zero if it is not. +.Pp +The +.Fn system +function +returns the exit status of the shell, or \-1 if the +.Xr wait 3 +for the shell failed. +A return value of 127 means the execution of the shell +failed. +.Sh SEE ALSO +.Xr sh 1 , +.Xr execve 2 , +.Xr wait 2 , +.Xr popen 3 +.Sh STANDARDS +The +.Fn system +function +conforms to +.St -ansiC . diff --git a/lib/libc/stdlib/system.c b/lib/libc/stdlib/system.c new file mode 100644 index 0000000..c438f17 --- /dev/null +++ b/lib/libc/stdlib/system.c @@ -0,0 +1,76 @@ +/* + * Copyright (c) 1988, 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. + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)system.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> +#include <sys/wait.h> +#include <signal.h> +#include <stdlib.h> +#include <stddef.h> +#include <unistd.h> +#include <paths.h> + +system(command) + const char *command; +{ + union wait pstat; + pid_t pid; + int omask; + sig_t intsave, quitsave; + + if (!command) /* just checking... */ + return(1); + + omask = sigblock(sigmask(SIGCHLD)); + switch(pid = vfork()) { + case -1: /* error */ + (void)sigsetmask(omask); + pstat.w_status = 0; + pstat.w_retcode = 127; + return(pstat.w_status); + case 0: /* child */ + (void)sigsetmask(omask); + execl(_PATH_BSHELL, "sh", "-c", command, (char *)NULL); + _exit(127); + } + intsave = signal(SIGINT, SIG_IGN); + quitsave = signal(SIGQUIT, SIG_IGN); + pid = waitpid(pid, (int *)&pstat, 0); + (void)sigsetmask(omask); + (void)signal(SIGINT, intsave); + (void)signal(SIGQUIT, quitsave); + return(pid == -1 ? -1 : pstat.w_status); +} |
