lsearch(3): reimplement using lfind(3)

lsearch(3) is really just lfind(3) with an additional branch to append
the key if lfind(3) fails.  If we get rid of the underlying
linear_base() function and move the search portion into lfind(3) and
the key-copying portion into lsearch(3) we get smaller and simpler
code.

Misc. notes:

- We do not need to keep the historical comment about errno.  lsearch(3)
  is pure computation and does not set errno.  That's really all you
  need to know.  The specification reserves no errors, either.

- We are using lfind(3) internally now, so it switches from
  PROTO_DEPRECATED to PROTO_NORMAL in hidden/search.h and needs
  DEF_WEAK in stdlib/lsearch.c.

With advice from guenther@ on symbol housekeeping in libc.

Thread: https://marc.info/?l=openbsd-tech&m=163885187632449&w=2

ok millert@

2 files changed, 15 insertions, 34 deletions

diff --git a/lib/libc/hidden/search.h b/lib/libc/hidden/search.h
index 338bb1c21a5..5981a83e8a0 100644
--- a/lib/libc/hidden/search.h
+++ b/lib/libc/hidden/search.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: search.h,v 1.1 2015/10/04 08:36:57 guenther Exp $	*/
+/*	$OpenBSD: search.h,v 1.2 2021/12/08 22:06:28 cheloha Exp $	*/
 /*
  * Copyright (c) 2015 Philip Guenther <guenther@openbsd.org>
  *
@@ -24,7 +24,7 @@ PROTO_DEPRECATED(hcreate);
 PROTO_DEPRECATED(hdestroy);
 PROTO_DEPRECATED(hsearch);
 PROTO_DEPRECATED(insque);
-PROTO_DEPRECATED(lfind);
+PROTO_NORMAL(lfind);
 PROTO_DEPRECATED(lsearch);
 PROTO_DEPRECATED(remque);
 PROTO_DEPRECATED(tdelete);
diff --git a/lib/libc/stdlib/lsearch.c b/lib/libc/stdlib/lsearch.c
index 93e200e1bdb..95ebf49b819 100644
--- a/lib/libc/stdlib/lsearch.c
+++ b/lib/libc/stdlib/lsearch.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: lsearch.c,v 1.6 2021/12/07 04:01:45 cheloha Exp $	*/
+/*	$OpenBSD: lsearch.c,v 1.7 2021/12/08 22:06:28 cheloha Exp $	*/
 
 /*
  * Copyright (c) 1989, 1993
@@ -37,53 +37,34 @@
 #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, void *base, size_t *nelp, size_t width,
     	cmp_fn_t compar)
 {
+	void *element = lfind(key, base, nelp, width, compar);
 
-	return(linear_base(key, base, nelp, width, compar, 1));
+	/*
+	 * Use memmove(3) to ensure the key is copied cleanly into the
+	 * array, even if the key overlaps with the end of the array.
+	 */
+	if (element == NULL) {
+		element = memmove((char *)base + *nelp * width, key, width);
+		*nelp += 1;
+	}
+	return element;
 }
 
 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;
-
-	/*
-	 * Use memmove(3) to ensure the key is copied cleanly into the
-	 * array, even if the key overlaps with the end of the array.
-	 */
-	memmove((void *)end, key, width);
-	return((void *)end);
+	return NULL;
 }
+DEF_WEAK(lfind);