diff options
| author | drochner <drochner@NetBSD.org> | 2005-07-06 14:43:24 +0000 |
|---|---|---|
| committer | drochner <drochner@NetBSD.org> | 2005-07-06 14:43:24 +0000 |
| commit | e866f2794bb798fa732f329e49161d9c83446011 (patch) | |
| tree | 99a14e485ec5b3ca18151a12df449c293d58e969 /lib/libc/stdlib | |
| parent | a5bc956f510fc939faff84d60404546c85a79360 (diff) | |
Move insque/remque/lsearch/lfind from libcompat to libc,
they are in XPG4-UNIX, XSH5.0, mentioned in SUSv3 etc.
Minimal update of the manpages. (more needed)
Diffstat (limited to 'lib/libc/stdlib')
| -rw-r--r-- | lib/libc/stdlib/Makefile.inc | 16 | ||||
| -rw-r--r-- | lib/libc/stdlib/insque.3 | 52 | ||||
| -rw-r--r-- | lib/libc/stdlib/insque.c | 57 | ||||
| -rw-r--r-- | lib/libc/stdlib/lsearch.3 | 98 | ||||
| -rw-r--r-- | lib/libc/stdlib/lsearch.c | 116 | ||||
| -rw-r--r-- | lib/libc/stdlib/remque.c | 52 |
6 files changed, 385 insertions, 6 deletions
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc index 94ecaaa1c50..d8626b6a47f 100644 --- a/lib/libc/stdlib/Makefile.inc +++ b/lib/libc/stdlib/Makefile.inc @@ -1,4 +1,4 @@ -# $NetBSD: Makefile.inc,v 1.58 2005/04/03 20:09:29 christos Exp $ +# $NetBSD: Makefile.inc,v 1.59 2005/07/06 14:43:24 drochner Exp $ # from: @(#)Makefile.inc 8.3 (Berkeley) 2/4/95 # stdlib sources @@ -8,11 +8,12 @@ SRCS+= _rand48.c _strtoimax.c _strtoumax.c _strtoll.c _strtoull.c \ a64l.c abort.c atexit.c atof.c atoi.c atol.c atoll.c \ bsearch.c calloc.c drand48.c erand48.c exit.c _Exit.c \ getenv.c getopt.c getopt_long.c getsubopt.c \ - hcreate.c heapsort.c jrand48.c \ - l64a.c lldiv.c lcong48.c lrand48.c malloc.c merge.c mrand48.c \ + hcreate.c heapsort.c insque.c jrand48.c \ + l64a.c lldiv.c lcong48.c lrand48.c lsearch.c \ + malloc.c merge.c mrand48.c \ nrand48.c putenv.c qabs.c qdiv.c qsort.c posix_openpt.c pty.c \ - radixsort.c rand.c rand_r.c random.c seed48.c setenv.c srand48.c \ - strsuftoll.c strtod.c \ + radixsort.c rand.c rand_r.c random.c remque.c \ + seed48.c setenv.c srand48.c strsuftoll.c strtod.c \ strtoimax.c strtol.c strtoll.c strtoq.c strtoul.c strtoull.c \ strtoumax.c strtouq.c system.c tdelete.c tfind.c tsearch.c twalk.c \ __unsetenv13.c unsetenv.c \ @@ -26,7 +27,8 @@ SRCS+= _rand48.c _strtoimax.c _strtoumax.c _strtoll.c _strtoull.c \ MAN+= a64l.3 abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 atoll.3 \ bsearch.3 div.3 exit.3 getenv.3 getopt.3 getopt_long.3 getsubopt.3 \ - grantpt.3 hcreate.3 labs.3 ldiv.3 llabs.3 lldiv.3 malloc.3 memory.3 \ + grantpt.3 hcreate.3 insque.3 labs.3 ldiv.3 llabs.3 lldiv.3 lsearch.3 \ + malloc.3 memory.3 \ posix_openpt.3 ptsname.3 qabs.3 \ qdiv.3 qsort.3 radixsort.3 rand48.3 rand.3 random.3 \ strsuftoll.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3 unlockpt.3 \ @@ -36,6 +38,8 @@ MLINKS+=a64l.3 l64a.3 MLINKS+=a64l.3 l64a_r.3 MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3 MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3 +MLINKS+=insque.3 remque.3 +MLINKS+=lsearch.3 lfind.3 MLINKS+=malloc.3 calloc.3 malloc.3 realloc.3 malloc.3 free.3 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 MLINKS+=rand.3 rand_r.3 diff --git a/lib/libc/stdlib/insque.3 b/lib/libc/stdlib/insque.3 new file mode 100644 index 00000000000..2e1f8b714c3 --- /dev/null +++ b/lib/libc/stdlib/insque.3 @@ -0,0 +1,52 @@ +.\" Copyright (c) 1993 John Brezak +.\" 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. The name of the author may 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. +.\" +.\" $NetBSD: insque.3,v 1.1 2005/07/06 14:43:24 drochner Exp $ +.\" +.Dd July 6, 2005 +.Dt INSQUE 3 +.Sh NAME +.Nm insque , +.Nm remque +.Nd insert/remove element from a queue +.Sh LIBRARY +.Lb libc +.Sh SYNOPSIS +.In search.h +.Ft void +.Fn insque "void *elem" "void *pred" +.Ft void +.Fn remque "void *elem" +.Sh DESCRIPTION +.Pp +.Fn insque +and +.Fn remque +manipulate queues built from doubly linked lists. +.Sh DIAGNOSTICS +These functions are not atomic unless that machine architecture allows it. +.Sh HISTORY +These are derived from the insque and remque instructions on a VAX. diff --git a/lib/libc/stdlib/insque.c b/lib/libc/stdlib/insque.c new file mode 100644 index 00000000000..7cbd26981bc --- /dev/null +++ b/lib/libc/stdlib/insque.c @@ -0,0 +1,57 @@ +/* + * Copyright (c) 1993 John Brezak + * 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. The name of the author may 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. + */ + +#include <sys/cdefs.h> +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: insque.c,v 1.1 2005/07/06 14:43:24 drochner Exp $"); +#endif /* LIBC_SCCS and not lint */ + +#include <assert.h> +#include <search.h> + +struct qelem { + struct qelem *q_forw; + struct qelem *q_back; +}; + +void +insque(entry, pred) + void *entry; + void *pred; +{ + struct qelem *e = (struct qelem *) entry; + struct qelem *p = (struct qelem *) pred; + + _DIAGASSERT(e != 0); + _DIAGASSERT(p != 0); + + e->q_forw = p->q_forw; + e->q_back = p; + p->q_forw->q_back = e; + p->q_forw = e; +} diff --git a/lib/libc/stdlib/lsearch.3 b/lib/libc/stdlib/lsearch.3 new file mode 100644 index 00000000000..42d4c981934 --- /dev/null +++ b/lib/libc/stdlib/lsearch.3 @@ -0,0 +1,98 @@ +.\" Copyright (c) 1989, 1991, 1993 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" 3. 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. +.\" +.\" from: @(#)lsearch.3 8.1 (Berkeley) 6/4/93 +.\" $NetBSD: lsearch.3,v 1.1 2005/07/06 14:43:24 drochner Exp $ +.\" +.Dd July 6, 2005 +.Dt LSEARCH 3 +.Os +.Sh NAME +.Nm lsearch , +.Nm lfind +.Nd linear searching routines +.Sh LIBRARY +.Lb libc +.Sh SYNOPSIS +.In search.h +.Ft char * +.Fn lsearch "const void *key" "const void *base" "size_t *nelp" "size_t width" "int (*compar)(const void *, const void *)" +.Ft char * +.Fn lfind "const void *key" "const void *base" "size_t *nelp" "size_t width" "int (*compar)(const void *, const void *)" +.Sh DESCRIPTION +.Pp +The functions +.Fn lsearch , +and +.Fn lfind +provide basic linear searching functionality. +.Pp +.Fa base +is the pointer to the beginning of an array. +The argument +.Fa nelp +is the current number of elements in the array, where each element +is +.Fa width +bytes long. +The +.Fa compar +function +is a comparison routine which is used to compare two elements. +It takes two arguments which point to the +.Fa key +object and to an array member, in that order, and must return an integer +less than, equivalent to, or greater than zero if the +.Fa key +object is considered, respectively, to be less than, equal to, or greater +than the array member. +.Pp +The +.Fn lsearch +and +.Fn lfind +functions +return a pointer into the array referenced by +.Fa base +where +.Fa key +is located. +If +.Fa key +does not exist, +.Fn lfind +will return a null pointer and +.Fn lsearch +will add it to the array. +When an element is added to the array by +.Fn lsearch +the location referenced by the argument +.Fa nelp +is incremented by one. +.Sh SEE ALSO +.Xr bsearch 3 , +.Xr db 3 diff --git a/lib/libc/stdlib/lsearch.c b/lib/libc/stdlib/lsearch.c new file mode 100644 index 00000000000..b895056e8f2 --- /dev/null +++ b/lib/libc/stdlib/lsearch.c @@ -0,0 +1,116 @@ +/* + * Copyright (c) 1989, 1993 + * The Regents of the University of California. All rights reserved. + * + * This code is derived from software contributed to Berkeley by + * Roger L. Snyder. + * + * 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 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 <sys/cdefs.h> +#if defined(LIBC_SCCS) && !defined(lint) +#if 0 +static char sccsid[] = "@(#)lsearch.c 8.1 (Berkeley) 6/4/93"; +#else +__RCSID("$NetBSD: lsearch.c,v 1.1 2005/07/06 14:43:24 drochner Exp $"); +#endif +#endif /* LIBC_SCCS and not lint */ + +#include <sys/types.h> + +#include <assert.h> +#include <errno.h> +#include <string.h> +#include <search.h> + +typedef int (*cmp_fn_t) __P((const void *, const void *)); +static void *linear_base __P((const void *, const void *, size_t *, size_t, + cmp_fn_t, int)); + +void * +lsearch(key, base, nelp, width, compar) + const void *key, *base; + size_t *nelp, width; + cmp_fn_t compar; +{ + + _DIAGASSERT(key != NULL); + _DIAGASSERT(base != NULL); + _DIAGASSERT(compar != NULL); + + return(linear_base(key, base, nelp, width, compar, 1)); +} + +void * +lfind(key, base, nelp, width, compar) + const void *key, *base; + size_t *nelp, width; + cmp_fn_t compar; +{ + + _DIAGASSERT(key != NULL); + _DIAGASSERT(base != NULL); + _DIAGASSERT(compar != NULL); + + return(linear_base(key, base, nelp, width, compar, 0)); +} + +static void * +linear_base(key, base, nelp, width, compar, add_flag) + const void *key, *base; + size_t *nelp, width; + cmp_fn_t compar; + int add_flag; +{ + char *element, *end; + + _DIAGASSERT(key != NULL); + _DIAGASSERT(base != NULL); + _DIAGASSERT(compar != NULL); + + /* LINTED const castaway */ + end = (char *)base + *nelp * width; + /* LINTED const castaway */ + for (element = (char *)base; element < end; element += width) + if (!compar(element, key)) /* key found */ + return element; + + if (!add_flag) /* key not found */ + return(NULL); + + /* + * The UNIX System User's Manual, 1986 edition claims that + * a NULL pointer is returned by lsearch with errno set + * appropriately, if there is not enough room in the table + * to add a new item. This can't be done as none of these + * routines have any method of determining the size of the + * table. This comment isn't in the 1986-87 System V + * manual. + */ + ++*nelp; + memcpy(end, key, width); + return end; +} diff --git a/lib/libc/stdlib/remque.c b/lib/libc/stdlib/remque.c new file mode 100644 index 00000000000..7d2f3eee994 --- /dev/null +++ b/lib/libc/stdlib/remque.c @@ -0,0 +1,52 @@ +/* + * Copyright (c) 1993 John Brezak + * 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. The name of the author may 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. + */ + +#include <sys/cdefs.h> +#if defined(LIBC_SCCS) && !defined(lint) +__RCSID("$NetBSD: remque.c,v 1.1 2005/07/06 14:43:24 drochner Exp $"); +#endif /* LIBC_SCCS and not lint */ + +#include <assert.h> +#include <search.h> + +struct qelem { + struct qelem *q_forw; + struct qelem *q_back; +}; + +void +remque(element) + void *element; +{ + struct qelem *e = (struct qelem *) element; + + _DIAGASSERT(e != 0); + + e->q_forw->q_back = e->q_back; + e->q_back->q_forw = e->q_forw; +} |
