twalk(3)                                                       twalk(3)

  tsearch()

  NAME

    tdelete(), tfind(), tsearch(), twalk() - manage a binary search tree

  SYNOPSIS

    #include 

    void *tsearch (const void *key, void **rootp,
                   int (*compar)(const void *, const void *))
    void *tfind (const void *key, void **rootp,
                 int (*compar)(const void *, const void *))
    void *tdelete (const void *key, void **rootp,
                 int (*compar)(const void *, const void *))
    void twalk (const void *root, void (*action)(const void *, VISIT, int));

  DESCRIPTION

    The tsearch(3), tfind(3), tdelete(3), and twalk(3) function manage binary
    search trees. tsearch(3) is used to build and access the tree; tfind(3)
    searches the tree but will not insert nodes. The tdelete(3) function
    deletes a node from a tree, and the twalk(3) function traverses a tree.

    The arguments for tsearch(3), tfind(3), and tdelete(3) are identical. The
    key is a pointer to the element to be located (for tsearch(3) and
    tfind(3)), added (for tsearch(3)), or deleted (for tdelete(3)). The rootp
    is a pointer to a variable that points to the root node of the tree. If
    rootp is NULL, it indicates an empty tree. The compar argument is the
    address of a user-supplied comparison routine which is called with the
    pointers to the elements being compared. The comparision function doesn't
    need to compare every byte; the elements of the tree can contain arbitrary
    data as well as the values actually being compared. The routine returns an
    int:

    <0
        if the first argument is less than the second argument

    0
        if the first argument is equal to the second argument

    >0
        if the first argument is greater than the second argument

    Both tsearch(3) and tfind(3) search the tree. If the element pointed to by
    key is found, they return a pointer to that element. It is the
    responsibility of the calling function to copy the element. If the element
    can't be found, tsearch(3) inserts it in the tree and returns a pointer to
    this new node, while tfind(3) simply returns a null pointer.

    The tdelete(3) function deletes the node indicated by key and returns a
    pointer to the successor of the deleted node (one of the children), or if
    there are no children, returns a pointer to the root of the tree. If the
    root node is deleted, the function changes the variable pointed to by
    rootp. Tdelete(3) returns NULL if the node can't be found or when the last
    node has been deleted.

    The twalk(3) function traverses a binary search tree, starting with the
    node pointed to by root. (The root of the walk can be any node in the
    tree; the walk visits the tree below that node.) The second argument to
    twalk(3), action, is a pointer to a function which is invoked at each
    node. The function pointed to by action takes three arguments:
    *     The address of the node to be visited;
    *     a value from the enumerated type VISIT (defined in ).
          which indicates whether this is the first, second, or third time the
          types assume a depth-first, left-to-right walk of the tree, and are:
          preorder:
              Visiting a node before any of its children.
          postorder:
              Visiting a node after its left child and before its right.
          endorder:
              Visiting a node after its children.
          leaf:
              The node is a leaf node.
    *     the level of the node in the tree, where the root is level 0.

  RETURN VALUE

    The tsearch(3) function returns a pointer to the node if it was found; if
    the item was inserted, the function returns a pointer to the inserted
    item. If there is not enough space to create a new node, or if rootp is a
    null pointer on entry, tsearch(3) returns a null pointer.

    The tfind(3) function returns a pointer to the node if it was found; if it
    was not found, or if rootp is a null pointer on entry, the function
    returns a null pointer.

    The tdelete(3) function returns a pointer to the parent of the deleted
    node; if the node was not found, or if rootp is a null pointer on entry,
    it returns a null pointer.

    The twalk(3) function does not return a value.

  NOTES

    Don't be confused by the meaning of postorder. Here it refers to visiting
    a node after its left child and before its right. Some people refer to the
    order of visiting tree nodes as preorder, inorder, and postorder.

    This implementation uses malloc(3) across trees. Using tdelete(3) to
    remove all of the nodes in a given tree may not free all of the memory
    associated with that tree because some of the memory may also be
    associated with another tree. When all of the nodes used by all of the
    trees associated with a given program are tdelete(3)d, all of the memory
    is freed.

  SEE ALSO

    bsearch(3)

    hsearch(3)

    lsearch(3)

  USAGE NOTES

    All of these functions are thread safe.

    None of these functions are async-signal safe.