tdelete.3p (10937B)
- '\" 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 .