GNU Info

Info Node: (libc.info)Tree Search Function

(libc.info)Tree Search Function


Prev: Hash Search Function Up: Searching and Sorting
Enter node , (file) or (file)node

The `tsearch' function.
=======================

   Another common form to organize data for efficient search is to use
trees.  The `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 described in the chapter are all described in the
System V and X/Open specifications and are therefore quite portable.

   In contrast to the `hsearch' functions the `tsearch' functions can
be used with arbitrary data and not only zero-terminated strings.

   The `tsearch' functions have the advantage that no function to
initialize data structures is necessary.  A simple pointer of type
`void *' initialized to `NULL' is a valid tree and can be extended or
searched.

 - Function: void * tsearch (const void *KEY, void **ROOTP,
          comparison_fn_t COMPAR)
     The `tsearch' function searches in the tree pointed to by `*ROOTP'
     for an element matching KEY.  The function pointed to by COMPAR is
     used to determine whether two elements match.  Note: Comparison
     Functions, for a specification of the functions which can be
     used for the COMPAR parameter.

     If the tree does not contain a matching entry the KEY value will
     be added to the tree.  `tsearch' does not make a copy of the object
     pointed to by 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 ROOTP has the
     same value after the call.  This also shows that it is not safe to
     call the `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 KEY).  If an entry had to be created and the
     program ran out of space `NULL' is returned.

 - Function: void * tfind (const void *KEY, void *const *ROOTP,
          comparison_fn_t COMPAR)
     The `tfind' function is similar to the `tsearch' function.  It
     locates an element matching the one pointed to by KEY and returns
     a pointer to this element.  But if no matching element is
     available no new element is entered (note that the ROOTP parameter
     points to a constant pointer).  Instead the function returns
     `NULL'.

   Another advantage of the `tsearch' function in contrast to the
`hsearch' functions is that there is an easy way to remove elements.

 - Function: void * tdelete (const void *KEY, void **ROOTP,
          comparison_fn_t COMPAR)
     To remove a specific element matching KEY from the tree `tdelete'
     can be used.  It locates the matching element using the same
     method as `tfind'.  The corresponding element is then removed and
     a pointer to the parent of the deleted node is returned by the
     function.  If there is no matching entry in the tree nothing can be
     deleted and the function returns `NULL'.  If the root of the tree
     is deleted `tdelete' returns some unspecified value not equal to
     `NULL'.

 - Function: void tdestroy (void *VROOT, __free_fn_t FREEFCT)
     If the complete search tree has to be removed one can use
     `tdestroy'.  It frees all resources allocated by the `tsearch'
     function to generate the tree pointed to by VROOT.

     For the data in each tree node the function FREEFCT is called.
     The pointer to the data is passed as the argument to the function.
     If no such work is necessary 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 System V or
     X/Open specifications.

   In addition to the function 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:

     void __action_fn_t (const void *nodep, VISIT value, int level);

   The NODEP is the data value of the current node (once given as the
KEY argument to `tsearch').  LEVEL is a numeric value which corresponds
to the depth of the current node in the tree.  The root node has the
depth 0 and its children have a depth of 1 and so on.  The `VISIT' type
is an enumeration type.

 - Data Type: VISIT
     The `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 children are processed.  This makes it
     possible to handle all three methods of tree traversal (or even a
     combination of them).

    `preorder'
          The current node is an internal node and the function is
          called before the first child was processed.

    `postorder'
          The current node is an internal node and the function is
          called after the first child was processed.

    `endorder'
          The current node is an internal node and the function is
          called after the second child was processed.

    `leaf'
          The current node is a leaf.

 - Function: void twalk (const void *ROOT, __action_fn_t ACTION)
     For each node in the tree with a node pointed to by ROOT, the
     `twalk' function calls the function provided by the parameter
     ACTION.  For leaf nodes the function is called exactly once with
     VALUE set to `leaf'.  For internal nodes the function is called
     three times, setting the VALUE parameter or ACTION to the
     appropriate value.  The LEVEL argument for the ACTION function is
     computed while descending the tree with increasing the value by
     one for the descend to a child, starting with the value 0 for the
     root node.

     Since the functions used for the ACTION parameter to `twalk' must
     not modify the tree data, it is safe to run `twalk' in more than
     one thread at the same time, working on the same tree.  It is also
     safe to call `tfind' in parallel.  Functions which modify the tree
     must not be used, otherwise the behavior is undefined.


automatically generated by info2www version 1.2.2.9