1.\" $OpenBSD: tsearch.3,v 1.22 2022/03/31 17:27:16 naddy Exp $ 2.\" 3.\" Copyright (c) 1997 Todd C. Miller <millert@openbsd.org> 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: March 31 2022 $ 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.In 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. 71If the node to be deleted is the root of the binary search tree, 72.Fa rootp 73will be adjusted and an unspecified non-null pointer will be returned. 74It takes the same arguments as 75.Fn tfind 76and 77.Fn tsearch . 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 tdelete 100returns a pointer to the parent of the deleted node or an unspecified 101non-null pointer if the root node is deleted. 102.Pp 103.Fn tfind , 104.Fn tsearch , 105and 106.Fn tdelete 107return 108.Dv NULL 109if 110.Fa rootp 111is 112.Dv NULL 113or the datum cannot be found. 114.Sh SEE ALSO 115.Xr bsearch 3 , 116.Xr lsearch 3 117.Sh STANDARDS 118These functions conform to 119.St -p1003.1-2008 . 120.Sh CAVEATS 121The value returned when deleting the root node was unspecified before 122the 123.St -p1003.1-2008 124standard, so users of the 125.Fn tdelete 126function should be wary of relying on a specific behaviour. 127