467 lines
12 KiB
HTML
467 lines
12 KiB
HTML
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML><HEAD><TITLE>Man page of TSEARCH</TITLE>
|
|
</HEAD><BODY>
|
|
<H1>TSEARCH</H1>
|
|
Section: Linux Programmer's Manual (3)<BR>Updated: 2019-05-09<BR><A HREF="#index">Index</A>
|
|
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
|
|
|
|
<A NAME="lbAB"> </A>
|
|
<H2>NAME</H2>
|
|
|
|
tsearch, tfind, tdelete, twalk, tdestroy - manage a binary search tree
|
|
<A NAME="lbAC"> </A>
|
|
<H2>SYNOPSIS</H2>
|
|
|
|
<PRE>
|
|
<B>#include <<A HREF="file:///usr/include/search.h">search.h</A>></B>
|
|
|
|
<B>typedef enum { preorder, postorder, endorder, leaf } VISIT;</B>
|
|
|
|
<B>void *tsearch(const void *</B><I>key</I><B>, void **</B><I>rootp</I><B>,</B>
|
|
<B> int (*</B><I>compar</I><B>)(const void *, const void *));</B>
|
|
|
|
<B>void *tfind(const void *</B><I>key</I><B>, void *const *</B><I>rootp</I><B>,</B>
|
|
<B> int (*</B><I>compar</I><B>)(const void *, const void *));</B>
|
|
|
|
<B>void *tdelete(const void *</B><I>key</I><B>, void **</B><I>rootp</I><B>,</B>
|
|
<B> int (*</B><I>compar</I><B>)(const void *, const void *));</B>
|
|
|
|
<B>void twalk(const void *</B><I>root</I><B>,</B>
|
|
<B> void (*</B><I>action</I><B>)(const void *</B><I>nodep</I><B>, VISIT </B><I>which</I><B>,</B>
|
|
<B> int </B><I>depth</I><B>));</B>
|
|
|
|
<B>#define _GNU_SOURCE</B> /* See <A HREF="/cgi-bin/man/man2html?7+feature_test_macros">feature_test_macros</A>(7) */
|
|
<B>#include <<A HREF="file:///usr/include/search.h">search.h</A>></B>
|
|
|
|
<B>void twalk_r(const void *</B><I>root</I><B>,</B>
|
|
<B> void (*</B><I>action</I><B>)(const void *</B><I>nodep</I><B>, VISIT </B><I>which</I><B>,</B>
|
|
<B> void *</B><I>closure</I><B>),</B>
|
|
<B> void *</B><I>closure</I><B>);</B>
|
|
|
|
<B>void tdestroy(void *</B><I>root</I><B>, void (*</B><I>free_node</I><B>)(void *</B><I>nodep</I><B>));</B>
|
|
</PRE>
|
|
|
|
<A NAME="lbAD"> </A>
|
|
<H2>DESCRIPTION</H2>
|
|
|
|
<B>tsearch</B>(),
|
|
|
|
<B>tfind</B>(),
|
|
|
|
<B>twalk</B>(),
|
|
|
|
and
|
|
<B>tdelete</B>()
|
|
|
|
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</I>
|
|
|
|
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.
|
|
<P>
|
|
|
|
<B>tsearch</B>()
|
|
|
|
searches the tree for an item.
|
|
<I>key</I>
|
|
|
|
points to the item to be searched for.
|
|
<I>rootp</I>
|
|
|
|
points to a variable which points to the root of the tree.
|
|
If the tree is empty,
|
|
then the variable that
|
|
<I>rootp</I>
|
|
|
|
points to should be set to NULL.
|
|
If the item is found in the tree, then
|
|
<B>tsearch</B>()
|
|
|
|
returns a pointer
|
|
to the corresponding tree node.
|
|
(In other words,
|
|
<B>tsearch</B>()
|
|
|
|
returns a pointer to a pointer to the data item.)
|
|
If the item is not found, then
|
|
<B>tsearch</B>()
|
|
|
|
adds it, and returns a
|
|
pointer to the corresponding tree node.
|
|
<P>
|
|
|
|
<B>tfind</B>()
|
|
|
|
is like
|
|
<B>tsearch</B>(),
|
|
|
|
except that if the item is not
|
|
found, then
|
|
<B>tfind</B>()
|
|
|
|
returns NULL.
|
|
<P>
|
|
|
|
<B>tdelete</B>()
|
|
|
|
deletes an item from the tree.
|
|
Its arguments are the same as for
|
|
<B>tsearch</B>().
|
|
|
|
<P>
|
|
|
|
<B>twalk</B>()
|
|
|
|
performs depth-first, left-to-right traversal of a binary
|
|
tree.
|
|
<I>root</I>
|
|
|
|
points to the starting node for the traversal.
|
|
If that node is not the root, then only part of the tree will be visited.
|
|
<B>twalk</B>()
|
|
|
|
calls the user function
|
|
<I>action</I>
|
|
|
|
each time a node is
|
|
visited (that is, three times for an internal node, and once for a
|
|
leaf).
|
|
<I>action</I>,
|
|
|
|
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
|
|
<B>preorder</B>,
|
|
|
|
<B>postorder</B>,
|
|
|
|
or
|
|
<B>endorder</B>
|
|
|
|
depending on whether this is the first, second, or
|
|
third visit to the internal node,
|
|
or the value
|
|
<B>leaf</B>
|
|
|
|
if this is the single visit to a leaf node.
|
|
(These symbols are defined in
|
|
<I><<A HREF="file:///usr/include/search.h">search.h</A>></I>.)
|
|
|
|
The third argument is the depth of the node;
|
|
the root node has depth zero.
|
|
<P>
|
|
|
|
(More commonly,
|
|
<B>preorder</B>,
|
|
|
|
<B>postorder</B>,
|
|
|
|
and
|
|
<B>endorder</B>
|
|
|
|
are known as
|
|
<B>preorder</B>,
|
|
|
|
<B>inorder</B>,
|
|
|
|
and
|
|
<B>postorder</B>:
|
|
|
|
before visiting the children, after the first and before the second,
|
|
and after visiting the children.
|
|
Thus, the choice of name
|
|
<B>postorder</B>
|
|
|
|
is rather confusing.)
|
|
<P>
|
|
|
|
<B>twalk_r</B>()
|
|
|
|
is similar to
|
|
<B>twalk</B>(),
|
|
|
|
but instead of the
|
|
<I>depth</I>
|
|
|
|
argument, the
|
|
<I>closure</I>
|
|
|
|
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.
|
|
<P>
|
|
|
|
<B>tdestroy</B>()
|
|
|
|
removes the whole tree pointed to by
|
|
<I>root</I>,
|
|
|
|
freeing all resources allocated by the
|
|
<B>tsearch</B>()
|
|
|
|
function.
|
|
For the data in each tree node the function
|
|
<I>free_node</I>
|
|
|
|
is called.
|
|
The pointer to the data is passed as the argument to the function.
|
|
If no such work is necessary,
|
|
<I>free_node</I>
|
|
|
|
must point to a function
|
|
doing nothing.
|
|
<A NAME="lbAE"> </A>
|
|
<H2>RETURN VALUE</H2>
|
|
|
|
<B>tsearch</B>()
|
|
|
|
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.
|
|
<B>tfind</B>()
|
|
|
|
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.
|
|
<P>
|
|
|
|
<B>tdelete</B>()
|
|
|
|
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,
|
|
<B>tdelete</B>()
|
|
|
|
returns a dangling pointer that must not be accessed.
|
|
<P>
|
|
|
|
<B>tsearch</B>(),
|
|
|
|
<B>tfind</B>(),
|
|
|
|
and
|
|
<B>tdelete</B>()
|
|
|
|
also
|
|
return NULL if
|
|
<I>rootp</I>
|
|
|
|
was NULL on entry.
|
|
<A NAME="lbAF"> </A>
|
|
<H2>VERSIONS</H2>
|
|
|
|
<B>twalk_r</B>()
|
|
|
|
is available in glibc since version 2.30.
|
|
<A NAME="lbAG"> </A>
|
|
<H2>ATTRIBUTES</H2>
|
|
|
|
For an explanation of the terms used in this section, see
|
|
<B><A HREF="/cgi-bin/man/man2html?7+attributes">attributes</A></B>(7).
|
|
|
|
<TABLE BORDER>
|
|
<TR VALIGN=top><TD><B>Interface</B></TD><TD><B>Attribute</B></TD><TD><B>Value</B><BR></TD></TR>
|
|
<TR VALIGN=top><TD>
|
|
<B>tsearch</B>(),
|
|
|
|
<B>tfind</B>(),
|
|
|
|
<BR>
|
|
|
|
<B>tdelete</B>()
|
|
|
|
</TD><TD>Thread safety</TD><TD>MT-Safe race:rootp<BR></TD></TR>
|
|
<TR VALIGN=top><TD>
|
|
<B>twalk</B>()
|
|
|
|
</TD><TD>Thread safety</TD><TD>MT-Safe race:root<BR></TD></TR>
|
|
<TR VALIGN=top><TD>
|
|
<B>twalk_r</B>()
|
|
|
|
</TD><TD>Thread safety</TD><TD>MT-Safe race:root<BR></TD></TR>
|
|
<TR VALIGN=top><TD>
|
|
<B>tdestroy</B>()
|
|
|
|
</TD><TD>Thread safety</TD><TD>MT-Safe<BR></TD></TR>
|
|
</TABLE>
|
|
|
|
<A NAME="lbAH"> </A>
|
|
<H2>CONFORMING TO</H2>
|
|
|
|
POSIX.1-2001, POSIX.1-2008, SVr4.
|
|
The functions
|
|
<B>tdestroy</B>()
|
|
|
|
and
|
|
<B>twalk_r</B>()
|
|
|
|
are GNU extensions.
|
|
<A NAME="lbAI"> </A>
|
|
<H2>NOTES</H2>
|
|
|
|
<B>twalk</B>()
|
|
|
|
takes a pointer to the root, while the other functions
|
|
take a pointer to a variable which points to the root.
|
|
<P>
|
|
|
|
<B>tdelete</B>()
|
|
|
|
frees the memory required for the node in the tree.
|
|
The user is responsible for freeing the memory for the corresponding
|
|
data.
|
|
<P>
|
|
|
|
The example program depends on the fact that
|
|
<B>twalk</B>()
|
|
|
|
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.
|
|
<A NAME="lbAJ"> </A>
|
|
<H2>EXAMPLE</H2>
|
|
|
|
The following program inserts twelve random numbers into a binary
|
|
tree, where duplicate numbers are collapsed, then prints the numbers
|
|
in order.
|
|
<P>
|
|
|
|
|
|
#define _GNU_SOURCE /* Expose declaration of tdestroy() */
|
|
#include <<A HREF="file:///usr/include/search.h">search.h</A>>
|
|
#include <<A HREF="file:///usr/include/stdlib.h">stdlib.h</A>>
|
|
#include <<A HREF="file:///usr/include/stdio.h">stdio.h</A>>
|
|
#include <<A HREF="file:///usr/include/time.h">time.h</A>>
|
|
<P>
|
|
static void *root = NULL;
|
|
<P>
|
|
static void *
|
|
xmalloc(unsigned n)
|
|
{
|
|
<BR> void *p;
|
|
<BR> p = <A HREF="/cgi-bin/man/man2html?n+malloc">malloc</A>(n);
|
|
<BR> if (p)
|
|
<BR> return p;
|
|
<BR> fprintf(stderr, "insufficient memory\n");
|
|
<BR> exit(EXIT_FAILURE);
|
|
}
|
|
<P>
|
|
static int
|
|
compare(const void *pa, const void *pb)
|
|
{
|
|
<BR> if (*(int *) pa < *(int *) pb)
|
|
<BR> return -1;
|
|
<BR> if (*(int *) pa > *(int *) pb)
|
|
<BR> return 1;
|
|
<BR> return 0;
|
|
}
|
|
<P>
|
|
static void
|
|
action(const void *nodep, VISIT which, int depth)
|
|
{
|
|
<BR> int *datap;
|
|
<P>
|
|
<BR> switch (which) {
|
|
<BR> case preorder:
|
|
<BR> break;
|
|
<BR> case postorder:
|
|
<BR> datap = *(int **) nodep;
|
|
<BR> printf("%6d\n", *datap);
|
|
<BR> break;
|
|
<BR> case endorder:
|
|
<BR> break;
|
|
<BR> case leaf:
|
|
<BR> datap = *(int **) nodep;
|
|
<BR> printf("%6d\n", *datap);
|
|
<BR> break;
|
|
<BR> }
|
|
}
|
|
<P>
|
|
int
|
|
main(void)
|
|
{
|
|
<BR> int i, *ptr;
|
|
<BR> void *val;
|
|
<P>
|
|
<BR> srand(time(NULL));
|
|
<BR> for (i = 0; i < 12; i++) {
|
|
<BR> ptr = xmalloc(sizeof(int));
|
|
<BR> *ptr = rand() & 0xff;
|
|
<BR> val = tsearch((void *) ptr, &root, compare);
|
|
<BR> if (val == NULL)
|
|
<BR> exit(EXIT_FAILURE);
|
|
<BR> else if ((*(int **) val) != ptr)
|
|
<BR> free(ptr);
|
|
<BR> }
|
|
<BR> twalk(root, action);
|
|
<BR> tdestroy(root, free);
|
|
<BR> exit(EXIT_SUCCESS);
|
|
}
|
|
|
|
<A NAME="lbAK"> </A>
|
|
<H2>SEE ALSO</H2>
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+bsearch">bsearch</A></B>(3),
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+hsearch">hsearch</A></B>(3),
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+lsearch">lsearch</A></B>(3),
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+qsort">qsort</A></B>(3)
|
|
|
|
<A NAME="lbAL"> </A>
|
|
<H2>COLOPHON</H2>
|
|
|
|
This page is part of release 5.05 of the Linux
|
|
<I>man-pages</I>
|
|
|
|
project.
|
|
A description of the project,
|
|
information about reporting bugs,
|
|
and the latest version of this page,
|
|
can be found at
|
|
<A HREF="https://www.kernel.org/doc/man-pages/.">https://www.kernel.org/doc/man-pages/.</A>
|
|
<P>
|
|
|
|
<HR>
|
|
<A NAME="index"> </A><H2>Index</H2>
|
|
<DL>
|
|
<DT id="1"><A HREF="#lbAB">NAME</A><DD>
|
|
<DT id="2"><A HREF="#lbAC">SYNOPSIS</A><DD>
|
|
<DT id="3"><A HREF="#lbAD">DESCRIPTION</A><DD>
|
|
<DT id="4"><A HREF="#lbAE">RETURN VALUE</A><DD>
|
|
<DT id="5"><A HREF="#lbAF">VERSIONS</A><DD>
|
|
<DT id="6"><A HREF="#lbAG">ATTRIBUTES</A><DD>
|
|
<DT id="7"><A HREF="#lbAH">CONFORMING TO</A><DD>
|
|
<DT id="8"><A HREF="#lbAI">NOTES</A><DD>
|
|
<DT id="9"><A HREF="#lbAJ">EXAMPLE</A><DD>
|
|
<DT id="10"><A HREF="#lbAK">SEE ALSO</A><DD>
|
|
<DT id="11"><A HREF="#lbAL">COLOPHON</A><DD>
|
|
</DL>
|
|
<HR>
|
|
This document was created by
|
|
<A HREF="/cgi-bin/man/man2html">man2html</A>,
|
|
using the manual pages.<BR>
|
|
Time: 00:05:58 GMT, March 31, 2021
|
|
</BODY>
|
|
</HTML>
|