(_hurd_sig_post): __sig_post renamed to __msg_sig_post.
[kopensolaris-gnu/glibc.git] / manual / search.texi
1 @node Searching and Sorting, Pattern Matching, Locales, Top
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.
8
9 @menu
10 * Comparison Functions::        Defining how to compare two objects.
11                                  Since the sort and search facilities
12                                  are general, you have to specify the
13                                  ordering. 
14 * Array Search Function::       The @code{bsearch} function.
15 * Array Sort Function::         The @code{qsort} function.
16 * Search/Sort Example::         An example program.
17 @end menu
18
19 @node Comparison Functions, Array Search Function,  , Searching and Sorting
20 @section Defining the Comparison Function
21 @cindex Comparison Function
22
23 In order to use the sorted array library functions, you have to describe
24 how to compare the elements of the array.
25
26 To do this, you supply a comparison function to compare two elements of
27 the array.  The library will call this function, passing as arguments
28 pointers to two array elements to be compared.  Your comparison function
29 should return a value the way @code{strcmp} (@pxref{String/Array
30 Comparison}) does: negative if the first argument is ``less'' than the
31 second, zero if they are ``equal'', and positive if the first argument
32 is ``greater''.
33
34 Here is an example of a comparison function which works with an array of
35 numbers of type @code{double}:
36
37 @smallexample
38 int
39 compare_doubles (const double *a, const double *b)
40 @{
41   return (int) (*a - *b);
42 @}
43 @end smallexample
44
45 The header file @file{stdlib.h} defines a name for the data type of
46 comparison functions.  This type is a GNU extension.
47
48 @comment stdlib.h
49 @comment GNU
50 @tindex comparison_fn_t
51 @smallexample
52 int comparison_fn_t (const void *, const void *);
53 @end smallexample
54
55 @node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting
56 @section Array Search Function
57 @cindex search function (for arrays)
58 @cindex binary search function (for arrays)
59 @cindex array search function
60
61 To search a sorted array for an element matching the key, use the
62 @code{bsearch} function.  The prototype for this function is in
63 the header file @file{stdlib.h}.
64 @pindex stdlib.h
65
66 @comment stdlib.h
67 @comment ANSI
68 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
69 The @code{bsearch} function searches the sorted array @var{array} for an object
70 that is equivalent to @var{key}.  The array contains @var{count} elements,
71 each of which is of size @var{size} bytes.  
72
73 The @var{compare} function is used to perform the comparison.  This
74 function is called with two pointer arguments and should return an
75 integer less than, equal to, or greater than zero corresponding to
76 whether its first argument is considered less than, equal to, or greater
77 than its second argument.  The elements of the @var{array} must already
78 be sorted in ascending order according to this comparison function.
79
80 The return value is a pointer to the matching array element, or a null
81 pointer if no match is found.  If the array contains more than one element
82 that matches, the one that is returned is unspecified.
83
84 This function derives its name from the fact that it is implemented
85 using the binary search algorithm.
86 @end deftypefun
87
88 @node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting
89 @section Array Sort Function
90 @cindex sort function (for arrays)
91 @cindex quick sort function (for arrays)
92 @cindex array sort function
93
94 To sort an array using an arbitrary comparison function, use the
95 @code{qsort} function.  The prototype for this function is in
96 @file{stdlib.h}.
97 @pindex stdlib.h
98
99 @comment stdlib.h
100 @comment ANSI
101 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
102 The @var{qsort} function sorts the array @var{array}.  The array contains
103 @var{count} elements, each of which is of size @var{size}.
104
105 The @var{compare} function is used to perform the comparison on the
106 array elements.  This function is called with two pointer arguments and
107 should return an integer less than, equal to, or greater than zero
108 corresponding to whether its first argument is considered less than,
109 equal to, or greater than its second argument.
110
111 @cindex stable sorting
112 @strong{Warning:} If two objects compare as equal, their order after
113 sorting is unpredictable.  That is to say, the sorting is not stable.
114 This can make a difference when the comparison considers only part of
115 the elements.  Two elements with the same sort key may differ in other
116 respects.
117
118 If you want the effect of a stable sort, you can get this result by
119 writing the comparison function so that, lacking other reason
120 distinguish between two elements, it compares them by their addresses.
121 Note that doing this may make the sorting algorithm less efficient, so
122 do it only if necessary.
123
124 Here is a simple example of sorting an array of doubles in numerical
125 order, using the comparison function defined above (@pxref{Comparison
126 Functions}):
127
128 @smallexample
129 @{
130   double *array;
131   int size;
132   @dots{}
133   qsort (array, size, sizeof (double), compare_doubles);
134 @}
135 @end smallexample
136
137 The @code{qsort} function derives its name from the fact that it was
138 originally implemented using the ``quick sort'' algorithm.
139 @end deftypefun
140
141 @node Search/Sort Example,  , Array Sort Function, Searching and Sorting
142 @section Searching and Sorting Example
143
144 Here is an example showing the use of @code{qsort} and @code{bsearch}
145 with an array of structures.  The objects in the array are sorted
146 by comparing their @code{name} fields with the @code{strcmp} function.
147 Then, we can look up individual objects based on their names.
148
149 @comment This example is dedicated to the memory of Jim Henson.  RIP.
150 @smallexample
151 @include search.c.texi
152 @end smallexample
153
154 @cindex Kermit the frog
155 The output from this program looks like:
156
157 @smallexample
158 Kermit, the frog
159 Piggy, the pig
160 Gonzo, the whatever
161 Fozzie, the bear
162 Sam, the eagle
163 Robin, the frog
164 Animal, the animal
165 Camilla, the chicken
166 Sweetums, the monster
167 Dr. Strangepork, the pig
168 Link Hogthrob, the pig
169 Zoot, the human
170 Dr. Bunsen Honeydew, the human
171 Beaker, the human
172 Swedish Chef, the human
173
174 Animal, the animal
175 Beaker, the human
176 Camilla, the chicken
177 Dr. Bunsen Honeydew, the human
178 Dr. Strangepork, the pig
179 Fozzie, the bear
180 Gonzo, the whatever
181 Kermit, the frog
182 Link Hogthrob, the pig
183 Piggy, the pig
184 Robin, the frog
185 Sam, the eagle
186 Swedish Chef, the human
187 Sweetums, the monster
188 Zoot, the human
189
190 Kermit, the frog
191 Gonzo, the whatever
192 Couldn't find Janice.
193 @end smallexample
194
195