summaryrefslogtreecommitdiffstats
path: root/man3/tsearch.3
diff options
context:
space:
mode:
Diffstat (limited to 'man3/tsearch.3')
-rw-r--r--man3/tsearch.3357
1 files changed, 357 insertions, 0 deletions
diff --git a/man3/tsearch.3 b/man3/tsearch.3
new file mode 100644
index 0000000..ff20302
--- /dev/null
+++ b/man3/tsearch.3
@@ -0,0 +1,357 @@
+'\" t
+.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
+.\"
+.\" SPDX-License-Identifier: Linux-man-pages-copyleft
+.\"
+.TH tsearch 3 2023-07-20 "Linux man-pages 6.05.01"
+.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>
+.PP
+.B typedef enum { preorder, postorder, endorder, leaf } VISIT;
+.PP
+.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 ));
+.PP
+.BR "#define _GNU_SOURCE" " /* See feature_test_macros(7) */"
+.B #include <search.h>
+.PP
+.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.
+.PP
+.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.
+.PP
+.BR tfind ()
+is like
+.BR tsearch (),
+except that if the item is not
+found, then
+.BR tfind ()
+returns NULL.
+.PP
+.BR tdelete ()
+deletes an item from the tree.
+Its arguments are the same as for
+.BR tsearch ().
+.PP
+.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.
+.PP
+(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.)
+.PP
+.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.
+.PP
+.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.
+.PP
+.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.
+.PP
+.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
+.sp 1
+.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.
+.PP
+.BR tdelete ()
+frees the memory required for the node in the tree.
+The user is responsible for freeing the memory for the corresponding
+data.
+.PP
+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.
+.PP
+.\" 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)