move lsearch(3) and insque(3) from libcompat -> libc; they are now POSIX

3 files changed, 205 insertions, 7 deletions

diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index 98c13c8c8e6..d2034982fe2 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -5,10 +5,10 @@
 
 SRCS+=	a64l.c abort.c atexit.c atoi.c atof.c atol.c atoll.c bsearch.c \
 	calloc.c cfree.c exit.c ecvt.c gcvt.c getenv.c getopt.c getopt_long.c \
-	getsubopt.c heapsort.c l64a.c malloc.c merge.c multibyte.c putenv.c \
-	qsort.c radixsort.c rand.c random.c realpath.c setenv.c strtod.c \
-	strtol.c strtoll.c strtoul.c strtoull.c system.c tfind.c tsearch.c \
-	_rand48.c drand48.c erand48.c jrand48.c lcong48.c lrand48.c \
+	getsubopt.c heapsort.c l64a.c lsearch.c malloc.c merge.c multibyte.c \
+	putenv.c qsort.c radixsort.c rand.c random.c realpath.c setenv.c \
+	strtod.c strtol.c strtoll.c strtoul.c strtoull.c system.c tfind.c \
+	tsearch.c _rand48.c drand48.c erand48.c jrand48.c lcong48.c lrand48.c \
 	mrand48.c nrand48.c seed48.c srand48.c qabs.c qdiv.c
 
 .if   (${MACHINE_ARCH} == "m68k")
@@ -34,13 +34,14 @@ SRCS+=	abs.c div.c labs.c ldiv.c
 
 MAN+=	a64l.3 abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 atoll.3 \
 	bsearch.3 div.3 ecvt.3 exit.3 getenv.3 getopt.3 getopt_long.3 \
-	getsubopt.3 labs.3 ldiv.3 malloc.3 memory.3 qabs.3 qdiv.3 qsort.3 \
-	radixsort.3 rand48.3 rand.3 random.3 realpath.3 strtod.3 strtol.3 \
-	strtoul.3 system.3 tsearch.3
+	getsubopt.3 labs.3 ldiv.3 lsearch.3 malloc.3 memory.3 qabs.3 qdiv.3 \
+	qsort.3 radixsort.3 rand48.3 rand.3 random.3 realpath.3 strtod.3 \
+	strtol.3 strtoul.3 system.3 tsearch.3
 
 MLINKS+=ecvt.3 fcvt.3 ecvt.3 gcvt.3
 MLINKS+=getenv.3 setenv.3 getenv.3 unsetenv.3 getenv.3 putenv.3
 MLINKS+=getopt_long.3 getopt_long_only.3
+MLINKS+=lsearch.3 lfind.3
 MLINKS+=malloc.3 free.3 malloc.3 realloc.3 malloc.3 calloc.3
 MLINKS+=malloc.3 cfree.3 malloc.3 malloc.conf.5
 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3
diff --git a/lib/libc/stdlib/lsearch.3 b/lib/libc/stdlib/lsearch.3
new file mode 100644
index 00000000000..3e17d131e45
--- /dev/null
+++ b/lib/libc/stdlib/lsearch.3
@@ -0,0 +1,107 @@
+.\" 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. 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.
+.\"
+.\"     @(#)lsearch.3	8.1 (Berkeley) 6/4/93
+.\"
+.Dd June 4, 1993
+.Dt LSEARCH 3
+.Os
+.Sh NAME
+.Nm lsearch ,
+.Nm lfind
+.Nd linear searching routines
+.Sh SYNOPSIS
+.Ft char *
+.Fn lsearch "const void *key" "const void *base" "size_t *nelp" "size_t width" "int (*compar)(void *, void *)"
+.Ft char *
+.Fn lfind "const void *key" "const void *base" "size_t *nelp" "size_t width" "int (*compar)(void *, void *)"
+.Sh DESCRIPTION
+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
+.Sh STANDARDS
+The
+.Fn lsearch
+and
+.Fn lfind
+functions conform to the
+.St -p1003.1-01
+and
+.St -xpg4.3 .
+specifications.
diff --git a/lib/libc/stdlib/lsearch.c b/lib/libc/stdlib/lsearch.c
new file mode 100644
index 00000000000..ba0aad3cfcb
--- /dev/null
+++ b/lib/libc/stdlib/lsearch.c
@@ -0,0 +1,90 @@
+/*
+ * 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. 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[] = "@(#)lsearch.c	8.1 (Berkeley) 6/4/93";
+#endif /* LIBC_SCCS and not lint */
+
+#include <sys/types.h>
+#include <string.h>
+#include <search.h>
+
+typedef int (*cmp_fn_t)(const void *, const void *);
+static void *linear_base(const void *, const void *, size_t *, size_t,
+    cmp_fn_t, int);
+
+void *
+lsearch(const void *key, const void *base, size_t *nelp, size_t width,
+    	cmp_fn_t compar)
+{
+
+	return(linear_base(key, base, nelp, width, compar, 1));
+}
+
+void *
+lfind(const void *key, const void *base, size_t *nelp, size_t width,
+	cmp_fn_t compar)
+{
+	return(linear_base(key, base, nelp, width, compar, 0));
+}
+
+static void *
+linear_base(const void *key, const void *base, size_t *nelp, size_t width,
+	cmp_fn_t compar, int add_flag)
+{
+	const char *element, *end;
+
+	end = (const char *)base + *nelp * width;
+	for (element = base; element < end; element += width)
+		if (!compar(key, element))		/* key found */
+			return((void *)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((void *)end, key, width);
+	return((void *)end);
+}