From 0674b9825d2b89985e4947e13f7ff95932dbab72 Mon Sep 17 00:00:00 2001 From: cheloha Date: Wed, 8 Dec 2021 22:06:28 +0000 Subject: [PATCH] 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@ --- lib/libc/hidden/search.h | 4 ++-- lib/libc/stdlib/lsearch.c | 45 +++++++++++---------------------------- 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 * @@ -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,27 +37,27 @@ #include 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; @@ -65,25 +65,6 @@ linear_base(const void *key, const void *base, size_t *nelp, size_t 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); -- 2.20.1