diff options
Diffstat (limited to 'manual')
| -rw-r--r-- | manual/filesys.texi | 206 | ||||
| -rw-r--r-- | manual/maint.texi | 60 | ||||
| -rw-r--r-- | manual/search.texi | 366 |
3 files changed, 621 insertions, 11 deletions
diff --git a/manual/filesys.texi b/manual/filesys.texi index 5ddd8a20a7..7e8a1a12d2 100644 --- a/manual/filesys.texi +++ b/manual/filesys.texi @@ -17,6 +17,8 @@ access permissions and modification times. file names. * Accessing Directories:: Finding out what files a directory contains. +* Working on Directory Trees:: Apply actions to all files or a selectable + subset of a directory hierachy. * Hard Links:: Adding alternate names to a file. * Symbolic Links:: A file that ``points to'' a file name. * Deleting Files:: How to delete a file, and what that means. @@ -500,6 +502,210 @@ Please note the simple selector function for this example. Since we want to see all directory entries we always return @code{1}. +@node Working on Directory Trees +@section Working on Directory Trees +@cindex directory hierachy +@cindex hierachy, directory +@cindex tree, directory + +The functions to handle files in directories described so far allowed to +retrieve all the information in small pieces or process all files in a +directory (see @code{scandir}). Sometimes it is useful to process whole +hierachies of directories and the contained files. The X/Open +specification define two functions to do this. The simpler form is +derived from an early definition in @w{System V} systems and therefore +this function is available on SVID derived systems. The prototypes and +required definitions can be found in the @file{ftw.h} header. + +Both functions of this @code{ftw} family take as one of the arguments a +reference to a callback function. The functions must be of these types. + +@deftp {Data Type} __ftw_func_t + +@smallexample +int (*) (const char *, const struct stat *, int) +@end smallexample + +Type for callback functions given to the @code{ftw} function. The first +parameter will contain a pointer to the filename, the second parameter +will point to an object of type @code{struct stat} which will be filled +for the file named by the first parameter. + +@noindent +The last parameter is a flag given more information about the current +file. It can have the following values: + +@vindex FTW_F +@vindex FTW_D +@vindex FTW_NS +@vindex FTW_DNR +@vindex FTW_SL +@table @code +@item FTW_F +The current item is a normal file or files which do not fit into one of +the following categories. This means especially special files, sockets +etc. +@item FTW_D +The current item is a directory. +@item FTW_NS +The @code{stat} call to fill the object pointed to by the second +parameter failed and so the information is invalid. +@item FTW_DNR +The item is a directory which cannot be read. +@item FTW_SL +The item is a symbolic link. Since symbolic links are normally followed +seeing this value in a @code{ftw} callback function means the referenced +file does not exist. The situation for @code{nftw} is different. + +This value is only available if the program is compiled with +@code{_BSD_SOURCE} or @code{_XOPEN_EXTENDED} defined before including +the first header. The original SVID systems do not have symbolic links. +@end table +@end deftp + +@deftp {Data Type} __nftw_func_t + +@smallexample +int (*) (const char *, const struct stat *, int, struct FTW *) +@end smallexample + +@vindex FTW_DP +@vindex FTW_SLN +The first three arguments have the same as for the @code{__ftw_func_t} +type. A difference is that for the third argument some additional +values are defined to allow finer differentiation: +@table @code +@item FTW_DP +The current item is a directory and all subdirectories have already been +visited and reported. This flag is returned instead of @code{FTW_D} if +the @code{FTW_DEPTH} flag is given to @code{nftw} (see below). +@item FTW_SLN +The current item is a stale symbolic link. The file it points to does +not exist. +@end table + +The last parameter of the callback function is a pointer to a structure +with some extra information as described below. +@end deftp + +@deftp {Data Type} {struct FTW} +The contained information helps to interpret the name parameter and +gives some information about current state of the traversal of the +directory hierachy. + +@table @code +@item int base +The value specifies which part of the filename argument given in the +first parameter to the callback function is the name of the file. The +rest of the string is the path to locate the file. This information is +especially important if the @code{FTW_CHDIR} flag for @code{nftw} was +set since then the current directory is the one the current item is +found in. +@item int level +While processing the directory the functions tracks how many directories +have been examine to find the current item. This nesting level is +@math{0} for the item given starting item (file or directory) and is +incremented by one for each entered directory. +@end table +@end deftp + + +@comment ftw.h +@comment SVID +@deftypefun int ftw (const char *@var{filename}, __ftw_func_t @var{func}, int @var{descriptors}) +The @code{ftw} function calls the callback function given in the +parameter @var{func} for every item which is found in the directory +specified by @var{filename} and all directories below. The function +follows symbolic links if necessary but does not process an item twice. +If @var{filename} names no directory this item is the only object +reported by calling the callback function. + +The filename given to the callback function is constructed by taking the +@var{filename} parameter and appending the names of all passed +directories and then the local file name. So the callback function can +use this parameter to access the file. Before the callback function is +called @code{ftw} calls @code{stat} for this file and passes the +information up to the callback function. If this @code{stat} call was +not successful the failure is indicated by setting the falg argument of +the callback function to @code{FTW_NS}. Otherwise the flag is set +according to the description given in the description of +@code{__ftw_func_t} above. + +The callback function is expected to return @math{0} to indicate that no +error occurred and the processing should be continued. If an error +occurred in the callback function or the call to @code{ftw} shall return +immediately the callback function can return a value other than +@math{0}. This is the only correct way to stop the function. The +program must not use @code{setjmp} or similar techniques to continue the +program in another place. This would leave the resources allocated in +the @code{ftw} function allocated. + +The @var{descriptors} parameter to the @code{ftw} function specifies how +many file descriptors the @code{ftw} function is allowed to consume. +The more descriptors can be used the faster the function can run. For +each level of directories at most one descriptor is used so that for +very deep directory hierachies the limit on open file descriptors for +the process or the system can be exceeded. Beside this the limit on +file descriptors is counted together for all threads in a multi-threaded +program and therefore it is always good too limit the maximal number of +open descriptors to a reasonable number. + +The return value of the @code{ftw} function is @math{0} if all callback +function calls returned @math{0} and all actions performed by the +@code{ftw} succeeded. If some function call failed (other than calling +@code{stat} on an item) the function return @math{-1}. If a callback +function returns a value other than @math{0} this value is returned as +the return value of @code{ftw}. +@end deftypefun + +@comment ftw.h +@comment XPG4.2 +@deftypefun int nftw (const char *@var{filename}, __nftw_func_t @var{func}, int @var{descriptors}, int @var{flag}) +The @code{nftw} functions works like the @code{ftw} functions. It calls +the callback function @var{func} for all items it finds in the directory +@var{filename} and below. At most @var{descriptors} file descriptors +are consumed during the @code{nftw} call. + +The differences are that for one the callback function is of a different +type. It is of type @w{@code{struct FTW *}} and provides the callback +functions the information described above. + +The second difference is that @code{nftw} takes an additional fourth +argument which is @math{0} or a combination of any of the following +values, combined using bitwise OR. + +@table @code +@item FTW_PHYS +While traversing the directory symbolic links are not followed. I.e., +if this flag is given symbolic links are reported using the +@code{FTW_SL} value for the type parameter to the callback function. +Please note that if this flag is used the appearence of @code{FTW_SL} in +a callback function does not mean the referenced file does not exist. +To indicate this the extra value @code{FTW_SLN} exists. +@item FTW_MOUNT +The callback function is only called for items which are on the same +mounted filesystem as the directory given as the @var{filename} +parameter to @code{nftw}. +@item FTW_CHDIR +If this flag is given the current working directory is changed to the +directory containing the reported object before the callback function is +called. +@item FTW_DEPTH +If this option is given the function visits first all files and +subdirectories before the callback function is called for the directory +itself (depth-first processing). This also means the type flag given to +the callback function is @code{FTW_DP} and not @code{FTW_D}. +@end table + +The return value is computed in the same way as for @code{ftw}. +@code{nftw} return @math{0} if no failure occurred in @code{nftw} and +all callback function call return values are also @math{0}. For +internal errors such as memory problems @math{-1} is returned and +@var{errno} is set accordingly. If the return value of a callback +invocation is nonzero this very same value is returned. +@end deftypefun + + @node Hard Links @section Hard Links @cindex hard link diff --git a/manual/maint.texi b/manual/maint.texi index 3675c4faba..d8e835f441 100644 --- a/manual/maint.texi +++ b/manual/maint.texi @@ -176,11 +176,15 @@ facilities, type @code{make check}. This will produce several files with names like @file{@var{program}.out}. To format the @cite{GNU C Library Reference Manual} for printing, type -@w{@code{make dvi}}. +@w{@code{make dvi}}. You need a working @TeX{} installation to do this. To install the library and its header files, and the Info files of the manual, type @code{make install}. This will build things if necessary, -before installing them.@refill +before installing them. If you want to install the files in a different +place than the one specified at configuration time you can specify a +value for the Makefile variable @code{install_root} on the command line. +This is useful to create chroot'ed environment or to prepare binary +releases.@refill @node Tools for Installation @appendixsubsec Recommended Tools to Install the GNU C Library @@ -192,15 +196,17 @@ build the GNU C library: @itemize @bullet @item -@code{make} 3.75 +@code{make} 3.76.1 You need the latest version of GNU @code{make}. Modifying the GNU C Library to work with other @code{make} programs would be so hard that we -recommend you port GNU @code{make} instead. @strong{Really.} -We recommend version GNU @code{make} version 3.75 or later. +recommend you port GNU @code{make} instead. @strong{Really.} We +recommend version GNU @code{make} version 3.75, 3.76.1 or later. +Version 3.76 is known to have a bug which only shows up in big projects +like GNU @code{libc}. @item -GCC 2.7.2 +GCC 2.7.2.3 On most platforms, the GNU C library can only be compiled with the GNU C compiler. We recommend GCC version 2.7.2 or later; earlier versions may @@ -216,8 +222,43 @@ Using the GNU @code{binutils} (assembler, linker, and related tools) is preferable when possible, and they are required to build an ELF shared C library. We recommend @code{binutils} version 2.8.1 or later; earlier versions are known to have problems or to not support all architectures. + +@item +@code{texinfo} 3.11 + +To correctly translate and install the Texinfo documentation you need +this version of the @code{texinfo} package. Former versions did not +understand all the tags used in the document and also the installation +mechanisms for the info files was not present or worked differently. + +On some Debian Linux based systems the used @code{install-info} program +works differently. Here you have to run make like this: + +@smallexample +make INSTALL_INFO=/path/to/GNU/install-info install +@end smallexample +@end itemize + +If you change any configuration file you will need also + +@itemize @bullet +@item +@code{autoconf} 2.12 @end itemize +@noindent +and if you change any of the message translation files you will also need + +@itemize @bullet +@item +@code{GNU gettext} 0.10 or later +@end itemize + +@noindent +If you upgrade your source tree using the patches made available you probably +will need those package above in any case. + + @node Supported Configurations @appendixsubsec Supported Configurations @cindex configurations, all supported @@ -834,7 +875,7 @@ The DES encryption function @code{crypt} and related functions were contributed by Michael Glad. @item -The @code{ftw} function was contributed by Ian Lance Taylor. +The @code{ftw} and @code{nftw} function was contributed by Ulrich Drepper. @item The startup code to support SunOS shared libraries was contributed by @@ -894,6 +935,11 @@ The port to Linux/m68k (@code{m68k-@var{anything}-linux}) was contributed by Andreas Schwab. @item +The ports to Linux/ARM (@code{arm-@var{ANYTHING}-linuxaout}) and ARM +standalone (@code{arm-@var{ANYTHING}-none}), as well as parts of the +IPv6 support code, were contributed by Philip Blundell. + +@item Richard Henderson contributed the ELF dynamic linking code and other support for the Alpha processor. diff --git a/manual/search.texi b/manual/search.texi index abb93bb5a8..356d976555 100644 --- a/manual/search.texi +++ b/manual/search.texi @@ -14,9 +14,11 @@ and the total number of elements. * Array Search Function:: The @code{bsearch} function. * Array Sort Function:: The @code{qsort} function. * Search/Sort Example:: An example program. +* Hash Search Function:: The @code{hsearch} function. +* Tree Search Function:: The @code{tsearch} function. @end menu -@node Comparison Functions, Array Search Function, , Searching and Sorting +@node Comparison Functions @section Defining the Comparison Function @cindex Comparison Function @@ -52,12 +54,53 @@ comparison functions. This type is a GNU extension. int comparison_fn_t (const void *, const void *); @end smallexample -@node Array Search Function, Array Sort Function, Comparison Functions, Searching and Sorting +@node Array Search Function @section Array Search Function @cindex search function (for arrays) @cindex binary search function (for arrays) @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 +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}) +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. + +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 +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}) +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} +function adds the object pointed to by @var{key} (with a size of +@var{size} bytes) at the end of the array and it increments the value of +@code{*@var{nmemb}} to reflect this addition. + +This means for the caller that if it is not sure that the array contains +the element one is searching for the memory allocated for the array +starting at @var{base} must have room for at least @var{size} more +bytes. If one is sure the element is in the array it is better to use +@code{lfind} so having more room in the array is always necessary when +calling @code{lsearch}. +@end deftypefun + To search a sorted array for an element matching the key, use the @code{bsearch} function. The prototype for this function is in the header file @file{stdlib.h}. @@ -85,7 +128,7 @@ This function derives its name from the fact that it is implemented using the binary search algorithm. @end deftypefun -@node Array Sort Function, Search/Sort Example, Array Search Function, Searching and Sorting +@node Array Sort Function @section Array Sort Function @cindex sort function (for arrays) @cindex quick sort function (for arrays) @@ -138,7 +181,7 @@ The @code{qsort} function derives its name from the fact that it was originally implemented using the ``quick sort'' algorithm. @end deftypefun -@node Search/Sort Example, , Array Sort Function, Searching and Sorting +@node Search/Sort Example @section Searching and Sorting Example Here is an example showing the use of @code{qsort} and @code{bsearch} @@ -191,3 +234,318 @@ Kermit, the frog Gonzo, the whatever Couldn't find Janice. @end smallexample + + +@node Hash Search Function +@section The @code{hsearch} function. + +The functions mentioned so far in this chapter are 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. + +@comment search.h +@comment SVID +@deftypefun int hcreate (size_t @var{nel}) +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 +number of elements in the hashing table larger than the expected maximal +number of elements. Hashing tables usually work inefficient 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 +information. + +The weakest aspect of this function is that there can be at most one +hashing table used throught 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 +arbitrary 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 +something went wrong. This could either mean there is already a hashing +table in use or the program runs out of memory. +@end deftypefun + +@comment search.h +@comment SVID +@deftypefun void hdestroy (void) +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 +table with possibly different size. + +It is important to remember that the elements contained in the hashing +table at the time @code{hdestroy} is called are @emph{not} freed by this +function. It is the responsibility of the program code to free those +strings (if necessary at all). Freeing all the element memory iss not +possible without extra, separately kept information since there is no +function to iterate through all available elements in the hashing table. +If it is really necessary to free a table and all elements the +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 unpleasent mechanism and it also shows that this kind of +hashing tables 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. + +@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. +@end table +@end deftp + +@comment search.h +@comment SVID +@deftypefun {ENTRY *} hsearch (ENTRY @var{item}, ACTION @var{action}) +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 +alternatively insert the key element into the hashing table, possibly +replacing a previous value (if @var{action} is @code{ENTER}). + +The key is denoted by a pointer to an object of type @code{ENTRY}. For +locating the corresponding position in the hashing table only the +@code{key} element of the structure is used. + +The return value depends on the @var{action} parameter value. If it is +@code{FIND} the value is a pointer to the matching element in the +hashing table or @code{NULL} if no matching element exists. If +@var{action} is @code{ENTER} the return value is only @code{NULL} if the +programs runs out of memory while adding the new element to the table. +Otherwise the return value is a pointer to the element in the hashing +table which contains newly added element based on the data in @var{key}. +@end deftypefun + +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 +which is described by the content of an object of the type @code{struct +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}) +The @code{hcreate_r} function intializes 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 +that the initialized data structure is controlled by the user. + +This allows to have more than once hashing table at one time. The +memory necessary for the @code{struct hsearch_data} object can be +allocated dynamically. + +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. +@end deftypefun + +@comment search.h +@comment GNU +@deftypefun void hdestroy_r (struct hsearch_data *@var{htab}) +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 +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}) +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 functio works on the +table described by the object pointed to by @var{htab} (which is +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 +@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 later case the global variable @var{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 +unknown key and @var{action} set to @code{ENTER}. +@item ESRCH +The @var{action} parameter is @code{FIND} and no corresponding element +is found in the table. +@end table +@end deftypefun + + +@node Tree Search Function +@section The @code{tsearch} function. + +Another common form to organize data for efficient search is to use +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 +never exceeded even for input data which cause problems for simple +binary tree implementations. + +The functions desribed in the chapter are all described in the @w{System +V} and X/Open specifications and are therefore quite portable. + +In contrast to the @code{hsearch} functions the @code{tsearch} functions +can be used with arbitrary data and not only zero-terminated strings. + +The @code{tsearch} functions have the advantage that no function to +initialize data structures is necessary. A simple pointer of type +@code{void *} initialized to @code{NULL} is a valid tree and can be +extended or searched. + +@comment search.h +@comment SVID +@deftypefun {void *} tsearch (const void *@var{key}, void **@var{rootp}, comparison_fn_t @var{compar}) +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 wether two elements +match. @xref{Comparison Functions} for a specification of the functions +which can be used for the @var{compar} parameter. + +If the tree does not contain a matching entry the @var{key} value will +be added to the tree. @code{tsearch} does not make a copy of the object +pointed to by @var{key} (how could it since the size is unknown). +Instead it adds a reference to this object which means the object must +be available as long as the tree data structure is used. + +The tree is represented by a pointer to a pointer since it is sometimes +necessary to change the root node of the tree. So it must not be +assumed that the variable pointed to by @var{rootp} has the same value +after the call. This also shows that it is not safe to call the +@code{tsearch} function more than once at the same time using the same +tree. It is no problem to run it more than once at a time on different +trees. + +The return value is a pointer to the matching element in the tree. If a +new element was created the pointer points to the new data (which is in +fact @var{key}). If an entry had to be created and the program ran out +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}) +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 +new element is entered (note that the @var{rootp} parameter points to a +constant pointer). Instead the function returns @code{NULL}. +@end deftypefun + +Another advantage of the @code{tsearch} function 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}) +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 +and the data if this tree node is returned by the function. If there is +no matching entry in the tree nothing can be deleted and the function +returns @code{NULL}. +@end deftypefun + +@comment search.h +@comment GNU +@deftypefun void tdestroy (void *@var{vroot}, __free_fn_t @var{freefct}) +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}. + +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 +no such work is necessary @var{freefct} must point to a function doing +nothing. It is called in any case. + +This function is a GNU extension and not covered by the @w{System V} or +X/Open specifications. +@end deftypefun + +In addition to the function to create and destroy the tree data +structure there is another function which allows to apply a function on +all elements of the tree. The function must have this type: + +@smallexample +int __action_fn_t (const void *nodep, VISIT value, int level); +@end smallexample + +The @var{nodep} is the data value of the current node (nce given as the +@var{key} argument to @code{tsearch}). @var{level} is a numeric value +which corresponds to the depth of the current node in the tree. The +root node has the depth @math{0} and its children have a depth of +@math{1} and so on. The @code{VISIT} type is an enumeration type. + +@deftp {Data Type} VISIT +The @code{VISIT} value indicates the status of the current node in the +tree and how the function is called. The status of a node is either +`leaf' or `internal node'. For each leaf node the function is called +exactly once, for each internal node it is called three times: before +the first child is processed, after the first child is processed and +after both childs are processed. This makes it possible to handle all +three methods of tree traversal (or even a combination of them). + +@table @code +@item preorder +The current node is an internal node and the function is called before +the first child was processed. +@item endorder +The current node is an internal node and the function is called after +the first child was processed. +@item postorder +The current node is an internal node and the function is called after +the second child was processed. +@item leaf +The current node is a leaf. +@end table +@end deftp + +@comment search.h +@comment SVID +@deftypefun void twalk (const void *@var{root}, __action_fn_t @var{action}) +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 escend 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} is 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 behaviour is undefined. +@end deftypefun |