1.\" $OpenBSD: tsearch.3,v 1.16 2007/05/31 19:19:32 jmc Exp $ 2.\" 3.\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com> 4.\" 5.\" Permission to use, copy, modify, and distribute this software for any 6.\" purpose with or without fee is hereby granted, provided that the above 7.\" copyright notice and this permission notice appear in all copies. 8.\" 9.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES 10.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF 11.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR 12.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES 13.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN 14.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF 15.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. 16.\" 17.Dd $Mdocdate: May 31 2007 $ 18.Dt TSEARCH 3 19.Os 20.Sh NAME 21.Nm tsearch , 22.Nm tfind , 23.Nm tdelete , 24.Nm twalk 25.Nd manipulate binary search trees 26.Sh SYNOPSIS 27.Fd #include <search.h> 28.Ft void * 29.Fn tdelete "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" 30.Ft void * 31.Fn tfind "const void *key" "void * const *rootp" "int (*compar) (const void *, const void *)" 32.Ft void * 33.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)" 34.Ft void 35.Fn twalk "const void *root" "void (*action) (const void *, VISIT, int)" 36.Sh DESCRIPTION 37The 38.Fn tdelete , 39.Fn tfind , 40.Fn tsearch , 41and 42.Fn twalk 43functions manage binary search trees based on algorithms T and D 44from Knuth (6.2.2). 45The comparison function passed in by 46the user has the same style of return values as 47.Xr strcmp 3 . 48.Pp 49.Fn tfind 50searches for the datum matched by the argument 51.Fa key 52in the binary tree rooted at 53.Fa rootp , 54returning a pointer to the datum if it is found and 55.Dv NULL 56if it is not. 57.Pp 58.Fn tsearch 59is identical to 60.Fn tfind 61except that if no match is found, 62.Fa key 63is inserted into the tree and a pointer to it is returned. 64If 65.Fa rootp 66points to a null value a new binary search tree is created. 67.Pp 68.Fn tdelete 69deletes a node from the specified binary search tree and returns 70a pointer to the parent of the node to be deleted. 71It takes the same arguments as 72.Fn tfind 73and 74.Fn tsearch . 75If the node to be deleted is the root of the binary search tree, 76.Fa rootp 77will be adjusted and a pointer to the new root will be returned. 78.Pp 79.Fn twalk 80walks the binary search tree rooted in 81.Fa root 82and calls the function 83.Fa action 84on each node. 85.Fa action 86is called with three arguments: a pointer to the current node, 87a value from the enum 88.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;" 89specifying the traversal type, and a node level (where level 90zero is the root of the tree). 91.Sh RETURN VALUES 92The 93.Fn tsearch 94function returns 95.Dv NULL 96if allocation of a new node fails (usually 97due to a lack of free memory). 98.Pp 99.Fn tfind , 100.Fn tsearch , 101and 102.Fn tdelete 103return 104.Dv NULL 105if 106.Fa rootp 107is 108.Dv NULL 109or the datum cannot be found. 110.Pp 111The 112.Fn twalk 113function returns no value. 114.Sh SEE ALSO 115.Xr bsearch 3 , 116.Xr lsearch 3 117.Sh STANDARDS 118These functions conform to 119.St -p1003.1-2004 . 120.Sh CAVEATS 121The 122.St -p1003.1-2004 123standard does not specify what value should be returned when deleting the 124root node. 125Since implementations vary, the user of the 126.Fn tdelete 127function should not rely on a specific behaviour. 128