diff options
Diffstat (limited to 'man-pages-posix-2017/man3p/bsearch.3p')
| -rw-r--r-- | man-pages-posix-2017/man3p/bsearch.3p | 195 |
1 files changed, 195 insertions, 0 deletions
diff --git a/man-pages-posix-2017/man3p/bsearch.3p b/man-pages-posix-2017/man3p/bsearch.3p new file mode 100644 index 0000000..2232654 --- /dev/null +++ b/man-pages-posix-2017/man3p/bsearch.3p @@ -0,0 +1,195 @@ +'\" et +.TH BSEARCH "3P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual" +.\" +.SH PROLOG +This manual page is part of the POSIX Programmer's Manual. +The Linux implementation of this interface may differ (consult +the corresponding Linux manual page for details of Linux behavior), +or the interface may not be implemented on Linux. +.\" +.SH NAME +bsearch +\(em binary search a sorted table +.SH SYNOPSIS +.LP +.nf +#include <stdlib.h> +.P +void *bsearch(const void *\fIkey\fP, const void *\fIbase\fP, size_t \fInel\fP, + size_t \fIwidth\fP, int (*\fIcompar\fP)(const void *, const void *)); +.fi +.SH DESCRIPTION +The functionality described on this reference page is aligned with the +ISO\ C standard. Any conflict between the requirements described here and the +ISO\ C standard is unintentional. This volume of POSIX.1\(hy2017 defers to the ISO\ C standard. +.P +The +\fIbsearch\fR() +function shall search an array of +.IR nel +objects, the initial element of which is pointed to by +.IR base , +for an element that matches the object pointed to by +.IR key . +The size of each element in the array is specified by +.IR width . +If the +.IR nel +argument has the value zero, the comparison function pointed to by +.IR compar +shall not be called and no match shall be found. +.P +The comparison function pointed to by +.IR compar +shall be called with two arguments that point to the +.IR key +object and to an array element, in that order. +.P +The application shall ensure that the comparison function pointed to by +.IR compar +does not alter the contents of the array. The implementation may +reorder elements of the array between calls to the comparison function, +but shall not alter the contents of any individual element. +.P +The implementation shall ensure that the first argument is always a +pointer to the key. +.P +When the same objects (consisting of width bytes, irrespective of their +current positions in the array) are passed more than once to the +comparison function, the results shall be consistent with one another. +That is, the same object shall always compare the same way with the +key. +.P +The application shall ensure that the function returns an integer less +than, equal to, or greater than 0 if the +.IR key +object is considered, respectively, to be less than, to match, or to be +greater than the array element. The application shall ensure that the +array consists of all the elements that compare less than, all the +elements that compare equal to, and all the elements that compare +greater than the +.IR key +object, in that order. +.SH "RETURN VALUE" +The +\fIbsearch\fR() +function shall return a pointer to a matching member of the array, or a +null pointer if no match is found. If two or more members compare +equal, which member is returned is unspecified. +.SH ERRORS +No errors are defined. +.LP +.IR "The following sections are informative." +.SH "EXAMPLES" +The example below searches a table containing pointers to nodes +consisting of a string and its length. The table is ordered +alphabetically on the string in the node pointed to by each entry. +.P +The code fragment below reads in strings and either finds the +corresponding node and prints out the string and its length, or prints +an error message. +.sp +.RS 4 +.nf + +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +.P +#define\ TABSIZE 1000 +.P +struct node { /* These are stored in the table. */ + char *string; + int length; +}; +struct node table[TABSIZE]; /* Table to be searched. */ + . + . + . +{ + struct node *node_ptr, node; + /* Routine to compare 2 nodes. */ + int node_compare(const void *, const void *); + . + . + . + while (scanf("%ms", &node.string) != EOF) { + node_ptr = (struct node *)bsearch((void *)(&node), + (void *)table, TABSIZE, + sizeof(struct node), node_compare); + if (node_ptr != NULL) { + (void)printf("string = %20s, length = %d\en", + node_ptr->string, node_ptr->length); + } else { + (void)printf("not found: %s\en", node.string); + } + free(node.string); + } +} +/* + This routine compares two nodes based on an + alphabetical ordering of the string field. +*/ +int +node_compare(const void *node1, const void *node2) +{ + return strcoll(((const struct node *)node1)->string, + ((const struct node *)node2)->string); +} +.fi +.P +.RE +.SH "APPLICATION USAGE" +The pointers to the key and the element at the base of the table should +be of type pointer-to-element. +.P +The comparison function need not compare every byte, so arbitrary data +may be contained in the elements in addition to the values being +compared. +.P +In practice, the array is usually sorted according to the comparison +function. +.SH RATIONALE +The requirement that the second argument (hereafter referred to as +.IR p ) +to the comparison function is a pointer to an element of the array +implies that for every call all of the following expressions are +non-zero: +.sp +.RS 4 +.nf + +( (char *)p - (char *)base ) % width == 0 +(char *)p >= (char *)base +(char *)p < (char *)base + nel * width +.fi +.P +.RE +.SH "FUTURE DIRECTIONS" +None. +.SH "SEE ALSO" +.IR "\fIhcreate\fR\^(\|)", +.IR "\fIlsearch\fR\^(\|)", +.IR "\fIqsort\fR\^(\|)", +.IR "\fItdelete\fR\^(\|)" +.P +The Base Definitions volume of POSIX.1\(hy2017, +.IR "\fB<stdlib.h>\fP" +.\" +.SH COPYRIGHT +Portions of this text are reprinted and reproduced in electronic form +from IEEE Std 1003.1-2017, Standard for Information Technology +-- Portable Operating System Interface (POSIX), The Open Group Base +Specifications Issue 7, 2018 Edition, +Copyright (C) 2018 by the Institute of +Electrical and Electronics Engineers, Inc and The Open Group. +In the event of any discrepancy between this version and the original IEEE and +The Open Group Standard, the original IEEE and The Open Group Standard +is the referee document. The original Standard can be obtained online at +http://www.opengroup.org/unix/online.html . +.PP +Any typographical or formatting errors that appear +in this page are most likely +to have been introduced during the conversion of the source files to +man page format. To report such errors, see +https://www.kernel.org/doc/man-pages/reporting_bugs.html . |