@cindex array search function
Generally searching for a specific element in an array means that
-potentially all elements must be checked. The GNU C library contains
+potentially all elements must be checked. @Theglibc{} contains
functions to perform linear search. The prototypes for the following
two functions can be found in @file{search.h}.
-@comment search.h
-@comment SVID
-@deftypefun {void *} lfind (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
+@deftypefun {void *} lfind (const void *@var{key}, const void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
The @code{lfind} function searches in the array with @code{*@var{nmemb}}
elements of @var{size} bytes pointed to by @var{base} for an element
which matches the one pointed to by @var{key}. The function pointed to
-by @var{compar} is used decide whether two elements match.
+by @var{compar} is used to decide whether two elements match.
The return value is a pointer to the matching element in the array
starting at @var{base} if it is found. If no matching element is
available @code{NULL} is returned.
The mean runtime of this function is @code{*@var{nmemb}}/2. This
-function should only be used elements often get added to or deleted from
+function should only be used if elements often get added to or deleted from
the array in which case it might not be useful to sort the array before
searching.
@end deftypefun
-@comment search.h
-@comment SVID
@deftypefun {void *} lsearch (const void *@var{key}, void *@var{base}, size_t *@var{nmemb}, size_t @var{size}, comparison_fn_t @var{compar})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
+@c A signal handler that interrupted an insertion and performed an
+@c insertion itself would leave the array in a corrupt state (e.g. one
+@c new element initialized twice, with parts of both initializations
+@c prevailing, and another uninitialized element), but this is just a
+@c special case of races on user-controlled objects, that have to be
+@c avoided by users.
+
+@c In case of cancellation, we know the array won't be left in a corrupt
+@c state; the new element is initialized before the element count is
+@c incremented, and the compiler can't reorder these operations because
+@c it can't know that they don't alias. So, we'll either cancel after
+@c the increment and the initialization are both complete, or the
+@c increment won't have taken place, and so how far the initialization
+@c got doesn't matter.
The @code{lsearch} function is similar to the @code{lfind} function. It
searches the given array for an element and returns it if found. The
difference is that if no matching element is found the @code{lsearch}
the header file @file{stdlib.h}.
@pindex stdlib.h
-@comment stdlib.h
-@comment ISO
@deftypefun {void *} bsearch (const void *@var{key}, const void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
+@standards{ISO, stdlib.h}
+@safety{@prelim{}@mtsafe{}@assafe{}@acsafe{}}
The @code{bsearch} function searches the sorted array @var{array} for an object
that is equivalent to @var{key}. The array contains @var{count} elements,
each of which is of size @var{size} bytes.
@file{stdlib.h}.
@pindex stdlib.h
-@comment stdlib.h
-@comment ISO
@deftypefun void qsort (void *@var{array}, size_t @var{count}, size_t @var{size}, comparison_fn_t @var{compare})
-The @var{qsort} function sorts the array @var{array}. The array contains
-@var{count} elements, each of which is of size @var{size}.
+@standards{ISO, stdlib.h}
+@safety{@prelim{}@mtsafe{}@assafe{}@acunsafe{@acucorrupt{}}}
+The @code{qsort} function sorts the array @var{array}. The array
+contains @var{count} elements, each of which is of size @var{size}.
The @var{compare} function is used to perform the comparison on the
array elements. This function is called with two pointer arguments and
the elements. Two elements with the same sort key may differ in other
respects.
-If you want the effect of a stable sort, you can get this result by
-writing the comparison function so that, lacking other reason
-distinguish between two elements, it compares them by their addresses.
-Note that doing this may make the sorting algorithm less efficient, so
-do it only if necessary.
+Although the object addresses passed to the comparison function lie
+within the array, they need not correspond with the original locations
+of those objects because the sorting algorithm may swap around objects
+in the array before making some comparisons. The only way to perform
+a stable sort with @code{qsort} is to first augment the objects with a
+monotonic counter of some kind.
Here is a simple example of sorting an array of doubles in numerical
order, using the comparison function defined above (@pxref{Comparison
@node Hash Search Function
@section The @code{hsearch} function.
-The functions mentioned so far in this chapter are searching in a sorted
+The functions mentioned so far in this chapter are for searching in a sorted
or unsorted array. There are other methods to organize information
which later should be searched. The costs of insert, delete and search
differ. One possible implementation is using hashing tables.
-The following functions are declared in the the header file @file{search.h}.
+The following functions are declared in the header file @file{search.h}.
-@comment search.h
-@comment SVID
@deftypefun int hcreate (size_t @var{nel})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtunsafe{@mtasurace{:hsearch}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}}
+@c hcreate @mtasurace:hsearch @ascuheap @acucorrupt @acsmem
+@c hcreate_r dup @mtsrace:htab @ascuheap @acucorrupt @acsmem
The @code{hcreate} function creates a hashing table which can contain at
least @var{nel} elements. There is no possibility to grow this table so
-it is necessary to choose the value for @var{nel} wisely. The used
-methods to implement this function might make it necessary to make the
+it is necessary to choose the value for @var{nel} wisely. The method
+used to implement this function might make it necessary to make the
number of elements in the hashing table larger than the expected maximal
-number of elements. Hashing tables usually work inefficient if they are
+number of elements. Hashing tables usually work inefficiently if they are
filled 80% or more. The constant access time guaranteed by hashing can
only be achieved if few collisions exist. See Knuth's ``The Art of
Computer Programming, Part 3: Searching and Sorting'' for more
The weakest aspect of this function is that there can be at most one
hashing table used through the whole program. The table is allocated
-in local memory out of control of the programmer. As an extension the
-GNU C library provides an additional set of functions with an reentrant
-interface which provide a similar interface but which allow to keep
+in local memory out of control of the programmer. As an extension @theglibc{}
+provides an additional set of functions with a reentrant
+interface which provides a similar interface but which allows keeping
arbitrarily many hashing tables.
It is possible to use more than one hashing table in the program run if
the former table is first destroyed by a call to @code{hdestroy}.
-The function returns a non-zero value if successful. If it return zero
+The function returns a non-zero value if successful. If it returns zero,
something went wrong. This could either mean there is already a hashing
-table in use or the program runs out of memory.
+table in use or the program ran out of memory.
@end deftypefun
-@comment search.h
-@comment SVID
@deftypefun void hdestroy (void)
+@standards{SVID, search.h}
+@safety{@prelim{}@mtunsafe{@mtasurace{:hsearch}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}}
+@c hdestroy @mtasurace:hsearch @ascuheap @acucorrupt @acsmem
+@c hdestroy_r dup @mtsrace:htab @ascuheap @acucorrupt @acsmem
The @code{hdestroy} function can be used to free all the resources
allocated in a previous call of @code{hcreate}. After a call to this
function it is again possible to call @code{hcreate} and allocate a new
programmer has to keep a list of all table elements and before calling
@code{hdestroy} s/he has to free all element's data using this list.
This is a very unpleasant mechanism and it also shows that this kind of
-hashing tables is mainly meant for tables which are created once and
+hashing table is mainly meant for tables which are created once and
used until the end of the program run.
@end deftypefun
Entries of the hashing table and keys for the search are defined using
this type:
-@deftp {Data type} {struct ENTRY}
-Both elements of this structure are pointers to zero-terminated strings.
-This is a limiting restriction of the functionality of the
-@code{hsearch} functions. They can only be used for data sets which use
-the NUL character always and solely to terminate the records. It is not
-possible to handle general binary data.
-
+@deftp {Data type} ENTRY
@table @code
@item char *key
Pointer to a zero-terminated string of characters describing the key for
the search or the element in the hashing table.
-@item char *data
-Pointer to a zero-terminated string of characters describing the data.
-If the functions will be called only for searching an existing entry
-this element might stay undefined since it is not used.
+
+This is a limiting restriction of the functionality of the
+@code{hsearch} functions: They can only be used for data sets which
+use the NUL character always and solely to terminate keys. It is not
+possible to handle general binary data for keys.
+
+@item void *data
+Generic pointer for use by the application. The hashing table
+implementation preserves this pointer in entries, but does not use it
+in any way otherwise.
@end table
@end deftp
-@comment search.h
-@comment SVID
+@deftp {Data type} {struct entry}
+The underlying type of @code{ENTRY}.
+@end deftp
+
@deftypefun {ENTRY *} hsearch (ENTRY @var{item}, ACTION @var{action})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtunsafe{@mtasurace{:hsearch}}@asunsafe{}@acunsafe{@acucorrupt{/action==ENTER}}}
+@c hsearch @mtasurace:hsearch @acucorrupt/action==ENTER
+@c hsearch_r dup @mtsrace:htab @acucorrupt/action==ENTER
To search in a hashing table created using @code{hcreate} the
-@code{hsearch} function must be used. This function can perform simple
-search for an element (if @var{action} has the @code{FIND}) or it can
+@code{hsearch} function must be used. This function can perform a simple
+search for an element (if @var{action} has the value @code{FIND}) or it can
alternatively insert the key element into the hashing table. Entries
are never replaced.
locating the corresponding position in the hashing table only the
@code{key} element of the structure is used.
-If an entry with matching key is found the @var{action} parameter is
+If an entry with a matching key is found the @var{action} parameter is
irrelevant. The found entry is returned. If no matching entry is found
and the @var{action} parameter has the value @code{FIND} the function
returns a @code{NULL} pointer. If no entry is found and the
A pointer to the newly added entry is returned.
@end deftypefun
-As mentioned before the hashing table used by the functions described so
+As mentioned before, the hashing table used by the functions described so
far is global and there can be at any time at most one hashing table in
the program. A solution is to use the following functions which are a
GNU extension. All have in common that they operate on a hashing table
hsearch_data}. This type should be treated as opaque, none of its
members should be changed directly.
-@comment search.h
-@comment GNU
@deftypefun int hcreate_r (size_t @var{nel}, struct hsearch_data *@var{htab})
+@standards{GNU, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:htab}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}}
+@c Unlike the lsearch array, the htab is (at least in part) opaque, so
+@c let's make it absolutely clear that ensuring exclusive access is a
+@c caller responsibility.
+
+@c Cancellation is unlikely to leave the htab in a corrupt state: the
+@c last field to be initialized is the one that tells whether the entire
+@c data structure was initialized, and there's a function call (calloc)
+@c in between that will often ensure all other fields are written before
+@c the table. However, should this call be inlined (say with LTO), this
+@c assumption may not hold. The calloc call doesn't cross our library
+@c interface barrier, so let's consider this could happen and mark this
+@c with @acucorrupt. It's no safety loss, since we already have
+@c @ascuheap anyway...
+
+@c hcreate_r @mtsrace:htab @ascuheap @acucorrupt @acsmem
+@c isprime ok
+@c calloc dup @ascuheap @acsmem
The @code{hcreate_r} function initializes the object pointed to by
@var{htab} to contain a hashing table with at least @var{nel} elements.
So this function is equivalent to the @code{hcreate} function except
dynamically. It must be initialized with zero before calling this
function.
-The return value is non-zero if the operation were successful. if the
-return value is zero something went wrong which probably means the
-programs runs out of memory.
+The return value is non-zero if the operation was successful. If the
+return value is zero, something went wrong, which probably means the
+program ran out of memory.
@end deftypefun
-@comment search.h
-@comment GNU
@deftypefun void hdestroy_r (struct hsearch_data *@var{htab})
+@standards{GNU, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:htab}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}}
+@c The table is released while the table pointer still points to it.
+@c Async cancellation is thus unsafe, but it already was because we call
+@c free(). Using the table in a handler while it's being released would
+@c also be dangerous, but calling free() already makes it unsafe, and
+@c the requirement on the caller to ensure exclusive access already
+@c guarantees this doesn't happen, so we don't get @asucorrupt.
+
+@c hdestroy_r @mtsrace:htab @ascuheap @acucorrupt @acsmem
+@c free dup @ascuheap @acsmem
The @code{hdestroy_r} function frees all resources allocated by the
@code{hcreate_r} function for this very same object @var{htab}. As for
-@code{hdestroy} it is the programs responsibility to free the strings
+@code{hdestroy} it is the program's responsibility to free the strings
for the elements of the table.
@end deftypefun
-@comment search.h
-@comment GNU
@deftypefun int hsearch_r (ENTRY @var{item}, ACTION @var{action}, ENTRY **@var{retval}, struct hsearch_data *@var{htab})
+@standards{GNU, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:htab}}@assafe{}@acunsafe{@acucorrupt{/action==ENTER}}}
+@c Callers have to ensure mutual exclusion; insertion, if cancelled,
+@c leaves the table in a corrupt state.
+
+@c hsearch_r @mtsrace:htab @acucorrupt/action==ENTER
+@c strlen dup ok
+@c strcmp dup ok
The @code{hsearch_r} function is equivalent to @code{hsearch}. The
meaning of the first two arguments is identical. But instead of
operating on a single global hashing table the function works on the
initialized by a call to @code{hcreate_r}).
Another difference to @code{hcreate} is that the pointer to the found
-entry in the table is not the return value of the functions. It is
-returned by storing it in a pointer variables pointed to by the
+entry in the table is not the return value of the function. It is
+returned by storing it in a pointer variable pointed to by the
@var{retval} parameter. The return value of the function is an integer
value indicating success if it is non-zero and failure if it is zero.
-In the latter case the global variable @var{errno} signals the reason for
+In the latter case the global variable @code{errno} signals the reason for
the failure.
@table @code
@item ENOMEM
-The table is filled and @code{hsearch_r} was called with an so far
+The table is filled and @code{hsearch_r} was called with a so far
unknown key and @var{action} set to @code{ENTER}.
@item ESRCH
The @var{action} parameter is @code{FIND} and no corresponding element
trees. The @code{tsearch} function family provides a nice interface to
functions to organize possibly large amounts of data by providing a mean
access time proportional to the logarithm of the number of elements.
-The GNU C library implementation even guarantees that this bound is
+@Theglibc{} implementation even guarantees that this bound is
never exceeded even for input data which cause problems for simple
binary tree implementations.
extended or searched. The prototypes for these functions can be found
in the header file @file{search.h}.
-@comment search.h
-@comment SVID
@deftypefun {void *} tsearch (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:rootp}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}}
+@c The tree is not modified in a thread-safe manner, and rotations may
+@c leave the tree in an inconsistent state that could be observed in an
+@c asynchronous signal handler (except for the caller-synchronization
+@c requirement) or after asynchronous cancellation of the thread
+@c performing the rotation or the insertion.
The @code{tsearch} function searches in the tree pointed to by
@code{*@var{rootp}} for an element matching @var{key}. The function
pointed to by @var{compar} is used to determine whether two elements
of space @code{NULL} is returned.
@end deftypefun
-@comment search.h
-@comment SVID
@deftypefun {void *} tfind (const void *@var{key}, void *const *@var{rootp}, comparison_fn_t @var{compar})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:rootp}}@assafe{}@acsafe{}}
The @code{tfind} function is similar to the @code{tsearch} function. It
locates an element matching the one pointed to by @var{key} and returns
a pointer to this element. But if no matching element is available no
constant pointer). Instead the function returns @code{NULL}.
@end deftypefun
-Another advantage of the @code{tsearch} function in contrast to the
+Another advantage of the @code{tsearch} functions in contrast to the
@code{hsearch} functions is that there is an easy way to remove
elements.
-@comment search.h
-@comment SVID
@deftypefun {void *} tdelete (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:rootp}}@asunsafe{@ascuheap{}}@acunsafe{@acucorrupt{} @acsmem{}}}
To remove a specific element matching @var{key} from the tree
@code{tdelete} can be used. It locates the matching element using the
same method as @code{tfind}. The corresponding element is then removed
@code{NULL}.
@end deftypefun
-@comment search.h
-@comment GNU
@deftypefun void tdestroy (void *@var{vroot}, __free_fn_t @var{freefct})
+@standards{GNU, search.h}
+@safety{@prelim{}@mtsafe{}@asunsafe{@ascuheap{}}@acunsafe{@acsmem{}}}
If the complete search tree has to be removed one can use
@code{tdestroy}. It frees all resources allocated by the @code{tsearch}
-function to generate the tree pointed to by @var{vroot}.
+functions to generate the tree pointed to by @var{vroot}.
For the data in each tree node the function @var{freefct} is called.
The pointer to the data is passed as the argument to the function. If
X/Open specifications.
@end deftypefun
-In addition to the function to create and destroy the tree data
+In addition to the functions to create and destroy the tree data
structure, there is another function which allows you to apply a
function to all elements of the tree. The function must have this type:
after both children are processed. This makes it possible to handle all
three methods of tree traversal (or even a combination of them).
-@table @code
+@vtable @code
@item preorder
The current node is an internal node and the function is called before
the first child was processed.
the second child was processed.
@item leaf
The current node is a leaf.
-@end table
+@end vtable
@end deftp
-@comment search.h
-@comment SVID
@deftypefun void twalk (const void *@var{root}, __action_fn_t @var{action})
+@standards{SVID, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:root}}@assafe{}@acsafe{}}
For each node in the tree with a node pointed to by @var{root}, the
@code{twalk} function calls the function provided by the parameter
@var{action}. For leaf nodes the function is called exactly once with
@var{value} set to @code{leaf}. For internal nodes the function is
called three times, setting the @var{value} parameter or @var{action} to
the appropriate value. The @var{level} argument for the @var{action}
-function is computed while descending the tree with increasing the value
-by one for the descend to a child, starting with the value @math{0} for
+function is computed while descending the tree by increasing the value
+by one for each descent to a child, starting with the value @math{0} for
the root node.
Since the functions used for the @var{action} parameter to @code{twalk}
must not modify the tree data, it is safe to run @code{twalk} in more
than one thread at the same time, working on the same tree. It is also
safe to call @code{tfind} in parallel. Functions which modify the tree
-must not be used, otherwise the behavior is undefined.
+must not be used, otherwise the behavior is undefined. However, it is
+difficult to pass data external to the tree to the callback function
+without resorting to global variables (and thread safety issues), so
+see the @code{twalk_r} function below.
+@end deftypefun
+
+@deftypefun void twalk_r (const void *@var{root}, void (*@var{action}) (const void *@var{key}, VISIT @var{which}, void *@var{closure}), void *@var{closure})
+@standards{GNU, search.h}
+@safety{@prelim{}@mtsafe{@mtsrace{:root}}@assafe{}@acsafe{}}
+For each node in the tree with a node pointed to by @var{root}, the
+@code{twalk_r} function calls the function provided by the parameter
+@var{action}. For leaf nodes the function is called exactly once with
+@var{which} set to @code{leaf}. For internal nodes the function is
+called three times, setting the @var{which} parameter of @var{action} to
+the appropriate value. The @var{closure} parameter is passed down to
+each call of the @var{action} function, unmodified.
+
+It is possible to implement the @code{twalk} function on top of the
+@code{twalk_r} function, which is why there is no separate level
+parameter.
+
+@smallexample
+@include twalk.c.texi
+@end smallexample
@end deftypefun
projects / thirdparty / glibc.git / blobdiff