Decorate definitions with info about header file and source.
[kopensolaris-gnu/glibc.git] / manual / search.texi
1 @node Searching and Sorting
2 @chapter Searching and Sorting 
3
4 This chapter describes functions for searching and sorting arrays of
5 arbitrary objects.  You pass the appropriate comparison function to be
6 applied as an argument, along with the size of the objects in the array
7 and the total number of elements.  The return value from the comparison
8 function should follow the same conventions as the @code{strcmp}
9 function; @pxref{String/Array Comparison}.
10
11 @menu
12 * Array Search Function::               The @code{bsearch} function.
13 * Array Sort Function::                 The @code{qsort} function.
14 * Searching and Sorting Example::       An example program.
15 @end menu
16
17 @node Array Search Function
18 @section Array Search Function
19
20 To search a sorted array for an element matching the key, use the
21 @code{bsearch} function.  The prototype for this function is in
22 the header file @file{<stdlib.h>}.
23
24 @comment stdlib.h
25 @comment ANSI
26 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
27 The @code{bsearch} function searches the sorted array @var{array} for an object
28 that is equivalent to @var{key}.  The array contains @var{count} elements,
29 each of which is of size @var{size}.
30
31 The @var{compare} function is used to perform the comparison.  This
32 function is called with two pointer arguments and should return an
33 integer less than, equal to, or greater than zero corresponding to
34 whether its first argument is considered less than, equal to, or greater
35 than its second argument.  The elements of the @var{array} must already
36 be sorted in ascending order according to this comparison function.
37
38 The return value is a pointer to the matching array element, or a null
39 pointer if no match is found.  If the array contains more than one element
40 that matches, the one that is returned is unspecified.
41
42 Although the specific algorithm used by this function is not specified,
43 traditionally a binary search algorithm has been used; hence the name of
44 the function.
45 @end deftypefun
46
47 @node Array Sort Function
48 @section Array Sort Function
49
50 To sort an array using an arbitrary comparison function, use the
51 @code{qsort} function.  The prototype for this function is in
52 @file{<stdlib.h>}.
53
54 @comment stdlib.h
55 @comment ANSI
56 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, int (*@var{compare}) (const void *, const void *))
57 The @var{qsort} function sorts the array @var{array}.  The array contains
58 @var{count} elements, each of which is of size @var{size}.
59
60 The @var{compare} function is used to compare perform the comparison on
61 the array elements.  This function is called with two pointer arguments
62 and should return an integer less than, equal to, or greater than zero
63 corresponding to whether its first argument is considered less than,
64 equal to, or greater than its second argument.  If two objects compare
65 as equal, their order in the sorted array is unspecified.
66
67 Although the specific algorithm used by this function is not specified,
68 traditionally a quick sort algorithm has been used; hence the name of
69 the function.
70 @end deftypefun
71
72
73 @node Searching and Sorting Example
74 @section Searching and Sorting Example
75
76 Here is an example showing the use of @code{qsort} and @code{bsearch}
77 with an array of @code{struct}s.  The objects in the array are sorted
78 by comparing their @code{name} fields with the @code{strcmp} function.
79 Then, we can look up individual objects based on their names.
80
81 @comment This example is dedicated to the memory of Jim Henson.  RIP.
82 @example
83 #include <stdlib.h>
84 #include <stdio.h>
85 #include <string.h>
86
87 /* @r{Define an array of critters to sort.} */
88
89 struct critter @{
90   char *name;
91   char *species;
92   @};
93
94 struct critter muppets[] = @{@{"Kermit", "frog"@},
95                             @{"Piggy", "pig"@},
96                             @{"Gonzo", "whatever"@},
97                             @{"Fozzie", "bear"@},
98                             @{"Sam", "eagle"@},
99                             @{"Robin", "frog"@},
100                             @{"Animal", "animal"@},
101                             @{"Camilla", "chicken"@},
102                             @{"Sweetums", "monster"@},
103                             @{"Dr. Strangepork", "pig"@},
104                             @{"Link Hogthrob", "pig"@},
105                             @{"Zoot", "human"@},
106                             @{"Dr. Bunsen Honeydew", "human"@},
107                             @{"Beaker", "human"@},
108                             @{"Swedish Chef", "human"@}@};
109
110 int count = sizeof(muppets) / sizeof(struct critter);
111
112
113
114 /* @r{This is the comparison function used for sorting and searching.} */
115
116 int critter_cmp (const struct critter *c1, const struct critter *c2)
117 @{
118   return strcmp (c1->name, c2->name);
119 @}
120
121
122 /* @r{Print information about a critter.} */
123
124 void print_critter (const struct critter *c)
125 @{
126   printf ("%s, the %s\n", c->name, c->species);
127 @}
128
129
130 /* @r{Do the lookup into the sorted array.} */
131
132 void find_critter (char *name)
133 @{
134   struct critter target, *result;
135   target.name = name;
136   result = bsearch (&target, muppets, count, sizeof(struct critter),
137                     critter_cmp);
138   if (result)
139     print_critter (result);
140   else
141     printf ("Couldn't find %s.\n", name);
142 @}
143
144
145 /* @r{Main program.} */
146
147 void main (void)
148 @{
149   int i;
150   
151   qsort (muppets, count, sizeof(struct critter), critter_cmp);
152
153   for (i=0; i<count; i++)
154     print_critter (&muppets[i]);
155   printf ("\n");
156
157   find_critter ("Kermit");
158   find_critter ("Gonzo");
159   find_critter ("Janice");
160 @}  
161 @end example
162
163 The output from this program looks like:
164
165 @example
166 Animal, the animal
167 Beaker, the human
168 Camilla, the chicken
169 Dr. Bunsen Honeydew, the human
170 Dr. Strangepork, the pig
171 Fozzie, the bear
172 Gonzo, the whatever
173 Kermit, the frog
174 Link Hogthrob, the pig
175 Piggy, the pig
176 Robin, the frog
177 Sam, the eagle
178 Swedish Chef, the human
179 Sweetums, the monster
180 Zoot, the human
181
182
183 Kermit, the frog
184 Gonzo, the whatever
185 Couldn't find Janice.
186 @end example
187
188