diff options
Diffstat (limited to 'lib/libc/stdlib/bsearch.3')
| -rw-r--r-- | lib/libc/stdlib/bsearch.3 | 156 |
1 files changed, 156 insertions, 0 deletions
diff --git a/lib/libc/stdlib/bsearch.3 b/lib/libc/stdlib/bsearch.3 new file mode 100644 index 000000000000..712be0f98381 --- /dev/null +++ b/lib/libc/stdlib/bsearch.3 @@ -0,0 +1,156 @@ +.\" Copyright (c) 1990, 1991, 1993, 1994 +.\" The Regents of the University of California. All rights reserved. +.\" +.\" This code is derived from software contributed to Berkeley by +.\" the American National Standards Committee X3, on Information +.\" Processing Systems. +.\" +.\" 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. 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. +.\" +.Dd July 17, 2019 +.Dt BSEARCH 3 +.Os +.Sh NAME +.Nm bsearch +.Nd binary search of a sorted table +.Sh LIBRARY +.Lb libc +.Sh SYNOPSIS +.In stdlib.h +.Ft void * +.Fn bsearch "const void *key" "const void *base" "size_t nmemb" "size_t size" "int (*compar) (const void *, const void *)" +.Sh DESCRIPTION +The +.Fn bsearch +function searches an array of +.Fa nmemb +objects, the initial member of which is +pointed to by +.Fa base , +for a member that matches the object pointed to by +.Fa key . +The size of each member of the array is specified by +.Fa size . +.Pp +The contents of the array should be in ascending sorted order according +to the comparison function referenced by +.Fa compar . +The +.Fa compar +routine +is expected to have +two arguments which point to the +.Fa key +object and to an array member, in that order, and should return an integer +less than, equal to, or greater than zero if the +.Fa key +object is found, respectively, to be less than, to match, or be +greater than the array member. +See the +.Fa int_compare +sample function in +.Xr qsort 3 +for a comparison function that is also compatible with +.Fn bsearch . +.Sh RETURN VALUES +The +.Fn bsearch +function returns a pointer to a matching member of the array, or a null +pointer if no match is found. +If two members compare as equal, which member is matched is unspecified. +.Sh EXAMPLES +A sample program that searches people by age in a sorted array: +.Bd -literal +#include <assert.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> + +struct person { + const char *name; + int age; +}; + +static int +compare(const void *a, const void *b) +{ + const int *age; + const struct person *person; + + age = a; + person = b; + + return (*age - person->age); +} + +int +main(void) +{ + struct person *friend; + int age; + /* Sorted array */ + const struct person friends[] = { + { "paul", 22 }, + { "anne", 25 }, + { "fred", 25 }, + { "mary", 27 }, + { "mark", 35 }, + { "bill", 50 } + }; + const size_t len = sizeof(friends) / sizeof(friends[0]); + + age = 22; + friend = bsearch(&age, friends, len, sizeof(friends[0]), compare); + assert(strcmp(friend->name, "paul") == 0); + printf("name: %s\enage: %d\en", friend->name, friend->age); + + age = 25; + friend = bsearch(&age, friends, len, sizeof(friends[0]), compare); + + /* + * For multiple elements with the same key, it is implementation + * defined which will be returned + */ + assert(strcmp(friend->name, "fred") == 0 || + strcmp(friend->name, "anne") == 0); + printf("name: %s\enage: %d\en", friend->name, friend->age); + + age = 30; + friend = bsearch(&age, friends, len, sizeof(friends[0]), compare); + assert(friend == NULL); + printf("friend aged 30 not found\en"); +} +.Ed +.Sh SEE ALSO +.Xr db 3 , +.Xr lsearch 3 , +.Xr qsort 3 +.\" .Xr tsearch 3 +.Sh STANDARDS +The +.Fn bsearch +function conforms to +.St -isoC . |