diff options
Diffstat (limited to 'man3/tsearch.3')
| -rw-r--r-- | man3/tsearch.3 | 75 |
1 files changed, 55 insertions, 20 deletions
diff --git a/man3/tsearch.3 b/man3/tsearch.3 index ba95558150..9adc8e5f57 100644 --- a/man3/tsearch.3 +++ b/man3/tsearch.3 @@ -49,7 +49,12 @@ tsearch, tfind, tdelete, twalk, tdestroy \- manage a binary tree .RE .fi .SH DESCRIPTION -\fBtsearch\fP(), \fBtfind\fP(), \fBtwalk\fP(), and \fBtdelete\fP() manage a +.BR tsearch (), +.BR tfind (), +.BR twalk (), +and +.BR tdelete () +manage a binary 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 @@ -61,26 +66,40 @@ 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 -\fBtsearch\fP() searches the tree for an item. +.BR tsearch () +searches the tree for an item. \fIkey\fP points to the item to be searched for. \fIrootp\fP points to a variable which points to the root of the tree. If the tree is empty, then the variable that \fIrootp\fP points to should be set to NULL. -If the item is found in the tree, then \fBtsearch\fP() returns a pointer +If the item is found in the tree, then +.BR tsearch () +returns a pointer to it. -If it is not found, then \fBtsearch\fP() adds it, and returns a +If it is not found, then +.BR tsearch () +adds it, and returns a pointer to the newly added item. .PP -\fBtfind\fP() is like \fBtsearch\fP(), except that if the item is not -found, then \fBtfind\fP() returns NULL. +.BR tfind () +is like +.BR tsearch (), +except that if the item is not +found, then +.BR tfind () +returns NULL. .PP -\fBtdelete\fP() deletes an item from the tree. -Its arguments are the same as for \fBtsearch\fP(). +.BR tdelete () +deletes an item from the tree. +Its arguments are the same as for +.BR tsearch (). .PP -\fBtwalk\fP() performs depth-first, left-to-right traversal of a binary +.BR twalk () +performs depth-first, left-to-right traversal of a binary tree. \fIroot\fP points to the starting node for the traversal. If that node is not the root, then only part of the tree will be visited. -\fBtwalk\fP() calls the user function \fIaction\fP each time a node is +.BR twalk () +calls the user function \fIaction\fP each time a node is visited (that is, three times for an internal node, and once for a leaf). \fIaction\fP, in turn, takes three arguments. The first is a pointer to the node being visited. @@ -100,39 +119,55 @@ and after visiting the children. Thus, the choice of name \fBpost\%order\fP is rather confusing.) .PP -\fBtdestroy\fP() removes the whole tree pointed to by \fIroot\fP, -freeing all resources allocated by the \fBtsearch\fP() function. +.BR tdestroy () +removes the whole tree pointed to by \fIroot\fP, +freeing all resources allocated by the +.BR tsearch () +function. For the data in each tree node the function \fIfree_node\fP is called. The pointer to the data is passed as the argument to the function. If no such work is necessary \fIfree_node\fP must point to a function doing nothing. .SH "RETURN VALUE" -\fBtsearch\fP() returns a pointer to a matching item in the tree, or to +.BR tsearch () +returns a pointer to a matching item in the tree, or to the newly added item, or NULL if there was insufficient memory -to add the item. \fBtfind\fP() returns a pointer to the item, or +to add the item. +.BR tfind () +returns a pointer to the item, or NULL if no match is found. If there are multiple elements that match the key, the element returned is unspecified. .PP -\fBtdelete\fP() returns a pointer to the parent of the item deleted, or +.BR tdelete () +returns a pointer to the parent of the item deleted, or NULL if the item was not found. .PP -\fBtsearch\fP(), \fBtfind\fP(), and \fBtdelete\fP() also +.BR tsearch (), +.BR tfind (), +and +.BR tdelete () +also return NULL if \fIrootp\fP was NULL on entry. .SH WARNINGS -\fBtwalk\fP() takes a pointer to the root, while the other functions +.BR twalk () +takes a pointer to the root, while the other functions take a pointer to a variable which points to the root. .PP -\fBtwalk\fP() uses \fBpostorder\fP to mean "after the left subtree, but +.BR twalk () +uses \fBpostorder\fP to mean "after the left subtree, but before the right subtree". Some authorities would call this "inorder", and reserve "postorder" to mean "after both subtrees". .PP -\fBtdelete\fP() frees the memory required for the node in the tree. +.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 \fBtwalk\fP() makes no +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 |