- 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.

3 files changed, 165 insertions, 2 deletions

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);
+}