diff options
Diffstat (limited to 'man3/tsearch.3')
| -rw-r--r-- | man3/tsearch.3 | 353 |
1 files changed, 0 insertions, 353 deletions
diff --git a/man3/tsearch.3 b/man3/tsearch.3 deleted file mode 100644 index 958de6d2c..000000000 --- a/man3/tsearch.3 +++ /dev/null @@ -1,353 +0,0 @@ -'\" t -.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com> -.\" -.\" SPDX-License-Identifier: Linux-man-pages-copyleft -.\" -.TH tsearch 3 (date) "Linux man-pages (unreleased)" -.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). -.ad l -.nh -.TS -allbox; -lbx lb lb -l l l. -Interface Attribute Value -T{ -.BR tsearch (), -.BR tfind (), -.BR tdelete () -T} Thread safety MT-Safe race:rootp -T{ -.BR twalk () -T} Thread safety MT-Safe race:root -T{ -.BR twalk_r () -T} Thread safety MT-Safe race:root -T{ -.BR tdestroy () -T} Thread safety MT-Safe -.TE -.hy -.ad -.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) |