diff options
Diffstat (limited to 'man-pages-posix-2003/man3p/bsearch.3p')
| -rw-r--r-- | man-pages-posix-2003/man3p/bsearch.3p | 178 |
1 files changed, 178 insertions, 0 deletions
diff --git a/man-pages-posix-2003/man3p/bsearch.3p b/man-pages-posix-2003/man3p/bsearch.3p new file mode 100644 index 0000000..b9efcc0 --- /dev/null +++ b/man-pages-posix-2003/man3p/bsearch.3p @@ -0,0 +1,178 @@ +.\" Copyright (c) 2001-2003 The Open Group, All Rights Reserved +.TH "BSEARCH" 3P 2003 "IEEE/The Open Group" "POSIX Programmer's Manual" +.\" bsearch +.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 \- binary search a sorted table +.SH SYNOPSIS +.LP +\fB#include <stdlib.h> +.br +.sp +void *bsearch(const void *\fP\fIkey\fP\fB, const void *\fP\fIbase\fP\fB, +size_t\fP \fInel\fP\fB, +.br +\ \ \ \ \ \ size_t\fP \fIwidth\fP\fB, int (*\fP\fIcompar\fP\fB)(const +void *, const void *)); +.br +\fP +.SH DESCRIPTION +.LP +The \fIbsearch\fP() function shall search an array of \fInel\fP objects, +the initial element of which is pointed to by +\fIbase\fP, for an element that matches the object pointed to by \fIkey\fP. +The size of each element in the array is specified by +\fIwidth\fP. If the \fInel\fP argument has the value zero, the comparison +function pointed to by \fIcompar\fP shall not be +called and no match shall be found. +.LP +The comparison function pointed to by \fIcompar\fP shall be called +with two arguments that point to the \fIkey\fP object and +to an array element, in that order. +.LP +The application shall ensure that the comparison function pointed +to by \fIcompar\fP 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. +.LP +The implementation shall ensure that the first argument is always +a pointer to the key. +.LP +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. +.LP +The application shall ensure that the function returns an integer +less than, equal to, or greater than 0 if the \fIkey\fP +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 \fIkey\fP object, in that order. +.SH RETURN VALUE +.LP +The \fIbsearch\fP() 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 +.LP +No errors are defined. +.LP +\fIThe following sections are informative.\fP +.SH EXAMPLES +.LP +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. +.LP +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 +.nf + +\fB#include <stdio.h> +#include <stdlib.h> +#include <string.h> +.sp + +#define TABSIZE 1000 + +.sp + +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 *); + char str_space[20]; /* Space to read string into. */ + . + . + . + node.string = str_space; + while (scanf("%s", 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\\n", + node_ptr->string, node_ptr->length); + } else { + (void)printf("not found: %s\\n", 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); +} +\fP +.fi +.RE +.SH APPLICATION USAGE +.LP +The pointers to the key and the element at the base of the table should +be of type pointer-to-element. +.LP +The comparison function need not compare every byte, so arbitrary +data may be contained in the elements in addition to the +values being compared. +.LP +In practice, the array is usually sorted according to the comparison +function. +.SH RATIONALE +.LP +The requirement that the second argument (hereafter referred to as +\fIp\fP) 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 +.nf + +\fB((char *)p - (char *(base) % width == 0 +(char *)p >= (char *)base +(char *)p < (char *)base + nel * width +\fP +.fi +.RE +.SH FUTURE DIRECTIONS +.LP +None. +.SH SEE ALSO +.LP +\fIhcreate\fP(), \fIlsearch\fP(), \fIqsort\fP(), \fItsearch\fP(), +the Base Definitions volume of +IEEE\ Std\ 1003.1-2001, \fI<stdlib.h>\fP +.SH COPYRIGHT +Portions of this text are reprinted and reproduced in electronic form +from IEEE Std 1003.1, 2003 Edition, Standard for Information Technology +-- Portable Operating System Interface (POSIX), The Open Group Base +Specifications Issue 6, Copyright (C) 2001-2003 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 . |