- Remove the lsearch() and lfind() functions and their manpage from

   the compatibility library libcompat.
 - Add new implementations of lsearch() and lfind() which conform to
   IEEE Std 1003.1-2001 to libc.  Add a new manual page for them and
   add them to the makefile.
 - Add function prototypes for lsearch() and lfind() to the search.h
   header.

7 files changed, 171 insertions, 205 deletions

diff --git a/include/search.h b/include/search.h
index 566aac8..4e4606f 100644
--- a/include/search.h
+++ b/include/search.h
@@ -50,6 +50,10 @@ int	 hcreate(size_t);
 void	 hdestroy(void);
 ENTRY	*hsearch(ENTRY, ACTION);
 void	 insque(void *, void *);
+void	*lfind(const void *, const void *, size_t *, size_t,
+	    int (*)(const void *, const void *));
+void	*lsearch(const void *, void *, size_t *, size_t,
+	    int (*)(const void *, const void *));
 void	 remque(void *);
 void	*tdelete(const void * __restrict, void ** __restrict,
 	    int (*)(const void *, const void *));
diff --git a/lib/libc/stdlib/Makefile.inc b/lib/libc/stdlib/Makefile.inc
index b04c2da..a21e4c4 100644
--- a/lib/libc/stdlib/Makefile.inc
+++ b/lib/libc/stdlib/Makefile.inc
@@ -7,7 +7,7 @@
 MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
 	bsearch.c calloc.c div.c exit.c getenv.c getopt.c getopt_long.c \
 	getsubopt.c hcreate.c heapsort.c imaxabs.c imaxdiv.c insque.c \
-	labs.c ldiv.c llabs.c lldiv.c malloc.c merge.c putenv.c \
+	labs.c ldiv.c llabs.c lldiv.c lsearch.c malloc.c merge.c putenv.c \
 	qsort.c qsort_r.c radixsort.c rand.c random.c reallocf.c realpath.c \
 	remque.c setenv.c strfmon.c strhash.c strtod.c strtoimax.c strtol.c \
 	strtoll.c strtoq.c strtoul.c strtoull.c strtoumax.c strtouq.c \
@@ -22,7 +22,7 @@ MISRCS+=_Exit.c abort.c abs.c atexit.c atof.c atoi.c atol.c atoll.c \
 MAN+=	abort.3 abs.3 alloca.3 atexit.3 atof.3 atoi.3 atol.3 bsearch.3 \
 	div.3 exit.3 getenv.3 getopt.3 getopt_long.3 getsubopt.3 hcreate.3 \
 	imaxabs.3 imaxdiv.3 insque.3 labs.3 ldiv.3 llabs.3 lldiv.3 \
-	malloc.3 memory.3 qsort.3 radixsort.3 rand.3 random.3 \
+	lsearch.3 malloc.3 memory.3 qsort.3 radixsort.3 rand.3 random.3 \
 	realpath.3 strfmon.3 strtod.3 strtol.3 strtoul.3 system.3 tsearch.3
 
 MLINKS+=atol.3 atoll.3
@@ -30,6 +30,7 @@ MLINKS+=exit.3 _Exit.3
 MLINKS+=getenv.3 putenv.3 getenv.3 setenv.3 getenv.3 unsetenv.3
 MLINKS+=hcreate.3 hdestroy.3 hcreate.3 hsearch.3
 MLINKS+=insque.3 remque.3
+MLINKS+=lsearch.3 lfind.3
 MLINKS+=qsort.3 heapsort.3 qsort.3 mergesort.3 qsort.3 qsort_r.3
 MLINKS+=rand.3 rand_r.3 rand.3 srand.3 rand.3 sranddev.3
 MLINKS+=random.3 initstate.3 random.3 setstate.3 random.3 srandom.3 \
diff --git a/lib/libc/stdlib/lsearch.3 b/lib/libc/stdlib/lsearch.3
new file mode 100644
index 0000000..a53dcb1
--- /dev/null
+++ b/lib/libc/stdlib/lsearch.3
@@ -0,0 +1,98 @@
+.\"
+.\" 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. 
+.\"
+.\" $FreeBSD$
+.\"
+.Dd October 11, 2002
+.Dt LSEARCH 3
+.Os
+.Sh NAME
+.Nm lsearch ,
+.Nm lfind
+.Nd linear search and append
+.Sh LIBRARY
+.Lb libc
+.Sh SYNOPSIS
+.In search.h
+.Ft void *
+.Fn lsearch "const void *key" "void *base" "size_t *nelp" "size_t width" \
+    "int (*compar)(const void *, const void *)"
+.Ft void *
+.Fn lfind "const void *key" "const void *base" "size_t *nelp" "size_t width" \
+    "int (*compar)(const void *, const void *)"
+.Sh DESCRIPTION
+.Pp
+The
+.Fn lsearch
+and
+.Fn lfind
+functions walk linearly through an array and compare each element with
+the one to be sought using a supplied comparison function.
+.Pp
+.Fa key
+points to an element that matches the one that is searched.
+The array's address in memory is denoted by the 
+.Fa base
+argument.
+The width of one element (i.e. the size as returned by
+.Fn sizeof )
+is passed as the   
+.Fa width 
+argument.
+The number of valid elements contained in the array (not the number of
+elements the array has space reserved for) is given in the integer pointed
+to by
+.Fa nelp .
+The
+.Fa compar
+argument points to a function which compares its two arguments and returns
+zero if they are matching and non-zero otherwise.
+.Pp
+If no matching element was found in the array, 
+.Fn lsearch 
+copies
+.Fa key
+into the position after the last element and increments the
+integer pointed to by
+.Fa nelp .
+.Sh RETURN VALUES
+.Fn lsearch
+and
+.Fn lfind
+return a pointer to the first element found.
+If no element was found,
+.Fn lsearch
+returns a pointer to the newly added element, whereas
+.Fn lfind
+returns
+.Dv NULL .
+Both functions return
+.Dv NULL
+if an error occurs.
+.Sh SEE ALSO
+.Xr bsearch 3 ,
+.Xr hsearch 3 ,
+.Xr tsearch 3
+.Sh HISTORY
+The
+.Fn lsearch
+and
+.Fn lfind
+functions appeared in
+.Bx 4.2 .
+In
+.Fx 5.0 ,
+they reappeared conforming to
+.St -p1003.1-2001 .
+.Sh STANDARDS
+The
+.Fn lsearch
+and
+.Fn lfind
+functions conform to
+.St -p1003.1-2001 .
diff --git a/lib/libc/stdlib/lsearch.c b/lib/libc/stdlib/lsearch.c
new file mode 100644
index 0000000..e4d1dd5
--- /dev/null
+++ b/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 <sys/types.h>
+#include <sys/cdefs.h>
+__FBSDID("$FreeBSD$");
+
+#define	_SEARCH_PRIVATE
+#include <search.h>
+#include <stdint.h>	/* for uint8_t */
+#include <stdlib.h>	/* for NULL */
+#include <string.h>	/* 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/lib/libcompat/4.3/lsearch.3 b/lib/libcompat/4.3/lsearch.3
deleted file mode 100644
index 3863ce1..0000000
--- a/lib/libcompat/4.3/lsearch.3
+++ /dev/null
@@ -1,105 +0,0 @@
-.\" 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
-.\" $FreeBSD$
-.\"
-.Dd June 4, 1993
-.Dt LSEARCH 3
-.Os
-.Sh NAME
-.Nm lsearch ,
-.Nm lfind
-.Nd linear searching routines
-.Sh LIBRARY
-.Lb libcompat
-.Sh SYNOPSIS
-.In sys/types.h
-.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
-.Bf -symbolic
-This interface was obsolete before it was written.
-.Ef
-.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/libcompat/4.3/lsearch.c b/lib/libcompat/4.3/lsearch.c
deleted file mode 100644
index 3d46715..0000000
--- a/lib/libcompat/4.3/lsearch.c
+++ /dev/null
@@ -1,95 +0,0 @@
-/*
- * 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/cdefs.h>
-__FBSDID("$FreeBSD$");
-
-#include <sys/types.h>
-#include <unistd.h>
-#include <string.h>
-
-static char *linear_base();
-
-char *
-lsearch(key, base, nelp, width, compar)
-	char *key, *base;
-	u_int *nelp, width;
-	int (*compar)();
-{
-	return(linear_base(key, base, nelp, width, compar, 1));
-}
-
-char *
-lfind(key, base, nelp, width, compar)
-	char *key, *base;
-	u_int *nelp, width;
-	int (*compar)();
-{
-	return(linear_base(key, base, nelp, width, compar, 0));
-}
-
-static char *
-linear_base(key, base, nelp, width, compar, add_flag)
-	char *key, *base;
-	u_int *nelp, width;
-	int (*compar)(), add_flag;
-{
-	char *element, *end;
-
-	end = base + *nelp * width;
-	for (element = 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 was isn't in the 1986-87 System V
-	 * manual.
-	 */
-	++*nelp;
-	bcopy(key, end, (int)width);
-	return(end);
-}
diff --git a/lib/libcompat/Makefile b/lib/libcompat/Makefile
index bd1dd9e..17abf90 100644
--- a/lib/libcompat/Makefile
+++ b/lib/libcompat/Makefile
@@ -23,15 +23,14 @@ MLINKS+=cftime.3 ascftime.3
 
 # compat 4.3 sources
 # XXX MISSING:	ecvt.c gcvt.c sibuf.c sobuf.c strout.c
-SRCS+=	cfree.c lsearch.c regex.c rexec.c
+SRCS+=	cfree.c regex.c rexec.c
 
 # XXX MISSING:	ecvt.0
-MAN+=	4.3/cfree.3 4.3/lsearch.3 4.3/re_comp.3 4.3/rexec.3
+MAN+=	4.3/cfree.3 4.3/re_comp.3 4.3/rexec.3
 
 # XXX MISSING:	ecvt.3, so can't MLINK
 #MLINKS+=ecvt.3 fcvt.3 ecvt.3 gcvt.3
 MLINKS+=re_comp.3 re_exec.3
-MLINKS+=lsearch.3 lfind.3
 
 # compat 4.4 sources
 SRCS+=	cuserid.c