diff options
Diffstat (limited to 'man3/tsearch.3')
| -rw-r--r-- | man3/tsearch.3 | 357 |
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) |