diff --git a/src/lib/libc/stdlib/Makefile b/src/lib/libc/stdlib/Makefile new file mode 100644 index 0000000..e102385 --- /dev/null +++ b/src/lib/libc/stdlib/Makefile @@ -0,0 +1,35 @@ +# $Id$ +# The System Makefile (C) 2002 The UbixOS Project + +# Include Global 'Source' Options +include ../../../Makefile.inc +include ../../Makefile.inc +include ../Makefile.inc + +#Objects +OBJS = _Exit.o a64l.o abort.o abs.o atexit.o atof.o atoi.o atol.o atoll.o bsearch.o calloc.o div.o exit.o getenv.o getopt.o getopt_long.o getsubopt.o grantpt.o hcreate.o heapsort.o imaxabs.o imaxdiv.o insque.o l64a.o labs.o ldiv.o llabs.o lldiv.o lsearch.o malloc.o merge.o putenv.o qsort.o qsort_r.o radixsort.o rand.o random.o reallocf.o realpath.o remque.o setenv.o strfmon.o strtoimax.o strtol.o strtoll.o strtonum.o strtoq.o strtoul.o strtoull.o strtoumax.o strtouq.o system.o tdelete.o tfind.o tsearch.o twalk.o +#Output +OUTPUT = libc.so + +$(OUTPUT): $(OBJS) + +# Compile the source files +.cc.o: + $(CXX) $(CFLAGS) -Wall -nostdlib -O $(INCLUDES) -c -o $@ $< + +.cc.s: + $(CXX) $(CFLAGS) -Wall -nostdlib -O $(INCLUDES) -S -o $@ $< + +.c.o: + $(CC) $(CFLAGS) -Wall -nostdlib -O $(INCLUDES) -c $< + +.c.s: + $(CC) $(CFLAGS) -Wall -nostdlib -O $(INCLUDES) -S -o $@ $< + +.S.o: + $(CC) $(CFLAGS) -Wall -nostdlib -c -o $@ $< + +# Clean up the junk +clean: + $(REMOVE) $(OBJS) $(OUTPUT) + diff --git a/src/lib/libc/stdlib/_Exit.c b/src/lib/libc/stdlib/_Exit.c new file mode 100644 index 0000000..3a2e94e --- /dev/null +++ b/src/lib/libc/stdlib/_Exit.c @@ -0,0 +1,22 @@ +/* + * This file is in the public domain. Written by Garrett A. Wollman, + * 2002-09-07. + * + * $FreeBSD: src/lib/libc/stdlib/_Exit.c,v 1.1 2002/09/10 02:04:49 wollman Exp $ + */ + +#include +#include + +/* + * ISO C99 added this function to provide for Standard C applications + * which needed something like POSIX _exit(). A new interface was created + * in case it turned out that _exit() was insufficient to meet the + * requirements of ISO C. (That's probably not the case, but here + * is where you would put the extra code if it were.) + */ +void +_Exit(int code) +{ + _exit(code); +} diff --git a/src/lib/libc/stdlib/a64l.c b/src/lib/libc/stdlib/a64l.c new file mode 100644 index 0000000..493deda --- /dev/null +++ b/src/lib/libc/stdlib/a64l.c @@ -0,0 +1,46 @@ +/*- + * Written by J.T. Conklin . + * Public domain. + */ + +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: a64l.c,v 1.8 2000/01/22 22:19:19 mycroft Exp $"); +#endif /* not lint */ +#endif + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/a64l.c,v 1.1.2.2 2006/05/24 18:14:34 jkim Exp $"); + +#include +#include + +#define ADOT 46 /* ASCII '.' */ +#define ASLASH 47 /* ASCII '/' */ +#define A0 48 /* ASCII '0' */ +#define AA 65 /* ASCII 'A' */ +#define Aa 97 /* ASCII 'a' */ + +long +a64l(const char *s) +{ + long shift; + int digit, i, value; + + value = 0; + shift = 0; + for (i = 0; *s != '\0' && i < 6; i++, s++) { + if (*s <= ASLASH) + digit = *s - ASLASH + 1; + else if (*s <= A0 + 9) + digit = *s - A0 + 2; + else if (*s <= AA + 25) + digit = *s - AA + 12; + else + digit = *s - Aa + 38; + + value |= digit << shift; + shift += 6; + } + return (value); +} diff --git a/src/lib/libc/stdlib/abort.c b/src/lib/libc/stdlib/abort.c new file mode 100644 index 0000000..18d0c73 --- /dev/null +++ b/src/lib/libc/stdlib/abort.c @@ -0,0 +1,83 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/abort.c,v 1.9 2003/08/16 11:43:57 davidxu Exp $"); + +#include "namespace.h" +#include +#include +#include +#include +#include +#include "un-namespace.h" + +void (*__cleanup)(); + +void +abort() +{ + struct sigaction act; + + /* + * POSIX requires we flush stdio buffers on abort. + * XXX ISO C requires that abort() be async-signal-safe. + */ + if (__cleanup) + (*__cleanup)(); + + sigfillset(&act.sa_mask); + /* + * Don't block SIGABRT to give any handler a chance; we ignore + * any errors -- ISO C doesn't allow abort to return anyway. + */ + sigdelset(&act.sa_mask, SIGABRT); + (void)_sigprocmask(SIG_SETMASK, &act.sa_mask, NULL); + (void)raise(SIGABRT); + + /* + * If SIGABRT was ignored, or caught and the handler returns, do + * it again, only harder. + */ + act.sa_handler = SIG_DFL; + act.sa_flags = 0; + sigfillset(&act.sa_mask); + (void)_sigaction(SIGABRT, &act, NULL); + sigdelset(&act.sa_mask, SIGABRT); + (void)_sigprocmask(SIG_SETMASK, &act.sa_mask, NULL); + (void)raise(SIGABRT); + exit(1); +} diff --git a/src/lib/libc/stdlib/abs.c b/src/lib/libc/stdlib/abs.c new file mode 100644 index 0000000..26f87eb --- /dev/null +++ b/src/lib/libc/stdlib/abs.c @@ -0,0 +1,47 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/abs.c,v 1.2 2002/03/22 21:53:09 obrien Exp $"); + +#include + +int +abs(j) + int j; +{ + return(j < 0 ? -j : j); +} diff --git a/src/lib/libc/stdlib/atexit.c b/src/lib/libc/stdlib/atexit.c new file mode 100644 index 0000000..bd94bcd --- /dev/null +++ b/src/lib/libc/stdlib/atexit.c @@ -0,0 +1,189 @@ +/*- + * 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.2 (Berkeley) 7/3/94"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/atexit.c,v 1.7 2003/12/19 17:11:20 kan Exp $"); + +#include "namespace.h" +#include +#include +#include +#include +#include "atexit.h" +#include "un-namespace.h" + +#include "libc_private.h" + +#define ATEXIT_FN_EMPTY 0 +#define ATEXIT_FN_STD 1 +#define ATEXIT_FN_CXA 2 + +static pthread_mutex_t atexit_mutex = PTHREAD_MUTEX_INITIALIZER; + +#define _MUTEX_LOCK(x) if (__isthreaded) _pthread_mutex_lock(x) +#define _MUTEX_UNLOCK(x) if (__isthreaded) _pthread_mutex_unlock(x) + +struct atexit { + struct atexit *next; /* next in list */ + int ind; /* next index in this table */ + struct atexit_fn { + int fn_type; /* ATEXIT_? from above */ + union { + void (*std_func)(void); + void (*cxa_func)(void *); + } fn_ptr; /* function pointer */ + void *fn_arg; /* argument for CXA callback */ + void *fn_dso; /* shared module handle */ + } fns[ATEXIT_SIZE]; /* the table itself */ +}; + +static struct atexit *__atexit; /* points to head of LIFO stack */ + +/* + * Register the function described by 'fptr' to be called at application + * exit or owning shared object unload time. This is a helper function + * for atexit and __cxa_atexit. + */ +static int +atexit_register(struct atexit_fn *fptr) +{ + static struct atexit __atexit0; /* one guaranteed table */ + struct atexit *p; + + _MUTEX_LOCK(&atexit_mutex); + if ((p = __atexit) == NULL) + __atexit = p = &__atexit0; + else while (p->ind >= ATEXIT_SIZE) { + struct atexit *old__atexit; + old__atexit = __atexit; + _MUTEX_UNLOCK(&atexit_mutex); + if ((p = (struct atexit *)malloc(sizeof(*p))) == NULL) + return (-1); + _MUTEX_LOCK(&atexit_mutex); + if (old__atexit != __atexit) { + /* Lost race, retry operation */ + _MUTEX_UNLOCK(&atexit_mutex); + free(p); + _MUTEX_LOCK(&atexit_mutex); + p = __atexit; + continue; + } + p->ind = 0; + p->next = __atexit; + __atexit = p; + } + p->fns[p->ind++] = *fptr; + _MUTEX_UNLOCK(&atexit_mutex); + return 0; +} + +/* + * Register a function to be performed at exit. + */ +int +atexit(void (*func)(void)) +{ + struct atexit_fn fn; + int error; + + fn.fn_type = ATEXIT_FN_STD; + fn.fn_ptr.std_func = func;; + fn.fn_arg = NULL; + fn.fn_dso = NULL; + + error = atexit_register(&fn); + return (error); +} + +/* + * Register a function to be performed at exit or when an shared object + * with given dso handle is unloaded dynamically. + */ +int +__cxa_atexit(void (*func)(void *), void *arg, void *dso) +{ + struct atexit_fn fn; + int error; + + fn.fn_type = ATEXIT_FN_CXA; + fn.fn_ptr.cxa_func = func;; + fn.fn_arg = arg; + fn.fn_dso = dso; + + error = atexit_register(&fn); + return (error); +} + +/* + * Call all handlers registered with __cxa_atexit for the shared + * object owning 'dso'. Note: if 'dso' is NULL, then all remaining + * handlers are called. + */ +void +__cxa_finalize(void *dso) +{ + struct atexit *p; + struct atexit_fn fn; + int n; + + _MUTEX_LOCK(&atexit_mutex); + for (p = __atexit; p; p = p->next) { + for (n = p->ind; --n >= 0;) { + if (p->fns[n].fn_type == ATEXIT_FN_EMPTY) + continue; /* already been called */ + if (dso != NULL && dso != p->fns[n].fn_dso) + continue; /* wrong DSO */ + fn = p->fns[n]; + /* + Mark entry to indicate that this particular handler + has already been called. + */ + p->fns[n].fn_type = ATEXIT_FN_EMPTY; + _MUTEX_UNLOCK(&atexit_mutex); + + /* Call the function of correct type. */ + if (fn.fn_type == ATEXIT_FN_CXA) + fn.fn_ptr.cxa_func(fn.fn_arg); + else if (fn.fn_type == ATEXIT_FN_STD) + fn.fn_ptr.std_func(); + _MUTEX_LOCK(&atexit_mutex); + } + } + _MUTEX_UNLOCK(&atexit_mutex); +} diff --git a/src/lib/libc/stdlib/atof.c b/src/lib/libc/stdlib/atof.c new file mode 100644 index 0000000..ca69ab6 --- /dev/null +++ b/src/lib/libc/stdlib/atof.c @@ -0,0 +1,47 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/atof.c,v 1.5 2004/02/10 20:42:32 cperciva Exp $"); + +#include + +double +atof(ascii) + const char *ascii; +{ + return strtod(ascii, (char **)NULL); +} diff --git a/src/lib/libc/stdlib/atoi.c b/src/lib/libc/stdlib/atoi.c new file mode 100644 index 0000000..3da2fda --- /dev/null +++ b/src/lib/libc/stdlib/atoi.c @@ -0,0 +1,47 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/atoi.c,v 1.5 2002/03/22 21:53:09 obrien Exp $"); + +#include + +int +atoi(str) + const char *str; +{ + return (int)strtol(str, (char **)NULL, 10); +} diff --git a/src/lib/libc/stdlib/atol.c b/src/lib/libc/stdlib/atol.c new file mode 100644 index 0000000..c66c04e --- /dev/null +++ b/src/lib/libc/stdlib/atol.c @@ -0,0 +1,47 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/atol.c,v 1.4 2002/03/22 21:53:09 obrien Exp $"); + +#include + +long +atol(str) + const char *str; +{ + return strtol(str, (char **)NULL, 10); +} diff --git a/src/lib/libc/stdlib/atoll.c b/src/lib/libc/stdlib/atoll.c new file mode 100644 index 0000000..b7c38b8 --- /dev/null +++ b/src/lib/libc/stdlib/atoll.c @@ -0,0 +1,44 @@ +/* + * 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. + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/atoll.c,v 1.4 2002/03/22 21:53:10 obrien Exp $"); + +#include + +long long +atoll(str) + const char *str; +{ + return strtoll(str, (char **)NULL, 10); +} diff --git a/src/lib/libc/stdlib/bsearch.c b/src/lib/libc/stdlib/bsearch.c new file mode 100644 index 0000000..7717582 --- /dev/null +++ b/src/lib/libc/stdlib/bsearch.c @@ -0,0 +1,83 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/bsearch.c,v 1.3 2002/03/21 22:48:41 obrien Exp $"); + +#include +#include + +/* + * 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) + const void *key; + const void *base0; + size_t nmemb; + size_t size; + int (*compar)(const void *, const void *); +{ + const char *base = base0; + size_t lim; + int cmp; + 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/src/lib/libc/stdlib/calloc.c b/src/lib/libc/stdlib/calloc.c new file mode 100644 index 0000000..0bdbb23 --- /dev/null +++ b/src/lib/libc/stdlib/calloc.c @@ -0,0 +1,61 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/calloc.c,v 1.7 2002/08/04 04:11:48 ache Exp $"); + +#include +#include +#include +#include + +void * +calloc(num, size) + size_t num; + size_t size; +{ + void *p; + + if (size != 0 && SIZE_T_MAX / size < num) { + errno = ENOMEM; + return (NULL); + } + + size *= num; + if ( (p = malloc(size)) ) + bzero(p, size); + return(p); +} diff --git a/src/lib/libc/stdlib/div.c b/src/lib/libc/stdlib/div.c new file mode 100644 index 0000000..54278d6 --- /dev/null +++ b/src/lib/libc/stdlib/div.c @@ -0,0 +1,81 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/div.c,v 1.2 2002/03/22 21:53:10 obrien Exp $"); + +#include /* 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/src/lib/libc/stdlib/exit.c b/src/lib/libc/stdlib/exit.c new file mode 100644 index 0000000..e71b3db --- /dev/null +++ b/src/lib/libc/stdlib/exit.c @@ -0,0 +1,73 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/exit.c,v 1.7 2003/12/19 17:11:20 kan Exp $"); + +#include "namespace.h" +#include +#include +#include "un-namespace.h" +#include "atexit.h" + +void (*__cleanup)(); + +/* + * This variable is zero until a process has created a thread. + * It is used to avoid calling locking functions in libc when they + * are not required. By default, libc is intended to be(come) + * thread-safe, but without a (significant) penalty to non-threaded + * processes. + */ +int __isthreaded = 0; + +/* + * Exit, flushing stdio buffers if necessary. + */ +void +exit(status) + int status; +{ + /* Ensure that the auto-initialization routine is linked in: */ + extern int _thread_autoinit_dummy_decl; + + _thread_autoinit_dummy_decl = 1; + + __cxa_finalize(NULL); + if (__cleanup) + (*__cleanup)(); + _exit(status); +} diff --git a/src/lib/libc/stdlib/getenv.c b/src/lib/libc/stdlib/getenv.c new file mode 100644 index 0000000..aa15989 --- /dev/null +++ b/src/lib/libc/stdlib/getenv.c @@ -0,0 +1,93 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/getenv.c,v 1.4 2002/03/21 22:48:41 obrien Exp $"); + +#include +#include +#include + +inline char *__findenv(const char *, int *); + +/* + * __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. + */ +inline char * +__findenv(name, offset) + const char *name; + int *offset; +{ + extern char **environ; + int len, i; + const char *np; + char **p, *cp; + + if (name == NULL || environ == NULL) + return (NULL); + for (np = name; *np && *np != '='; ++np) + continue; + len = np - name; + for (p = environ; (cp = *p) != NULL; ++p) { + for (np = name, i = len; i && *cp; i--) + if (*cp++ != *np++) + break; + if (i == 0 && *cp++ == '=') { + *offset = p - environ; + return (cp); + } + } + return (NULL); +} + +/* + * getenv -- + * Returns ptr to value associated with name, if any, else NULL. + */ +char * +getenv(name) + const char *name; +{ + int offset; + + return (__findenv(name, &offset)); +} diff --git a/src/lib/libc/stdlib/getopt.c b/src/lib/libc/stdlib/getopt.c new file mode 100644 index 0000000..efcfa0a --- /dev/null +++ b/src/lib/libc/stdlib/getopt.c @@ -0,0 +1,139 @@ +/* $NetBSD: getopt.c,v 1.26 2003/08/07 16:43:40 agc Exp $ */ + +/* + * 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.3 (Berkeley) 4/27/95"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/getopt.c,v 1.7 2004/03/06 17:05:45 ache Exp $"); + +#include "namespace.h" +#include +#include +#include +#include +#include "un-namespace.h" + +#include "libc_private.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; +{ + static char *place = EMSG; /* option letter processing */ + char *oli; /* option letter list index */ + + if (optreset || *place == 0) { /* update scanning pointer */ + optreset = 0; + place = nargv[optind]; + if (optind >= nargc || *place++ != '-') { + /* Argument is absent or is not an option */ + place = EMSG; + return (-1); + } + optopt = *place++; + if (optopt == '-' && *place == 0) { + /* "--" => end of options */ + ++optind; + place = EMSG; + return (-1); + } + if (optopt == 0) { + /* Solitary '-', treat as a '-' option + if the program (eg su) is looking for it. */ + place = EMSG; + if (strchr(ostr, '-') == NULL) + return (-1); + optopt = '-'; + } + } else + optopt = *place++; + + /* See if option letter is one the caller wanted... */ + if (optopt == ':' || (oli = strchr(ostr, optopt)) == NULL) { + if (*place == 0) + ++optind; + if (opterr && *ostr != ':') + (void)fprintf(stderr, + "%s: illegal option -- %c\n", _getprogname(), + optopt); + return (BADCH); + } + + /* Does this option need an argument? */ + if (oli[1] != ':') { + /* don't need argument */ + optarg = NULL; + if (*place == 0) + ++optind; + } else { + /* Option-argument is either the rest of this argument or the + entire next argument. */ + if (*place) + optarg = place; + else if (nargc > ++optind) + optarg = nargv[optind]; + else { + /* option-argument absent */ + place = EMSG; + if (*ostr == ':') + return (BADARG); + if (opterr) + (void)fprintf(stderr, + "%s: option requires an argument -- %c\n", + _getprogname(), optopt); + return (BADCH); + } + place = EMSG; + ++optind; + } + return (optopt); /* return option letter */ +} diff --git a/src/lib/libc/stdlib/getopt_long.c b/src/lib/libc/stdlib/getopt_long.c new file mode 100644 index 0000000..668d322 --- /dev/null +++ b/src/lib/libc/stdlib/getopt_long.c @@ -0,0 +1,625 @@ +/* $OpenBSD: getopt_long.c,v 1.21 2006/09/22 17:22:05 millert Exp $ */ +/* $NetBSD: getopt_long.c,v 1.15 2002/01/31 22:43:40 tv Exp $ */ + +/* + * Copyright (c) 2002 Todd C. Miller + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * Sponsored in part by the Defense Advanced Research Projects + * Agency (DARPA) and Air Force Research Laboratory, Air Force + * Materiel Command, USAF, under agreement number F39502-99-1-0512. + */ +/*- + * Copyright (c) 2000 The NetBSD Foundation, Inc. + * All rights reserved. + * + * This code is derived from software contributed to The NetBSD Foundation + * by Dieter Baron and Thomas Klausner. + * + * 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 NetBSD + * Foundation, Inc. and its contributors. + * 4. Neither the name of The NetBSD Foundation 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 NETBSD FOUNDATION, INC. 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 FOUNDATION 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 0 +#if defined(LIBC_SCCS) && !defined(lint) +static char *rcsid = "$OpenBSD: getopt_long.c,v 1.16 2004/02/04 18:17:25 millert Exp $"; +#endif /* LIBC_SCCS and not lint */ +#endif +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/getopt_long.c,v 1.12.8.1 2006/09/25 17:19:28 ache Exp $"); + +#include +#include +#include +#include +#include + +#define GNU_COMPATIBLE /* Be more compatible, configure's use us! */ + +#if 0 /* we prefer to keep our getopt(3) */ +#define REPLACE_GETOPT /* use this getopt as the system getopt(3) */ +#endif + +#ifdef REPLACE_GETOPT +int opterr = 1; /* if error message should be printed */ +int optind = 1; /* index into parent argv vector */ +int optopt = '?'; /* character checked for validity */ +int optreset; /* reset getopt */ +char *optarg; /* argument associated with option */ +#endif + +#define PRINT_ERROR ((opterr) && (*options != ':')) + +#define FLAG_PERMUTE 0x01 /* permute non-options to the end of argv */ +#define FLAG_ALLARGS 0x02 /* treat non-options as args to option "-1" */ +#define FLAG_LONGONLY 0x04 /* operate as getopt_long_only */ + +/* return values */ +#define BADCH (int)'?' +#define BADARG ((*options == ':') ? (int)':' : (int)'?') +#define INORDER (int)1 + +#define EMSG "" + +#ifdef GNU_COMPATIBLE +#define NO_PREFIX (-1) +#define D_PREFIX 0 +#define DD_PREFIX 1 +#define W_PREFIX 2 +#endif + +static int getopt_internal(int, char * const *, const char *, + const struct option *, int *, int); +static int parse_long_options(char * const *, const char *, + const struct option *, int *, int, int); +static int gcd(int, int); +static void permute_args(int, int, int, char * const *); + +static char *place = EMSG; /* option letter processing */ + +/* XXX: set optreset to 1 rather than these two */ +static int nonopt_start = -1; /* first non option argument (for permute) */ +static int nonopt_end = -1; /* first option after non options (for permute) */ + +/* Error messages */ +static const char recargchar[] = "option requires an argument -- %c"; +static const char illoptchar[] = "illegal option -- %c"; /* From P1003.2 */ +#ifdef GNU_COMPATIBLE +static int dash_prefix = NO_PREFIX; +static const char gnuoptchar[] = "invalid option -- %c"; + +static const char recargstring[] = "option `%s%s' requires an argument"; +static const char ambig[] = "option `%s%.*s' is ambiguous"; +static const char noarg[] = "option `%s%.*s' doesn't allow an argument"; +static const char illoptstring[] = "unrecognized option `%s%s'"; +#else +static const char recargstring[] = "option requires an argument -- %s"; +static const char ambig[] = "ambiguous option -- %.*s"; +static const char noarg[] = "option doesn't take an argument -- %.*s"; +static const char illoptstring[] = "unknown option -- %s"; +#endif + +/* + * Compute the greatest common divisor of a and b. + */ +static int +gcd(int a, int b) +{ + int c; + + c = a % b; + while (c != 0) { + a = b; + b = c; + c = a % b; + } + + return (b); +} + +/* + * Exchange the block from nonopt_start to nonopt_end with the block + * from nonopt_end to opt_end (keeping the same order of arguments + * in each block). + */ +static void +permute_args(int panonopt_start, int panonopt_end, int opt_end, + char * const *nargv) +{ + int cstart, cyclelen, i, j, ncycle, nnonopts, nopts, pos; + char *swap; + + /* + * compute lengths of blocks and number and size of cycles + */ + nnonopts = panonopt_end - panonopt_start; + nopts = opt_end - panonopt_end; + ncycle = gcd(nnonopts, nopts); + cyclelen = (opt_end - panonopt_start) / ncycle; + + for (i = 0; i < ncycle; i++) { + cstart = panonopt_end+i; + pos = cstart; + for (j = 0; j < cyclelen; j++) { + if (pos >= panonopt_end) + pos -= nnonopts; + else + pos += nopts; + swap = nargv[pos]; + /* LINTED const cast */ + ((char **) nargv)[pos] = nargv[cstart]; + /* LINTED const cast */ + ((char **)nargv)[cstart] = swap; + } + } +} + +/* + * parse_long_options -- + * Parse long options in argc/argv argument vector. + * Returns -1 if short_too is set and the option does not match long_options. + */ +static int +parse_long_options(char * const *nargv, const char *options, + const struct option *long_options, int *idx, int short_too, int flags) +{ + char *current_argv, *has_equal; +#ifdef GNU_COMPATIBLE + char *current_dash; +#endif + size_t current_argv_len; + int i, match, exact_match, second_partial_match; + + current_argv = place; +#ifdef GNU_COMPATIBLE + switch (dash_prefix) { + case D_PREFIX: + current_dash = "-"; + break; + case DD_PREFIX: + current_dash = "--"; + break; + case W_PREFIX: + current_dash = "-W "; + break; + default: + current_dash = ""; + break; + } +#endif + match = -1; + exact_match = 0; + second_partial_match = 0; + + optind++; + + if ((has_equal = strchr(current_argv, '=')) != NULL) { + /* argument found (--option=arg) */ + current_argv_len = has_equal - current_argv; + has_equal++; + } else + current_argv_len = strlen(current_argv); + + for (i = 0; long_options[i].name; i++) { + /* find matching long option */ + if (strncmp(current_argv, long_options[i].name, + current_argv_len)) + continue; + + if (strlen(long_options[i].name) == current_argv_len) { + /* exact match */ + match = i; + exact_match = 1; + break; + } + /* + * If this is a known short option, don't allow + * a partial match of a single character. + */ + if (short_too && current_argv_len == 1) + continue; + + if (match == -1) /* first partial match */ + match = i; + else if ((flags & FLAG_LONGONLY) || + long_options[i].has_arg != + long_options[match].has_arg || + long_options[i].flag != long_options[match].flag || + long_options[i].val != long_options[match].val) + second_partial_match = 1; + } + if (!exact_match && second_partial_match) { + /* ambiguous abbreviation */ + if (PRINT_ERROR) + warnx(ambig, +#ifdef GNU_COMPATIBLE + current_dash, +#endif + (int)current_argv_len, + current_argv); + optopt = 0; + return (BADCH); + } + if (match != -1) { /* option found */ + if (long_options[match].has_arg == no_argument + && has_equal) { + if (PRINT_ERROR) + warnx(noarg, +#ifdef GNU_COMPATIBLE + current_dash, +#endif + (int)current_argv_len, + current_argv); + /* + * XXX: GNU sets optopt to val regardless of flag + */ + if (long_options[match].flag == NULL) + optopt = long_options[match].val; + else + optopt = 0; +#ifdef GNU_COMPATIBLE + return (BADCH); +#else + return (BADARG); +#endif + } + if (long_options[match].has_arg == required_argument || + long_options[match].has_arg == optional_argument) { + if (has_equal) + optarg = has_equal; + else if (long_options[match].has_arg == + required_argument) { + /* + * optional argument doesn't use next nargv + */ + optarg = nargv[optind++]; + } + } + if ((long_options[match].has_arg == required_argument) + && (optarg == NULL)) { + /* + * Missing argument; leading ':' indicates no error + * should be generated. + */ + if (PRINT_ERROR) + warnx(recargstring, +#ifdef GNU_COMPATIBLE + current_dash, +#endif + current_argv); + /* + * XXX: GNU sets optopt to val regardless of flag + */ + if (long_options[match].flag == NULL) + optopt = long_options[match].val; + else + optopt = 0; + --optind; + return (BADARG); + } + } else { /* unknown option */ + if (short_too) { + --optind; + return (-1); + } + if (PRINT_ERROR) + warnx(illoptstring, +#ifdef GNU_COMPATIBLE + current_dash, +#endif + current_argv); + optopt = 0; + return (BADCH); + } + if (idx) + *idx = match; + if (long_options[match].flag) { + *long_options[match].flag = long_options[match].val; + return (0); + } else + return (long_options[match].val); +} + +/* + * getopt_internal -- + * Parse argc/argv argument vector. Called by user level routines. + */ +static int +getopt_internal(int nargc, char * const *nargv, const char *options, + const struct option *long_options, int *idx, int flags) +{ + char *oli; /* option letter list index */ + int optchar, short_too; + int posixly_correct; /* no static, can be changed on the fly */ + + if (options == NULL) + return (-1); + + /* + * Disable GNU extensions if POSIXLY_CORRECT is set or options + * string begins with a '+'. + */ + posixly_correct = (getenv("POSIXLY_CORRECT") != NULL); +#ifdef GNU_COMPATIBLE + if (*options == '-') + flags |= FLAG_ALLARGS; + else if (posixly_correct || *options == '+') + flags &= ~FLAG_PERMUTE; +#else + if (posixly_correct || *options == '+') + flags &= ~FLAG_PERMUTE; + else if (*options == '-') + flags |= FLAG_ALLARGS; +#endif + if (*options == '+' || *options == '-') + options++; + + /* + * XXX Some GNU programs (like cvs) set optind to 0 instead of + * XXX using optreset. Work around this braindamage. + */ + if (optind == 0) + optind = optreset = 1; + + optarg = NULL; + if (optreset) + nonopt_start = nonopt_end = -1; +start: + if (optreset || !*place) { /* update scanning pointer */ + optreset = 0; + if (optind >= nargc) { /* end of argument vector */ + place = EMSG; + if (nonopt_end != -1) { + /* do permutation, if we have to */ + permute_args(nonopt_start, nonopt_end, + optind, nargv); + optind -= nonopt_end - nonopt_start; + } + else if (nonopt_start != -1) { + /* + * If we skipped non-options, set optind + * to the first of them. + */ + optind = nonopt_start; + } + nonopt_start = nonopt_end = -1; + return (-1); + } + if (*(place = nargv[optind]) != '-' || +#ifdef GNU_COMPATIBLE + place[1] == '\0') { +#else + (place[1] == '\0' && strchr(options, '-') == NULL)) { +#endif + place = EMSG; /* found non-option */ + if (flags & FLAG_ALLARGS) { + /* + * GNU extension: + * return non-option as argument to option 1 + */ + optarg = nargv[optind++]; + return (INORDER); + } + if (!(flags & FLAG_PERMUTE)) { + /* + * If no permutation wanted, stop parsing + * at first non-option. + */ + return (-1); + } + /* do permutation */ + if (nonopt_start == -1) + nonopt_start = optind; + else if (nonopt_end != -1) { + permute_args(nonopt_start, nonopt_end, + optind, nargv); + nonopt_start = optind - + (nonopt_end - nonopt_start); + nonopt_end = -1; + } + optind++; + /* process next argument */ + goto start; + } + if (nonopt_start != -1 && nonopt_end == -1) + nonopt_end = optind; + + /* + * If we have "-" do nothing, if "--" we are done. + */ + if (place[1] != '\0' && *++place == '-' && place[1] == '\0') { + optind++; + place = EMSG; + /* + * We found an option (--), so if we skipped + * non-options, we have to permute. + */ + if (nonopt_end != -1) { + permute_args(nonopt_start, nonopt_end, + optind, nargv); + optind -= nonopt_end - nonopt_start; + } + nonopt_start = nonopt_end = -1; + return (-1); + } + } + + /* + * Check long options if: + * 1) we were passed some + * 2) the arg is not just "-" + * 3) either the arg starts with -- we are getopt_long_only() + */ + if (long_options != NULL && place != nargv[optind] && + (*place == '-' || (flags & FLAG_LONGONLY))) { + short_too = 0; +#ifdef GNU_COMPATIBLE + dash_prefix = D_PREFIX; +#endif + if (*place == '-') { + place++; /* --foo long option */ +#ifdef GNU_COMPATIBLE + dash_prefix = DD_PREFIX; +#endif + } else if (*place != ':' && strchr(options, *place) != NULL) + short_too = 1; /* could be short option too */ + + optchar = parse_long_options(nargv, options, long_options, + idx, short_too, flags); + if (optchar != -1) { + place = EMSG; + return (optchar); + } + } + + if ((optchar = (int)*place++) == (int)':' || + (optchar == (int)'-' && *place != '\0') || + (oli = strchr(options, optchar)) == NULL) { + /* + * If the user specified "-" and '-' isn't listed in + * options, return -1 (non-option) as per POSIX. + * Otherwise, it is an unknown option character (or ':'). + */ + if (optchar == (int)'-' && *place == '\0') + return (-1); + if (!*place) + ++optind; +#ifdef GNU_COMPATIBLE + if (PRINT_ERROR) + warnx(posixly_correct ? illoptchar : gnuoptchar, + optchar); +#else + if (PRINT_ERROR) + warnx(illoptchar, optchar); +#endif + optopt = optchar; + return (BADCH); + } + if (long_options != NULL && optchar == 'W' && oli[1] == ';') { + /* -W long-option */ + if (*place) /* no space */ + /* NOTHING */; + else if (++optind >= nargc) { /* no arg */ + place = EMSG; + if (PRINT_ERROR) + warnx(recargchar, optchar); + optopt = optchar; + return (BADARG); + } else /* white space */ + place = nargv[optind]; +#ifdef GNU_COMPATIBLE + dash_prefix = W_PREFIX; +#endif + optchar = parse_long_options(nargv, options, long_options, + idx, 0, flags); + place = EMSG; + return (optchar); + } + if (*++oli != ':') { /* doesn't take argument */ + if (!*place) + ++optind; + } else { /* takes (optional) argument */ + optarg = NULL; + if (*place) /* no white space */ + optarg = place; + else if (oli[1] != ':') { /* arg not optional */ + if (++optind >= nargc) { /* no arg */ + place = EMSG; + if (PRINT_ERROR) + warnx(recargchar, optchar); + optopt = optchar; + return (BADARG); + } else + optarg = nargv[optind]; + } + place = EMSG; + ++optind; + } + /* dump back option letter */ + return (optchar); +} + +#ifdef REPLACE_GETOPT +/* + * getopt -- + * Parse argc/argv argument vector. + * + * [eventually this will replace the BSD getopt] + */ +int +getopt(int nargc, char * const *nargv, const char *options) +{ + + /* + * We don't pass FLAG_PERMUTE to getopt_internal() since + * the BSD getopt(3) (unlike GNU) has never done this. + * + * Furthermore, since many privileged programs call getopt() + * before dropping privileges it makes sense to keep things + * as simple (and bug-free) as possible. + */ + return (getopt_internal(nargc, nargv, options, NULL, NULL, 0)); +} +#endif /* REPLACE_GETOPT */ + +/* + * getopt_long -- + * Parse argc/argv argument vector. + */ +int +getopt_long(int nargc, char * const *nargv, const char *options, + const struct option *long_options, int *idx) +{ + + return (getopt_internal(nargc, nargv, options, long_options, idx, + FLAG_PERMUTE)); +} + +/* + * getopt_long_only -- + * Parse argc/argv argument vector. + */ +int +getopt_long_only(int nargc, char * const *nargv, const char *options, + const struct option *long_options, int *idx) +{ + + return (getopt_internal(nargc, nargv, options, long_options, idx, + FLAG_PERMUTE|FLAG_LONGONLY)); +} diff --git a/src/lib/libc/stdlib/getsubopt.c b/src/lib/libc/stdlib/getsubopt.c new file mode 100644 index 0000000..488706a --- /dev/null +++ b/src/lib/libc/stdlib/getsubopt.c @@ -0,0 +1,101 @@ +/*- + * 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[] = "@(#)getsubopt.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/getsubopt.c,v 1.6 2004/02/23 03:30:02 ache Exp $"); + +#include +#include + +/* + * 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; + +int +getsubopt(optionp, tokens, valuep) + char **optionp, **valuep; + char * const *tokens; +{ + int cnt; + 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/src/lib/libc/stdlib/grantpt.c b/src/lib/libc/stdlib/grantpt.c new file mode 100644 index 0000000..fd21382 --- /dev/null +++ b/src/lib/libc/stdlib/grantpt.c @@ -0,0 +1,257 @@ +/* + * Copyright (c) 2002 The FreeBSD Project, Inc. + * All rights reserved. + * + * This software includes code contributed to the FreeBSD Project + * by Ryan Younce of North Carolina State 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. Neither the name of the FreeBSD Project 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 FREEBSD PROJECT 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 FREEBSD PROJECT OR ITS 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. + */ + +#include +#ifndef lint +__FBSDID("$FreeBSD: src/lib/libc/stdlib/grantpt.c,v 1.4 2005/07/07 17:48:40 marcus Exp $"); +#endif /* not lint */ + +#include "namespace.h" +#include +#include +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "un-namespace.h" + +#define PTM_PREFIX "pty" /* pseudo tty master naming convention */ +#define PTS_PREFIX "tty" /* pseudo tty slave naming convention */ + +/* + * The following are range values for pseudo TTY devices. Pseudo TTYs have a + * name of /dev/[pt]ty[p-sP-S][0-9a-v], yielding 256 combinations per major. + */ +#define PT_MAX 256 +#define PT_DEV1 "pqrsPQRS" +#define PT_DEV2 "0123456789abcdefghijklmnopqrstuv" + +/* + * grantpt(3) support utility. + */ +#define _PATH_PTCHOWN "/usr/libexec/pt_chown" + +/* + * ISPTM(x) returns 0 for struct stat x if x is not a pty master. + * The bounds checking may be unnecessary but it does eliminate doubt. + */ +#define ISPTM(x) (S_ISCHR((x).st_mode) && \ + minor((x).st_rdev) >= 0 && \ + minor((x).st_rdev) < PT_MAX) + +/* + * grantpt(): grant ownership of a slave pseudo-terminal device to the + * current user. + */ + +int +grantpt(int fildes) +{ + int retval, serrno, status; + pid_t pid, spid; + gid_t gid; + char *slave; + sigset_t oblock, nblock; + struct group *grp; + + retval = -1; + serrno = errno; + + if ((slave = ptsname(fildes)) != NULL) { + /* + * Block SIGCHLD. + */ + (void)sigemptyset(&nblock); + (void)sigaddset(&nblock, SIGCHLD); + (void)_sigprocmask(SIG_BLOCK, &nblock, &oblock); + + switch (pid = fork()) { + case -1: + break; + case 0: /* child */ + /* + * pt_chown expects the master pseudo TTY to be its + * standard input. + */ + (void)_dup2(fildes, STDIN_FILENO); + (void)_sigprocmask(SIG_SETMASK, &oblock, NULL); + execl(_PATH_PTCHOWN, _PATH_PTCHOWN, (char *)NULL); + _exit(EX_UNAVAILABLE); + /* NOTREACHED */ + default: /* parent */ + /* + * Just wait for the process. Error checking is + * done below. + */ + while ((spid = _waitpid(pid, &status, 0)) == -1 && + (errno == EINTR)) + ; + if (spid != -1 && WIFEXITED(status) && + WEXITSTATUS(status) == EX_OK) + retval = 0; + else + errno = EACCES; + break; + } + + /* + * Restore process's signal mask. + */ + (void)_sigprocmask(SIG_SETMASK, &oblock, NULL); + + if (retval) { + /* + * pt_chown failed. Try to manually change the + * permissions for the slave. + */ + gid = (grp = getgrnam("tty")) ? grp->gr_gid : -1; + if (chown(slave, getuid(), gid) == -1 || + chmod(slave, S_IRUSR | S_IWUSR | S_IWGRP) == -1) + errno = EACCES; + else + retval = 0; + } + } + + if (!retval) + errno = serrno; + + return (retval); +} + +/* + * posix_openpt(): open the first available master pseudo-terminal device + * and return descriptor. + */ +int +posix_openpt(int oflag) +{ + char *mc1, *mc2, master[] = _PATH_DEV PTM_PREFIX "XY"; + const char *pc1, *pc2; + int fildes, bflag, serrno; + + fildes = -1; + bflag = 0; + serrno = errno; + + /* + * Check flag validity. POSIX doesn't require it, + * but we still do so. + */ + if (oflag & ~(O_RDWR | O_NOCTTY)) + errno = EINVAL; + else { + mc1 = master + strlen(_PATH_DEV PTM_PREFIX); + mc2 = mc1 + 1; + + /* Cycle through all possible master PTY devices. */ + for (pc1 = PT_DEV1; !bflag && (*mc1 = *pc1); ++pc1) + for (pc2 = PT_DEV2; (*mc2 = *pc2) != '\0'; ++pc2) { + /* + * Break out if we successfully open a PTY, + * or if open() fails due to limits. + */ + if ((fildes = _open(master, oflag)) != -1 || + (errno == EMFILE || errno == ENFILE)) { + ++bflag; + break; + } + } + + if (fildes != -1) + errno = serrno; + else if (!bflag) + errno = EAGAIN; + } + + return (fildes); +} + +/* + * ptsname(): return the pathname of the slave pseudo-terminal device + * associated with the specified master. + */ +char * +ptsname(int fildes) +{ + static char slave[] = _PATH_DEV PTS_PREFIX "XY"; + char *retval; + struct stat sbuf; + + retval = NULL; + + if (_fstat(fildes, &sbuf) == 0) { + if (!ISPTM(sbuf)) + errno = EINVAL; + else { + (void)snprintf(slave, sizeof(slave), + _PATH_DEV PTS_PREFIX "%s", + devname(sbuf.st_rdev, S_IFCHR) + + strlen(PTM_PREFIX)); + retval = slave; + } + } + + return (retval); +} + +/* + * unlockpt(): unlock a pseudo-terminal device pair. + */ +int +unlockpt(int fildes) +{ + int retval; + struct stat sbuf; + + /* + * Unlocking a master/slave pseudo-terminal pair has no meaning in a + * non-streams PTY environment. However, we do ensure fildes is a + * valid master pseudo-terminal device. + */ + if ((retval = _fstat(fildes, &sbuf)) == 0 && !ISPTM(sbuf)) { + errno = EINVAL; + retval = -1; + } + + return (retval); +} diff --git a/src/lib/libc/stdlib/hcreate.c b/src/lib/libc/stdlib/hcreate.c new file mode 100644 index 0000000..6ab33e5 --- /dev/null +++ b/src/lib/libc/stdlib/hcreate.c @@ -0,0 +1,185 @@ +/* $NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $ */ + +/* + * Copyright (c) 2001 Christopher G. Demetriou + * 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 for the + * NetBSD Project. See http://www.netbsd.org/ for + * information about NetBSD. + * 4. The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``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 AUTHOR 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. + * + * <> + */ + +/* + * hcreate() / hsearch() / hdestroy() + * + * SysV/XPG4 hash table functions. + * + * Implementation done based on NetBSD manual page and Solaris manual page, + * plus my own personal experience about how they're supposed to work. + * + * I tried to look at Knuth (as cited by the Solaris manual page), but + * nobody had a copy in the office, so... + */ + +#include +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: hcreate.c,v 1.2 2001/02/19 21:26:04 ross Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif +__FBSDID("$FreeBSD: src/lib/libc/stdlib/hcreate.c,v 1.3 2002/06/27 13:18:27 deischen Exp $"); + +#include +#include +#include +#include +#include +#include + +/* + * DO NOT MAKE THIS STRUCTURE LARGER THAN 32 BYTES (4 ptrs on 64-bit + * ptr machine) without adjusting MAX_BUCKETS_LG2 below. + */ +struct internal_entry { + SLIST_ENTRY(internal_entry) link; + ENTRY ent; +}; +SLIST_HEAD(internal_head, internal_entry); + +#define MIN_BUCKETS_LG2 4 +#define MIN_BUCKETS (1 << MIN_BUCKETS_LG2) + +/* + * max * sizeof internal_entry must fit into size_t. + * assumes internal_entry is <= 32 (2^5) bytes. + */ +#define MAX_BUCKETS_LG2 (sizeof (size_t) * 8 - 1 - 5) +#define MAX_BUCKETS ((size_t)1 << MAX_BUCKETS_LG2) + +/* Default hash function, from db/hash/hash_func.c */ +extern u_int32_t (*__default_hash)(const void *, size_t); + +static struct internal_head *htable; +static size_t htablesize; + +int +hcreate(size_t nel) +{ + size_t idx; + unsigned int p2; + + /* Make sure this this isn't called when a table already exists. */ + if (htable != NULL) { + errno = EINVAL; + return 0; + } + + /* If nel is too small, make it min sized. */ + if (nel < MIN_BUCKETS) + nel = MIN_BUCKETS; + + /* If it's too large, cap it. */ + if (nel > MAX_BUCKETS) + nel = MAX_BUCKETS; + + /* If it's is not a power of two in size, round up. */ + if ((nel & (nel - 1)) != 0) { + for (p2 = 0; nel != 0; p2++) + nel >>= 1; + nel = 1 << p2; + } + + /* Allocate the table. */ + htablesize = nel; + htable = malloc(htablesize * sizeof htable[0]); + if (htable == NULL) { + errno = ENOMEM; + return 0; + } + + /* Initialize it. */ + for (idx = 0; idx < htablesize; idx++) + SLIST_INIT(&htable[idx]); + + return 1; +} + +void +hdestroy(void) +{ + struct internal_entry *ie; + size_t idx; + + if (htable == NULL) + return; + + for (idx = 0; idx < htablesize; idx++) { + while (!SLIST_EMPTY(&htable[idx])) { + ie = SLIST_FIRST(&htable[idx]); + SLIST_REMOVE_HEAD(&htable[idx], link); + free(ie->ent.key); + free(ie); + } + } + free(htable); + htable = NULL; +} + +ENTRY * +hsearch(ENTRY item, ACTION action) +{ + struct internal_head *head; + struct internal_entry *ie; + uint32_t hashval; + size_t len; + + len = strlen(item.key); + hashval = (*__default_hash)(item.key, len); + + head = &htable[hashval & (htablesize - 1)]; + ie = SLIST_FIRST(head); + while (ie != NULL) { + if (strcmp(ie->ent.key, item.key) == 0) + break; + ie = SLIST_NEXT(ie, link); + } + + if (ie != NULL) + return &ie->ent; + else if (action == FIND) + return NULL; + + ie = malloc(sizeof *ie); + if (ie == NULL) + return NULL; + ie->ent.key = item.key; + ie->ent.data = item.data; + + SLIST_INSERT_HEAD(head, ie, link); + return &ie->ent; +} diff --git a/src/lib/libc/stdlib/heapsort.c b/src/lib/libc/stdlib/heapsort.c new file mode 100644 index 0000000..e846be2 --- /dev/null +++ b/src/lib/libc/stdlib/heapsort.c @@ -0,0 +1,185 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/heapsort.c,v 1.4 2002/03/21 22:48:41 obrien Exp $"); + +#include +#include +#include + +/* + * 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)(const void *, const void *); +{ + int cnt, i, j, l; + 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/src/lib/libc/stdlib/imaxabs.c b/src/lib/libc/stdlib/imaxabs.c new file mode 100644 index 0000000..531de24 --- /dev/null +++ b/src/lib/libc/stdlib/imaxabs.c @@ -0,0 +1,36 @@ +/*- + * Copyright (c) 2001 Mike Barcroft + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/imaxabs.c,v 1.1 2001/11/15 02:05:03 mike Exp $"); + +#include + +intmax_t +imaxabs(intmax_t j) +{ + return (j < 0 ? -j : j); +} diff --git a/src/lib/libc/stdlib/imaxdiv.c b/src/lib/libc/stdlib/imaxdiv.c new file mode 100644 index 0000000..ff3087b --- /dev/null +++ b/src/lib/libc/stdlib/imaxdiv.c @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 2001 Mike Barcroft + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/imaxdiv.c,v 1.1 2001/11/15 02:05:03 mike Exp $"); + +#include + +/* See comments in div.c for implementation details. */ +imaxdiv_t +imaxdiv(intmax_t numer, intmax_t denom) +{ + imaxdiv_t retval; + + retval.quot = numer / denom; + retval.rem = numer % denom; + if (numer >= 0 && retval.rem < 0) { + retval.quot++; + retval.rem -= denom; + } + return (retval); +} diff --git a/src/lib/libc/stdlib/insque.c b/src/lib/libc/stdlib/insque.c new file mode 100644 index 0000000..92984b0 --- /dev/null +++ b/src/lib/libc/stdlib/insque.c @@ -0,0 +1,47 @@ +/* + * Initial implementation: + * Copyright (c) 2002 Robert Drehmel + * All rights reserved. + * + * As long as the above copyright statement and this notice remain + * unchanged, you can do what ever you want with this file. + */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/insque.c,v 1.3 2003/01/04 07:34:41 tjr Exp $"); + +#define _SEARCH_PRIVATE +#include +#ifdef DEBUG +#include +#else +#include /* for NULL */ +#endif + +void +insque(void *element, void *pred) +{ + struct que_elem *prev, *next, *elem; + + elem = (struct que_elem *)element; + prev = (struct que_elem *)pred; + + if (prev == NULL) { + elem->prev = elem->next = NULL; + return; + } + + next = prev->next; + if (next != NULL) { +#ifdef DEBUG + if (next->prev != prev) { + fprintf(stderr, "insque: Inconsistency detected:" + " next(%p)->prev(%p) != prev(%p)\n", + next, next->prev, prev); + } +#endif + next->prev = elem; + } + prev->next = elem; + elem->prev = prev; + elem->next = next; +} diff --git a/src/lib/libc/stdlib/l64a.c b/src/lib/libc/stdlib/l64a.c new file mode 100644 index 0000000..c503558 --- /dev/null +++ b/src/lib/libc/stdlib/l64a.c @@ -0,0 +1,52 @@ +/* + * Written by J.T. Conklin . + * Public domain. + */ + +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: l64a.c,v 1.13 2003/07/26 19:24:54 salo Exp $"); +#endif /* not lint */ +#endif + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/l64a.c,v 1.1.2.1 2006/01/27 05:17:25 trhodes Exp $"); + +#include + +#define ADOT 46 /* ASCII '.' */ +#define ASLASH ADOT + 1 /* ASCII '/' */ +#define A0 48 /* ASCII '0' */ +#define AA 65 /* ASCII 'A' */ +#define Aa 97 /* ASCII 'a' */ + +char * +l64a(long value) +{ + static char buf[8]; + + (void)l64a_r(value, buf, sizeof(buf)); + return (buf); +} + +int +l64a_r(long value, char *buffer, int buflen) +{ + long v; + int digit; + + v = value & (long)0xffffffff; + for (; v != 0 && buflen > 1; buffer++, buflen--) { + digit = v & 0x3f; + if (digit < 2) + *buffer = digit + ADOT; + else if (digit < 12) + *buffer = digit + A0 - 2; + else if (digit < 38) + *buffer = digit + AA - 12; + else + *buffer = digit + Aa - 38; + v >>= 6; + } + return (v == 0 ? 0 : -1); +} diff --git a/src/lib/libc/stdlib/labs.c b/src/lib/libc/stdlib/labs.c new file mode 100644 index 0000000..42e63d1 --- /dev/null +++ b/src/lib/libc/stdlib/labs.c @@ -0,0 +1,47 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/labs.c,v 1.2 2002/03/22 21:53:10 obrien Exp $"); + +#include + +long +labs(j) + long j; +{ + return(j < 0 ? -j : j); +} diff --git a/src/lib/libc/stdlib/ldiv.c b/src/lib/libc/stdlib/ldiv.c new file mode 100644 index 0000000..560d5c2 --- /dev/null +++ b/src/lib/libc/stdlib/ldiv.c @@ -0,0 +1,60 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/ldiv.c,v 1.2 2002/03/22 21:53:10 obrien Exp $"); + +#include /* 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/src/lib/libc/stdlib/llabs.c b/src/lib/libc/stdlib/llabs.c new file mode 100644 index 0000000..4721fce --- /dev/null +++ b/src/lib/libc/stdlib/llabs.c @@ -0,0 +1,36 @@ +/*- + * Copyright (c) 2001 Mike Barcroft + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/llabs.c,v 1.1 2001/11/15 02:05:03 mike Exp $"); + +#include + +long long +llabs(long long j) +{ + return (j < 0 ? -j : j); +} diff --git a/src/lib/libc/stdlib/lldiv.c b/src/lib/libc/stdlib/lldiv.c new file mode 100644 index 0000000..c9a4853 --- /dev/null +++ b/src/lib/libc/stdlib/lldiv.c @@ -0,0 +1,45 @@ +/*- + * Copyright (c) 2001 Mike Barcroft + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/lldiv.c,v 1.1 2001/11/15 02:05:03 mike Exp $"); + +#include + +/* See comments in div.c for implementation details. */ +lldiv_t +lldiv(long long numer, long long denom) +{ + lldiv_t retval; + + retval.quot = numer / denom; + retval.rem = numer % denom; + if (numer >= 0 && retval.rem < 0) { + retval.quot++; + retval.rem -= denom; + } + return (retval); +} diff --git a/src/lib/libc/stdlib/lsearch.c b/src/lib/libc/stdlib/lsearch.c new file mode 100644 index 0000000..791bc49 --- /dev/null +++ b/src/lib/libc/stdlib/lsearch.c @@ -0,0 +1,64 @@ +/* + * Initial implementation: + * Copyright (c) 2002 Robert Drehmel + * All rights reserved. + * + * As long as the above copyright statement and this notice remain + * unchanged, you can do what ever you want with this file. + */ +#include +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/lsearch.c,v 1.1 2002/10/16 14:29:22 robert Exp $"); + +#define _SEARCH_PRIVATE +#include +#include /* for uint8_t */ +#include /* for NULL */ +#include /* for memcpy() prototype */ + +static void *lwork(const void *, const void *, size_t *, size_t, + int (*)(const void *, const void *), int); + +void *lsearch(const void *key, void *base, size_t *nelp, size_t width, + int (*compar)(const void *, const void *)) +{ + + return (lwork(key, base, nelp, width, compar, 1)); +} + +void *lfind(const void *key, const void *base, size_t *nelp, size_t width, + int (*compar)(const void *, const void *)) +{ + + return (lwork(key, base, nelp, width, compar, 0)); +} + +static void * +lwork(const void *key, const void *base, size_t *nelp, size_t width, + int (*compar)(const void *, const void *), int addelem) +{ + uint8_t *ep, *endp; + + /* + * Cast to an integer value first to avoid the warning for removing + * 'const' via a cast. + */ + ep = (uint8_t *)(uintptr_t)base; + for (endp = (uint8_t *)(ep + width * *nelp); ep < endp; ep += width) { + if (compar(key, ep) == 0) + return (ep); + } + + /* lfind() shall return when the key was not found. */ + if (!addelem) + return (NULL); + + /* + * lsearch() adds the key to the end of the table and increments + * the number of elements. + */ + memcpy(endp, key, width); + ++*nelp; + + return (endp); +} diff --git a/src/lib/libc/stdlib/malloc.c b/src/lib/libc/stdlib/malloc.c new file mode 100644 index 0000000..05b238e --- /dev/null +++ b/src/lib/libc/stdlib/malloc.c @@ -0,0 +1,1166 @@ +/* + * ---------------------------------------------------------------------------- + * "THE BEER-WARE LICENSE" (Revision 42): + * wrote this file. As long as you retain this notice you + * can do whatever you want with this stuff. If we meet some day, and you think + * this stuff is worth it, you can buy me a beer in return. Poul-Henning Kamp + * ---------------------------------------------------------------------------- + * + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/malloc.c,v 1.90.2.1 2005/09/18 03:45:24 scottl Exp $"); + +/* + * Defining MALLOC_EXTRA_SANITY will enable extra checks which are related + * to internal conditions and consistency in malloc.c. This has a + * noticeable runtime performance hit, and generally will not do you + * any good unless you fiddle with the internals of malloc or want + * to catch random pointer corruption as early as possible. + */ +#undef MALLOC_EXTRA_SANITY + +/* + * What to use for Junk. This is the byte value we use to fill with + * when the 'J' option is enabled. + */ +#define SOME_JUNK 0xd0 /* as in "Duh" :-) */ + +/* + * The basic parameters you can tweak. + * + * malloc_pageshift pagesize = 1 << malloc_pageshift + * It's probably best if this is the native + * page size, but it doesn't have to be. + * + * malloc_minsize minimum size of an allocation in bytes. + * If this is too small it's too much work + * to manage them. This is also the smallest + * unit of alignment used for the storage + * returned by malloc/realloc. + * + */ + +#include "namespace.h" +#if defined(__FreeBSD__) +# if defined(__i386__) +# define malloc_pageshift 12U +# define malloc_minsize 16U +# endif +# if defined(__ia64__) +# define malloc_pageshift 13U +# define malloc_minsize 16U +# endif +# if defined(__alpha__) +# define malloc_pageshift 13U +# define malloc_minsize 16U +# endif +# if defined(__sparc64__) +# define malloc_pageshift 13U +# define malloc_minsize 16U +# endif +# if defined(__amd64__) +# define malloc_pageshift 12U +# define malloc_minsize 16U +# endif +# if defined(__arm__) +# define malloc_pageshift 12U +# define malloc_minsize 16U +# endif +# define HAS_UTRACE + /* + * Make malloc/free/realloc thread-safe in libc for use with + * kernel threads. + */ +# include "libc_private.h" +# include "spinlock.h" + static spinlock_t thread_lock = _SPINLOCK_INITIALIZER; + spinlock_t *__malloc_lock = &thread_lock; +# define _MALLOC_LOCK() if (__isthreaded) _SPINLOCK(&thread_lock); +# define _MALLOC_UNLOCK() if (__isthreaded) _SPINUNLOCK(&thread_lock); +#endif /* __FreeBSD__ */ + +#if defined(__sparc__) && defined(sun) +# define malloc_pageshift 12U +# define malloc_minsize 16U +# define MAP_ANON (0) + static int fdzero; +# define MMAP_FD fdzero +# define INIT_MMAP() \ + { if ((fdzero = _open(_PATH_DEVZERO, O_RDWR, 0000)) == -1) \ + wrterror("open of /dev/zero"); } +# define MADV_FREE MADV_DONTNEED +#endif /* __sparc__ */ + +/* Insert your combination here... */ +#if defined(__FOOCPU__) && defined(__BAROS__) +# define malloc_pageshift 12U +# define malloc_minsize 16U +#endif /* __FOOCPU__ && __BAROS__ */ + +#ifndef ZEROSIZEPTR +#define ZEROSIZEPTR ((void *)(uintptr_t)(1 << (malloc_pageshift - 1))) +#endif + +/* + * No user serviceable parts behind this point. + */ +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include "un-namespace.h" + +/* + * This structure describes a page worth of chunks. + */ + +struct pginfo { + struct pginfo *next; /* next on the free list */ + void *page; /* Pointer to the page */ + u_short size; /* size of this page's chunks */ + u_short shift; /* How far to shift for this size chunks */ + u_short free; /* How many free chunks */ + u_short total; /* How many chunk */ + u_int bits[1]; /* Which chunks are free */ +}; + +/* + * This structure describes a number of free pages. + */ + +struct pgfree { + struct pgfree *next; /* next run of free pages */ + struct pgfree *prev; /* prev run of free pages */ + void *page; /* pointer to free pages */ + void *end; /* pointer to end of free pages */ + size_t size; /* number of bytes free */ +}; + +/* + * How many bits per u_int in the bitmap. + * Change only if not 8 bits/byte + */ +#define MALLOC_BITS (8*sizeof(u_int)) + +/* + * Magic values to put in the page_directory + */ +#define MALLOC_NOT_MINE ((struct pginfo*) 0) +#define MALLOC_FREE ((struct pginfo*) 1) +#define MALLOC_FIRST ((struct pginfo*) 2) +#define MALLOC_FOLLOW ((struct pginfo*) 3) +#define MALLOC_MAGIC ((struct pginfo*) 4) + +#ifndef malloc_pageshift +#define malloc_pageshift 12U +#endif + +#ifndef malloc_minsize +#define malloc_minsize 16U +#endif + +#if !defined(malloc_pagesize) +#define malloc_pagesize (1UL<>1) +#endif + +/* A mask for the offset inside a page. */ +#define malloc_pagemask ((malloc_pagesize)-1) + +#define pageround(foo) (((foo) + (malloc_pagemask))&(~(malloc_pagemask))) +#define ptr2index(foo) (((u_long)(foo) >> malloc_pageshift)-malloc_origo) + +#ifndef _MALLOC_LOCK +#define _MALLOC_LOCK() +#endif + +#ifndef _MALLOC_UNLOCK +#define _MALLOC_UNLOCK() +#endif + +#ifndef MMAP_FD +#define MMAP_FD (-1) +#endif + +#ifndef INIT_MMAP +#define INIT_MMAP() +#endif + +/* Number of free pages we cache */ +static unsigned malloc_cache = 16; + +/* The offset from pagenumber to index into the page directory */ +static u_long malloc_origo; + +/* The last index in the page directory we care about */ +static u_long last_index; + +/* Pointer to page directory. Allocated "as if with" malloc */ +static struct pginfo **page_dir; + +/* How many slots in the page directory */ +static unsigned malloc_ninfo; + +/* Free pages line up here */ +static struct pgfree free_list; + +/* Abort(), user doesn't handle problems. */ +static int malloc_abort = 0; + +/* Are we trying to die ? */ +static int suicide; + +/* always realloc ? */ +static int malloc_realloc; + +#if defined(MADV_FREE) +/* pass the kernel a hint on free pages ? */ +static int malloc_hint = 0; +#endif + +/* xmalloc behaviour ? */ +static int malloc_xmalloc; + +/* sysv behaviour for malloc(0) ? */ +static int malloc_sysv; + +/* zero fill ? */ +static int malloc_zero; + +/* junk fill ? */ +static int malloc_junk = 0; + +#ifdef HAS_UTRACE + +/* utrace ? */ +static int malloc_utrace; + +struct ut { void *p; size_t s; void *r; }; + +void utrace(struct ut *, int); + +#define UTRACE(a, b, c) \ + if (malloc_utrace) \ + {struct ut u; u.p=a; u.s = b; u.r=c; utrace(&u, sizeof u);} +#else /* !HAS_UTRACE */ +#define UTRACE(a,b,c) +#endif /* HAS_UTRACE */ + +/* my last break. */ +static void *malloc_brk; + +/* one location cache for free-list holders */ +static struct pgfree *px; + +/* compile-time options */ +const char *_malloc_options; + +/* Name of the current public function */ +static const char *malloc_func; + +/* Macro for mmap */ +#define MMAP(size) \ + mmap(NULL, (size), PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, \ + MMAP_FD, (off_t)0); + +/* + * Necessary function declarations + */ +static int extend_pgdir(u_long index); +static void *imalloc(size_t size); +static void ifree(void *ptr); +static void *irealloc(void *ptr, size_t size); + +static void +wrtmessage(const char *p1, const char *p2, const char *p3, const char *p4) +{ + + _write(STDERR_FILENO, p1, strlen(p1)); + _write(STDERR_FILENO, p2, strlen(p2)); + _write(STDERR_FILENO, p3, strlen(p3)); + _write(STDERR_FILENO, p4, strlen(p4)); +} + +void (*_malloc_message)(const char *p1, const char *p2, const char *p3, + const char *p4) = wrtmessage; + +static void +wrterror(char const *p) +{ + + suicide = 1; + _malloc_message(_getprogname(), malloc_func, " error: ", p); + abort(); +} + +static void +wrtwarning(char *p) +{ + + /* + * Sensitive processes, somewhat arbitrarily defined here as setuid, + * setgid, root and wheel cannot afford to have malloc mistakes. + */ + if (malloc_abort || issetugid() || getuid() == 0 || getgid() == 0) + wrterror(p); + _malloc_message(_getprogname(), malloc_func, " warning: ", p); +} + +/* + * Allocate a number of pages from the OS + */ +static void * +map_pages(size_t pages) +{ + caddr_t result, tail; + + result = (caddr_t)pageround((u_long)sbrk(0)); + tail = result + (pages << malloc_pageshift); + if (tail < result) + return (NULL); + + if (brk(tail)) { +#ifdef MALLOC_EXTRA_SANITY + wrterror("(ES): map_pages fails\n"); +#endif /* MALLOC_EXTRA_SANITY */ + return (NULL); + } + + last_index = ptr2index(tail) - 1; + malloc_brk = tail; + + if ((last_index+1) >= malloc_ninfo && !extend_pgdir(last_index)) + return (NULL); + + return (result); +} + +/* + * Extend page directory + */ +static int +extend_pgdir(u_long index) +{ + struct pginfo **new, **old; + u_long i, oldlen; + + /* Make it this many pages */ + i = index * sizeof *page_dir; + i /= malloc_pagesize; + i += 2; + + /* remember the old mapping size */ + oldlen = malloc_ninfo * sizeof *page_dir; + + /* + * NOTE: we allocate new pages and copy the directory rather than tempt + * fate by trying to "grow" the region.. There is nothing to prevent + * us from accidently re-mapping space that's been allocated by our caller + * via dlopen() or other mmap(). + * + * The copy problem is not too bad, as there is 4K of page index per + * 4MB of malloc arena. + * + * We can totally avoid the copy if we open a file descriptor to associate + * the anon mappings with. Then, when we remap the pages at the new + * address, the old pages will be "magically" remapped.. But this means + * keeping open a "secret" file descriptor..... + */ + + /* Get new pages */ + new = (struct pginfo**) MMAP(i * malloc_pagesize); + if (new == MAP_FAILED) + return (0); + + /* Copy the old stuff */ + memcpy(new, page_dir, + malloc_ninfo * sizeof *page_dir); + + /* register the new size */ + malloc_ninfo = i * malloc_pagesize / sizeof *page_dir; + + /* swap the pointers */ + old = page_dir; + page_dir = new; + + /* Now free the old stuff */ + munmap(old, oldlen); + return (1); +} + +/* + * Initialize the world + */ +static void +malloc_init(void) +{ + const char *p; + char b[64]; + int i, j; + int save_errno = errno; + + INIT_MMAP(); + +#ifdef MALLOC_EXTRA_SANITY + malloc_junk = 1; +#endif /* MALLOC_EXTRA_SANITY */ + + for (i = 0; i < 3; i++) { + if (i == 0) { + j = readlink("/etc/malloc.conf", b, sizeof b - 1); + if (j <= 0) + continue; + b[j] = '\0'; + p = b; + } else if (i == 1 && issetugid() == 0) { + p = getenv("MALLOC_OPTIONS"); + } else if (i == 1) { + continue; + } else { + p = _malloc_options; + } + for (; p != NULL && *p != '\0'; p++) { + switch (*p) { + case '>': malloc_cache <<= 1; break; + case '<': malloc_cache >>= 1; break; + case 'a': malloc_abort = 0; break; + case 'A': malloc_abort = 1; break; +#if defined(MADV_FREE) + case 'h': malloc_hint = 0; break; + case 'H': malloc_hint = 1; break; +#endif + case 'r': malloc_realloc = 0; break; + case 'R': malloc_realloc = 1; break; + case 'j': malloc_junk = 0; break; + case 'J': malloc_junk = 1; break; +#ifdef HAS_UTRACE + case 'u': malloc_utrace = 0; break; + case 'U': malloc_utrace = 1; break; +#endif + case 'v': malloc_sysv = 0; break; + case 'V': malloc_sysv = 1; break; + case 'x': malloc_xmalloc = 0; break; + case 'X': malloc_xmalloc = 1; break; + case 'z': malloc_zero = 0; break; + case 'Z': malloc_zero = 1; break; + default: + _malloc_message(_getprogname(), malloc_func, + " warning: ", "unknown char in MALLOC_OPTIONS\n"); + break; + } + } + } + + + UTRACE(0, 0, 0); + + /* + * We want junk in the entire allocation, and zero only in the part + * the user asked for. + */ + if (malloc_zero) + malloc_junk=1; + + /* Allocate one page for the page directory */ + page_dir = (struct pginfo **) MMAP(malloc_pagesize); + + if (page_dir == MAP_FAILED) + wrterror("mmap(2) failed, check limits\n"); + + /* + * We need a maximum of malloc_pageshift buckets, steal these from the + * front of the page_directory; + */ + malloc_origo = ((u_long)pageround((u_long)sbrk(0))) >> malloc_pageshift; + malloc_origo -= malloc_pageshift; + + malloc_ninfo = malloc_pagesize / sizeof *page_dir; + + /* Recalculate the cache size in bytes, and make sure it's nonzero */ + + if (!malloc_cache) + malloc_cache++; + + malloc_cache <<= malloc_pageshift; + + /* + * This is a nice hack from Kaleb Keithly (kaleb@x.org). + * We can sbrk(2) further back when we keep this on a low address. + */ + px = (struct pgfree *) imalloc (sizeof *px); + errno = save_errno; +} + +/* + * Allocate a number of complete pages + */ +static void * +malloc_pages(size_t size) +{ + void *p, *delay_free = NULL; + size_t i; + struct pgfree *pf; + u_long index; + + size = pageround(size); + + p = NULL; + + /* Look for free pages before asking for more */ + for(pf = free_list.next; pf; pf = pf->next) { + +#ifdef MALLOC_EXTRA_SANITY + if (pf->size & malloc_pagemask) + wrterror("(ES): junk length entry on free_list\n"); + if (!pf->size) + wrterror("(ES): zero length entry on free_list\n"); + if (pf->page == pf->end) + wrterror("(ES): zero entry on free_list\n"); + if (pf->page > pf->end) + wrterror("(ES): sick entry on free_list\n"); + if ((void*)pf->page >= (void*)sbrk(0)) + wrterror("(ES): entry on free_list past brk\n"); + if (page_dir[ptr2index(pf->page)] != MALLOC_FREE) + wrterror("(ES): non-free first page on free-list\n"); + if (page_dir[ptr2index(pf->end)-1] != MALLOC_FREE) + wrterror("(ES): non-free last page on free-list\n"); +#endif /* MALLOC_EXTRA_SANITY */ + + if (pf->size < size) + continue; + + if (pf->size == size) { + p = pf->page; + if (pf->next != NULL) + pf->next->prev = pf->prev; + pf->prev->next = pf->next; + delay_free = pf; + break; + } + + p = pf->page; + pf->page = (char *)pf->page + size; + pf->size -= size; + break; + } + +#ifdef MALLOC_EXTRA_SANITY + if (p != NULL && page_dir[ptr2index(p)] != MALLOC_FREE) + wrterror("(ES): allocated non-free page on free-list\n"); +#endif /* MALLOC_EXTRA_SANITY */ + + size >>= malloc_pageshift; + + /* Map new pages */ + if (p == NULL) + p = map_pages(size); + + if (p != NULL) { + + index = ptr2index(p); + page_dir[index] = MALLOC_FIRST; + for (i=1;ibits[0] * + (((malloc_pagesize >> bits)+MALLOC_BITS-1) / MALLOC_BITS); + + /* Don't waste more than two chunks on this */ + if ((1<<(bits)) <= l+l) { + bp = (struct pginfo *)pp; + } else { + bp = (struct pginfo *)imalloc(l); + if (bp == NULL) { + ifree(pp); + return (0); + } + } + + bp->size = (1<shift = bits; + bp->total = bp->free = malloc_pagesize >> bits; + bp->page = pp; + + /* set all valid bits in the bitmap */ + k = bp->total; + i = 0; + + /* Do a bunch at a time */ + for(;k-i >= MALLOC_BITS; i += MALLOC_BITS) + bp->bits[i / MALLOC_BITS] = ~0; + + for(; i < k; i++) + bp->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS); + + if (bp == bp->page) { + /* Mark the ones we stole for ourselves */ + for(i=0;l > 0;i++) { + bp->bits[i/MALLOC_BITS] &= ~(1<<(i%MALLOC_BITS)); + bp->free--; + bp->total--; + l -= (1 << bits); + } + } + + /* MALLOC_LOCK */ + + page_dir[ptr2index(pp)] = bp; + + bp->next = page_dir[bits]; + page_dir[bits] = bp; + + /* MALLOC_UNLOCK */ + + return (1); +} + +/* + * Allocate a fragment + */ +static void * +malloc_bytes(size_t size) +{ + int i,j; + u_int u; + struct pginfo *bp; + int k; + u_int *lp; + + /* Don't bother with anything less than this */ + if (size < malloc_minsize) + size = malloc_minsize; + + /* Find the right bucket */ + j = 1; + i = size-1; + while (i >>= 1) + j++; + + /* If it's empty, make a page more of that size chunks */ + if (page_dir[j] == NULL && !malloc_make_chunks(j)) + return (NULL); + + bp = page_dir[j]; + + /* Find first word of bitmap which isn't empty */ + for (lp = bp->bits; !*lp; lp++) + ; + + /* Find that bit, and tweak it */ + u = 1; + k = 0; + while (!(*lp & u)) { + u += u; + k++; + } + *lp ^= u; + + /* If there are no more free, remove from free-list */ + if (!--bp->free) { + page_dir[j] = bp->next; + bp->next = NULL; + } + + /* Adjust to the real offset of that chunk */ + k += (lp-bp->bits)*MALLOC_BITS; + k <<= bp->shift; + + if (malloc_junk) + memset((u_char *)bp->page + k, SOME_JUNK, bp->size); + + return ((u_char *)bp->page + k); +} + +/* + * Allocate a piece of memory + */ +static void * +imalloc(size_t size) +{ + void *result; + + if (suicide) + abort(); + + if ((size + malloc_pagesize) < size) /* Check for overflow */ + result = NULL; + else if ((size + malloc_pagesize) >= (uintptr_t)page_dir) + result = NULL; + else if (size <= malloc_maxsize) + result = malloc_bytes(size); + else + result = malloc_pages(size); + + if (malloc_zero && result != NULL) + memset(result, 0, size); + + return (result); +} + +/* + * Change the size of an allocation. + */ +static void * +irealloc(void *ptr, size_t size) +{ + void *p; + u_long osize, index; + struct pginfo **mp; + int i; + + if (suicide) + abort(); + + index = ptr2index(ptr); + + if (index < malloc_pageshift) { + wrtwarning("junk pointer, too low to make sense\n"); + return (NULL); + } + + if (index > last_index) { + wrtwarning("junk pointer, too high to make sense\n"); + return (NULL); + } + + mp = &page_dir[index]; + + if (*mp == MALLOC_FIRST) { /* Page allocation */ + + /* Check the pointer */ + if ((u_long)ptr & malloc_pagemask) { + wrtwarning("modified (page-) pointer\n"); + return (NULL); + } + + /* Find the size in bytes */ + for (osize = malloc_pagesize; *(++mp) == MALLOC_FOLLOW;) + osize += malloc_pagesize; + + if (!malloc_realloc && /* Unless we have to, */ + size <= osize && /* .. or are too small, */ + size > (osize - malloc_pagesize)) { /* .. or can free a page, */ + if (malloc_junk) + memset((u_char *)ptr + size, SOME_JUNK, osize-size); + return (ptr); /* ..don't do anything else. */ + } + + } else if (*mp >= MALLOC_MAGIC) { /* Chunk allocation */ + + /* Check the pointer for sane values */ + if (((u_long)ptr & ((*mp)->size-1))) { + wrtwarning("modified (chunk-) pointer\n"); + return (NULL); + } + + /* Find the chunk index in the page */ + i = ((u_long)ptr & malloc_pagemask) >> (*mp)->shift; + + /* Verify that it isn't a free chunk already */ + if ((*mp)->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) { + wrtwarning("chunk is already free\n"); + return (NULL); + } + + osize = (*mp)->size; + + if (!malloc_realloc && /* Unless we have to, */ + size <= osize && /* ..or are too small, */ + (size > osize/2 || /* ..or could use a smaller size, */ + osize == malloc_minsize)) { /* ..(if there is one) */ + if (malloc_junk) + memset((u_char *)ptr + size, SOME_JUNK, osize-size); + return (ptr); /* ..don't do anything else. */ + } + + } else { + wrtwarning("pointer to wrong page\n"); + return (NULL); + } + + p = imalloc(size); + + if (p != NULL) { + /* copy the lesser of the two sizes, and free the old one */ + if (!size || !osize) + ; + else if (osize < size) + memcpy(p, ptr, osize); + else + memcpy(p, ptr, size); + ifree(ptr); + } + return (p); +} + +/* + * Free a sequence of pages + */ + +static __inline void +free_pages(void *ptr, u_long index, struct pginfo const *info) +{ + u_long i; + struct pgfree *pf, *pt=NULL; + u_long l; + void *tail; + + if (info == MALLOC_FREE) { + wrtwarning("page is already free\n"); + return; + } + + if (info != MALLOC_FIRST) { + wrtwarning("pointer to wrong page\n"); + return; + } + + if ((u_long)ptr & malloc_pagemask) { + wrtwarning("modified (page-) pointer\n"); + return; + } + + /* Count how many pages and mark them free at the same time */ + page_dir[index] = MALLOC_FREE; + for (i = 1; page_dir[index+i] == MALLOC_FOLLOW; i++) + page_dir[index + i] = MALLOC_FREE; + + l = i << malloc_pageshift; + + if (malloc_junk) + memset(ptr, SOME_JUNK, l); + +#if defined(MADV_FREE) + if (malloc_hint) + madvise(ptr, l, MADV_FREE); +#endif + + tail = (char *)ptr+l; + + /* add to free-list */ + if (px == NULL) + px = imalloc(sizeof *px); /* This cannot fail... */ + px->page = ptr; + px->end = tail; + px->size = l; + if (free_list.next == NULL) { + + /* Nothing on free list, put this at head */ + px->next = free_list.next; + px->prev = &free_list; + free_list.next = px; + pf = px; + px = NULL; + + } else { + + /* Find the right spot, leave pf pointing to the modified entry. */ + tail = (char *)ptr+l; + + for(pf = free_list.next; pf->end < ptr && pf->next != NULL; + pf = pf->next) + ; /* Race ahead here */ + + if (pf->page > tail) { + /* Insert before entry */ + px->next = pf; + px->prev = pf->prev; + pf->prev = px; + px->prev->next = px; + pf = px; + px = NULL; + } else if (pf->end == ptr ) { + /* Append to the previous entry */ + pf->end = (char *)pf->end + l; + pf->size += l; + if (pf->next != NULL && pf->end == pf->next->page ) { + /* And collapse the next too. */ + pt = pf->next; + pf->end = pt->end; + pf->size += pt->size; + pf->next = pt->next; + if (pf->next != NULL) + pf->next->prev = pf; + } + } else if (pf->page == tail) { + /* Prepend to entry */ + pf->size += l; + pf->page = ptr; + } else if (pf->next == NULL) { + /* Append at tail of chain */ + px->next = NULL; + px->prev = pf; + pf->next = px; + pf = px; + px = NULL; + } else { + wrterror("freelist is destroyed\n"); + } + } + + /* Return something to OS ? */ + if (pf->next == NULL && /* If we're the last one, */ + pf->size > malloc_cache && /* ..and the cache is full, */ + pf->end == malloc_brk && /* ..and none behind us, */ + malloc_brk == sbrk(0)) { /* ..and it's OK to do... */ + + /* + * Keep the cache intact. Notice that the '>' above guarantees that + * the pf will always have at least one page afterwards. + */ + pf->end = (char *)pf->page + malloc_cache; + pf->size = malloc_cache; + + brk(pf->end); + malloc_brk = pf->end; + + index = ptr2index(pf->end); + + for(i=index;i <= last_index;) + page_dir[i++] = MALLOC_NOT_MINE; + + last_index = index - 1; + + /* XXX: We could realloc/shrink the pagedir here I guess. */ + } + if (pt != NULL) + ifree(pt); +} + +/* + * Free a chunk, and possibly the page it's on, if the page becomes empty. + */ + +static __inline void +free_bytes(void *ptr, u_long index, struct pginfo *info) +{ + int i; + struct pginfo **mp; + void *vp; + + /* Find the chunk number on the page */ + i = ((u_long)ptr & malloc_pagemask) >> info->shift; + + if (((u_long)ptr & (info->size-1))) { + wrtwarning("modified (chunk-) pointer\n"); + return; + } + + if (info->bits[i/MALLOC_BITS] & (1<<(i%MALLOC_BITS))) { + wrtwarning("chunk is already free\n"); + return; + } + + if (malloc_junk) + memset(ptr, SOME_JUNK, info->size); + + info->bits[i/MALLOC_BITS] |= 1<<(i%MALLOC_BITS); + info->free++; + + mp = page_dir + info->shift; + + if (info->free == 1) { + + /* Page became non-full */ + + mp = page_dir + info->shift; + /* Insert in address order */ + while (*mp && (*mp)->next && (*mp)->next->page < info->page) + mp = &(*mp)->next; + info->next = *mp; + *mp = info; + return; + } + + if (info->free != info->total) + return; + + /* Find & remove this page in the queue */ + while (*mp != info) { + mp = &((*mp)->next); +#ifdef MALLOC_EXTRA_SANITY + if (!*mp) + wrterror("(ES): Not on queue\n"); +#endif /* MALLOC_EXTRA_SANITY */ + } + *mp = info->next; + + /* Free the page & the info structure if need be */ + page_dir[ptr2index(info->page)] = MALLOC_FIRST; + vp = info->page; /* Order is important ! */ + if(vp != (void*)info) + ifree(info); + ifree(vp); +} + +static void +ifree(void *ptr) +{ + struct pginfo *info; + u_long index; + + /* This is legal */ + if (ptr == NULL) + return; + + /* If we're already sinking, don't make matters any worse. */ + if (suicide) + return; + + index = ptr2index(ptr); + + if (index < malloc_pageshift) { + wrtwarning("junk pointer, too low to make sense\n"); + return; + } + + if (index > last_index) { + wrtwarning("junk pointer, too high to make sense\n"); + return; + } + + info = page_dir[index]; + + if (info < MALLOC_MAGIC) + free_pages(ptr, index, info); + else + free_bytes(ptr, index, info); + return; +} + +static void * +pubrealloc(void *ptr, size_t size, const char *func) +{ + void *r; + int err = 0; + static int malloc_active; /* Recusion flag for public interface. */ + static unsigned malloc_started; /* Set when initialization has been done */ + + /* + * If a thread is inside our code with a functional lock held, and then + * catches a signal which calls us again, we would get a deadlock if the + * lock is not of a recursive type. + */ + _MALLOC_LOCK(); + malloc_func = func; + if (malloc_active > 0) { + if (malloc_active == 1) { + wrtwarning("recursive call\n"); + malloc_active = 2; + } + _MALLOC_UNLOCK(); + errno = EDOOFUS; + return (NULL); + } + malloc_active = 1; + + if (!malloc_started) { + if (ptr != NULL) { + wrtwarning("malloc() has never been called\n"); + malloc_active = 0; + _MALLOC_UNLOCK(); + errno = EDOOFUS; + return (NULL); + } + malloc_init(); + malloc_started = 1; + } + + if (ptr == ZEROSIZEPTR) + ptr = NULL; + if (malloc_sysv && !size) { + if (ptr != NULL) + ifree(ptr); + r = NULL; + } else if (!size) { + if (ptr != NULL) + ifree(ptr); + r = ZEROSIZEPTR; + } else if (ptr == NULL) { + r = imalloc(size); + err = (r == NULL); + } else { + r = irealloc(ptr, size); + err = (r == NULL); + } + UTRACE(ptr, size, r); + malloc_active = 0; + _MALLOC_UNLOCK(); + if (malloc_xmalloc && err) + wrterror("out of memory\n"); + if (err) + errno = ENOMEM; + return (r); +} + +/* + * These are the public exported interface routines. + */ + +void * +malloc(size_t size) +{ + + return (pubrealloc(NULL, size, " in malloc():")); +} + +void +free(void *ptr) +{ + + pubrealloc(ptr, 0, " in free():"); +} + +void * +realloc(void *ptr, size_t size) +{ + + return (pubrealloc(ptr, size, " in realloc():")); +} + diff --git a/src/lib/libc/stdlib/merge.c b/src/lib/libc/stdlib/merge.c new file mode 100644 index 0000000..de3440a --- /dev/null +++ b/src/lib/libc/stdlib/merge.c @@ -0,0 +1,355 @@ +/*- + * 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 */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/merge.c,v 1.7 2005/01/12 03:39:34 brian Exp $"); + +/* + * 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 + +#include +#include +#include + +static void setup(u_char *, u_char *, size_t, size_t, + int (*)(const void *, const void *)); +static void insertionsort(u_char *, size_t, size_t, + int (*)(const void *, const void *)); + +#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; + size_t size; + int (*cmp)(const void *, const void *); +{ + size_t i; + int sense; + int big, iflag; + 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); + } + + if (nmemb == 0) + return (0); + + /* + * 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 */ + 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; + 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)(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)(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/src/lib/libc/stdlib/putenv.c b/src/lib/libc/stdlib/putenv.c new file mode 100644 index 0000000..c8f3b60 --- /dev/null +++ b/src/lib/libc/stdlib/putenv.c @@ -0,0 +1,60 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/putenv.c,v 1.2 2002/03/22 21:53:10 obrien Exp $"); + +#include +#include + +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/src/lib/libc/stdlib/qsort.c b/src/lib/libc/stdlib/qsort.c new file mode 100644 index 0000000..f1add73 --- /dev/null +++ b/src/lib/libc/stdlib/qsort.c @@ -0,0 +1,197 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.12 2002/09/10 02:04:49 wollman Exp $"); + +#include + +#ifdef I_AM_QSORT_R +typedef int cmp_t(void *, const void *, const void *); +#else +typedef int cmp_t(const void *, const void *); +#endif +static inline char *med3(char *, char *, char *, cmp_t *, void *); +static inline void swapfunc(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); \ + TYPE *pi = (TYPE *) (parmi); \ + TYPE *pj = (TYPE *) (parmj); \ + do { \ + 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) + +#ifdef I_AM_QSORT_R +#define CMP(t, x, y) (cmp((t), (x), (y))) +#else +#define CMP(t, x, y) (cmp((x), (y))) +#endif + +static inline char * +med3(char *a, char *b, char *c, cmp_t *cmp, void *thunk +#ifndef I_AM_QSORT_R +__unused +#endif +) +{ + return CMP(thunk, a, b) < 0 ? + (CMP(thunk, b, c) < 0 ? b : (CMP(thunk, a, c) < 0 ? c : a )) + :(CMP(thunk, b, c) > 0 ? b : (CMP(thunk, a, c) < 0 ? a : c )); +} + +#ifdef I_AM_QSORT_R +void +qsort_r(void *a, size_t n, size_t es, void *thunk, cmp_t *cmp) +#else +#define thunk NULL +void +qsort(void *a, size_t n, size_t es, cmp_t *cmp) +#endif +{ + 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 = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; + pl > (char *)a && CMP(thunk, pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + pm = (char *)a + (n / 2) * es; + if (n > 7) { + pl = a; + pn = (char *)a + (n - 1) * es; + if (n > 40) { + d = (n / 8) * es; + pl = med3(pl, pl + d, pl + 2 * d, cmp, thunk); + pm = med3(pm - d, pm, pm + d, cmp, thunk); + pn = med3(pn - 2 * d, pn - d, pn, cmp, thunk); + } + pm = med3(pl, pm, pn, cmp, thunk); + } + swap(a, pm); + pa = pb = (char *)a + es; + + pc = pd = (char *)a + (n - 1) * es; + for (;;) { + while (pb <= pc && (r = CMP(thunk, pb, a)) <= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pa, pb); + pa += es; + } + pb += es; + } + while (pb <= pc && (r = CMP(thunk, 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 = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; + pl > (char *)a && CMP(thunk, pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + + pn = (char *)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) +#ifdef I_AM_QSORT_R + qsort_r(a, r / es, es, thunk, cmp); +#else + qsort(a, r / es, es, cmp); +#endif + 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/src/lib/libc/stdlib/qsort_r.c b/src/lib/libc/stdlib/qsort_r.c new file mode 100644 index 0000000..f7c0e54 --- /dev/null +++ b/src/lib/libc/stdlib/qsort_r.c @@ -0,0 +1,8 @@ +/* + * This file is in the public domain. Originally written by Garrett + * A. Wollman. + * + * $FreeBSD: src/lib/libc/stdlib/qsort_r.c,v 1.1 2002/09/10 02:04:49 wollman Exp $ + */ +#define I_AM_QSORT_R +#include "qsort.c" diff --git a/src/lib/libc/stdlib/radixsort.c b/src/lib/libc/stdlib/radixsort.c new file mode 100644 index 0000000..5f9eaeb --- /dev/null +++ b/src/lib/libc/stdlib/radixsort.c @@ -0,0 +1,331 @@ +/*- + * 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.2 (Berkeley) 4/28/95"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/radixsort.c,v 1.7 2003/11/11 04:59:23 kientzle Exp $"); + +/* + * 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 +#include +#include +#include + +typedef struct { + const u_char **sa; + int sn, si; +} stack; + +static inline void simplesort +(const u_char **, int, int, const u_char *, u_int); +static void r_sort_a(const u_char **, int, int, const u_char *, u_int); +static void r_sort_b(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. */ +static 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; + int c; + 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; + } + } + + /* + * Special case: if all strings have the same + * character at position i, move on to the next + * character. + */ + if (nc == 1 && count[bmin] == n) { + push(a, n, i+1); + nc = count[bmin] = 0; + 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. */ +static 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; + int c; + 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 */ + const u_char **a; + int n, b; + const u_char *tr; + u_int endch; +{ + 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/src/lib/libc/stdlib/rand.c b/src/lib/libc/stdlib/rand.c new file mode 100644 index 0000000..359e12a --- /dev/null +++ b/src/lib/libc/stdlib/rand.c @@ -0,0 +1,172 @@ +/*- + * 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. + * + * Posix rand_r function added May 1999 by Wes Peters . + */ + +#if defined(LIBC_SCCS) && !defined(lint) +static char sccsid[] = "@(#)rand.c 8.1 (Berkeley) 6/14/93"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/rand.c,v 1.15 2003/02/17 03:52:35 ache Exp $"); + +#include "namespace.h" +#include /* for sranddev() */ +#include +#include /* for sranddev() */ +#include +#include /* for sranddev() */ +#include "un-namespace.h" + +#ifdef TEST +#include +#endif /* TEST */ + +static int +do_rand(unsigned long *ctx) +{ +#ifdef USE_WEAK_SEEDING +/* + * Historic implementation compatibility. + * The random sequences do not vary much with the seed, + * even with overflowing. + */ + return ((*ctx = *ctx * 1103515245 + 12345) % ((u_long)RAND_MAX + 1)); +#else /* !USE_WEAK_SEEDING */ +/* + * Compute x = (7^5 * x) mod (2^31 - 1) + * wihout overflowing 31 bits: + * (2^31 - 1) = 127773 * (7^5) + 2836 + * From "Random number generators: good ones are hard to find", + * Park and Miller, Communications of the ACM, vol. 31, no. 10, + * October 1988, p. 1195. + */ + long hi, lo, x; + + /* Can't be initialized with 0, so use another value. */ + if (*ctx == 0) + *ctx = 123459876; + hi = *ctx / 127773; + lo = *ctx % 127773; + x = 16807 * lo - 2836 * hi; + if (x < 0) + x += 0x7fffffff; + return ((*ctx = x) % ((u_long)RAND_MAX + 1)); +#endif /* !USE_WEAK_SEEDING */ +} + + +int +rand_r(unsigned int *ctx) +{ + u_long val = (u_long) *ctx; + int r = do_rand(&val); + + *ctx = (unsigned int) val; + return (r); +} + + +static u_long next = 1; + +int +rand() +{ + return (do_rand(&next)); +} + +void +srand(seed) +u_int seed; +{ + next = seed; +} + + +/* + * sranddev: + * + * Many programs choose the seed value in a totally predictable manner. + * This often causes problems. We seed the generator using the much more + * secure random(4) interface. + */ +void +sranddev() +{ + int fd, done; + + done = 0; + fd = _open("/dev/random", O_RDONLY, 0); + if (fd >= 0) { + if (_read(fd, (void *) &next, sizeof(next)) == sizeof(next)) + done = 1; + _close(fd); + } + + if (!done) { + struct timeval tv; + unsigned long junk; + + gettimeofday(&tv, NULL); + srand((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk); + } +} + + +#ifdef TEST + +main() +{ + int i; + unsigned myseed; + + printf("seeding rand with 0x19610910: \n"); + srand(0x19610910); + + printf("generating three pseudo-random numbers:\n"); + for (i = 0; i < 3; i++) + { + printf("next random number = %d\n", rand()); + } + + printf("generating the same sequence with rand_r:\n"); + myseed = 0x19610910; + for (i = 0; i < 3; i++) + { + printf("next random number = %d\n", rand_r(&myseed)); + } + + return 0; +} + +#endif /* TEST */ + diff --git a/src/lib/libc/stdlib/random.c b/src/lib/libc/stdlib/random.c new file mode 100644 index 0000000..f42436a --- /dev/null +++ b/src/lib/libc/stdlib/random.c @@ -0,0 +1,506 @@ +/* + * 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.2 (Berkeley) 5/19/95"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/random.c,v 1.24 2004/01/20 03:02:18 das Exp $"); + +#include "namespace.h" +#include /* for srandomdev() */ +#include /* for srandomdev() */ +#include +#include +#include +#include /* for srandomdev() */ +#include "un-namespace.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 uint32_t's; 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 ints 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 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. + * + * Modified 28 December 1994 by Jacob S. Rosenberg. + * The following changes have been made: + * All references to the type u_int have been changed to unsigned long. + * All references to type int have been changed to type long. Other + * cleanups have been made as well. A warning for both initstate and + * setstate has been inserted to the effect that on Sparc platforms + * the 'arg_state' variable must be forced to begin on word boundaries. + * This can be easily done by casting a long integer array to char *. + * The overall logic has been left STRICTLY alone. This software was + * tested on both a VAX and Sun SpacsStation with exactly the same + * results. The new version and the original give IDENTICAL results. + * The new version is somewhat faster than the original. As the + * documentation says: "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." For a buffer of + * 128 bytes, this new version runs about 19 percent faster and for a 16 + * byte buffer it is about 5 percent faster. + */ + +/* + * 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 */ + +#ifdef USE_WEAK_SEEDING +#define NSHUFF 0 +#else /* !USE_WEAK_SEEDING */ +#define NSHUFF 50 /* to drop some "seed -> 1st value" linearity */ +#endif /* !USE_WEAK_SEEDING */ + +static const int degrees[MAX_TYPES] = { DEG_0, DEG_1, DEG_2, DEG_3, DEG_4 }; +static const 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 uint32_t randtbl[DEG_3 + 1] = { + TYPE_3, +#ifdef USE_WEAK_SEEDING +/* Historic implementation compatibility */ +/* The random sequences do not vary much with the seed */ + 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, +#else /* !USE_WEAK_SEEDING */ + 0x991539b1, 0x16a5bce3, 0x6774a4cd, 0x3e01511e, 0x4e508aaa, 0x61048c05, + 0xf5500617, 0x846b7115, 0x6a19892c, 0x896a97af, 0xdb48f936, 0x14898454, + 0x37ffd106, 0xb58bff9c, 0x59e17104, 0xcf918a49, 0x09378c83, 0x52c7a471, + 0x8d293ea9, 0x1f4fc301, 0xc3db71be, 0x39b44e1c, 0xf8a44ef9, 0x4c8b80b1, + 0x19edc328, 0x87bf4bdd, 0xc9b240e5, 0xe9ee4b1b, 0x4382aee7, 0x535b6b41, + 0xf3bec5da +#endif /* !USE_WEAK_SEEDING */ +}; + +/* + * 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 uint32_t *fptr = &randtbl[SEP_3 + 1]; +static uint32_t *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 uint32_t *state = &randtbl[1]; +static int rand_type = TYPE_3; +static int rand_deg = DEG_3; +static int rand_sep = SEP_3; +static uint32_t *end_ptr = &randtbl[DEG_3 + 1]; + +static inline uint32_t good_rand(int32_t); + +static inline uint32_t good_rand (x) + int32_t x; +{ +#ifdef USE_WEAK_SEEDING +/* + * Historic implementation compatibility. + * The random sequences do not vary much with the seed, + * even with overflowing. + */ + return (1103515245 * x + 12345); +#else /* !USE_WEAK_SEEDING */ +/* + * Compute x = (7^5 * x) mod (2^31 - 1) + * wihout overflowing 31 bits: + * (2^31 - 1) = 127773 * (7^5) + 2836 + * From "Random number generators: good ones are hard to find", + * Park and Miller, Communications of the ACM, vol. 31, no. 10, + * October 1988, p. 1195. + */ + int32_t hi, lo; + + /* Can't be initialized with 0, so use another value. */ + if (x == 0) + x = 123459876; + hi = x / 127773; + lo = x % 127773; + x = 16807 * lo - 2836 * hi; + if (x < 0) + x += 0x7fffffff; + return (x); +#endif /* !USE_WEAK_SEEDING */ +} + +/* + * 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) + unsigned long x; +{ + int i, lim; + + state[0] = (uint32_t)x; + if (rand_type == TYPE_0) + lim = NSHUFF; + else { + for (i = 1; i < rand_deg; i++) + state[i] = good_rand(state[i - 1]); + fptr = &state[rand_sep]; + rptr = &state[0]; + lim = 10 * rand_deg; + } + for (i = 0; i < lim; i++) + (void)random(); +} + +/* + * srandomdev: + * + * Many programs choose the seed value in a totally predictable manner. + * This often causes problems. We seed the generator using the much more + * secure random(4) interface. Note that this particular seeding + * procedure can generate states which are impossible to reproduce by + * calling srandom() with any value, since the succeeding terms in the + * state buffer are no longer derived from the LC algorithm applied to + * a fixed seed. + */ +void +srandomdev() +{ + int fd, done; + size_t len; + + if (rand_type == TYPE_0) + len = sizeof state[0]; + else + len = rand_deg * sizeof state[0]; + + done = 0; + fd = _open("/dev/random", O_RDONLY, 0); + if (fd >= 0) { + if (_read(fd, (void *) state, len) == (ssize_t) len) + done = 1; + _close(fd); + } + + if (!done) { + struct timeval tv; + unsigned long junk; + + gettimeofday(&tv, NULL); + srandom((getpid() << 16) ^ tv.tv_sec ^ tv.tv_usec ^ junk); + return; + } + + if (rand_type != TYPE_0) { + fptr = &state[rand_sep]; + rptr = &state[0]; + } +} + +/* + * 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. + * + * Note: The Sparc platform requires that arg_state begin on an int + * word boundary; otherwise a bus error will occur. Even so, lint will + * complain about mis-alignment, but you should disregard these messages. + */ +char * +initstate(seed, arg_state, n) + unsigned long seed; /* seed for R.N.G. */ + char *arg_state; /* pointer to state array */ + long n; /* # bytes of state info */ +{ + char *ostate = (char *)(&state[-1]); + uint32_t *int_arg_state = (uint32_t *)arg_state; + + 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 (%ld 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 = int_arg_state + 1; /* first location */ + end_ptr = &state[rand_deg]; /* must set end_ptr before srandom */ + srandom(seed); + if (rand_type == TYPE_0) + int_arg_state[0] = rand_type; + else + int_arg_state[0] = 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. + * + * Note: The Sparc platform requires that arg_state begin on an int + * word boundary; otherwise a bus error will occur. Even so, lint will + * complain about mis-alignment, but you should disregard these messages. + */ +char * +setstate(arg_state) + char *arg_state; /* pointer to state array */ +{ + uint32_t *new_state = (uint32_t *)arg_state; + uint32_t type = new_state[0] % MAX_TYPES; + uint32_t 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() +{ + uint32_t i; + uint32_t *f, *r; + + if (rand_type == TYPE_0) { + i = state[0]; + state[0] = i = (good_rand(i)) & 0x7fffffff; + } else { + /* + * Use local variables rather than static variables for speed. + */ + f = fptr; r = rptr; + *f += *r; + i = (*f >> 1) & 0x7fffffff; /* chucking least random bit */ + if (++f >= end_ptr) { + f = state; + ++r; + } + else if (++r >= end_ptr) { + r = state; + } + + fptr = f; rptr = r; + } + return((long)i); +} diff --git a/src/lib/libc/stdlib/reallocf.c b/src/lib/libc/stdlib/reallocf.c new file mode 100644 index 0000000..d502006 --- /dev/null +++ b/src/lib/libc/stdlib/reallocf.c @@ -0,0 +1,41 @@ +/*- + * Copyright (c) 1998, M. Warner Losh + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/reallocf.c,v 1.4 2002/03/22 21:53:10 obrien Exp $"); + +#include + +void * +reallocf(void *ptr, size_t size) +{ + void *nptr; + + nptr = realloc(ptr, size); + if (!nptr && ptr) + free(ptr); + return (nptr); +} diff --git a/src/lib/libc/stdlib/realpath.c b/src/lib/libc/stdlib/realpath.c new file mode 100644 index 0000000..31e0977 --- /dev/null +++ b/src/lib/libc/stdlib/realpath.c @@ -0,0 +1,197 @@ +/* + * Copyright (c) 2003 Constantin S. Svintsoff + * + * 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. The names of the authors may not be used to endorse or promote + * products derived from this software without specific prior written + * permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/realpath.c,v 1.20 2003/05/28 08:23:01 fjoe Exp $"); + +#include "namespace.h" +#include +#include + +#include +#include +#include +#include +#include "un-namespace.h" + +/* + * char *realpath(const char *path, char resolved[PATH_MAX]); + * + * 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(const char *path, char resolved[PATH_MAX]) +{ + struct stat sb; + char *p, *q, *s; + size_t left_len, resolved_len; + unsigned symlinks; + int serrno, slen; + char left[PATH_MAX], next_token[PATH_MAX], symlink[PATH_MAX]; + + serrno = errno; + symlinks = 0; + if (path[0] == '/') { + resolved[0] = '/'; + resolved[1] = '\0'; + if (path[1] == '\0') + return (resolved); + resolved_len = 1; + left_len = strlcpy(left, path + 1, sizeof(left)); + } else { + if (getcwd(resolved, PATH_MAX) == NULL) { + strlcpy(resolved, ".", PATH_MAX); + return (NULL); + } + resolved_len = strlen(resolved); + left_len = strlcpy(left, path, sizeof(left)); + } + if (left_len >= sizeof(left) || resolved_len >= PATH_MAX) { + errno = ENAMETOOLONG; + return (NULL); + } + + /* + * Iterate over path components in `left'. + */ + while (left_len != 0) { + /* + * Extract the next path component and adjust `left' + * and its length. + */ + p = strchr(left, '/'); + s = p ? p : left + left_len; + if (s - left >= sizeof(next_token)) { + errno = ENAMETOOLONG; + return (NULL); + } + memcpy(next_token, left, s - left); + next_token[s - left] = '\0'; + left_len -= s - left; + if (p != NULL) + memmove(left, s + 1, left_len + 1); + if (resolved[resolved_len - 1] != '/') { + if (resolved_len + 1 >= PATH_MAX) { + errno = ENAMETOOLONG; + return (NULL); + } + resolved[resolved_len++] = '/'; + resolved[resolved_len] = '\0'; + } + if (next_token[0] == '\0') + continue; + else if (strcmp(next_token, ".") == 0) + continue; + else if (strcmp(next_token, "..") == 0) { + /* + * Strip the last path component except when we have + * single "/" + */ + if (resolved_len > 1) { + resolved[resolved_len - 1] = '\0'; + q = strrchr(resolved, '/') + 1; + *q = '\0'; + resolved_len = q - resolved; + } + continue; + } + + /* + * Append the next path component and lstat() it. If + * lstat() fails we still can return successfully if + * there are no more path components left. + */ + resolved_len = strlcat(resolved, next_token, PATH_MAX); + if (resolved_len >= PATH_MAX) { + errno = ENAMETOOLONG; + return (NULL); + } + if (lstat(resolved, &sb) != 0) { + if (errno == ENOENT && p == NULL) { + errno = serrno; + return (resolved); + } + return (NULL); + } + if (S_ISLNK(sb.st_mode)) { + if (symlinks++ > MAXSYMLINKS) { + errno = ELOOP; + return (NULL); + } + slen = readlink(resolved, symlink, sizeof(symlink) - 1); + if (slen < 0) + return (NULL); + symlink[slen] = '\0'; + if (symlink[0] == '/') { + resolved[1] = 0; + resolved_len = 1; + } else if (resolved_len > 1) { + /* Strip the last path component. */ + resolved[resolved_len - 1] = '\0'; + q = strrchr(resolved, '/') + 1; + *q = '\0'; + resolved_len = q - resolved; + } + + /* + * If there are any path components left, then + * append them to symlink. The result is placed + * in `left'. + */ + if (p != NULL) { + if (symlink[slen - 1] != '/') { + if (slen + 1 >= sizeof(symlink)) { + errno = ENAMETOOLONG; + return (NULL); + } + symlink[slen] = '/'; + symlink[slen + 1] = 0; + } + left_len = strlcat(symlink, left, sizeof(left)); + if (left_len >= sizeof(left)) { + errno = ENAMETOOLONG; + return (NULL); + } + } + left_len = strlcpy(left, symlink, sizeof(left)); + } + } + + /* + * Remove trailing slash except when the resolved pathname + * is a single "/". + */ + if (resolved_len > 1 && resolved[resolved_len - 1] == '/') + resolved[resolved_len - 1] = '\0'; + return (resolved); +} diff --git a/src/lib/libc/stdlib/remque.c b/src/lib/libc/stdlib/remque.c new file mode 100644 index 0000000..068a75f --- /dev/null +++ b/src/lib/libc/stdlib/remque.c @@ -0,0 +1,30 @@ +/* + * Initial implementation: + * Copyright (c) 2002 Robert Drehmel + * All rights reserved. + * + * As long as the above copyright statement and this notice remain + * unchanged, you can do what ever you want with this file. + */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/remque.c,v 1.3 2003/01/04 07:34:41 tjr Exp $"); + +#define _SEARCH_PRIVATE +#include +#include /* for NULL */ + +void +remque(void *element) +{ + struct que_elem *prev, *next, *elem; + + elem = (struct que_elem *)element; + + prev = elem->prev; + next = elem->next; + + if (prev != NULL) + prev->next = next; + if (next != NULL) + next->prev = prev; +} diff --git a/src/lib/libc/stdlib/setenv.c b/src/lib/libc/stdlib/setenv.c new file mode 100644 index 0000000..d7c0394 --- /dev/null +++ b/src/lib/libc/stdlib/setenv.c @@ -0,0 +1,120 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/setenv.c,v 1.9 2002/03/22 21:53:10 obrien Exp $"); + +#include +#include +#include + +char *__findenv(const char *, int *); + +/* + * setenv -- + * Set the value of the environmental variable "name" to be + * "value". If rewrite is set, replace any current value. + */ +int +setenv(name, value, rewrite) + const char *name; + const char *value; + int rewrite; +{ + extern char **environ; + static char **alloced; /* if allocated space before */ + 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 */ + int cnt; + char **p; + + for (p = environ, cnt = 0; *p; ++p, ++cnt); + if (alloced == environ) { /* just increase size */ + p = (char **)realloc((char *)environ, + (size_t)(sizeof(char *) * (cnt + 2))); + if (!p) + return (-1); + alloced = environ = p; + } + else { /* get new space */ + /* copy old entries into it */ + p = malloc((size_t)(sizeof(char *) * (cnt + 2))); + if (!p) + return (-1); + bcopy(environ, p, cnt * sizeof(char *)); + alloced = 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; + 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/src/lib/libc/stdlib/strfmon.c b/src/lib/libc/stdlib/strfmon.c new file mode 100644 index 0000000..db569d5 --- /dev/null +++ b/src/lib/libc/stdlib/strfmon.c @@ -0,0 +1,603 @@ +/*- + * Copyright (c) 2001 Alexey Zelkin + * 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. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR 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 AUTHOR 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. + * + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strfmon.c,v 1.14 2003/03/20 08:18:55 ache Exp $"); + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +/* internal flags */ +#define NEED_GROUPING 0x01 /* print digits grouped (default) */ +#define SIGN_POSN_USED 0x02 /* '+' or '(' usage flag */ +#define LOCALE_POSN 0x04 /* use locale defined +/- (default) */ +#define PARENTH_POSN 0x08 /* enclose negative amount in () */ +#define SUPRESS_CURR_SYMBOL 0x10 /* supress the currency from output */ +#define LEFT_JUSTIFY 0x20 /* left justify */ +#define USE_INTL_CURRENCY 0x40 /* use international currency symbol */ +#define IS_NEGATIVE 0x80 /* is argument value negative ? */ + +/* internal macros */ +#define PRINT(CH) do { \ + if (dst >= s + maxsize) \ + goto e2big_error; \ + *dst++ = CH; \ +} while (0) + +#define PRINTS(STR) do { \ + char *tmps = STR; \ + while (*tmps != '\0') \ + PRINT(*tmps++); \ +} while (0) + +#define GET_NUMBER(VAR) do { \ + VAR = 0; \ + while (isdigit((unsigned char)*fmt)) { \ + VAR *= 10; \ + VAR += *fmt - '0'; \ + fmt++; \ + } \ +} while (0) + +#define GRPCPY(howmany) do { \ + int i = howmany; \ + while (i-- > 0) { \ + avalue_size--; \ + *--bufend = *(avalue+avalue_size+padded); \ + } \ +} while (0) + +#define GRPSEP do { \ + *--bufend = thousands_sep; \ + groups++; \ +} while (0) + +static void __setup_vars(int, char *, char *, char *, char **); +static int __calc_left_pad(int, char *); +static char *__format_grouped_double(double, int *, int, int, int); + +ssize_t +strfmon(char * __restrict s, size_t maxsize, const char * __restrict format, + ...) +{ + va_list ap; + char *dst; /* output destination pointer */ + const char *fmt; /* current format poistion pointer */ + struct lconv *lc; /* pointer to lconv structure */ + char *asciivalue; /* formatted double pointer */ + + int flags; /* formatting options */ + int pad_char; /* padding character */ + int pad_size; /* pad size */ + int width; /* field width */ + int left_prec; /* left precision */ + int right_prec; /* right precision */ + double value; /* just value */ + char space_char = ' '; /* space after currency */ + + char cs_precedes, /* values gathered from struct lconv */ + sep_by_space, + sign_posn, + *signstr, + *currency_symbol; + + char *tmpptr; /* temporary vars */ + int sverrno; + + va_start(ap, format); + + lc = localeconv(); + dst = s; + fmt = format; + asciivalue = NULL; + currency_symbol = NULL; + pad_size = 0; + + while (*fmt) { + /* pass nonformating characters AS IS */ + if (*fmt != '%') + goto literal; + + /* '%' found ! */ + + /* "%%" mean just '%' */ + if (*(fmt+1) == '%') { + fmt++; + literal: + PRINT(*fmt++); + continue; + } + + /* set up initial values */ + flags = (NEED_GROUPING|LOCALE_POSN); + pad_char = ' '; /* padding character is "space" */ + left_prec = -1; /* no left precision specified */ + right_prec = -1; /* no right precision specified */ + width = -1; /* no width specified */ + value = 0; /* we have no value to print now */ + + /* Flags */ + while (1) { + switch (*++fmt) { + case '=': /* fill character */ + pad_char = *++fmt; + if (pad_char == '\0') + goto format_error; + continue; + case '^': /* not group currency */ + flags &= ~(NEED_GROUPING); + continue; + case '+': /* use locale defined signs */ + if (flags & SIGN_POSN_USED) + goto format_error; + flags |= (SIGN_POSN_USED|LOCALE_POSN); + continue; + case '(': /* enclose negatives with () */ + if (flags & SIGN_POSN_USED) + goto format_error; + flags |= (SIGN_POSN_USED|PARENTH_POSN); + continue; + case '!': /* suppress currency symbol */ + flags |= SUPRESS_CURR_SYMBOL; + continue; + case '-': /* alignment (left) */ + flags |= LEFT_JUSTIFY; + continue; + default: + break; + } + break; + } + + /* field Width */ + if (isdigit((unsigned char)*fmt)) { + GET_NUMBER(width); + /* Do we have enough space to put number with + * required width ? + */ + if (dst + width >= s + maxsize) + goto e2big_error; + } + + /* Left precision */ + if (*fmt == '#') { + if (!isdigit((unsigned char)*++fmt)) + goto format_error; + GET_NUMBER(left_prec); + } + + /* Right precision */ + if (*fmt == '.') { + if (!isdigit((unsigned char)*++fmt)) + goto format_error; + GET_NUMBER(right_prec); + } + + /* Conversion Characters */ + switch (*fmt++) { + case 'i': /* use internaltion currency format */ + flags |= USE_INTL_CURRENCY; + break; + case 'n': /* use national currency format */ + flags &= ~(USE_INTL_CURRENCY); + break; + default: /* required character is missing or + premature EOS */ + goto format_error; + } + + if (flags & USE_INTL_CURRENCY) { + currency_symbol = strdup(lc->int_curr_symbol); + if (currency_symbol != NULL) + space_char = *(currency_symbol+3); + } else + currency_symbol = strdup(lc->currency_symbol); + + if (currency_symbol == NULL) + goto end_error; /* ENOMEM. */ + + /* value itself */ + value = va_arg(ap, double); + + /* detect sign */ + if (value < 0) { + flags |= IS_NEGATIVE; + value = -value; + } + + /* fill left_prec with amount of padding chars */ + if (left_prec >= 0) { + pad_size = __calc_left_pad((flags ^ IS_NEGATIVE), + currency_symbol) - + __calc_left_pad(flags, currency_symbol); + if (pad_size < 0) + pad_size = 0; + } + + asciivalue = __format_grouped_double(value, &flags, + left_prec, right_prec, pad_char); + if (asciivalue == NULL) + goto end_error; /* errno already set */ + /* to ENOMEM by malloc() */ + + /* set some variables for later use */ + __setup_vars(flags, &cs_precedes, &sep_by_space, + &sign_posn, &signstr); + + /* + * Description of some LC_MONETARY's values: + * + * p_cs_precedes & n_cs_precedes + * + * = 1 - $currency_symbol precedes the value + * for a monetary quantity with a non-negative value + * = 0 - symbol succeeds the value + * + * p_sep_by_space & n_sep_by_space + * + * = 0 - no space separates $currency_symbol + * from the value for a monetary quantity with a + * non-negative value + * = 1 - space separates the symbol from the value + * = 2 - space separates the symbol and the sign string, + * if adjacent. + * + * p_sign_posn & n_sign_posn + * + * = 0 - parentheses enclose the quantity and the + * $currency_symbol + * = 1 - the sign string precedes the quantity and the + * $currency_symbol + * = 2 - the sign string succeeds the quantity and the + * $currency_symbol + * = 3 - the sign string precedes the $currency_symbol + * = 4 - the sign string succeeds the $currency_symbol + * + */ + + tmpptr = dst; + + while (pad_size-- > 0) + PRINT(' '); + + if (sign_posn == 0 && (flags & IS_NEGATIVE)) + PRINT('('); + + if (cs_precedes == 1) { + if (sign_posn == 1 || sign_posn == 3) { + PRINTS(signstr); + if (sep_by_space == 2) /* XXX: ? */ + PRINT(' '); + } + + if (!(flags & SUPRESS_CURR_SYMBOL)) { + PRINTS(currency_symbol); + + if (sign_posn == 4) { + if (sep_by_space == 2) + PRINT(space_char); + PRINTS(signstr); + if (sep_by_space == 1) + PRINT(' '); + } else if (sep_by_space == 1) + PRINT(space_char); + } + } else if (sign_posn == 1) + PRINTS(signstr); + + PRINTS(asciivalue); + + if (cs_precedes == 0) { + if (sign_posn == 3) { + if (sep_by_space == 1) + PRINT(' '); + PRINTS(signstr); + } + + if (!(flags & SUPRESS_CURR_SYMBOL)) { + if ((sign_posn == 3 && sep_by_space == 2) + || (sep_by_space == 1 + && (sign_posn == 0 + || sign_posn == 1 + || sign_posn == 2 + || sign_posn == 4))) + PRINT(space_char); + PRINTS(currency_symbol); /* XXX: len */ + if (sign_posn == 4) { + if (sep_by_space == 2) + PRINT(' '); + PRINTS(signstr); + } + } + } + + if (sign_posn == 2) { + if (sep_by_space == 2) + PRINT(' '); + PRINTS(signstr); + } + + if (sign_posn == 0 && (flags & IS_NEGATIVE)) + PRINT(')'); + + if (dst - tmpptr < width) { + if (flags & LEFT_JUSTIFY) { + while (dst - tmpptr < width) + PRINT(' '); + } else { + pad_size = dst-tmpptr; + memmove(tmpptr + width-pad_size, tmpptr, + pad_size); + memset(tmpptr, ' ', width-pad_size); + dst += width-pad_size; + } + } + } + + PRINT('\0'); + va_end(ap); + free(asciivalue); + free(currency_symbol); + return (dst - s - 1); /* return size of put data except trailing '\0' */ + +e2big_error: + errno = E2BIG; + goto end_error; + +format_error: + errno = EINVAL; + +end_error: + sverrno = errno; + if (asciivalue != NULL) + free(asciivalue); + if (currency_symbol != NULL) + free(currency_symbol); + errno = sverrno; + va_end(ap); + return (-1); +} + +static void +__setup_vars(int flags, char *cs_precedes, char *sep_by_space, + char *sign_posn, char **signstr) { + + struct lconv *lc = localeconv(); + + if ((flags & IS_NEGATIVE) && (flags & USE_INTL_CURRENCY)) { + *cs_precedes = lc->int_n_cs_precedes; + *sep_by_space = lc->int_n_sep_by_space; + *sign_posn = (flags & PARENTH_POSN) ? 0 : lc->int_n_sign_posn; + *signstr = (lc->negative_sign == '\0') ? "-" + : lc->negative_sign; + } else if (flags & USE_INTL_CURRENCY) { + *cs_precedes = lc->int_p_cs_precedes; + *sep_by_space = lc->int_p_sep_by_space; + *sign_posn = (flags & PARENTH_POSN) ? 0 : lc->int_p_sign_posn; + *signstr = lc->positive_sign; + } else if (flags & IS_NEGATIVE) { + *cs_precedes = lc->n_cs_precedes; + *sep_by_space = lc->n_sep_by_space; + *sign_posn = (flags & PARENTH_POSN) ? 0 : lc->n_sign_posn; + *signstr = (lc->negative_sign == '\0') ? "-" + : lc->negative_sign; + } else { + *cs_precedes = lc->p_cs_precedes; + *sep_by_space = lc->p_sep_by_space; + *sign_posn = (flags & PARENTH_POSN) ? 0 : lc->p_sign_posn; + *signstr = lc->positive_sign; + } + + /* Set defult values for unspecified information. */ + if (*cs_precedes != 0) + *cs_precedes = 1; + if (*sep_by_space == CHAR_MAX) + *sep_by_space = 0; + if (*sign_posn == CHAR_MAX) + *sign_posn = 0; +} + +static int +__calc_left_pad(int flags, char *cur_symb) { + + char cs_precedes, sep_by_space, sign_posn, *signstr; + int left_chars = 0; + + __setup_vars(flags, &cs_precedes, &sep_by_space, &sign_posn, &signstr); + + if (cs_precedes != 0) { + left_chars += strlen(cur_symb); + if (sep_by_space != 0) + left_chars++; + } + + switch (sign_posn) { + case 1: + left_chars += strlen(signstr); + break; + case 3: + case 4: + if (cs_precedes != 0) + left_chars += strlen(signstr); + } + return (left_chars); +} + +static int +get_groups(int size, char *grouping) { + + int chars = 0; + + if (*grouping == CHAR_MAX || *grouping <= 0) /* no grouping ? */ + return (0); + + while (size > (int)*grouping) { + chars++; + size -= (int)*grouping++; + /* no more grouping ? */ + if (*grouping == CHAR_MAX) + break; + /* rest grouping with same value ? */ + if (*grouping == 0) { + chars += (size - 1) / *(grouping - 1); + break; + } + } + return (chars); +} + +/* convert double to ASCII */ +static char * +__format_grouped_double(double value, int *flags, + int left_prec, int right_prec, int pad_char) { + + char *rslt; + char *avalue; + int avalue_size; + char fmt[32]; + + size_t bufsize; + char *bufend; + + int padded; + + struct lconv *lc = localeconv(); + char *grouping; + char decimal_point; + char thousands_sep; + + int groups = 0; + + grouping = lc->mon_grouping; + decimal_point = *lc->mon_decimal_point; + if (decimal_point == '\0') + decimal_point = *lc->decimal_point; + thousands_sep = *lc->mon_thousands_sep; + if (thousands_sep == '\0') + thousands_sep = *lc->thousands_sep; + + /* fill left_prec with default value */ + if (left_prec == -1) + left_prec = 0; + + /* fill right_prec with default value */ + if (right_prec == -1) { + if (*flags & USE_INTL_CURRENCY) + right_prec = lc->int_frac_digits; + else + right_prec = lc->frac_digits; + + if (right_prec == CHAR_MAX) /* POSIX locale ? */ + right_prec = 2; + } + + if (*flags & NEED_GROUPING) + left_prec += get_groups(left_prec, grouping); + + /* convert to string */ + snprintf(fmt, sizeof(fmt), "%%%d.%df", left_prec + right_prec + 1, + right_prec); + avalue_size = asprintf(&avalue, fmt, value); + if (avalue_size < 0) + return (NULL); + + /* make sure that we've enough space for result string */ + bufsize = strlen(avalue)*2+1; + rslt = malloc(bufsize); + if (rslt == NULL) { + free(avalue); + return (NULL); + } + memset(rslt, 0, bufsize); + bufend = rslt + bufsize - 1; /* reserve space for trailing '\0' */ + + /* skip spaces at beggining */ + padded = 0; + while (avalue[padded] == ' ') { + padded++; + avalue_size--; + } + + if (right_prec > 0) { + bufend -= right_prec; + memcpy(bufend, avalue + avalue_size+padded-right_prec, + right_prec); + *--bufend = decimal_point; + avalue_size -= (right_prec + 1); + } + + if ((*flags & NEED_GROUPING) && + thousands_sep != '\0' && /* XXX: need investigation */ + *grouping != CHAR_MAX && + *grouping > 0) { + while (avalue_size > (int)*grouping) { + GRPCPY(*grouping); + GRPSEP; + grouping++; + + /* no more grouping ? */ + if (*grouping == CHAR_MAX) + break; + + /* rest grouping with same value ? */ + if (*grouping == 0) { + grouping--; + while (avalue_size > *grouping) { + GRPCPY(*grouping); + GRPSEP; + } + } + } + if (avalue_size != 0) + GRPCPY(avalue_size); + padded -= groups; + + } else { + bufend -= avalue_size; + memcpy(bufend, avalue+padded, avalue_size); + if (right_prec == 0) + padded--; /* decrease assumed $decimal_point */ + } + + /* do padding with pad_char */ + if (padded > 0) { + bufend -= padded; + memset(bufend, pad_char, padded); + } + + bufsize = bufsize - (bufend - rslt) + 1; + memmove(rslt, bufend, bufsize); + free(avalue); + return (rslt); +} diff --git a/src/lib/libc/stdlib/strtoimax.c b/src/lib/libc/stdlib/strtoimax.c new file mode 100644 index 0000000..f5bc3b4 --- /dev/null +++ b/src/lib/libc/stdlib/strtoimax.c @@ -0,0 +1,144 @@ +/*- + * 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[] = "from @(#)strtol.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtoimax.c,v 1.11 2005/01/21 13:31:02 ache Exp $"); + +#include +#include +#include +#include + +/* + * Convert a string to an intmax_t integer. + * + * Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +intmax_t +strtoimax(const char * __restrict nptr, char ** __restrict endptr, int base) +{ + const char *s; + uintmax_t acc; + char c; + uintmax_t cutoff; + 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((unsigned char)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') && + ((s[1] >= '0' && s[1] <= '9') || + (s[1] >= 'A' && s[1] <= 'F') || + (s[1] >= 'a' && s[1] <= 'f'))) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + acc = any = 0; + if (base < 2 || base > 36) + goto noconv; + + /* + * 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 intmax_t 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. + */ + cutoff = neg ? (uintmax_t)-(INTMAX_MIN + INTMAX_MAX) + INTMAX_MAX + : INTMAX_MAX; + cutlim = cutoff % base; + cutoff /= base; + for ( ; ; c = *s++) { + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c -= 'A' - 10; + else if (c >= 'a' && c <= 'z') + c -= '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 ? INTMAX_MIN : INTMAX_MAX; + errno = ERANGE; + } else if (!any) { +noconv: + errno = EINVAL; + } else if (neg) + acc = -acc; + if (endptr != NULL) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/src/lib/libc/stdlib/strtol.c b/src/lib/libc/stdlib/strtol.c new file mode 100644 index 0000000..53a746e --- /dev/null +++ b/src/lib/libc/stdlib/strtol.c @@ -0,0 +1,144 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtol.c,v 1.19 2005/01/21 13:31:02 ache Exp $"); + +#include +#include +#include +#include + + +/* + * Convert a string to a long integer. + * + * Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +long +strtol(const char * __restrict nptr, char ** __restrict endptr, int base) +{ + const char *s; + unsigned long acc; + char c; + unsigned long cutoff; + 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((unsigned char)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') && + ((s[1] >= '0' && s[1] <= '9') || + (s[1] >= 'A' && s[1] <= 'F') || + (s[1] >= 'a' && s[1] <= 'f'))) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + acc = any = 0; + if (base < 2 || base > 36) + goto noconv; + + /* + * 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) + LONG_MAX + : LONG_MAX; + cutlim = cutoff % base; + cutoff /= base; + for ( ; ; c = *s++) { + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c -= 'A' - 10; + else if (c >= 'a' && c <= 'z') + c -= '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 (!any) { +noconv: + errno = EINVAL; + } else if (neg) + acc = -acc; + if (endptr != NULL) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/src/lib/libc/stdlib/strtoll.c b/src/lib/libc/stdlib/strtoll.c new file mode 100644 index 0000000..a24f6f8 --- /dev/null +++ b/src/lib/libc/stdlib/strtoll.c @@ -0,0 +1,144 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtoll.c,v 1.21 2005/01/21 13:31:02 ache Exp $"); + +#include +#include +#include +#include + +/* + * Convert a string to a long long integer. + * + * Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +long long +strtoll(const char * __restrict nptr, char ** __restrict endptr, int base) +{ + const char *s; + unsigned long long acc; + char c; + unsigned long long cutoff; + 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((unsigned char)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') && + ((s[1] >= '0' && s[1] <= '9') || + (s[1] >= 'A' && s[1] <= 'F') || + (s[1] >= 'a' && s[1] <= 'f'))) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + acc = any = 0; + if (base < 2 || base > 36) + goto noconv; + + /* + * 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. + */ + cutoff = neg ? (unsigned long long)-(LLONG_MIN + LLONG_MAX) + LLONG_MAX + : LLONG_MAX; + cutlim = cutoff % base; + cutoff /= base; + for ( ; ; c = *s++) { + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c -= 'A' - 10; + else if (c >= 'a' && c <= 'z') + c -= '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 ? LLONG_MIN : LLONG_MAX; + errno = ERANGE; + } else if (!any) { +noconv: + errno = EINVAL; + } else if (neg) + acc = -acc; + if (endptr != NULL) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/src/lib/libc/stdlib/strtonum.c b/src/lib/libc/stdlib/strtonum.c new file mode 100644 index 0000000..b99345c --- /dev/null +++ b/src/lib/libc/stdlib/strtonum.c @@ -0,0 +1,68 @@ +/*- + * Copyright (c) 2004 Ted Unangst and Todd Miller + * All rights reserved. + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + * + * $OpenBSD: strtonum.c,v 1.6 2004/08/03 19:38:01 millert Exp $ + */ + +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtonum.c,v 1.2.2.1 2006/04/04 19:56:46 andre Exp $"); + +#include +#include +#include + +#define INVALID 1 +#define TOOSMALL 2 +#define TOOLARGE 3 + +long long +strtonum(const char *numstr, long long minval, long long maxval, + const char **errstrp) +{ + long long ll = 0; + char *ep; + int error = 0; + struct errval { + const char *errstr; + int err; + } ev[4] = { + { NULL, 0 }, + { "invalid", EINVAL }, + { "too small", ERANGE }, + { "too large", ERANGE }, + }; + + ev[0].err = errno; + errno = 0; + if (minval > maxval) + error = INVALID; + else { + ll = strtoll(numstr, &ep, 10); + if (errno == EINVAL || numstr == ep || *ep != '\0') + error = INVALID; + else if ((ll == LLONG_MIN && errno == ERANGE) || ll < minval) + error = TOOSMALL; + else if ((ll == LLONG_MAX && errno == ERANGE) || ll > maxval) + error = TOOLARGE; + } + if (errstrp != NULL) + *errstrp = ev[error].errstr; + errno = ev[error].err; + if (error) + ll = 0; + + return (ll); +} diff --git a/src/lib/libc/stdlib/strtoq.c b/src/lib/libc/stdlib/strtoq.c new file mode 100644 index 0000000..6e8bcb8 --- /dev/null +++ b/src/lib/libc/stdlib/strtoq.c @@ -0,0 +1,52 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtoq.c,v 1.11 2002/08/15 09:25:04 robert Exp $"); + +#include + +#include + +/* + * Convert a string to a quad integer. + */ +quad_t +strtoq(const char *nptr, char **endptr, int base) +{ + + return strtoll(nptr, endptr, base); +} diff --git a/src/lib/libc/stdlib/strtoul.c b/src/lib/libc/stdlib/strtoul.c new file mode 100644 index 0000000..13deb32 --- /dev/null +++ b/src/lib/libc/stdlib/strtoul.c @@ -0,0 +1,122 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtoul.c,v 1.18 2005/01/21 13:31:02 ache Exp $"); + +#include +#include +#include +#include + +/* + * Convert a string to an unsigned long integer. + * + * Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +unsigned long +strtoul(const char * __restrict nptr, char ** __restrict endptr, int base) +{ + const char *s; + unsigned long acc; + char c; + unsigned long cutoff; + int neg, any, cutlim; + + /* + * See strtol for comments as to the logic used. + */ + s = nptr; + do { + c = *s++; + } while (isspace((unsigned char)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') && + ((s[1] >= '0' && s[1] <= '9') || + (s[1] >= 'A' && s[1] <= 'F') || + (s[1] >= 'a' && s[1] <= 'f'))) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + acc = any = 0; + if (base < 2 || base > 36) + goto noconv; + + cutoff = ULONG_MAX / base; + cutlim = ULONG_MAX % base; + for ( ; ; c = *s++) { + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c -= 'A' - 10; + else if (c >= 'a' && c <= 'z') + c -= '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 (!any) { +noconv: + errno = EINVAL; + } else if (neg) + acc = -acc; + if (endptr != NULL) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/src/lib/libc/stdlib/strtoull.c b/src/lib/libc/stdlib/strtoull.c new file mode 100644 index 0000000..51c08a0 --- /dev/null +++ b/src/lib/libc/stdlib/strtoull.c @@ -0,0 +1,122 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtoull.c,v 1.20 2005/01/21 13:31:02 ache Exp $"); + +#include +#include +#include +#include + +/* + * Convert a string to an unsigned long long integer. + * + * Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +unsigned long long +strtoull(const char * __restrict nptr, char ** __restrict endptr, int base) +{ + const char *s; + unsigned long long acc; + char c; + unsigned long long cutoff; + int neg, any, cutlim; + + /* + * See strtoq for comments as to the logic used. + */ + s = nptr; + do { + c = *s++; + } while (isspace((unsigned char)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') && + ((s[1] >= '0' && s[1] <= '9') || + (s[1] >= 'A' && s[1] <= 'F') || + (s[1] >= 'a' && s[1] <= 'f'))) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + acc = any = 0; + if (base < 2 || base > 36) + goto noconv; + + cutoff = ULLONG_MAX / base; + cutlim = ULLONG_MAX % base; + for ( ; ; c = *s++) { + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c -= 'A' - 10; + else if (c >= 'a' && c <= 'z') + c -= '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 = ULLONG_MAX; + errno = ERANGE; + } else if (!any) { +noconv: + errno = EINVAL; + } else if (neg) + acc = -acc; + if (endptr != NULL) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/src/lib/libc/stdlib/strtoumax.c b/src/lib/libc/stdlib/strtoumax.c new file mode 100644 index 0000000..442b281 --- /dev/null +++ b/src/lib/libc/stdlib/strtoumax.c @@ -0,0 +1,122 @@ +/*- + * 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[] = "from @(#)strtoul.c 8.1 (Berkeley) 6/4/93"; +#endif /* LIBC_SCCS and not lint */ +#include +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtoumax.c,v 1.10 2005/01/21 13:31:02 ache Exp $"); + +#include +#include +#include +#include + +/* + * Convert a string to a uintmax_t integer. + * + * Assumes that the upper and lower case + * alphabets and digits are each contiguous. + */ +uintmax_t +strtoumax(const char * __restrict nptr, char ** __restrict endptr, int base) +{ + const char *s; + uintmax_t acc; + char c; + uintmax_t cutoff; + int neg, any, cutlim; + + /* + * See strtoimax for comments as to the logic used. + */ + s = nptr; + do { + c = *s++; + } while (isspace((unsigned char)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') && + ((s[1] >= '0' && s[1] <= '9') || + (s[1] >= 'A' && s[1] <= 'F') || + (s[1] >= 'a' && s[1] <= 'f'))) { + c = s[1]; + s += 2; + base = 16; + } + if (base == 0) + base = c == '0' ? 8 : 10; + acc = any = 0; + if (base < 2 || base > 36) + goto noconv; + + cutoff = UINTMAX_MAX / base; + cutlim = UINTMAX_MAX % base; + for ( ; ; c = *s++) { + if (c >= '0' && c <= '9') + c -= '0'; + else if (c >= 'A' && c <= 'Z') + c -= 'A' - 10; + else if (c >= 'a' && c <= 'z') + c -= '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 = UINTMAX_MAX; + errno = ERANGE; + } else if (!any) { +noconv: + errno = EINVAL; + } else if (neg) + acc = -acc; + if (endptr != NULL) + *endptr = (char *)(any ? s - 1 : nptr); + return (acc); +} diff --git a/src/lib/libc/stdlib/strtouq.c b/src/lib/libc/stdlib/strtouq.c new file mode 100644 index 0000000..c0e0bef --- /dev/null +++ b/src/lib/libc/stdlib/strtouq.c @@ -0,0 +1,52 @@ +/*- + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/strtouq.c,v 1.11 2002/08/15 09:25:04 robert Exp $"); + +#include + +#include + +/* + * Convert a string to an unsigned quad integer. + */ +u_quad_t +strtouq(const char *nptr, char **endptr, int base) +{ + + return strtoull(nptr, endptr, base); +} diff --git a/src/lib/libc/stdlib/system.c b/src/lib/libc/stdlib/system.c new file mode 100644 index 0000000..fd2cc2a --- /dev/null +++ b/src/lib/libc/stdlib/system.c @@ -0,0 +1,102 @@ +/* + * 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 +__FBSDID("$FreeBSD: src/lib/libc/stdlib/system.c,v 1.10 2002/03/22 21:53:10 obrien Exp $"); + +#include "namespace.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include "un-namespace.h" +#include "libc_private.h" + +int +__system(command) + const char *command; +{ + pid_t pid, savedpid; + int pstat; + struct sigaction ign, intact, quitact; + sigset_t newsigblock, oldsigblock; + + if (!command) /* just checking... */ + return(1); + + /* + * Ignore SIGINT and SIGQUIT, block SIGCHLD. Remember to save + * existing signal dispositions. + */ + ign.sa_handler = SIG_IGN; + (void)sigemptyset(&ign.sa_mask); + ign.sa_flags = 0; + (void)_sigaction(SIGINT, &ign, &intact); + (void)_sigaction(SIGQUIT, &ign, &quitact); + (void)sigemptyset(&newsigblock); + (void)sigaddset(&newsigblock, SIGCHLD); + (void)_sigprocmask(SIG_BLOCK, &newsigblock, &oldsigblock); + switch(pid = fork()) { + case -1: /* error */ + break; + case 0: /* child */ + /* + * Restore original signal dispositions and exec the command. + */ + (void)_sigaction(SIGINT, &intact, NULL); + (void)_sigaction(SIGQUIT, &quitact, NULL); + (void)_sigprocmask(SIG_SETMASK, &oldsigblock, NULL); + execl(_PATH_BSHELL, "sh", "-c", command, (char *)NULL); + _exit(127); + default: /* parent */ + savedpid = pid; + do { + pid = _wait4(savedpid, &pstat, 0, (struct rusage *)0); + } while (pid == -1 && errno == EINTR); + break; + } + (void)_sigaction(SIGINT, &intact, NULL); + (void)_sigaction(SIGQUIT, &quitact, NULL); + (void)_sigprocmask(SIG_SETMASK, &oldsigblock, NULL); + return(pid == -1 ? -1 : pstat); +} + +__weak_reference(__system, system); +__weak_reference(__system, _system); diff --git a/src/lib/libc/stdlib/tdelete.c b/src/lib/libc/stdlib/tdelete.c new file mode 100644 index 0000000..7fb6893 --- /dev/null +++ b/src/lib/libc/stdlib/tdelete.c @@ -0,0 +1,71 @@ +/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +#include +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif +__FBSDID("$FreeBSD: src/lib/libc/stdlib/tdelete.c,v 1.6 2003/01/05 02:43:18 tjr Exp $"); + +#define _SEARCH_PRIVATE +#include +#include + + +/* + * delete node with given key + * + * vkey: key to be deleted + * vrootp: address of the root of the tree + * compar: function to carry out node comparisons + */ +void * +tdelete(const void * __restrict vkey, void ** __restrict vrootp, + int (*compar)(const void *, const void *)) +{ + node_t **rootp = (node_t **)vrootp; + node_t *p, *q, *r; + int cmp; + + if (rootp == NULL || (p = *rootp) == NULL) + return NULL; + + while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { + p = *rootp; + rootp = (cmp < 0) ? + &(*rootp)->llink : /* follow llink branch */ + &(*rootp)->rlink; /* follow rlink branch */ + if (*rootp == NULL) + return NULL; /* key not found */ + } + r = (*rootp)->rlink; /* D1: */ + if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ + q = r; + else if (r != NULL) { /* Right link is NULL? */ + if (r->llink == NULL) { /* D2: Find successor */ + r->llink = q; + q = r; + } else { /* D3: Find NULL link */ + for (q = r->llink; q->llink != NULL; q = r->llink) + r = q; + r->llink = q->rlink; + q->llink = (*rootp)->llink; + q->rlink = (*rootp)->rlink; + } + } + free(*rootp); /* D4: Free node */ + *rootp = q; /* link parent to new node */ + return p; +} diff --git a/src/lib/libc/stdlib/tfind.c b/src/lib/libc/stdlib/tfind.c new file mode 100644 index 0000000..b58ed88 --- /dev/null +++ b/src/lib/libc/stdlib/tfind.c @@ -0,0 +1,48 @@ +/* $NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +#include +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: tfind.c,v 1.2 1999/09/16 11:45:37 lukem Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif +__FBSDID("$FreeBSD: src/lib/libc/stdlib/tfind.c,v 1.5 2003/01/05 02:43:18 tjr Exp $"); + +#define _SEARCH_PRIVATE +#include +#include + +/* find a node, or return 0 */ +void * +tfind(vkey, vrootp, compar) + const void *vkey; /* key to be found */ + void * const *vrootp; /* address of the tree root */ + int (*compar)(const void *, const void *); +{ + node_t **rootp = (node_t **)vrootp; + + if (rootp == NULL) + return NULL; + + while (*rootp != NULL) { /* T1: */ + int r; + + if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ + return *rootp; /* key found */ + rootp = (r < 0) ? + &(*rootp)->llink : /* T3: follow left branch */ + &(*rootp)->rlink; /* T4: follow right branch */ + } + return NULL; +} diff --git a/src/lib/libc/stdlib/tsearch.c b/src/lib/libc/stdlib/tsearch.c new file mode 100644 index 0000000..edeccde --- /dev/null +++ b/src/lib/libc/stdlib/tsearch.c @@ -0,0 +1,58 @@ +/* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +#include +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif +__FBSDID("$FreeBSD: src/lib/libc/stdlib/tsearch.c,v 1.4 2003/01/05 02:43:18 tjr Exp $"); + +#define _SEARCH_PRIVATE +#include +#include + +/* find or insert datum into search tree */ +void * +tsearch(vkey, vrootp, compar) + const void *vkey; /* key to be located */ + void **vrootp; /* address of tree root */ + int (*compar)(const void *, const void *); +{ + node_t *q; + node_t **rootp = (node_t **)vrootp; + + if (rootp == NULL) + return NULL; + + while (*rootp != NULL) { /* Knuth's T1: */ + int r; + + if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ + return *rootp; /* we found it! */ + + rootp = (r < 0) ? + &(*rootp)->llink : /* T3: follow left branch */ + &(*rootp)->rlink; /* T4: follow right branch */ + } + + q = malloc(sizeof(node_t)); /* T5: key not found */ + if (q != 0) { /* make new node */ + *rootp = q; /* link new node to old */ + /* LINTED const castaway ok */ + q->key = (void *)vkey; /* initialize new node */ + q->llink = q->rlink = NULL; + } + return q; +} diff --git a/src/lib/libc/stdlib/twalk.c b/src/lib/libc/stdlib/twalk.c new file mode 100644 index 0000000..516ef44 --- /dev/null +++ b/src/lib/libc/stdlib/twalk.c @@ -0,0 +1,58 @@ +/* $NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $ */ + +/* + * Tree search generalized from Knuth (6.2.2) Algorithm T just like + * the AT&T man page says. + * + * The node_t structure is for internal use only, lint doesn't grok it. + * + * Written by reading the System V Interface Definition, not the code. + * + * Totally public domain. + */ + +#include +#if 0 +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: twalk.c,v 1.1 1999/02/22 10:33:16 christos Exp $"); +#endif /* LIBC_SCCS and not lint */ +#endif +__FBSDID("$FreeBSD: src/lib/libc/stdlib/twalk.c,v 1.5 2003/01/05 02:43:18 tjr Exp $"); + +#define _SEARCH_PRIVATE +#include +#include + +static void trecurse(const node_t *, + void (*action)(const void *, VISIT, int), int level); + +/* Walk the nodes of a tree */ +static void +trecurse(root, action, level) + const node_t *root; /* Root of the tree to be walked */ + void (*action)(const void *, VISIT, int); + int level; +{ + + if (root->llink == NULL && root->rlink == NULL) + (*action)(root, leaf, level); + else { + (*action)(root, preorder, level); + if (root->llink != NULL) + trecurse(root->llink, action, level + 1); + (*action)(root, postorder, level); + if (root->rlink != NULL) + trecurse(root->rlink, action, level + 1); + (*action)(root, endorder, level); + } +} + +/* Walk the nodes of a tree */ +void +twalk(vroot, action) + const void *vroot; /* Root of the tree to be walked */ + void (*action)(const void *, VISIT, int); +{ + if (vroot != NULL && action != NULL) + trecurse(vroot, action, 0); +}