summaryrefslogtreecommitdiff
path: root/lib/libc/stdlib
diff options
context:
space:
mode:
authordrochner <drochner@NetBSD.org>2005-07-06 14:43:24 +0000
committerdrochner <drochner@NetBSD.org>2005-07-06 14:43:24 +0000
commite866f2794bb798fa732f329e49161d9c83446011 (patch)
tree99a14e485ec5b3ca18151a12df449c293d58e969 /lib/libc/stdlib
parenta5bc956f510fc939faff84d60404546c85a79360 (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.inc16
-rw-r--r--lib/libc/stdlib/insque.352
-rw-r--r--lib/libc/stdlib/insque.c57
-rw-r--r--lib/libc/stdlib/lsearch.398
-rw-r--r--lib/libc/stdlib/lsearch.c116
-rw-r--r--lib/libc/stdlib/remque.c52
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;
+}