diff options
Diffstat (limited to 'man3/tsearch.3')
| -rw-r--r-- | man3/tsearch.3 | 200 |
1 files changed, 200 insertions, 0 deletions
diff --git a/man3/tsearch.3 b/man3/tsearch.3 new file mode 100644 index 000000000..f592f3bf8 --- /dev/null +++ b/man3/tsearch.3 @@ -0,0 +1,200 @@ +.\" Hey Emacs! This file is -*- nroff -*- source. +.\" Copyright 1995 by Jim Van Zandt <jrv@vanzandt.mv.com> +.\" +.\" Permission is granted to make and distribute verbatim copies of this +.\" manual provided the copyright notice and this permission notice are +.\" preserved on all copies. +.\" +.\" Permission is granted to copy and distribute modified versions of this +.\" manual under the conditions for verbatim copying, provided that the +.\" entire resulting derived work is distributed under the terms of a +.\" permission notice identical to this one. +.\" +.\" Since the Linux kernel and libraries are constantly changing, this +.\" manual page may be incorrect or out-of-date. The author(s) assume no +.\" responsibility for errors or omissions, or for damages resulting from +.\" the use of the information contained herein. The author(s) may not +.\" have taken the same level of care in the production of this manual, +.\" which is licensed free of charge, as they might when working +.\" professionally. +.\" +.\" Formatted or processed versions of this manual, if unaccompanied by +.\" the source, must acknowledge the copyright and authors of this work. +.\" +.TH TSEARCH 3 1995-09-24 "GNU" "Linux Programmer's Manual" +.SH NAME +tsearch, tfind, tdelete, twalk \- manage a binary tree +.SH SYNOPSIS +.nf +.B #include <search.h> +.sp +.BI "void *tsearch(const void *" key ", void **" rootp , +.BI " int(*" compar ")(const void *, const void *));" +.sp +.BI "void *tfind(const void *" key ", const void **" rootp , +.BI " int(*" compar ")(const void *, const void *));" +.sp +.BI "void *tdelete(const void *" key ", void **" rootp , +.BI " int(*" compar ")(const void *, const void *));" +.sp +.BI "void twalk(const void *" root ", void(*" action ")(const void *" nodep , +.BI " const VISIT " which , +.BI " const int " depth "));" +.sp +.B #define _GNU_SOURCE +.br +.B #include <search.h> +.sp +.BI "void tdestroy (void *" root ", void (*" free_node ")(void *" nodep )); +.RE +.fi +.SH DESCRIPTION +\fBtsearch\fP, \fBtfind\fP, \fBtwalk\fP, and \fBtdelete\fP 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 +corresponding data item. (The calling program must store the actual +data.) \fIcompar\fP 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 +\fBtsearch\fP 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 \fBNULL\fP. +If the item is found in the tree, then \fBtsearch\fP returns a pointer +to it. If it is not found, then \fBtsearch\fP 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 \fBNULL\fP. +.PP +\fBtdelete\fP deletes an item from the tree. Its arguments are the +same as for \fBtsearch\fP. +.PP +\fBtwalk\fP 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 +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. The second is an integer which +takes on the values \fBpreorder\fP, \fBpostorder\fP, and +\fBendorder\fP depending on whether this is the first, second, or +third visit to the internal node, or \fBleaf\fP if it is the single +visit to a leaf node. (These symbols are defined in +\fI<search.h>\fP.) The third argument is the depth of the node, with +zero being the root. +.PP +(More commonly, \fBpreorder\fP, \fBpostorder\fP, and \fBendorder\fP +are known as \fBpreorder\fP, \fBinorder\fP, and \fBpostorder\fP: +before visiting the children, after the first and before the second, +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 \fIrootp\fP, +freeing all resources allocated by the \fBtsearch\fP 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 +the newly added item, or \fBNULL\fP if there was insufficient memory +to add the item. \fBtfind\fP returns a pointer to the item, or +\fBNULL\fP 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 +\fBNULL\fP if the item was not found. +.PP +\fBtsearch\fP, \fBtfind\fP, and \fBtdelete\fP also +return \fBNULL\fP if \fIrootp\fP was \fBNULL\fP on entry. +.SH WARNINGS +\fBtwalk\fP 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 +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. +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 +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 SysV documentation. +.SH EXAMPLE +The following program inserts twelve random numbers into a binary +tree, where duplicate numbers are collapsed, then prints the numbers +in order. +.sp +.nf + #include <search.h> + #include <stdlib.h> + #include <stdio.h> + #include <time.h> + + void *root = NULL; + + void *xmalloc(unsigned n) { + void *p; + p = malloc(n); + if (p) return p; + fprintf(stderr, "insufficient memory\\n"); + exit(1); + } + + int compare(const void *pa, const void *pb) { + if (*(int *)pa < *(int *)pb) return -1; + if (*(int *)pa > *(int *)pb) return 1; + return 0; + } + + void action(const void *nodep, const VISIT which, const int depth) { + int *datap; + + switch(which) { + case preorder: + break; + case postorder: + datap = *(int **)nodep; + printf("%6d\\n", *datap); + break; + case endorder: + break; + case leaf: + datap = *(int **)nodep; + printf("%6d\\n", *datap); + break; + } + } + + int main() { + int i, *ptr; + void *val; + + srand(time(NULL)); + for (i = 0; i < 12; i++) { + ptr = (int *)xmalloc(sizeof(int)); + *ptr = rand()&0xff; + val = tsearch((void *)ptr, &root, compare); + if (val == NULL) exit(1); + } + twalk(root, action); + return 0; + } +.fi +.SH "CONFORMING TO" +SVID. +The function +.B tdestroy() +is a GNU extension. +.SH "SEE ALSO" +.BR bsearch (3), +.BR hsearch (3), +.BR lsearch (3), +.BR qsort (3) |