]>
Commit | Line | Data |
---|---|---|
40a55d20 | 1 | @node Searching and Sorting, Pattern Matching, Message Translation, Top |
7a68c94a | 2 | @c %MENU% General searching and sorting functions |
f65fd747 | 3 | @chapter Searching and Sorting |
28f540f4 RM |
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 | |
f65fd747 | 14 | ordering. |
28f540f4 RM |
15 | * Array Search Function:: The @code{bsearch} function. |
16 | * Array Sort Function:: The @code{qsort} function. | |
17 | * Search/Sort Example:: An example program. | |
2604afb1 UD |
18 | * Hash Search Function:: The @code{hsearch} function. |
19 | * Tree Search Function:: The @code{tsearch} function. | |
28f540f4 RM |
20 | @end menu |
21 | ||
2604afb1 | 22 | @node Comparison Functions |
28f540f4 RM |
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 | |
68ef28ed | 42 | compare_doubles (const void *a, const void *b) |
28f540f4 | 43 | @{ |
68ef28ed UD |
44 | const double *da = (const double *) a; |
45 | const double *db = (const double *) b; | |
46 | ||
47 | return (*da > *db) - (*da < *db); | |
28f540f4 RM |
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 | ||
2604afb1 | 61 | @node Array Search Function |
28f540f4 RM |
62 | @section Array Search Function |
63 | @cindex search function (for arrays) | |
64 | @cindex binary search function (for arrays) | |
65 | @cindex array search function | |
66 | ||
2604afb1 | 67 | Generally searching for a specific element in an array means that |
1f77f049 | 68 | potentially all elements must be checked. @Theglibc{} contains |
2604afb1 UD |
69 | functions to perform linear search. The prototypes for the following |
70 | two functions can be found in @file{search.h}. | |
71 | ||
8ded91fb | 72 | @deftypefun {void *} lfind (const void *@var{key}, const void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar}) |
d08a7e4c | 73 | @standards{SVID, search.h} |
433c45a2 | 74 | @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} |
2604afb1 UD |
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 | |
8ed0d867 | 78 | by @var{compar} is used to decide whether two elements match. |
2604afb1 UD |
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 | |
11bf311e | 85 | function should only be used if elements often get added to or deleted from |
2604afb1 UD |
86 | the array in which case it might not be useful to sort the array before |
87 | searching. | |
88 | @end deftypefun | |
89 | ||
2604afb1 | 90 | @deftypefun {void *} lsearch (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar}) |
d08a7e4c | 91 | @standards{SVID, search.h} |
433c45a2 AO |
92 | @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} |
93 | @c A signal handler that interrupted an insertion and performed an | |
94 | @c insertion itself would leave the array in a corrupt state (e.g. one | |
95 | @c new element initialized twice, with parts of both initializations | |
96 | @c prevailing, and another uninitialized element), but this is just a | |
97 | @c special case of races on user-controlled objects, that have to be | |
98 | @c avoided by users. | |
99 | ||
100 | @c In case of cancellation, we know the array won't be left in a corrupt | |
101 | @c state; the new element is initialized before the element count is | |
102 | @c incremented, and the compiler can't reorder these operations because | |
103 | @c it can't know that they don't alias. So, we'll either cancel after | |
104 | @c the increment and the initialization are both complete, or the | |
105 | @c increment won't have taken place, and so how far the initialization | |
106 | @c got doesn't matter. | |
2604afb1 UD |
107 | The @code{lsearch} function is similar to the @code{lfind} function. It |
108 | searches the given array for an element and returns it if found. The | |
109 | difference is that if no matching element is found the @code{lsearch} | |
110 | function adds the object pointed to by @var{key} (with a size of | |
111 | @var{size} bytes) at the end of the array and it increments the value of | |
112 | @code{*@var{nmemb}} to reflect this addition. | |
113 | ||
114 | This means for the caller that if it is not sure that the array contains | |
115 | the element one is searching for the memory allocated for the array | |
116 | starting at @var{base} must have room for at least @var{size} more | |
117 | bytes. If one is sure the element is in the array it is better to use | |
118 | @code{lfind} so having more room in the array is always necessary when | |
119 | calling @code{lsearch}. | |
120 | @end deftypefun | |
121 | ||
28f540f4 RM |
122 | To search a sorted array for an element matching the key, use the |
123 | @code{bsearch} function. The prototype for this function is in | |
124 | the header file @file{stdlib.h}. | |
125 | @pindex stdlib.h | |
126 | ||
28f540f4 | 127 | @deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare}) |
d08a7e4c | 128 | @standards{ISO, stdlib.h} |
433c45a2 | 129 | @safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}} |
28f540f4 RM |
130 | The @code{bsearch} function searches the sorted array @var{array} for an object |
131 | that is equivalent to @var{key}. The array contains @var{count} elements, | |
f65fd747 | 132 | each of which is of size @var{size} bytes. |
28f540f4 RM |
133 | |
134 | The @var{compare} function is used to perform the comparison. This | |
135 | function is called with two pointer arguments and should return an | |
136 | integer less than, equal to, or greater than zero corresponding to | |
137 | whether its first argument is considered less than, equal to, or greater | |
138 | than its second argument. The elements of the @var{array} must already | |
139 | be sorted in ascending order according to this comparison function. | |
140 | ||
141 | The return value is a pointer to the matching array element, or a null | |
142 | pointer if no match is found. If the array contains more than one element | |
143 | that matches, the one that is returned is unspecified. | |
144 | ||
145 | This function derives its name from the fact that it is implemented | |
146 | using the binary search algorithm. | |
147 | @end deftypefun | |
148 | ||
2604afb1 | 149 | @node Array Sort Function |
28f540f4 RM |
150 | @section Array Sort Function |
151 | @cindex sort function (for arrays) | |
152 | @cindex quick sort function (for arrays) | |
153 | @cindex array sort function | |
154 | ||
155 | To sort an array using an arbitrary comparison function, use the | |
156 | @code{qsort} function. The prototype for this function is in | |
157 | @file{stdlib.h}. | |
158 | @pindex stdlib.h | |
159 | ||
28f540f4 | 160 | @deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare}) |
d08a7e4c | 161 | @standards{ISO, stdlib.h} |
433c45a2 | 162 | @safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}} |
98fe149e AK |
163 | The @code{qsort} function sorts the array @var{array}. The array |
164 | contains @var{count} elements, each of which is of size @var{size}. | |
28f540f4 RM |
165 | |
166 | The @var{compare} function is used to perform the comparison on the | |
167 | array elements. This function is called with two pointer arguments and | |
168 | should return an integer less than, equal to, or greater than zero | |
169 | corresponding to whether its first argument is considered less than, | |
170 | equal to, or greater than its second argument. | |
171 | ||
172 | @cindex stable sorting | |
173 | @strong{Warning:} If two objects compare as equal, their order after | |
174 | sorting is unpredictable. That is to say, the sorting is not stable. | |
175 | This can make a difference when the comparison considers only part of | |
176 | the elements. Two elements with the same sort key may differ in other | |
177 | respects. | |
178 | ||
98fe149e AK |
179 | Although the object addresses passed to the comparison function lie |
180 | within the array, they need not correspond with the original locations | |
181 | of those objects because the sorting algorithm may swap around objects | |
182 | in the array before making some comparisons. The only way to perform | |
183 | a stable sort with @code{qsort} is to first augment the objects with a | |
184 | monotonic counter of some kind. | |
28f540f4 RM |
185 | |
186 | Here is a simple example of sorting an array of doubles in numerical | |
187 | order, using the comparison function defined above (@pxref{Comparison | |
188 | Functions}): | |
189 | ||
190 | @smallexample | |
191 | @{ | |
192 | double *array; | |
193 | int size; | |
194 | @dots{} | |
195 | qsort (array, size, sizeof (double), compare_doubles); | |
196 | @} | |
197 | @end smallexample | |
198 | ||
199 | The @code{qsort} function derives its name from the fact that it was | |
200 | originally implemented using the ``quick sort'' algorithm. | |
21ad6b26 AJ |
201 | |
202 | The implementation of @code{qsort} in this library might not be an | |
203 | in-place sort and might thereby use an extra amount of memory to store | |
204 | the array. | |
28f540f4 RM |
205 | @end deftypefun |
206 | ||
2604afb1 | 207 | @node Search/Sort Example |
28f540f4 RM |
208 | @section Searching and Sorting Example |
209 | ||
210 | Here is an example showing the use of @code{qsort} and @code{bsearch} | |
211 | with an array of structures. The objects in the array are sorted | |
212 | by comparing their @code{name} fields with the @code{strcmp} function. | |
213 | Then, we can look up individual objects based on their names. | |
214 | ||
215 | @comment This example is dedicated to the memory of Jim Henson. RIP. | |
216 | @smallexample | |
217 | @include search.c.texi | |
218 | @end smallexample | |
219 | ||
220 | @cindex Kermit the frog | |
221 | The output from this program looks like: | |
222 | ||
223 | @smallexample | |
224 | Kermit, the frog | |
225 | Piggy, the pig | |
226 | Gonzo, the whatever | |
227 | Fozzie, the bear | |
228 | Sam, the eagle | |
229 | Robin, the frog | |
230 | Animal, the animal | |
231 | Camilla, the chicken | |
232 | Sweetums, the monster | |
233 | Dr. Strangepork, the pig | |
234 | Link Hogthrob, the pig | |
235 | Zoot, the human | |
236 | Dr. Bunsen Honeydew, the human | |
237 | Beaker, the human | |
238 | Swedish Chef, the human | |
239 | ||
240 | Animal, the animal | |
241 | Beaker, the human | |
242 | Camilla, the chicken | |
243 | Dr. Bunsen Honeydew, the human | |
244 | Dr. Strangepork, the pig | |
245 | Fozzie, the bear | |
246 | Gonzo, the whatever | |
247 | Kermit, the frog | |
248 | Link Hogthrob, the pig | |
249 | Piggy, the pig | |
250 | Robin, the frog | |
251 | Sam, the eagle | |
252 | Swedish Chef, the human | |
253 | Sweetums, the monster | |
254 | Zoot, the human | |
255 | ||
256 | Kermit, the frog | |
257 | Gonzo, the whatever | |
258 | Couldn't find Janice. | |
259 | @end smallexample | |
2604afb1 UD |
260 | |
261 | ||
262 | @node Hash Search Function | |
263 | @section The @code{hsearch} function. | |
264 | ||
11bf311e | 265 | The functions mentioned so far in this chapter are for searching in a sorted |
2604afb1 UD |
266 | or unsorted array. There are other methods to organize information |
267 | which later should be searched. The costs of insert, delete and search | |
268 | differ. One possible implementation is using hashing tables. | |
11bf311e | 269 | The following functions are declared in the header file @file{search.h}. |
2604afb1 | 270 | |
2604afb1 | 271 | @deftypefun int hcreate (size_t @var{nel}) |
d08a7e4c | 272 | @standards{SVID, search.h} |
433c45a2 AO |
273 | @safety{@prelim{}@mtunsafe{@mtasurace{:hsearch}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}} |
274 | @c hcreate @mtasurace:hsearch @ascuheap @acucorrupt @acsmem | |
275 | @c hcreate_r dup @mtsrace:htab @ascuheap @acucorrupt @acsmem | |
2604afb1 UD |
276 | The @code{hcreate} function creates a hashing table which can contain at |
277 | least @var{nel} elements. There is no possibility to grow this table so | |
11bf311e UD |
278 | it is necessary to choose the value for @var{nel} wisely. The method |
279 | used to implement this function might make it necessary to make the | |
2604afb1 | 280 | number of elements in the hashing table larger than the expected maximal |
11bf311e | 281 | number of elements. Hashing tables usually work inefficiently if they are |
2604afb1 UD |
282 | filled 80% or more. The constant access time guaranteed by hashing can |
283 | only be achieved if few collisions exist. See Knuth's ``The Art of | |
284 | Computer Programming, Part 3: Searching and Sorting'' for more | |
285 | information. | |
286 | ||
287 | The weakest aspect of this function is that there can be at most one | |
f2ea0f5b | 288 | hashing table used through the whole program. The table is allocated |
1f77f049 | 289 | in local memory out of control of the programmer. As an extension @theglibc{} |
9dcc8f11 | 290 | provides an additional set of functions with a reentrant |
8ed0d867 | 291 | interface which provides a similar interface but which allows keeping |
49c091e5 | 292 | arbitrarily many hashing tables. |
2604afb1 UD |
293 | |
294 | It is possible to use more than one hashing table in the program run if | |
295 | the former table is first destroyed by a call to @code{hdestroy}. | |
296 | ||
8ed0d867 | 297 | The function returns a non-zero value if successful. If it returns zero, |
2604afb1 | 298 | something went wrong. This could either mean there is already a hashing |
8ed0d867 | 299 | table in use or the program ran out of memory. |
2604afb1 UD |
300 | @end deftypefun |
301 | ||
2604afb1 | 302 | @deftypefun void hdestroy (void) |
d08a7e4c | 303 | @standards{SVID, search.h} |
433c45a2 AO |
304 | @safety{@prelim{}@mtunsafe{@mtasurace{:hsearch}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}} |
305 | @c hdestroy @mtasurace:hsearch @ascuheap @acucorrupt @acsmem | |
306 | @c hdestroy_r dup @mtsrace:htab @ascuheap @acucorrupt @acsmem | |
2604afb1 UD |
307 | The @code{hdestroy} function can be used to free all the resources |
308 | allocated in a previous call of @code{hcreate}. After a call to this | |
309 | function it is again possible to call @code{hcreate} and allocate a new | |
310 | table with possibly different size. | |
311 | ||
312 | It is important to remember that the elements contained in the hashing | |
313 | table at the time @code{hdestroy} is called are @emph{not} freed by this | |
314 | function. It is the responsibility of the program code to free those | |
f2ea0f5b | 315 | strings (if necessary at all). Freeing all the element memory is not |
2604afb1 UD |
316 | possible without extra, separately kept information since there is no |
317 | function to iterate through all available elements in the hashing table. | |
318 | If it is really necessary to free a table and all elements the | |
319 | programmer has to keep a list of all table elements and before calling | |
320 | @code{hdestroy} s/he has to free all element's data using this list. | |
f2ea0f5b | 321 | This is a very unpleasant mechanism and it also shows that this kind of |
8ed0d867 | 322 | hashing table is mainly meant for tables which are created once and |
2604afb1 UD |
323 | used until the end of the program run. |
324 | @end deftypefun | |
325 | ||
326 | Entries of the hashing table and keys for the search are defined using | |
327 | this type: | |
328 | ||
2d8a22cd | 329 | @deftp {Data type} ENTRY |
2604afb1 UD |
330 | @table @code |
331 | @item char *key | |
332 | Pointer to a zero-terminated string of characters describing the key for | |
333 | the search or the element in the hashing table. | |
2d8a22cd FW |
334 | |
335 | This is a limiting restriction of the functionality of the | |
336 | @code{hsearch} functions: They can only be used for data sets which | |
337 | use the NUL character always and solely to terminate keys. It is not | |
338 | possible to handle general binary data for keys. | |
339 | ||
340 | @item void *data | |
341 | Generic pointer for use by the application. The hashing table | |
342 | implementation preserves this pointer in entries, but does not use it | |
343 | in any way otherwise. | |
2604afb1 UD |
344 | @end table |
345 | @end deftp | |
346 | ||
2d8a22cd FW |
347 | @deftp {Data type} {struct entry} |
348 | The underlying type of @code{ENTRY}. | |
349 | @end deftp | |
350 | ||
2604afb1 | 351 | @deftypefun {ENTRY *} hsearch (ENTRY @var{item}, ACTION @var{action}) |
d08a7e4c | 352 | @standards{SVID, search.h} |
433c45a2 AO |
353 | @safety{@prelim{}@mtunsafe{@mtasurace{:hsearch}}@asunsafe{}@acunsafe{@acucorrupt{/action==ENTER}}} |
354 | @c hsearch @mtasurace:hsearch @acucorrupt/action==ENTER | |
355 | @c hsearch_r dup @mtsrace:htab @acucorrupt/action==ENTER | |
2604afb1 | 356 | To search in a hashing table created using @code{hcreate} the |
8ed0d867 RJ |
357 | @code{hsearch} function must be used. This function can perform a simple |
358 | search for an element (if @var{action} has the value @code{FIND}) or it can | |
afdef815 UD |
359 | alternatively insert the key element into the hashing table. Entries |
360 | are never replaced. | |
2604afb1 UD |
361 | |
362 | The key is denoted by a pointer to an object of type @code{ENTRY}. For | |
363 | locating the corresponding position in the hashing table only the | |
364 | @code{key} element of the structure is used. | |
365 | ||
8ed0d867 | 366 | If an entry with a matching key is found the @var{action} parameter is |
afdef815 UD |
367 | irrelevant. The found entry is returned. If no matching entry is found |
368 | and the @var{action} parameter has the value @code{FIND} the function | |
369 | returns a @code{NULL} pointer. If no entry is found and the | |
370 | @var{action} parameter has the value @code{ENTER} a new entry is added | |
371 | to the hashing table which is initialized with the parameter @var{item}. | |
372 | A pointer to the newly added entry is returned. | |
2604afb1 UD |
373 | @end deftypefun |
374 | ||
8ed0d867 | 375 | As mentioned before, the hashing table used by the functions described so |
2604afb1 UD |
376 | far is global and there can be at any time at most one hashing table in |
377 | the program. A solution is to use the following functions which are a | |
378 | GNU extension. All have in common that they operate on a hashing table | |
379 | which is described by the content of an object of the type @code{struct | |
380 | hsearch_data}. This type should be treated as opaque, none of its | |
381 | members should be changed directly. | |
382 | ||
2604afb1 | 383 | @deftypefun int hcreate_r (size_t @var{nel}, struct hsearch_data *@var{htab}) |
d08a7e4c | 384 | @standards{GNU, search.h} |
433c45a2 AO |
385 | @safety{@prelim{}@mtsafe{@mtsrace{:htab}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}} |
386 | @c Unlike the lsearch array, the htab is (at least in part) opaque, so | |
387 | @c let's make it absolutely clear that ensuring exclusive access is a | |
388 | @c caller responsibility. | |
389 | ||
390 | @c Cancellation is unlikely to leave the htab in a corrupt state: the | |
391 | @c last field to be initialized is the one that tells whether the entire | |
392 | @c data structure was initialized, and there's a function call (calloc) | |
393 | @c in between that will often ensure all other fields are written before | |
394 | @c the table. However, should this call be inlined (say with LTO), this | |
395 | @c assumption may not hold. The calloc call doesn't cross our library | |
396 | @c interface barrier, so let's consider this could happen and mark this | |
397 | @c with @acucorrupt. It's no safety loss, since we already have | |
398 | @c @ascuheap anyway... | |
399 | ||
400 | @c hcreate_r @mtsrace:htab @ascuheap @acucorrupt @acsmem | |
401 | @c isprime ok | |
402 | @c calloc dup @ascuheap @acsmem | |
f2ea0f5b | 403 | The @code{hcreate_r} function initializes the object pointed to by |
2604afb1 UD |
404 | @var{htab} to contain a hashing table with at least @var{nel} elements. |
405 | So this function is equivalent to the @code{hcreate} function except | |
406 | that the initialized data structure is controlled by the user. | |
407 | ||
0d1ef15f UD |
408 | This allows having more than one hashing table at one time. The memory |
409 | necessary for the @code{struct hsearch_data} object can be allocated | |
410 | dynamically. It must be initialized with zero before calling this | |
411 | function. | |
2604afb1 | 412 | |
11bf311e UD |
413 | The return value is non-zero if the operation was successful. If the |
414 | return value is zero, something went wrong, which probably means the | |
8ed0d867 | 415 | program ran out of memory. |
2604afb1 UD |
416 | @end deftypefun |
417 | ||
2604afb1 | 418 | @deftypefun void hdestroy_r (struct hsearch_data *@var{htab}) |
d08a7e4c | 419 | @standards{GNU, search.h} |
433c45a2 AO |
420 | @safety{@prelim{}@mtsafe{@mtsrace{:htab}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}} |
421 | @c The table is released while the table pointer still points to it. | |
422 | @c Async cancellation is thus unsafe, but it already was because we call | |
423 | @c free(). Using the table in a handler while it's being released would | |
424 | @c also be dangerous, but calling free() already makes it unsafe, and | |
425 | @c the requirement on the caller to ensure exclusive access already | |
426 | @c guarantees this doesn't happen, so we don't get @asucorrupt. | |
427 | ||
428 | @c hdestroy_r @mtsrace:htab @ascuheap @acucorrupt @acsmem | |
429 | @c free dup @ascuheap @acsmem | |
2604afb1 UD |
430 | The @code{hdestroy_r} function frees all resources allocated by the |
431 | @code{hcreate_r} function for this very same object @var{htab}. As for | |
8ed0d867 | 432 | @code{hdestroy} it is the program's responsibility to free the strings |
2604afb1 UD |
433 | for the elements of the table. |
434 | @end deftypefun | |
435 | ||
2604afb1 | 436 | @deftypefun int hsearch_r (ENTRY @var{item}, ACTION @var{action}, ENTRY **@var{retval}, struct hsearch_data *@var{htab}) |
d08a7e4c | 437 | @standards{GNU, search.h} |
433c45a2 AO |
438 | @safety{@prelim{}@mtsafe{@mtsrace{:htab}}@assafe{}@acunsafe{@acucorrupt{/action==ENTER}}} |
439 | @c Callers have to ensure mutual exclusion; insertion, if cancelled, | |
440 | @c leaves the table in a corrupt state. | |
441 | ||
442 | @c hsearch_r @mtsrace:htab @acucorrupt/action==ENTER | |
443 | @c strlen dup ok | |
444 | @c strcmp dup ok | |
2604afb1 UD |
445 | The @code{hsearch_r} function is equivalent to @code{hsearch}. The |
446 | meaning of the first two arguments is identical. But instead of | |
f2ea0f5b | 447 | operating on a single global hashing table the function works on the |
2604afb1 UD |
448 | table described by the object pointed to by @var{htab} (which is |
449 | initialized by a call to @code{hcreate_r}). | |
450 | ||
451 | Another difference to @code{hcreate} is that the pointer to the found | |
8ed0d867 RJ |
452 | entry in the table is not the return value of the function. It is |
453 | returned by storing it in a pointer variable pointed to by the | |
2604afb1 UD |
454 | @var{retval} parameter. The return value of the function is an integer |
455 | value indicating success if it is non-zero and failure if it is zero. | |
010fe231 | 456 | In the latter case the global variable @code{errno} signals the reason for |
2604afb1 UD |
457 | the failure. |
458 | ||
459 | @table @code | |
460 | @item ENOMEM | |
9dcc8f11 | 461 | The table is filled and @code{hsearch_r} was called with a so far |
2604afb1 UD |
462 | unknown key and @var{action} set to @code{ENTER}. |
463 | @item ESRCH | |
464 | The @var{action} parameter is @code{FIND} and no corresponding element | |
465 | is found in the table. | |
466 | @end table | |
467 | @end deftypefun | |
468 | ||
469 | ||
470 | @node Tree Search Function | |
471 | @section The @code{tsearch} function. | |
472 | ||
473 | Another common form to organize data for efficient search is to use | |
474 | trees. The @code{tsearch} function family provides a nice interface to | |
475 | functions to organize possibly large amounts of data by providing a mean | |
476 | access time proportional to the logarithm of the number of elements. | |
1f77f049 | 477 | @Theglibc{} implementation even guarantees that this bound is |
2604afb1 UD |
478 | never exceeded even for input data which cause problems for simple |
479 | binary tree implementations. | |
480 | ||
f2ea0f5b | 481 | The functions described in the chapter are all described in the @w{System |
2604afb1 UD |
482 | V} and X/Open specifications and are therefore quite portable. |
483 | ||
484 | In contrast to the @code{hsearch} functions the @code{tsearch} functions | |
485 | can be used with arbitrary data and not only zero-terminated strings. | |
486 | ||
487 | The @code{tsearch} functions have the advantage that no function to | |
488 | initialize data structures is necessary. A simple pointer of type | |
489 | @code{void *} initialized to @code{NULL} is a valid tree and can be | |
ce460d04 RM |
490 | extended or searched. The prototypes for these functions can be found |
491 | in the header file @file{search.h}. | |
2604afb1 | 492 | |
2604afb1 | 493 | @deftypefun {void *} tsearch (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar}) |
d08a7e4c | 494 | @standards{SVID, search.h} |
433c45a2 AO |
495 | @safety{@prelim{}@mtsafe{@mtsrace{:rootp}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}} |
496 | @c The tree is not modified in a thread-safe manner, and rotations may | |
497 | @c leave the tree in an inconsistent state that could be observed in an | |
498 | @c asynchronous signal handler (except for the caller-synchronization | |
499 | @c requirement) or after asynchronous cancellation of the thread | |
500 | @c performing the rotation or the insertion. | |
2604afb1 UD |
501 | The @code{tsearch} function searches in the tree pointed to by |
502 | @code{*@var{rootp}} for an element matching @var{key}. The function | |
f2ea0f5b | 503 | pointed to by @var{compar} is used to determine whether two elements |
8b7fb588 | 504 | match. @xref{Comparison Functions}, for a specification of the functions |
2604afb1 UD |
505 | which can be used for the @var{compar} parameter. |
506 | ||
507 | If the tree does not contain a matching entry the @var{key} value will | |
508 | be added to the tree. @code{tsearch} does not make a copy of the object | |
509 | pointed to by @var{key} (how could it since the size is unknown). | |
510 | Instead it adds a reference to this object which means the object must | |
511 | be available as long as the tree data structure is used. | |
512 | ||
513 | The tree is represented by a pointer to a pointer since it is sometimes | |
514 | necessary to change the root node of the tree. So it must not be | |
515 | assumed that the variable pointed to by @var{rootp} has the same value | |
516 | after the call. This also shows that it is not safe to call the | |
517 | @code{tsearch} function more than once at the same time using the same | |
518 | tree. It is no problem to run it more than once at a time on different | |
519 | trees. | |
520 | ||
521 | The return value is a pointer to the matching element in the tree. If a | |
522 | new element was created the pointer points to the new data (which is in | |
523 | fact @var{key}). If an entry had to be created and the program ran out | |
524 | of space @code{NULL} is returned. | |
525 | @end deftypefun | |
526 | ||
2604afb1 | 527 | @deftypefun {void *} tfind (const void *@var{key}, void *const *@var{rootp}, comparison_fn_t @var{compar}) |
d08a7e4c | 528 | @standards{SVID, search.h} |
433c45a2 | 529 | @safety{@prelim{}@mtsafe{@mtsrace{:rootp}}@assafe{}@acsafe{}} |
2604afb1 UD |
530 | The @code{tfind} function is similar to the @code{tsearch} function. It |
531 | locates an element matching the one pointed to by @var{key} and returns | |
532 | a pointer to this element. But if no matching element is available no | |
533 | new element is entered (note that the @var{rootp} parameter points to a | |
534 | constant pointer). Instead the function returns @code{NULL}. | |
535 | @end deftypefun | |
536 | ||
8ed0d867 | 537 | Another advantage of the @code{tsearch} functions in contrast to the |
2604afb1 UD |
538 | @code{hsearch} functions is that there is an easy way to remove |
539 | elements. | |
540 | ||
2604afb1 | 541 | @deftypefun {void *} tdelete (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar}) |
d08a7e4c | 542 | @standards{SVID, search.h} |
433c45a2 | 543 | @safety{@prelim{}@mtsafe{@mtsrace{:rootp}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}} |
2604afb1 UD |
544 | To remove a specific element matching @var{key} from the tree |
545 | @code{tdelete} can be used. It locates the matching element using the | |
546 | same method as @code{tfind}. The corresponding element is then removed | |
2864e767 UD |
547 | and a pointer to the parent of the deleted node is returned by the |
548 | function. If there is no matching entry in the tree nothing can be | |
549 | deleted and the function returns @code{NULL}. If the root of the tree | |
550 | is deleted @code{tdelete} returns some unspecified value not equal to | |
551 | @code{NULL}. | |
2604afb1 UD |
552 | @end deftypefun |
553 | ||
2604afb1 | 554 | @deftypefun void tdestroy (void *@var{vroot}, __free_fn_t @var{freefct}) |
d08a7e4c | 555 | @standards{GNU, search.h} |
433c45a2 | 556 | @safety{@prelim{}@mtsafe{}@asunsafe{@ascuheap{}}@acunsafe{@acsmem{}}} |
2604afb1 UD |
557 | If the complete search tree has to be removed one can use |
558 | @code{tdestroy}. It frees all resources allocated by the @code{tsearch} | |
8ed0d867 | 559 | functions to generate the tree pointed to by @var{vroot}. |
2604afb1 UD |
560 | |
561 | For the data in each tree node the function @var{freefct} is called. | |
562 | The pointer to the data is passed as the argument to the function. If | |
563 | no such work is necessary @var{freefct} must point to a function doing | |
564 | nothing. It is called in any case. | |
565 | ||
566 | This function is a GNU extension and not covered by the @w{System V} or | |
567 | X/Open specifications. | |
568 | @end deftypefun | |
569 | ||
8ed0d867 | 570 | In addition to the functions to create and destroy the tree data |
e8b1163e AJ |
571 | structure, there is another function which allows you to apply a |
572 | function to all elements of the tree. The function must have this type: | |
2604afb1 UD |
573 | |
574 | @smallexample | |
8c479619 | 575 | void __action_fn_t (const void *nodep, VISIT value, int level); |
2604afb1 UD |
576 | @end smallexample |
577 | ||
8c479619 | 578 | The @var{nodep} is the data value of the current node (once given as the |
2604afb1 UD |
579 | @var{key} argument to @code{tsearch}). @var{level} is a numeric value |
580 | which corresponds to the depth of the current node in the tree. The | |
581 | root node has the depth @math{0} and its children have a depth of | |
582 | @math{1} and so on. The @code{VISIT} type is an enumeration type. | |
583 | ||
584 | @deftp {Data Type} VISIT | |
585 | The @code{VISIT} value indicates the status of the current node in the | |
586 | tree and how the function is called. The status of a node is either | |
587 | `leaf' or `internal node'. For each leaf node the function is called | |
588 | exactly once, for each internal node it is called three times: before | |
589 | the first child is processed, after the first child is processed and | |
f2ea0f5b | 590 | after both children are processed. This makes it possible to handle all |
2604afb1 UD |
591 | three methods of tree traversal (or even a combination of them). |
592 | ||
2fe82ca6 | 593 | @vtable @code |
2604afb1 UD |
594 | @item preorder |
595 | The current node is an internal node and the function is called before | |
596 | the first child was processed. | |
da2a3ca6 | 597 | @item postorder |
2604afb1 UD |
598 | The current node is an internal node and the function is called after |
599 | the first child was processed. | |
da2a3ca6 | 600 | @item endorder |
2604afb1 UD |
601 | The current node is an internal node and the function is called after |
602 | the second child was processed. | |
603 | @item leaf | |
604 | The current node is a leaf. | |
2fe82ca6 | 605 | @end vtable |
2604afb1 UD |
606 | @end deftp |
607 | ||
2604afb1 | 608 | @deftypefun void twalk (const void *@var{root}, __action_fn_t @var{action}) |
d08a7e4c | 609 | @standards{SVID, search.h} |
433c45a2 | 610 | @safety{@prelim{}@mtsafe{@mtsrace{:root}}@assafe{}@acsafe{}} |
da2a3ca6 | 611 | For each node in the tree with a node pointed to by @var{root}, the |
2604afb1 UD |
612 | @code{twalk} function calls the function provided by the parameter |
613 | @var{action}. For leaf nodes the function is called exactly once with | |
614 | @var{value} set to @code{leaf}. For internal nodes the function is | |
615 | called three times, setting the @var{value} parameter or @var{action} to | |
616 | the appropriate value. The @var{level} argument for the @var{action} | |
8ed0d867 RJ |
617 | function is computed while descending the tree by increasing the value |
618 | by one for each descent to a child, starting with the value @math{0} for | |
2604afb1 UD |
619 | the root node. |
620 | ||
621 | Since the functions used for the @var{action} parameter to @code{twalk} | |
da2a3ca6 UD |
622 | must not modify the tree data, it is safe to run @code{twalk} in more |
623 | than one thread at the same time, working on the same tree. It is also | |
2604afb1 | 624 | safe to call @code{tfind} in parallel. Functions which modify the tree |
7b807a35 FW |
625 | must not be used, otherwise the behavior is undefined. However, it is |
626 | difficult to pass data external to the tree to the callback function | |
627 | without resorting to global variables (and thread safety issues), so | |
628 | see the @code{twalk_r} function below. | |
629 | @end deftypefun | |
630 | ||
631 | @deftypefun void twalk_r (const void *@var{root}, void (*@var{action}) (const void *@var{key}, VISIT @var{which}, void *@var{closure}), void *@var{closure}) | |
632 | @standards{GNU, search.h} | |
633 | @safety{@prelim{}@mtsafe{@mtsrace{:root}}@assafe{}@acsafe{}} | |
634 | For each node in the tree with a node pointed to by @var{root}, the | |
635 | @code{twalk_r} function calls the function provided by the parameter | |
636 | @var{action}. For leaf nodes the function is called exactly once with | |
6807f47b CD |
637 | @var{which} set to @code{leaf}. For internal nodes the function is |
638 | called three times, setting the @var{which} parameter of @var{action} to | |
7b807a35 FW |
639 | the appropriate value. The @var{closure} parameter is passed down to |
640 | each call of the @var{action} function, unmodified. | |
641 | ||
642 | It is possible to implement the @code{twalk} function on top of the | |
643 | @code{twalk_r} function, which is why there is no separate level | |
644 | parameter. | |
645 | ||
646 | @smallexample | |
647 | @include twalk.c.texi | |
648 | @end smallexample | |
2604afb1 | 649 | @end deftypefun |