summaryrefslogtreecommitdiffstats
path: root/man3/tsearch.3
diff options
context:
space:
mode:
Diffstat (limited to 'man3/tsearch.3')
-rw-r--r--man3/tsearch.3356
1 files changed, 0 insertions, 356 deletions
diff --git a/man3/tsearch.3 b/man3/tsearch.3
deleted file mode 100644
index 1343cbe..0000000
--- a/man3/tsearch.3
+++ /dev/null
@@ -1,356 +0,0 @@
-'\" t
-.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
-.\"
-.\" SPDX-License-Identifier: Linux-man-pages-copyleft
-.\"
-.TH tsearch 3 2023-10-31 "Linux man-pages 6.7"
-.SH NAME
-tsearch, tfind, tdelete, twalk, twalk_r, tdestroy \- manage a binary search tree
-.SH LIBRARY
-Standard C library
-.RI ( libc ", " \-lc )
-.SH SYNOPSIS
-.nf
-.B #include <search.h>
-.P
-.B typedef enum { preorder, postorder, endorder, leaf } VISIT;
-.P
-.BI "void *tsearch(const void *" key ", void **" rootp ,
-.BI " int (*" compar ")(const void *, const void *));"
-.BI "void *tfind(const void *" key ", void *const *" rootp ,
-.BI " int (*" compar ")(const void *, const void *));"
-.BI "void *tdelete(const void *restrict " key ", void **restrict " rootp ,
-.BI " int (*" compar ")(const void *, const void *));"
-.BI "void twalk(const void *" root ,
-.BI " void (*" action ")(const void *" nodep ", VISIT " which ,
-.BI " int " depth ));
-.P
-.BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
-.B #include <search.h>
-.P
-.BI "void twalk_r(const void *" root ,
-.BI " void (*" action ")(const void *" nodep ", VISIT " which ,
-.BI " void *" closure ),
-.BI " void *" closure );
-.BI "void tdestroy(void *" root ", void (*" free_node ")(void *" nodep ));
-.fi
-.SH DESCRIPTION
-.BR tsearch (),
-.BR tfind (),
-.BR twalk (),
-and
-.BR tdelete ()
-manage a
-binary search tree.
-They are generalized from Knuth (6.2.2) Algorithm T.
-The first field in each node of the tree is a pointer to the
-corresponding data item.
-(The calling program must store the actual data.)
-.I compar
-points to a comparison routine, which takes
-pointers to two items.
-It should return an integer which is negative,
-zero, or positive, depending on whether the first item is less than,
-equal to, or greater than the second.
-.P
-.BR tsearch ()
-searches the tree for an item.
-.I key
-points to the item to be searched for.
-.I rootp
-points to a variable which points to the root of the tree.
-If the tree is empty,
-then the variable that
-.I rootp
-points to should be set to NULL.
-If the item is found in the tree, then
-.BR tsearch ()
-returns a pointer
-to the corresponding tree node.
-(In other words,
-.BR tsearch ()
-returns a pointer to a pointer to the data item.)
-If the item is not found, then
-.BR tsearch ()
-adds it, and returns a
-pointer to the corresponding tree node.
-.P
-.BR tfind ()
-is like
-.BR tsearch (),
-except that if the item is not
-found, then
-.BR tfind ()
-returns NULL.
-.P
-.BR tdelete ()
-deletes an item from the tree.
-Its arguments are the same as for
-.BR tsearch ().
-.P
-.BR twalk ()
-performs depth-first, left-to-right traversal of a binary
-tree.
-.I root
-points to the starting node for the traversal.
-If that node is not the root, then only part of the tree will be visited.
-.BR twalk ()
-calls the user function
-.I action
-each time a node is
-visited (that is, three times for an internal node, and once for a
-leaf).
-.IR action ,
-in turn, takes three arguments.
-The first argument is a pointer to the node being visited.
-The structure of the node is unspecified,
-but it is possible to cast the pointer to a pointer-to-pointer-to-element
-in order to access the element stored within the node.
-The application must not modify the structure pointed to by this argument.
-The second argument is an integer which
-takes one of the values
-.BR preorder ,
-.BR postorder ,
-or
-.B endorder
-depending on whether this is the first, second, or
-third visit to the internal node,
-or the value
-.B leaf
-if this is the single visit to a leaf node.
-(These symbols are defined in
-.IR <search.h> .)
-The third argument is the depth of the node;
-the root node has depth zero.
-.P
-(More commonly,
-.BR preorder ,
-.BR postorder ,
-and
-.B endorder
-are known as
-.BR preorder ,
-.BR inorder ,
-and
-.BR postorder :
-before visiting the children, after the first and before the second,
-and after visiting the children.
-Thus, the choice of name
-.B post\%order
-is rather confusing.)
-.P
-.BR twalk_r ()
-is similar to
-.BR twalk (),
-but instead of the
-.I depth
-argument, the
-.I closure
-argument pointer is passed to each invocation of the action callback,
-unchanged.
-This pointer can be used to pass information to and from
-the callback function in a thread-safe fashion, without resorting
-to global variables.
-.P
-.BR tdestroy ()
-removes the whole tree pointed to by
-.IR root ,
-freeing all resources allocated by the
-.BR tsearch ()
-function.
-For the data in each tree node the function
-.I free_node
-is called.
-The pointer to the data is passed as the argument to the function.
-If no such work is necessary,
-.I free_node
-must point to a function
-doing nothing.
-.SH RETURN VALUE
-.BR tsearch ()
-returns a pointer to a matching node in the tree, or to
-the newly added node, or NULL if there was insufficient memory
-to add the item.
-.BR tfind ()
-returns a pointer to the node, or
-NULL if no match is found.
-If there are multiple items that match the key,
-the item whose node is returned is unspecified.
-.P
-.BR tdelete ()
-returns a pointer to the parent of the node deleted, or
-NULL if the item was not found.
-If the deleted node was the root node,
-.BR tdelete ()
-returns a dangling pointer that must not be accessed.
-.P
-.BR tsearch (),
-.BR tfind (),
-and
-.BR tdelete ()
-also
-return NULL if
-.I rootp
-was NULL on entry.
-.SH ATTRIBUTES
-For an explanation of the terms used in this section, see
-.BR attributes (7).
-.TS
-allbox;
-lbx lb lb
-l l l.
-Interface Attribute Value
-T{
-.na
-.nh
-.BR tsearch (),
-.BR tfind (),
-.BR tdelete ()
-T} Thread safety MT-Safe race:rootp
-T{
-.na
-.nh
-.BR twalk ()
-T} Thread safety MT-Safe race:root
-T{
-.na
-.nh
-.BR twalk_r ()
-T} Thread safety MT-Safe race:root
-T{
-.na
-.nh
-.BR tdestroy ()
-T} Thread safety MT-Safe
-.TE
-.SH STANDARDS
-.TP
-.BR tsearch ()
-.TQ
-.BR tfind ()
-.TQ
-.BR tdelete ()
-.TQ
-.BR twalk ()
-POSIX.1-2008.
-.TP
-.BR tdestroy ()
-.TQ
-.BR twalk_r ()
-GNU.
-.SH HISTORY
-.TP
-.BR tsearch ()
-.TQ
-.BR tfind ()
-.TQ
-.BR tdelete ()
-.TQ
-.BR twalk ()
-POSIX.1-2001, POSIX.1-2008, SVr4.
-.TP
-.BR twalk_r ()
-glibc 2.30.
-.SH NOTES
-.BR twalk ()
-takes a pointer to the root, while the other functions
-take a pointer to a variable which points to the root.
-.P
-.BR tdelete ()
-frees the memory required for the node in the tree.
-The user is responsible for freeing the memory for the corresponding
-data.
-.P
-The example program depends on the fact that
-.BR twalk ()
-makes no
-further reference to a node after calling the user function with
-argument "endorder" or "leaf".
-This works with the GNU library
-implementation, but is not in the System V documentation.
-.SH EXAMPLES
-The following program inserts twelve random numbers into a binary
-tree, where duplicate numbers are collapsed, then prints the numbers
-in order.
-.P
-.\" SRC BEGIN (tsearch.c)
-.EX
-#define _GNU_SOURCE /* Expose declaration of tdestroy() */
-#include <search.h>
-#include <stddef.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <time.h>
-\&
-static void *root = NULL;
-\&
-static void *
-xmalloc(size_t n)
-{
- void *p;
-\&
- p = malloc(n);
- if (p)
- return p;
- fprintf(stderr, "insufficient memory\en");
- exit(EXIT_FAILURE);
-}
-\&
-static int
-compare(const void *pa, const void *pb)
-{
- if (*(int *) pa < *(int *) pb)
- return \-1;
- if (*(int *) pa > *(int *) pb)
- return 1;
- return 0;
-}
-\&
-static void
-action(const void *nodep, VISIT which, int depth)
-{
- int *datap;
-\&
- switch (which) {
- case preorder:
- break;
- case postorder:
- datap = *(int **) nodep;
- printf("%6d\en", *datap);
- break;
- case endorder:
- break;
- case leaf:
- datap = *(int **) nodep;
- printf("%6d\en", *datap);
- break;
- }
-}
-\&
-int
-main(void)
-{
- int *ptr;
- int **val;
-\&
- srand(time(NULL));
- for (unsigned int i = 0; i < 12; i++) {
- ptr = xmalloc(sizeof(*ptr));
- *ptr = rand() & 0xff;
- val = tsearch(ptr, &root, compare);
- if (val == NULL)
- exit(EXIT_FAILURE);
- if (*val != ptr)
- free(ptr);
- }
- twalk(root, action);
- tdestroy(root, free);
- exit(EXIT_SUCCESS);
-}
-.EE
-.\" SRC END
-.SH SEE ALSO
-.BR bsearch (3),
-.BR hsearch (3),
-.BR lsearch (3),
-.BR qsort (3)