logo

oasis-root

Compiled tree of Oasis Linux based on own branch at <https://hacktivis.me/git/oasis/> git clone https://anongit.hacktivis.me/git/oasis-root.git

bsearch.3p (6177B)


  1. '\" et
  2. .TH BSEARCH "3P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual"
  3. .\"
  4. .SH PROLOG
  5. This manual page is part of the POSIX Programmer's Manual.
  6. The Linux implementation of this interface may differ (consult
  7. the corresponding Linux manual page for details of Linux behavior),
  8. or the interface may not be implemented on Linux.
  9. .\"
  10. .SH NAME
  11. bsearch
  12. \(em binary search a sorted table
  13. .SH SYNOPSIS
  14. .LP
  15. .nf
  16. #include <stdlib.h>
  17. .P
  18. void *bsearch(const void *\fIkey\fP, const void *\fIbase\fP, size_t \fInel\fP,
  19. size_t \fIwidth\fP, int (*\fIcompar\fP)(const void *, const void *));
  20. .fi
  21. .SH DESCRIPTION
  22. The functionality described on this reference page is aligned with the
  23. ISO\ C standard. Any conflict between the requirements described here and the
  24. ISO\ C standard is unintentional. This volume of POSIX.1\(hy2017 defers to the ISO\ C standard.
  25. .P
  26. The
  27. \fIbsearch\fR()
  28. function shall search an array of
  29. .IR nel
  30. objects, the initial element of which is pointed to by
  31. .IR base ,
  32. for an element that matches the object pointed to by
  33. .IR key .
  34. The size of each element in the array is specified by
  35. .IR width .
  36. If the
  37. .IR nel
  38. argument has the value zero, the comparison function pointed to by
  39. .IR compar
  40. shall not be called and no match shall be found.
  41. .P
  42. The comparison function pointed to by
  43. .IR compar
  44. shall be called with two arguments that point to the
  45. .IR key
  46. object and to an array element, in that order.
  47. .P
  48. The application shall ensure that the comparison function pointed to by
  49. .IR compar
  50. does not alter the contents of the array. The implementation may
  51. reorder elements of the array between calls to the comparison function,
  52. but shall not alter the contents of any individual element.
  53. .P
  54. The implementation shall ensure that the first argument is always a
  55. pointer to the key.
  56. .P
  57. When the same objects (consisting of width bytes, irrespective of their
  58. current positions in the array) are passed more than once to the
  59. comparison function, the results shall be consistent with one another.
  60. That is, the same object shall always compare the same way with the
  61. key.
  62. .P
  63. The application shall ensure that the function returns an integer less
  64. than, equal to, or greater than 0 if the
  65. .IR key
  66. object is considered, respectively, to be less than, to match, or to be
  67. greater than the array element. The application shall ensure that the
  68. array consists of all the elements that compare less than, all the
  69. elements that compare equal to, and all the elements that compare
  70. greater than the
  71. .IR key
  72. object, in that order.
  73. .SH "RETURN VALUE"
  74. The
  75. \fIbsearch\fR()
  76. function shall return a pointer to a matching member of the array, or a
  77. null pointer if no match is found. If two or more members compare
  78. equal, which member is returned is unspecified.
  79. .SH ERRORS
  80. No errors are defined.
  81. .LP
  82. .IR "The following sections are informative."
  83. .SH "EXAMPLES"
  84. The example below searches a table containing pointers to nodes
  85. consisting of a string and its length. The table is ordered
  86. alphabetically on the string in the node pointed to by each entry.
  87. .P
  88. The code fragment below reads in strings and either finds the
  89. corresponding node and prints out the string and its length, or prints
  90. an error message.
  91. .sp
  92. .RS 4
  93. .nf
  94. #include <stdio.h>
  95. #include <stdlib.h>
  96. #include <string.h>
  97. .P
  98. #define\ TABSIZE 1000
  99. .P
  100. struct node { /* These are stored in the table. */
  101. char *string;
  102. int length;
  103. };
  104. struct node table[TABSIZE]; /* Table to be searched. */
  105. .
  106. .
  107. .
  108. {
  109. struct node *node_ptr, node;
  110. /* Routine to compare 2 nodes. */
  111. int node_compare(const void *, const void *);
  112. .
  113. .
  114. .
  115. while (scanf("%ms", &node.string) != EOF) {
  116. node_ptr = (struct node *)bsearch((void *)(&node),
  117. (void *)table, TABSIZE,
  118. sizeof(struct node), node_compare);
  119. if (node_ptr != NULL) {
  120. (void)printf("string = %20s, length = %d\en",
  121. node_ptr->string, node_ptr->length);
  122. } else {
  123. (void)printf("not found: %s\en", node.string);
  124. }
  125. free(node.string);
  126. }
  127. }
  128. /*
  129. This routine compares two nodes based on an
  130. alphabetical ordering of the string field.
  131. */
  132. int
  133. node_compare(const void *node1, const void *node2)
  134. {
  135. return strcoll(((const struct node *)node1)->string,
  136. ((const struct node *)node2)->string);
  137. }
  138. .fi
  139. .P
  140. .RE
  141. .SH "APPLICATION USAGE"
  142. The pointers to the key and the element at the base of the table should
  143. be of type pointer-to-element.
  144. .P
  145. The comparison function need not compare every byte, so arbitrary data
  146. may be contained in the elements in addition to the values being
  147. compared.
  148. .P
  149. In practice, the array is usually sorted according to the comparison
  150. function.
  151. .SH RATIONALE
  152. The requirement that the second argument (hereafter referred to as
  153. .IR p )
  154. to the comparison function is a pointer to an element of the array
  155. implies that for every call all of the following expressions are
  156. non-zero:
  157. .sp
  158. .RS 4
  159. .nf
  160. ( (char *)p - (char *)base ) % width == 0
  161. (char *)p >= (char *)base
  162. (char *)p < (char *)base + nel * width
  163. .fi
  164. .P
  165. .RE
  166. .SH "FUTURE DIRECTIONS"
  167. None.
  168. .SH "SEE ALSO"
  169. .IR "\fIhcreate\fR\^(\|)",
  170. .IR "\fIlsearch\fR\^(\|)",
  171. .IR "\fIqsort\fR\^(\|)",
  172. .IR "\fItdelete\fR\^(\|)"
  173. .P
  174. The Base Definitions volume of POSIX.1\(hy2017,
  175. .IR "\fB<stdlib.h>\fP"
  176. .\"
  177. .SH COPYRIGHT
  178. Portions of this text are reprinted and reproduced in electronic form
  179. from IEEE Std 1003.1-2017, Standard for Information Technology
  180. -- Portable Operating System Interface (POSIX), The Open Group Base
  181. Specifications Issue 7, 2018 Edition,
  182. Copyright (C) 2018 by the Institute of
  183. Electrical and Electronics Engineers, Inc and The Open Group.
  184. In the event of any discrepancy between this version and the original IEEE and
  185. The Open Group Standard, the original IEEE and The Open Group Standard
  186. is the referee document. The original Standard can be obtained online at
  187. http://www.opengroup.org/unix/online.html .
  188. .PP
  189. Any typographical or formatting errors that appear
  190. in this page are most likely
  191. to have been introduced during the conversion of the source files to
  192. man page format. To report such errors, see
  193. https://www.kernel.org/doc/man-pages/reporting_bugs.html .