bsearch(3c) - osol9

1bsearch(3C)              Standard C Library Functions              bsearch(3C)
2
3
4

NAME

6       bsearch - binary search a sorted table
7

SYNOPSIS

9       #include <stdlib.h>
10
11       void *bsearch(const void *key, const void *base, size_t nel, size_t size,
12            int (*compar)(const void *,const void *));
13
14

DESCRIPTION

16       The  bsearch()  function  is  a  binary search routine generalized from
17       Knuth (6.2.1) Algorithm B. It returns a pointer into a table (an array)
18       indicating  where  a  datum may be found or a null pointer if the datum
19       cannot be found. The table must  be  previously  sorted  in  increasing
20       order according to a comparison function pointed to by compar.
21
22
23       The  key argument points to a datum instance to be sought in the table.
24       The base argument points to the element at the base of the table.   The
25       nel argument is the number of elements in the table.  The size argument
26       is the number of bytes in each element.
27
28
29       The comparison function pointed to by compar is called with  two  argu‐
30       ments  that  point  to  the key object and to an array element, in that
31       order. The function must return an integer  less  than,  equal  to,  or
32       greater  than  0  if  the key object is considered, respectively, to be
33       less than, equal to, or greater than the array element.
34

RETURN VALUES

36       The bsearch() function returns a pointer to a matching  member  of  the
37       array,  or a null pointer if no match is found.  If two or more members
38       compare equal, which member is returned is unspecified.
39

USAGE

41       The pointers to the key and the element at the base of the table should
42       be of type pointer-to-element.
43
44
45       The  comparison function need not compare every byte, so arbitrary data
46       may be contained in the elements in addition to the values  being  com‐
47       pared.
48
49
50       If  the  number of elements in the table is less than the size reserved
51       for the table, nel should be the lower number.
52
53
54       The bsearch() function safely  allows  concurrent  access  by  multiple
55       threads to disjoint data, such as overlapping subtrees or tables.
56

EXAMPLES

58       Example 1 Examples for searching a table containing pointers to nodes.
59
60
61       The  example  below  searches a table containing pointers to nodes con‐
62       sisting of a string and its length. The table is ordered alphabetically
63       on the string in the node pointed to by each entry.
64
65
66
67       This  program  reads in strings and either finds the corresponding node
68       and prints out the string and its length, or prints an error message.
69
70
71         #include <stdio.h>
72         #include <stdlib.h>
73         #include <string.h>
74         struct node {  /* these are stored in the table */
75             char *string;
76             int length;
77         };
78         static struct node table[] = {    /* table to be searched */
79             { "asparagus", 10 },
80             { "beans", 6 },
81             { "tomato", 7 },
82             { "watermelon", 11 },
83         };
84
85         main()
86         {
87             struct node *node_ptr, node;
88             /* routine to compare 2 nodes */
89             static int node_compare(const void *, const void *);
90             char str_space[20];   /* space to read string into */
91
92             node.string = str_space;
93             while (scanf("%20s", node.string) != EOF) {
94                 node_ptr = bsearch( &node,
95                     table, sizeof(table)/sizeof(struct node),
96                     sizeof(struct node), node_compare);
97                 if (node_ptr != NULL) {
98                     (void) printf("string = %20s, length = %d\n",
99                         node_ptr−>string, node_ptr−>length);
100                 } else {
101                     (void)printf("not found: %20s\n", node.string);
102                 }
103             }
104             return(0);
105         }
106
107         /* routine to compare two nodes based on an  */
108         /* alphabetical ordering of the string field */
109         static int
110         node_compare(const void *node1, const void *node2) {
111             return (strcmp(
112                     ((const struct node *)node1)−>string,
113                     ((const struct node *)node2)−>string));
114         }
115
116

ATTRIBUTES

118       See attributes(5) for descriptions of the following attributes:
119
120
121
122
123       ┌─────────────────────────────┬─────────────────────────────┐
124       │      ATTRIBUTE TYPE         │      ATTRIBUTE VALUE        │
125       ├─────────────────────────────┼─────────────────────────────┤
126       │Interface Stability          │Standard                     │
127       ├─────────────────────────────┼─────────────────────────────┤
128       │MT-Level                     │MT-Safe                      │
129       └─────────────────────────────┴─────────────────────────────┘
130