Fix typo.
[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 @end deftypefun
187
188 @node Search/Sort Example
189 @section Searching and Sorting Example
190
191 Here is an example showing the use of @code{qsort} and @code{bsearch}
192 with an array of structures.  The objects in the array are sorted
193 by comparing their @code{name} fields with the @code{strcmp} function.
194 Then, we can look up individual objects based on their names.
195
196 @comment This example is dedicated to the memory of Jim Henson.  RIP.
197 @smallexample
198 @include search.c.texi
199 @end smallexample
200
201 @cindex Kermit the frog
202 The output from this program looks like:
203
204 @smallexample
205 Kermit, the frog
206 Piggy, the pig
207 Gonzo, the whatever
208 Fozzie, the bear
209 Sam, the eagle
210 Robin, the frog
211 Animal, the animal
212 Camilla, the chicken
213 Sweetums, the monster
214 Dr. Strangepork, the pig
215 Link Hogthrob, the pig
216 Zoot, the human
217 Dr. Bunsen Honeydew, the human
218 Beaker, the human
219 Swedish Chef, the human
220
221 Animal, the animal
222 Beaker, the human
223 Camilla, the chicken
224 Dr. Bunsen Honeydew, the human
225 Dr. Strangepork, the pig
226 Fozzie, the bear
227 Gonzo, the whatever
228 Kermit, the frog
229 Link Hogthrob, the pig
230 Piggy, the pig
231 Robin, the frog
232 Sam, the eagle
233 Swedish Chef, the human
234 Sweetums, the monster
235 Zoot, the human
236
237 Kermit, the frog
238 Gonzo, the whatever
239 Couldn't find Janice.
240 @end smallexample
241
242
243 @node Hash Search Function
244 @section The @code{hsearch} function.
245
246 The functions mentioned so far in this chapter are searching in a sorted
247 or unsorted array.  There are other methods to organize information
248 which later should be searched.  The costs of insert, delete and search
249 differ.  One possible implementation is using hashing tables.
250
251 @comment search.h
252 @comment SVID
253 @deftypefun int hcreate (size_t @var{nel})
254 The @code{hcreate} function creates a hashing table which can contain at
255 least @var{nel} elements.  There is no possibility to grow this table so
256 it is necessary to choose the value for @var{nel} wisely.  The used
257 methods to implement this function might make it necessary to make the
258 number of elements in the hashing table larger than the expected maximal
259 number of elements.  Hashing tables usually work inefficient if they are
260 filled 80% or more.  The constant access time guaranteed by hashing can
261 only be achieved if few collisions exist.  See Knuth's ``The Art of
262 Computer Programming, Part 3: Searching and Sorting'' for more
263 information.
264
265 The weakest aspect of this function is that there can be at most one
266 hashing table used through the whole program.  The table is allocated
267 in local memory out of control of the programmer.  As an extension the
268 GNU C library provides an additional set of functions with an reentrant
269 interface which provide a similar interface but which allow to keep
270 arbitrarily many hashing tables.
271
272 It is possible to use more than one hashing table in the program run if
273 the former table is first destroyed by a call to @code{hdestroy}.
274
275 The function returns a non-zero value if successful.  If it return zero
276 something went wrong.  This could either mean there is already a hashing
277 table in use or the program runs out of memory.
278 @end deftypefun
279
280 @comment search.h
281 @comment SVID
282 @deftypefun void hdestroy (void)
283 The @code{hdestroy} function can be used to free all the resources
284 allocated in a previous call of @code{hcreate}.  After a call to this
285 function it is again possible to call @code{hcreate} and allocate a new
286 table with possibly different size.
287
288 It is important to remember that the elements contained in the hashing
289 table at the time @code{hdestroy} is called are @emph{not} freed by this
290 function.  It is the responsibility of the program code to free those
291 strings (if necessary at all).  Freeing all the element memory is not
292 possible without extra, separately kept information since there is no
293 function to iterate through all available elements in the hashing table.
294 If it is really necessary to free a table and all elements the
295 programmer has to keep a list of all table elements and before calling
296 @code{hdestroy} s/he has to free all element's data using this list.
297 This is a very unpleasant mechanism and it also shows that this kind of
298 hashing tables is mainly meant for tables which are created once and
299 used until the end of the program run.
300 @end deftypefun
301
302 Entries of the hashing table and keys for the search are defined using
303 this type:
304
305 @deftp {Data type} {struct ENTRY}
306 Both elements of this structure are pointers to zero-terminated strings.
307 This is a limiting restriction of the functionality of the
308 @code{hsearch} functions.  They can only be used for data sets which use
309 the NUL character always and solely to terminate the records.  It is not
310 possible to handle general binary data.
311
312 @table @code
313 @item char *key
314 Pointer to a zero-terminated string of characters describing the key for
315 the search or the element in the hashing table.
316 @item char *data
317 Pointer to a zero-terminated string of characters describing the data.
318 If the functions will be called only for searching an existing entry
319 this element might stay undefined since it is not used.
320 @end table
321 @end deftp
322
323 @comment search.h
324 @comment SVID
325 @deftypefun {ENTRY *} hsearch (ENTRY @var{item}, ACTION @var{action})
326 To search in a hashing table created using @code{hcreate} the
327 @code{hsearch} function must be used.  This function can perform simple
328 search for an element (if @var{action} has the @code{FIND}) or it can
329 alternatively insert the key element into the hashing table, possibly
330 replacing a previous value (if @var{action} is @code{ENTER}).
331
332 The key is denoted by a pointer to an object of type @code{ENTRY}.  For
333 locating the corresponding position in the hashing table only the
334 @code{key} element of the structure is used.
335
336 The return value depends on the @var{action} parameter value.  If it is
337 @code{FIND} the value is a pointer to the matching element in the
338 hashing table or @code{NULL} if no matching element exists.  If
339 @var{action} is @code{ENTER} the return value is only @code{NULL} if the
340 programs runs out of memory while adding the new element to the table.
341 Otherwise the return value is a pointer to the element in the hashing
342 table which contains newly added element based on the data in @var{key}.
343 @end deftypefun
344
345 As mentioned before the hashing table used by the functions described so
346 far is global and there can be at any time at most one hashing table in
347 the program.  A solution is to use the following functions which are a
348 GNU extension.  All have in common that they operate on a hashing table
349 which is described by the content of an object of the type @code{struct
350 hsearch_data}.  This type should be treated as opaque, none of its
351 members should be changed directly.
352
353 @comment search.h
354 @comment GNU
355 @deftypefun int hcreate_r (size_t @var{nel}, struct hsearch_data *@var{htab})
356 The @code{hcreate_r} function initializes the object pointed to by
357 @var{htab} to contain a hashing table with at least @var{nel} elements.
358 So this function is equivalent to the @code{hcreate} function except
359 that the initialized data structure is controlled by the user.
360
361 This allows having more than one hashing table at one time.  The
362 memory necessary for the @code{struct hsearch_data} object can be
363 allocated dynamically.
364
365 The return value is non-zero if the operation were successful.  if the
366 return value is zero something went wrong which probably means the
367 programs runs out of memory.
368 @end deftypefun
369
370 @comment search.h
371 @comment GNU
372 @deftypefun void hdestroy_r (struct hsearch_data *@var{htab})
373 The @code{hdestroy_r} function frees all resources allocated by the
374 @code{hcreate_r} function for this very same object @var{htab}.  As for
375 @code{hdestroy} it is the programs responsibility to free the strings
376 for the elements of the table.
377 @end deftypefun
378
379 @comment search.h
380 @comment GNU
381 @deftypefun int hsearch_r (ENTRY @var{item}, ACTION @var{action}, ENTRY **@var{retval}, struct hsearch_data *@var{htab})
382 The @code{hsearch_r} function is equivalent to @code{hsearch}.  The
383 meaning of the first two arguments is identical.  But instead of
384 operating on a single global hashing table the function works on the
385 table described by the object pointed to by @var{htab} (which is
386 initialized by a call to @code{hcreate_r}).
387
388 Another difference to @code{hcreate} is that the pointer to the found
389 entry in the table is not the return value of the functions.  It is
390 returned by storing it in a pointer variables pointed to by the
391 @var{retval} parameter.  The return value of the function is an integer
392 value indicating success if it is non-zero and failure if it is zero.
393 In the latter case the global variable @var{errno} signals the reason for
394 the failure.
395
396 @table @code
397 @item ENOMEM
398 The table is filled and @code{hsearch_r} was called with an so far
399 unknown key and @var{action} set to @code{ENTER}.
400 @item ESRCH
401 The @var{action} parameter is @code{FIND} and no corresponding element
402 is found in the table.
403 @end table
404 @end deftypefun
405
406
407 @node Tree Search Function
408 @section The @code{tsearch} function.
409
410 Another common form to organize data for efficient search is to use
411 trees.  The @code{tsearch} function family provides a nice interface to
412 functions to organize possibly large amounts of data by providing a mean
413 access time proportional to the logarithm of the number of elements.
414 The GNU C library implementation even guarantees that this bound is
415 never exceeded even for input data which cause problems for simple
416 binary tree implementations.
417
418 The functions described in the chapter are all described in the @w{System
419 V} and X/Open specifications and are therefore quite portable.
420
421 In contrast to the @code{hsearch} functions the @code{tsearch} functions
422 can be used with arbitrary data and not only zero-terminated strings.
423
424 The @code{tsearch} functions have the advantage that no function to
425 initialize data structures is necessary.  A simple pointer of type
426 @code{void *} initialized to @code{NULL} is a valid tree and can be
427 extended or searched.
428
429 @comment search.h
430 @comment SVID
431 @deftypefun {void *} tsearch (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
432 The @code{tsearch} function searches in the tree pointed to by
433 @code{*@var{rootp}} for an element matching @var{key}.  The function
434 pointed to by @var{compar} is used to determine whether two elements
435 match.  @xref{Comparison Functions}, for a specification of the functions
436 which can be used for the @var{compar} parameter.
437
438 If the tree does not contain a matching entry the @var{key} value will
439 be added to the tree.  @code{tsearch} does not make a copy of the object
440 pointed to by @var{key} (how could it since the size is unknown).
441 Instead it adds a reference to this object which means the object must
442 be available as long as the tree data structure is used.
443
444 The tree is represented by a pointer to a pointer since it is sometimes
445 necessary to change the root node of the tree.  So it must not be
446 assumed that the variable pointed to by @var{rootp} has the same value
447 after the call.  This also shows that it is not safe to call the
448 @code{tsearch} function more than once at the same time using the same
449 tree.  It is no problem to run it more than once at a time on different
450 trees.
451
452 The return value is a pointer to the matching element in the tree.  If a
453 new element was created the pointer points to the new data (which is in
454 fact @var{key}).  If an entry had to be created and the program ran out
455 of space @code{NULL} is returned.
456 @end deftypefun
457
458 @comment search.h
459 @comment SVID
460 @deftypefun {void *} tfind (const void *@var{key}, void *const *@var{rootp}, comparison_fn_t @var{compar})
461 The @code{tfind} function is similar to the @code{tsearch} function.  It
462 locates an element matching the one pointed to by @var{key} and returns
463 a pointer to this element.  But if no matching element is available no
464 new element is entered (note that the @var{rootp} parameter points to a
465 constant pointer).  Instead the function returns @code{NULL}.
466 @end deftypefun
467
468 Another advantage of the @code{tsearch} function in contrast to the
469 @code{hsearch} functions is that there is an easy way to remove
470 elements.
471
472 @comment search.h
473 @comment SVID
474 @deftypefun {void *} tdelete (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
475 To remove a specific element matching @var{key} from the tree
476 @code{tdelete} can be used.  It locates the matching element using the
477 same method as @code{tfind}.  The corresponding element is then removed
478 and a pointer to the parent of the deleted node is returned by the
479 function.  If there is no matching entry in the tree nothing can be
480 deleted and the function returns @code{NULL}.  If the root of the tree
481 is deleted @code{tdelete} returns some unspecified value not equal to
482 @code{NULL}.
483 @end deftypefun
484
485 @comment search.h
486 @comment GNU
487 @deftypefun void tdestroy (void *@var{vroot}, __free_fn_t @var{freefct})
488 If the complete search tree has to be removed one can use
489 @code{tdestroy}.  It frees all resources allocated by the @code{tsearch}
490 function to generate the tree pointed to by @var{vroot}.
491
492 For the data in each tree node the function @var{freefct} is called.
493 The pointer to the data is passed as the argument to the function.  If
494 no such work is necessary @var{freefct} must point to a function doing
495 nothing.  It is called in any case.
496
497 This function is a GNU extension and not covered by the @w{System V} or
498 X/Open specifications.
499 @end deftypefun
500
501 In addition to the function to create and destroy the tree data
502 structure, there is another function which allows you to apply a
503 function to all elements of the tree.  The function must have this type:
504
505 @smallexample
506 void __action_fn_t (const void *nodep, VISIT value, int level);
507 @end smallexample
508
509 The @var{nodep} is the data value of the current node (once given as the
510 @var{key} argument to @code{tsearch}).  @var{level} is a numeric value
511 which corresponds to the depth of the current node in the tree.  The
512 root node has the depth @math{0} and its children have a depth of
513 @math{1} and so on.  The @code{VISIT} type is an enumeration type.
514
515 @deftp {Data Type} VISIT
516 The @code{VISIT} value indicates the status of the current node in the
517 tree and how the function is called.  The status of a node is either
518 `leaf' or `internal node'.  For each leaf node the function is called
519 exactly once, for each internal node it is called three times: before
520 the first child is processed, after the first child is processed and
521 after both children are processed.  This makes it possible to handle all
522 three methods of tree traversal (or even a combination of them).
523
524 @table @code
525 @item preorder
526 The current node is an internal node and the function is called before
527 the first child was processed.
528 @item endorder
529 The current node is an internal node and the function is called after
530 the first child was processed.
531 @item postorder
532 The current node is an internal node and the function is called after
533 the second child was processed.
534 @item leaf
535 The current node is a leaf.
536 @end table
537 @end deftp
538
539 @comment search.h
540 @comment SVID
541 @deftypefun void twalk (const void *@var{root}, __action_fn_t @var{action})
542 For each node in the tree with a node pointed to by @var{root} the
543 @code{twalk} function calls the function provided by the parameter
544 @var{action}.  For leaf nodes the function is called exactly once with
545 @var{value} set to @code{leaf}.  For internal nodes the function is
546 called three times, setting the @var{value} parameter or @var{action} to
547 the appropriate value.  The @var{level} argument for the @var{action}
548 function is computed while descending the tree with increasing the value
549 by one for the descend to a child, starting with the value @math{0} for
550 the root node.
551
552 Since the functions used for the @var{action} parameter to @code{twalk}
553 must not modify the tree data it is safe to run @code{twalk} is more
554 than one thread at the same time working on the same tree.  It is also
555 safe to call @code{tfind} in parallel.  Functions which modify the tree
556 must not be used.  Otherwise the behaviour is undefined.
557 @end deftypefun