1.\" $NetBSD$ 2.\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com> 3.\" All rights reserved. 4.\" 5.\" Redistribution and use in source and binary forms, with or without 6.\" modification, are permitted provided that the following conditions 7.\" are met: 8.\" 1. Redistributions of source code must retain the above copyright 9.\" notice, this list of conditions and the following disclaimer. 10.\" 2. Redistributions in binary form must reproduce the above copyright 11.\" notice, this list of conditions and the following disclaimer in the 12.\" documentation and/or other materials provided with the distribution. 13.\" 3. The name of the author may not be used to endorse or promote products 14.\" derived from this software without specific prior written permission. 15.\" 16.\" THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, 17.\" INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY 18.\" AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL 19.\" THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 20.\" EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 21.\" PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; 22.\" OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, 23.\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR 24.\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF 25.\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26.\" 27.\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp 28.\" 29.Dd June 4, 2017 30.Dt TSEARCH 3 31.Os 32.Sh NAME 33.Nm tsearch , tfind , tdelete , twalk 34.Nd manipulate binary search trees 35.Sh SYNOPSIS 36.In search.h 37.Ft void * 38.Fn tdelete "const void * restrict key" "posix_tnode ** restrict rootp" "int (*compar) (const void *, const void *)" 39.Ft posix_tnode * 40.Fn tfind "const void *key" "posix_tnode * const *rootp" "int (*compar) (const void *, const void *)" 41.Ft posix_tnode * 42.Fn tsearch "const void *key" "posix_tnode **rootp" "int (*compar) (const void *, const void *)" 43.Ft void 44.Fn twalk "const posix_tnode *root" "void (*action) (const posix_tnode *, VISIT, int)" 45.Sh DESCRIPTION 46The 47.Fn tdelete , 48.Fn tfind , 49.Fn tsearch , 50and 51.Fn twalk 52functions manage binary search trees. 53This implementation uses a balanced AVL tree, 54which due to its strong theoretical limit on the height of the tree has 55the advantage of calling the comparison function relatively 56infrequently. 57.Pp 58The comparison function passed in by 59the user has the same style of return values as 60.Xr strcmp 3 . 61.Pp 62The 63.Fn tfind 64function 65searches for the datum matched by the argument 66.Fa key 67in the binary tree rooted at 68.Fa rootp , 69returning a pointer to the datum if it is found and NULL 70if it is not. 71.Pp 72The 73.Fn tsearch 74function 75is identical to 76.Fn tfind 77except that if no match is found, 78.Fa key 79is inserted into the tree and a pointer to it is returned. 80If 81.Fa rootp 82points to a NULL value a new binary search tree is created. 83.Pp 84The 85.Fn tdelete 86function 87deletes a node from the specified binary search tree and returns 88a pointer to the parent of the node to be deleted. 89It takes the same arguments as 90.Fn tfind 91and 92.Fn tsearch . 93If the node to be deleted is the root of the binary search tree, 94.Fa rootp 95will be adjusted. 96.Pp 97The 98.Fn twalk 99function 100walks the binary search tree rooted in 101.Fa root 102and calls the function 103.Fa action 104on each node. 105The 106.Fa action 107function 108is called with three arguments: a pointer to the current node, 109a value from the enum 110.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;" 111specifying the traversal type, and a node level (where level 112zero is the root of the tree). 113.Sh RETURN VALUES 114The 115.Fn tsearch 116function returns NULL if allocation of a new node fails (usually 117due to a lack of free memory). 118.Pp 119The 120.Fn tfind , 121.Fn tsearch , 122and 123.Fn tdelete 124functions 125return NULL if 126.Fa rootp 127is NULL or the datum cannot be found. 128.Pp 129The 130.Fn twalk 131function returns no value. 132.Sh EXAMPLES 133This example uses 134.Fn tsearch 135to search for four strings in 136.Dv root . 137Because the strings are not already present, they are added. 138.Fn tsearch 139is called twice on the fourth string to demonstrate that a string is not added when it is already present. 140.Fn tfind 141is used to find the single instance of the fourth string, and 142.Fn tdelete 143removes it. 144Finally, 145.Fn twalk 146is used to return and display the resulting binary search tree. 147.Bd -literal 148#include <stdio.h> 149#include <search.h> 150#include <string.h> 151 152int 153comp(const void *a, const void *b) 154{ 155 156 return strcmp(a, b); 157} 158 159void 160printwalk(const posix_tnode * node, VISIT v, int __unused0) 161{ 162 163 if (v == postorder || v == leaf) { 164 printf("node: %s\en", *(char **)node); 165 } 166} 167 168int 169main(void) 170{ 171 posix_tnode *root = NULL; 172 173 char one[] = "blah1"; 174 char two[] = "blah-2"; 175 char three[] = "blah-3"; 176 char four[] = "blah-4"; 177 178 tsearch(one, &root, comp); 179 tsearch(two, &root, comp); 180 tsearch(three, &root, comp); 181 tsearch(four, &root, comp); 182 tsearch(four, &root, comp); 183 printf("four: %s\en", *(char **)tfind(four, &root, comp)); 184 tdelete(four, &root, comp); 185 186 twalk(root, printwalk); 187 return 0; 188} 189.Ed 190.Sh SEE ALSO 191.Xr bsearch 3 , 192.Xr hsearch 3 , 193.Xr lsearch 3 194.Sh STANDARDS 195These functions conform to 196.St -p1003.1-2008 . 197.Pp 198The 199.Fa posix_tnode 200type is not part of 201.St -p1003.1-2008 , 202but is expected to be standardized by future versions of the standard. 203It is defined as 204.Fa void 205for source-level compatibility. 206Using 207.Fa posix_tnode 208makes distinguishing between nodes and keys easier. 209