diff options
Diffstat (limited to 'man-pages-posix-2017/man3p/tdelete.3p')
| -rw-r--r-- | man-pages-posix-2017/man3p/tdelete.3p | 357 |
1 files changed, 357 insertions, 0 deletions
diff --git a/man-pages-posix-2017/man3p/tdelete.3p b/man-pages-posix-2017/man3p/tdelete.3p new file mode 100644 index 0000000..d1fbd93 --- /dev/null +++ b/man-pages-posix-2017/man3p/tdelete.3p @@ -0,0 +1,357 @@ +'\" et +.TH TDELETE "3P" 2017 "IEEE/The Open Group" "POSIX Programmer's Manual" +.\" +.SH PROLOG +This manual page is part of the POSIX Programmer's Manual. +The Linux implementation of this interface may differ (consult +the corresponding Linux manual page for details of Linux behavior), +or the interface may not be implemented on Linux. +.\" +.SH NAME +tdelete, +tfind, +tsearch, +twalk +\(em manage a binary search tree +.SH SYNOPSIS +.LP +.nf +#include <search.h> +.P +void *tdelete(const void *restrict \fIkey\fP, void **restrict \fIrootp\fP, + int(*\fIcompar\fP)(const void *, const void *)); +void *tfind(const void *\fIkey\fP, void *const *\fIrootp\fP, + int(*\fIcompar\fP)(const void *, const void *)); +void *tsearch(const void *\fIkey\fP, void **\fIrootp\fP, + int (*\fIcompar\fP)(const void *, const void *)); +void twalk(const void *\fIroot\fP, + void (*\fIaction\fP)(const void *, VISIT, int)); +.fi +.SH DESCRIPTION +The +\fItdelete\fR(), +\fItfind\fR(), +\fItsearch\fR(), +and +\fItwalk\fR() +functions manipulate binary search trees. Comparisons are made with a +user-supplied routine, the address of which is passed as the +.IR compar +argument. This routine is called with two arguments, which are the +pointers to the elements being compared. The application shall ensure +that the user-supplied routine returns an integer less than, equal to, +or greater than 0, according to whether the first argument is to be +considered less than, equal to, or greater than the second argument. +The comparison function need not compare every byte, so arbitrary data +may be contained in the elements in addition to the values being +compared. +.P +The +\fItsearch\fR() +function shall build and access the tree. The +.IR key +argument is a pointer to an element to be accessed or stored. If there +is a node in the tree whose element is equal to the value pointed to by +.IR key , +a pointer to this found node shall be returned. Otherwise, the value +pointed to by +.IR key +shall be inserted (that is, a new node is created and the value of +.IR key +is copied to this node), and a pointer to this node returned. Only +pointers are copied, so the application shall ensure that the calling +routine stores the data. The +.IR rootp +argument points to a variable that points to the root node of the +tree. A null pointer value for the variable pointed to by +.IR rootp +denotes an empty tree; in this case, the variable shall be set to point +to the node which shall be at the root of the new tree. +.P +Like +\fItsearch\fR(), +\fItfind\fR() +shall search for a node in the tree, returning a pointer to it if found. +However, if it is not found, +\fItfind\fR() +shall return a null pointer. The arguments for +\fItfind\fR() +are the same as for +\fItsearch\fR(). +.P +The +\fItdelete\fR() +function shall delete a node from a binary search tree. The arguments +are the same as for +\fItsearch\fR(). +The variable pointed to by +.IR rootp +shall be changed if the deleted node was the root of the tree. +If the deleted node was the root of the tree and had no children, the +variable pointed to by +.IR rootp +shall be set to a null pointer. The +\fItdelete\fR() +function shall return a pointer to the parent of the deleted node, or +an unspecified non-null pointer if the deleted node was the root node, +or a null pointer if the node is not found. +.P +If +\fItsearch\fR() +adds an element to a tree, or +\fItdelete\fR() +successfully deletes an element from a tree, the concurrent use of +that tree in another thread, or use of pointers produced by a previous +call to +\fItfind\fR() +or +\fItsearch\fR(), +produces undefined results. +.P +The +\fItwalk\fR() +function shall traverse a binary search tree. The +.IR root +argument is a pointer to the root node of the tree to be traversed. +(Any node in a tree may be used as the root for a walk below that +node.) The argument +.IR action +is the name of a routine to be invoked at each node. This routine is, +in turn, called with three arguments. The first argument shall be the +address of the node being visited. The structure pointed to by this +argument is unspecified and shall not be modified by the application, +but it shall be possible to cast a pointer-to-node into a +pointer-to-pointer-to-element to access the element stored in the node. +The second argument shall be a value from an enumeration data type: +.sp +.RS 4 +.nf + +typedef enum { preorder, postorder, endorder, leaf } VISIT; +.fi +.P +.RE +.P +(defined in +.IR <search.h> ), +depending on whether this is the first, second, or third time that the +node is visited (during a depth-first, left-to-right traversal of the +tree), or whether the node is a leaf. The third argument shall be +the level of the node in the tree, with the root being level 0. +.P +If the calling function alters the pointer to the root, the result is +undefined. +.P +If the functions pointed to by +.IR action +or +.IR compar +(for any of these binary search functions) change the tree, the results +are undefined. +.P +These functions are thread-safe only as long as multiple threads +do not access the same tree. +.SH "RETURN VALUE" +If the node is found, both +\fItsearch\fR() +and +\fItfind\fR() +shall return a pointer to it. If not, +\fItfind\fR() +shall return a null pointer, and +\fItsearch\fR() +shall return a pointer to the inserted item. +.P +A null pointer shall be returned by +\fItsearch\fR() +if there is not enough space available to create a new node. +.P +A null pointer shall be returned by +\fItdelete\fR(), +\fItfind\fR(), +and +\fItsearch\fR() +if +.IR rootp +is a null pointer on entry. +.P +The +\fItdelete\fR() +function shall return a pointer to the parent of the deleted node, or +an unspecified non-null pointer if the deleted node was the root node, +or a null pointer if the node is not found. +.P +The +\fItwalk\fR() +function shall not return a value. +.SH ERRORS +No errors are defined. +.LP +.IR "The following sections are informative." +.SH "EXAMPLES" +The following code reads in strings and stores structures containing a +pointer to each string and a count of its length. It then walks the +tree, printing out the stored strings and their lengths in alphabetical +order. +.sp +.RS 4 +.nf + +#include <limits.h> +#include <search.h> +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +.P +struct element { /* Pointers to these are stored in the tree. */ + int count; + char string[]; +}; +.P +void *root = NULL; /* This points to the root. */ +.P +int main(void) +{ + char str[_POSIX2_LINE_MAX+1]; + int length = 0; + struct element *elementptr; + void *node; + void print_node(const void *, VISIT, int); + int node_compare(const void *, const void *), + delete_root(const void *, const void *); +.P + while (fgets(str, sizeof(str), stdin)) { + /* Set element. */ + length = strlen(str); + if (str[length-1] == \(aq\en\(aq) + str[--length] = \(aq\e0\(aq; + elementptr = malloc(sizeof(struct element) + length + 1); + strcpy(elementptr->string, str); + elementptr->count = 1; + /* Put element into the tree. */ + node = tsearch((void *)elementptr, &root, node_compare); + if (node == NULL) { + fprintf(stderr, + "tsearch: Not enough space available\en"); + exit(EXIT_FAILURE); + } + else if (*(struct element **)node != elementptr) { + /* A node containing the element already exists */ + (*(struct element **)node)->count++; + free(elementptr); + } + } + twalk(root, print_node); +.P + /* Delete all nodes in the tree */ + while (root != NULL) { + elementptr = *(struct element **)root; + printf("deleting node: string = %s, count = %d\en", + elementptr->string, + elementptr->count); + tdelete((void *)elementptr, &root, delete_root); + free(elementptr); + } +.P + return 0; +} +.P +/* + * This routine compares two nodes, based on an + * alphabetical ordering of the string field. + */ +int +node_compare(const void *node1, const void *node2) +{ + return strcmp(((const struct element *) node1)->string, + ((const struct element *) node2)->string); +} +.P +/* + * This comparison routine can be used with tdelete() + * when explicitly deleting a root node, as no comparison + * is necessary. + */ +int +delete_root(const void *node1, const void *node2) +{ + return 0; +} +.P +/* + * This routine prints out a node, the second time + * twalk encounters it or if it is a leaf. + */ +void +print_node(const void *ptr, VISIT order, int level) +{ + const struct element *p = *(const struct element **) ptr; +.P + if (order == postorder || order == leaf) { + (void) printf("string = %s, count = %d\en", + p->string, p->count); + } +} +.fi +.P +.RE +.SH "APPLICATION USAGE" +The +.IR root +argument to +\fItwalk\fR() +is one level of indirection less than the +.IR rootp +arguments to +\fItdelete\fR() +and +\fItsearch\fR(). +.P +There are two nomenclatures used to refer to the order in which tree +nodes are visited. The +\fItwalk\fR() +function uses \fBpreorder\fP, \fBpostorder\fP, and \fBendorder\fP to +refer respectively to visiting a node before any of its children, after +its left child and before its right, and after both its children. The +alternative nomenclature uses \fBpreorder\fP, \fBinorder\fP, and +\fBpostorder\fP to refer to the same visits, which could result in some +confusion over the meaning of \fBpostorder\fP. +.P +Since the return value of +\fItdelete\fR() +is an unspecified non-null pointer in the case that the root of the tree +has been deleted, applications should only use the return value of +\fItdelete\fR() +as indication of success or failure and should not assume it can be +dereferenced. Some implementations in this case will return a pointer to +the new root of the tree (or to an empty tree if the deleted root node +was the only node in the tree); other implementations return arbitrary +non-null pointers. +.SH RATIONALE +None. +.SH "FUTURE DIRECTIONS" +None. +.SH "SEE ALSO" +.IR "\fIhcreate\fR\^(\|)", +.IR "\fIlsearch\fR\^(\|)" +.P +The Base Definitions volume of POSIX.1\(hy2017, +.IR "\fB<search.h>\fP" +.\" +.SH COPYRIGHT +Portions of this text are reprinted and reproduced in electronic form +from IEEE Std 1003.1-2017, Standard for Information Technology +-- Portable Operating System Interface (POSIX), The Open Group Base +Specifications Issue 7, 2018 Edition, +Copyright (C) 2018 by the Institute of +Electrical and Electronics Engineers, Inc and The Open Group. +In the event of any discrepancy between this version and the original IEEE and +The Open Group Standard, the original IEEE and The Open Group Standard +is the referee document. The original Standard can be obtained online at +http://www.opengroup.org/unix/online.html . +.PP +Any typographical or formatting errors that appear +in this page are most likely +to have been introduced during the conversion of the source files to +man page format. To report such errors, see +https://www.kernel.org/doc/man-pages/reporting_bugs.html . |