Fix typos.
[kopensolaris-gnu/glibc.git] / manual / search.texi
1 @node Searching and Sorting, Pattern Matching, Message Translation, Top
2 @c %MENU% General searching and sorting functions
3 @chapter Searching and Sorting
4
5 This chapter describes functions for searching and sorting arrays of
6 arbitrary objects.  You pass the appropriate comparison function to be
7 applied as an argument, along with the size of the objects in the array
8 and the total number of elements.
9
10 @menu
11 * Comparison Functions::        Defining how to compare two objects.
12                                  Since the sort and search facilities
13                                  are general, you have to specify the
14                                  ordering.
15 * Array Search Function::       The @code{bsearch} function.
16 * Array Sort Function::         The @code{qsort} function.
17 * Search/Sort Example::         An example program.
18 * Hash Search Function::        The @code{hsearch} function.
19 * Tree Search Function::        The @code{tsearch} function.
20 @end menu
21
22 @node Comparison Functions
23 @section Defining the Comparison Function
24 @cindex Comparison Function
25
26 In order to use the sorted array library functions, you have to describe
27 how to compare the elements of the array.
28
29 To do this, you supply a comparison function to compare two elements of
30 the array.  The library will call this function, passing as arguments
31 pointers to two array elements to be compared.  Your comparison function
32 should return a value the way @code{strcmp} (@pxref{String/Array
33 Comparison}) does: negative if the first argument is ``less'' than the
34 second, zero if they are ``equal'', and positive if the first argument
35 is ``greater''.
36
37 Here is an example of a comparison function which works with an array of
38 numbers of type @code{double}:
39
40 @smallexample
41 int
42 compare_doubles (const void *a, const void *b)
43 @{
44   const double *da = (const double *) a;
45   const double *db = (const double *) b;
46
47   return (*da > *db) - (*da < *db);
48 @}
49 @end smallexample
50
51 The header file @file{stdlib.h} defines a name for the data type of
52 comparison functions.  This type is a GNU extension.
53
54 @comment stdlib.h
55 @comment GNU
56 @tindex comparison_fn_t
57 @smallexample
58 int comparison_fn_t (const void *, const void *);
59 @end smallexample
60
61 @node Array Search Function
62 @section Array Search Function
63 @cindex search function (for arrays)
64 @cindex binary search function (for arrays)
65 @cindex array search function
66
67 Generally searching for a specific element in an array means that
68 potentially all elements must be checked.  The GNU C library contains
69 functions to perform linear search.  The prototypes for the following
70 two functions can be found in @file{search.h}.
71
72 @comment search.h
73 @comment SVID
74 @deftypefun {void *} lfind (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
75 The @code{lfind} function searches in the array with @code{*@var{nmemb}}
76 elements of @var{size} bytes pointed to by @var{base} for an element
77 which matches the one pointed to by @var{key}.  The function pointed to
78 by @var{compar} is used decide whether two elements match.
79
80 The return value is a pointer to the matching element in the array
81 starting at @var{base} if it is found.  If no matching element is
82 available @code{NULL} is returned.
83
84 The mean runtime of this function is @code{*@var{nmemb}}/2.  This
85 function should only be used elements often get added to or deleted from
86 the array in which case it might not be useful to sort the array before
87 searching.
88 @end deftypefun
89
90 @comment search.h
91 @comment SVID
92 @deftypefun {void *} lsearch (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
93 The @code{lsearch} function is similar to the @code{lfind} function.  It
94 searches the given array for an element and returns it if found.  The
95 difference is that if no matching element is found the @code{lsearch}
96 function adds the object pointed to by @var{key} (with a size of
97 @var{size} bytes) at the end of the array and it increments the value of
98 @code{*@var{nmemb}} to reflect this addition.
99
100 This means for the caller that if it is not sure that the array contains
101 the element one is searching for the memory allocated for the array
102 starting at @var{base} must have room for at least @var{size} more
103 bytes.  If one is sure the element is in the array it is better to use
104 @code{lfind} so having more room in the array is always necessary when
105 calling @code{lsearch}.
106 @end deftypefun
107
108 To search a sorted array for an element matching the key, use the
109 @code{bsearch} function.  The prototype for this function is in
110 the header file @file{stdlib.h}.
111 @pindex stdlib.h
112
113 @comment stdlib.h
114 @comment ISO
115 @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
116 The @code{bsearch} function searches the sorted array @var{array} for an object
117 that is equivalent to @var{key}.  The array contains @var{count} elements,
118 each of which is of size @var{size} bytes.
119
120 The @var{compare} function is used to perform the comparison.  This
121 function is called with two pointer arguments and should return an
122 integer less than, equal to, or greater than zero corresponding to
123 whether its first argument is considered less than, equal to, or greater
124 than its second argument.  The elements of the @var{array} must already
125 be sorted in ascending order according to this comparison function.
126
127 The return value is a pointer to the matching array element, or a null
128 pointer if no match is found.  If the array contains more than one element
129 that matches, the one that is returned is unspecified.
130
131 This function derives its name from the fact that it is implemented
132 using the binary search algorithm.
133 @end deftypefun
134
135 @node Array Sort Function
136 @section Array Sort Function
137 @cindex sort function (for arrays)
138 @cindex quick sort function (for arrays)
139 @cindex array sort function
140
141 To sort an array using an arbitrary comparison function, use the
142 @code{qsort} function.  The prototype for this function is in
143 @file{stdlib.h}.
144 @pindex stdlib.h
145
146 @comment stdlib.h
147 @comment ISO
148 @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
149 The @var{qsort} function sorts the array @var{array}.  The array contains
150 @var{count} elements, each of which is of size @var{size}.
151
152 The @var{compare} function is used to perform the comparison on the
153 array elements.  This function is called with two pointer arguments and
154 should return an integer less than, equal to, or greater than zero
155 corresponding to whether its first argument is considered less than,
156 equal to, or greater than its second argument.
157
158 @cindex stable sorting
159 @strong{Warning:} If two objects compare as equal, their order after
160 sorting is unpredictable.  That is to say, the sorting is not stable.
161 This can make a difference when the comparison considers only part of
162 the elements.  Two elements with the same sort key may differ in other
163 respects.
164
165 If you want the effect of a stable sort, you can get this result by
166 writing the comparison function so that, lacking other reason
167 distinguish between two elements, it compares them by their addresses.
168 Note that doing this may make the sorting algorithm less efficient, so
169 do it only if necessary.
170
171 Here is a simple example of sorting an array of doubles in numerical
172 order, using the comparison function defined above (@pxref{Comparison
173 Functions}):
174
175 @smallexample
176 @{
177   double *array;
178   int size;
179   @dots{}
180   qsort (array, size, sizeof (double), compare_doubles);
181 @}
182 @end smallexample
183
184 The @code{qsort} function derives its name from the fact that it was
185 originally implemented using the ``quick sort'' algorithm.
186
187 The implementation of @code{qsort} in this library might not be an
188 in-place sort and might thereby use an extra amount of memory to store
189 the array.
190 @end deftypefun
191
192 @node Search/Sort Example
193 @section Searching and Sorting Example
194
195 Here is an example showing the use of @code{qsort} and @code{bsearch}
196 with an array of structures.  The objects in the array are sorted
197 by comparing their @code{name} fields with the @code{strcmp} function.
198 Then, we can look up individual objects based on their names.
199
200 @comment This example is dedicated to the memory of Jim Henson.  RIP.
201 @smallexample
202 @include search.c.texi
203 @end smallexample
204
205 @cindex Kermit the frog
206 The output from this program looks like:
207
208 @smallexample
209 Kermit, the frog
210 Piggy, the pig
211 Gonzo, the whatever
212 Fozzie, the bear
213 Sam, the eagle
214 Robin, the frog
215 Animal, the animal
216 Camilla, the chicken
217 Sweetums, the monster
218 Dr. Strangepork, the pig
219 Link Hogthrob, the pig
220 Zoot, the human
221 Dr. Bunsen Honeydew, the human
222 Beaker, the human
223 Swedish Chef, the human
224
225 Animal, the animal
226 Beaker, the human
227 Camilla, the chicken
228 Dr. Bunsen Honeydew, the human
229 Dr. Strangepork, the pig
230 Fozzie, the bear
231 Gonzo, the whatever
232 Kermit, the frog
233 Link Hogthrob, the pig
234 Piggy, the pig
235 Robin, the frog
236 Sam, the eagle
237 Swedish Chef, the human
238 Sweetums, the monster
239 Zoot, the human
240
241 Kermit, the frog
242 Gonzo, the whatever
243 Couldn't find Janice.
244 @end smallexample
245
246
247 @node Hash Search Function
248 @section The @code{hsearch} function.
249
250 The functions mentioned so far in this chapter are searching in a sorted
251 or unsorted array.  There are other methods to organize information
252 which later should be searched.  The costs of insert, delete and search
253 differ.  One possible implementation is using hashing tables.
254
255 @comment search.h
256 @comment SVID
257 @deftypefun int hcreate (size_t @var{nel})
258 The @code{hcreate} function creates a hashing table which can contain at
259 least @var{nel} elements.  There is no possibility to grow this table so
260 it is necessary to choose the value for @var{nel} wisely.  The used
261 methods to implement this function might make it necessary to make the
262 number of elements in the hashing table larger than the expected maximal
263 number of elements.  Hashing tables usually work inefficient if they are
264 filled 80% or more.  The constant access time guaranteed by hashing can
265 only be achieved if few collisions exist.  See Knuth's ``The Art of
266 Computer Programming, Part 3: Searching and Sorting'' for more
267 information.
268
269 The weakest aspect of this function is that there can be at most one
270 hashing table used through the whole program.  The table is allocated
271 in local memory out of control of the programmer.  As an extension the
272 GNU C library provides an additional set of functions with an reentrant
273 interface which provide a similar interface but which allow to keep
274 arbitrarily many hashing tables.
275
276 It is possible to use more than one hashing table in the program run if
277 the former table is first destroyed by a call to @code{hdestroy}.
278
279 The function returns a non-zero value if successful.  If it return zero
280 something went wrong.  This could either mean there is already a hashing
281 table in use or the program runs out of memory.
282 @end deftypefun
283
284 @comment search.h
285 @comment SVID
286 @deftypefun void hdestroy (void)
287 The @code{hdestroy} function can be used to free all the resources
288 allocated in a previous call of @code{hcreate}.  After a call to this
289 function it is again possible to call @code{hcreate} and allocate a new
290 table with possibly different size.
291
292 It is important to remember that the elements contained in the hashing
293 table at the time @code{hdestroy} is called are @emph{not} freed by this
294 function.  It is the responsibility of the program code to free those
295 strings (if necessary at all).  Freeing all the element memory is not
296 possible without extra, separately kept information since there is no
297 function to iterate through all available elements in the hashing table.
298 If it is really necessary to free a table and all elements the
299 programmer has to keep a list of all table elements and before calling
300 @code{hdestroy} s/he has to free all element's data using this list.
301 This is a very unpleasant mechanism and it also shows that this kind of
302 hashing tables is mainly meant for tables which are created once and
303 used until the end of the program run.
304 @end deftypefun
305
306 Entries of the hashing table and keys for the search are defined using
307 this type:
308
309 @deftp {Data type} {struct ENTRY}
310 Both elements of this structure are pointers to zero-terminated strings.
311 This is a limiting restriction of the functionality of the
312 @code{hsearch} functions.  They can only be used for data sets which use
313 the NUL character always and solely to terminate the records.  It is not
314 possible to handle general binary data.
315
316 @table @code
317 @item char *key
318 Pointer to a zero-terminated string of characters describing the key for
319 the search or the element in the hashing table.
320 @item char *data
321 Pointer to a zero-terminated string of characters describing the data.
322 If the functions will be called only for searching an existing entry
323 this element might stay undefined since it is not used.
324 @end table
325 @end deftp
326
327 @comment search.h
328 @comment SVID
329 @deftypefun {ENTRY *} hsearch (ENTRY @var{item}, ACTION @var{action})
330 To search in a hashing table created using @code{hcreate} the
331 @code{hsearch} function must be used.  This function can perform simple
332 search for an element (if @var{action} has the @code{FIND}) or it can
333 alternatively insert the key element into the hashing table, possibly
334 replacing a previous value (if @var{action} is @code{ENTER}).
335
336 The key is denoted by a pointer to an object of type @code{ENTRY}.  For
337 locating the corresponding position in the hashing table only the
338 @code{key} element of the structure is used.
339
340 The return value depends on the @var{action} parameter value.  If it is
341 @code{FIND} the value is a pointer to the matching element in the
342 hashing table or @code{NULL} if no matching element exists.  If
343 @var{action} is @code{ENTER} the return value is only @code{NULL} if the
344 programs runs out of memory while adding the new element to the table.
345 Otherwise the return value is a pointer to the element in the hashing
346 table which contains newly added element based on the data in @var{key}.
347 @end deftypefun
348
349 As mentioned before the hashing table used by the functions described so
350 far is global and there can be at any time at most one hashing table in
351 the program.  A solution is to use the following functions which are a
352 GNU extension.  All have in common that they operate on a hashing table
353 which is described by the content of an object of the type @code{struct
354 hsearch_data}.  This type should be treated as opaque, none of its
355 members should be changed directly.
356
357 @comment search.h
358 @comment GNU
359 @deftypefun int hcreate_r (size_t @var{nel}, struct hsearch_data *@var{htab})
360 The @code{hcreate_r} function initializes the object pointed to by
361 @var{htab} to contain a hashing table with at least @var{nel} elements.
362 So this function is equivalent to the @code{hcreate} function except
363 that the initialized data structure is controlled by the user.
364
365 This allows having more than one hashing table at one time.  The
366 memory necessary for the @code{struct hsearch_data} object can be
367 allocated dynamically.
368
369 The return value is non-zero if the operation were successful.  if the
370 return value is zero something went wrong which probably means the
371 programs runs out of memory.
372 @end deftypefun
373
374 @comment search.h
375 @comment GNU
376 @deftypefun void hdestroy_r (struct hsearch_data *@var{htab})
377 The @code{hdestroy_r} function frees all resources allocated by the
378 @code{hcreate_r} function for this very same object @var{htab}.  As for
379 @code{hdestroy} it is the programs responsibility to free the strings
380 for the elements of the table.
381 @end deftypefun
382
383 @comment search.h
384 @comment GNU
385 @deftypefun int hsearch_r (ENTRY @var{item}, ACTION @var{action}, ENTRY **@var{retval}, struct hsearch_data *@var{htab})
386 The @code{hsearch_r} function is equivalent to @code{hsearch}.  The
387 meaning of the first two arguments is identical.  But instead of
388 operating on a single global hashing table the function works on the
389 table described by the object pointed to by @var{htab} (which is
390 initialized by a call to @code{hcreate_r}).
391
392 Another difference to @code{hcreate} is that the pointer to the found
393 entry in the table is not the return value of the functions.  It is
394 returned by storing it in a pointer variables pointed to by the
395 @var{retval} parameter.  The return value of the function is an integer
396 value indicating success if it is non-zero and failure if it is zero.
397 In the latter case the global variable @var{errno} signals the reason for
398 the failure.
399
400 @table @code
401 @item ENOMEM
402 The table is filled and @code{hsearch_r} was called with an so far
403 unknown key and @var{action} set to @code{ENTER}.
404 @item ESRCH
405 The @var{action} parameter is @code{FIND} and no corresponding element
406 is found in the table.
407 @end table
408 @end deftypefun
409
410
411 @node Tree Search Function
412 @section The @code{tsearch} function.
413
414 Another common form to organize data for efficient search is to use
415 trees.  The @code{tsearch} function family provides a nice interface to
416 functions to organize possibly large amounts of data by providing a mean
417 access time proportional to the logarithm of the number of elements.
418 The GNU C library implementation even guarantees that this bound is
419 never exceeded even for input data which cause problems for simple
420 binary tree implementations.
421
422 The functions described in the chapter are all described in the @w{System
423 V} and X/Open specifications and are therefore quite portable.
424
425 In contrast to the @code{hsearch} functions the @code{tsearch} functions
426 can be used with arbitrary data and not only zero-terminated strings.
427
428 The @code{tsearch} functions have the advantage that no function to
429 initialize data structures is necessary.  A simple pointer of type
430 @code{void *} initialized to @code{NULL} is a valid tree and can be
431 extended or searched.
432
433 @comment search.h
434 @comment SVID
435 @deftypefun {void *} tsearch (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
436 The @code{tsearch} function searches in the tree pointed to by
437 @code{*@var{rootp}} for an element matching @var{key}.  The function
438 pointed to by @var{compar} is used to determine whether two elements
439 match.  @xref{Comparison Functions}, for a specification of the functions
440 which can be used for the @var{compar} parameter.
441
442 If the tree does not contain a matching entry the @var{key} value will
443 be added to the tree.  @code{tsearch} does not make a copy of the object
444 pointed to by @var{key} (how could it since the size is unknown).
445 Instead it adds a reference to this object which means the object must
446 be available as long as the tree data structure is used.
447
448 The tree is represented by a pointer to a pointer since it is sometimes
449 necessary to change the root node of the tree.  So it must not be
450 assumed that the variable pointed to by @var{rootp} has the same value
451 after the call.  This also shows that it is not safe to call the
452 @code{tsearch} function more than once at the same time using the same
453 tree.  It is no problem to run it more than once at a time on different
454 trees.
455
456 The return value is a pointer to the matching element in the tree.  If a
457 new element was created the pointer points to the new data (which is in
458 fact @var{key}).  If an entry had to be created and the program ran out
459 of space @code{NULL} is returned.
460 @end deftypefun
461
462 @comment search.h
463 @comment SVID
464 @deftypefun {void *} tfind (const void *@var{key}, void *const *@var{rootp}, comparison_fn_t @var{compar})
465 The @code{tfind} function is similar to the @code{tsearch} function.  It
466 locates an element matching the one pointed to by @var{key} and returns
467 a pointer to this element.  But if no matching element is available no
468 new element is entered (note that the @var{rootp} parameter points to a
469 constant pointer).  Instead the function returns @code{NULL}.
470 @end deftypefun
471
472 Another advantage of the @code{tsearch} function in contrast to the
473 @code{hsearch} functions is that there is an easy way to remove
474 elements.
475
476 @comment search.h
477 @comment SVID
478 @deftypefun {void *} tdelete (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
479 To remove a specific element matching @var{key} from the tree
480 @code{tdelete} can be used.  It locates the matching element using the
481 same method as @code{tfind}.  The corresponding element is then removed
482 and a pointer to the parent of the deleted node is returned by the
483 function.  If there is no matching entry in the tree nothing can be
484 deleted and the function returns @code{NULL}.  If the root of the tree
485 is deleted @code{tdelete} returns some unspecified value not equal to
486 @code{NULL}.
487 @end deftypefun
488
489 @comment search.h
490 @comment GNU
491 @deftypefun void tdestroy (void *@var{vroot}, __free_fn_t @var{freefct})
492 If the complete search tree has to be removed one can use
493 @code{tdestroy}.  It frees all resources allocated by the @code{tsearch}
494 function to generate the tree pointed to by @var{vroot}.
495
496 For the data in each tree node the function @var{freefct} is called.
497 The pointer to the data is passed as the argument to the function.  If
498 no such work is necessary @var{freefct} must point to a function doing
499 nothing.  It is called in any case.
500
501 This function is a GNU extension and not covered by the @w{System V} or
502 X/Open specifications.
503 @end deftypefun
504
505 In addition to the function to create and destroy the tree data
506 structure, there is another function which allows you to apply a
507 function to all elements of the tree.  The function must have this type:
508
509 @smallexample
510 void __action_fn_t (const void *nodep, VISIT value, int level);
511 @end smallexample
512
513 The @var{nodep} is the data value of the current node (once given as the
514 @var{key} argument to @code{tsearch}).  @var{level} is a numeric value
515 which corresponds to the depth of the current node in the tree.  The
516 root node has the depth @math{0} and its children have a depth of
517 @math{1} and so on.  The @code{VISIT} type is an enumeration type.
518
519 @deftp {Data Type} VISIT
520 The @code{VISIT} value indicates the status of the current node in the
521 tree and how the function is called.  The status of a node is either
522 `leaf' or `internal node'.  For each leaf node the function is called
523 exactly once, for each internal node it is called three times: before
524 the first child is processed, after the first child is processed and
525 after both children are processed.  This makes it possible to handle all
526 three methods of tree traversal (or even a combination of them).
527
528 @table @code
529 @item preorder
530 The current node is an internal node and the function is called before
531 the first child was processed.
532 @item postorder
533 The current node is an internal node and the function is called after
534 the first child was processed.
535 @item endorder
536 The current node is an internal node and the function is called after
537 the second child was processed.
538 @item leaf
539 The current node is a leaf.
540 @end table
541 @end deftp
542
543 @comment search.h
544 @comment SVID
545 @deftypefun void twalk (const void *@var{root}, __action_fn_t @var{action})
546 For each node in the tree with a node pointed to by @var{root}, the
547 @code{twalk} function calls the function provided by the parameter
548 @var{action}.  For leaf nodes the function is called exactly once with
549 @var{value} set to @code{leaf}.  For internal nodes the function is
550 called three times, setting the @var{value} parameter or @var{action} to
551 the appropriate value.  The @var{level} argument for the @var{action}
552 function is computed while descending the tree with increasing the value
553 by one for the descend to a child, starting with the value @math{0} for
554 the root node.
555
556 Since the functions used for the @var{action} parameter to @code{twalk}
557 must not modify the tree data, it is safe to run @code{twalk} in more
558 than one thread at the same time, working on the same tree.  It is also
559 safe to call @code{tfind} in parallel.  Functions which modify the tree
560 must not be used, otherwise the behavior is undefined.
561 @end deftypefun