git.saurik.com Git - apple/libc.git/blame_incremental

... / ...

Commit	Line	Data
	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	.\" $FreeBSD: src/lib/libc/stdlib/tsearch.3,v 1.15 2006/06/23 13:36:33 keramida Exp $
	29	.\"
	30	.Dd June 15, 1997
	31	.Dt TSEARCH 3
	32	.Os
	33	.Sh NAME
	34	.Nm tdelete ,
	35	.Nm tfind ,
	36	.Nm tsearch ,
	37	.Nm twalk
	38	.Nd manipulate binary search trees
	39	.Sh SYNOPSIS
	40	.In search.h
	41	.Ft void *
	42	.Fo tdelete
	43	.Fa "const void *restrict key"
	44	.Fa "void **restrict rootp"
	45	.Fa "int (compar) (const void key1, const void *key2)"
	46	.Fc
	47	.Ft void *
	48	.Fo tfind
	49	.Fa "const void *key"
	50	.Fa "void const rootp"
	51	.Fa "int (compar) (const void key1, const void *key2)"
	52	.Fc
	53	.Ft void *
	54	.Fo tsearch
	55	.Fa "const void *key"
	56	.Fa "void **rootp"
	57	.Fa "int (compar) (const void key1, const void *key2)"
	58	.Fc
	59	.Ft void
	60	.Fo twalk
	61	.Fa "const void *root"
	62	.Fa "void (action) (const void node, VISIT order, int level)"
	63	.Fc
	64	.Sh DESCRIPTION
	65	The
	66	.Fn tdelete ,
	67	.Fn tfind ,
	68	.Fn tsearch ,
	69	and
	70	.Fn twalk
	71	functions manage binary search trees, based on algorithms T and D
	72	from Knuth (6.2.2).
	73	The comparison function passed in by
	74	the user takes two arguments, each of which is a key
	75	pointer.
	76	This function has the same style of return values as
	77	.Xr strcmp 3 .
	78	.Pp
	79	The
	80	.Fn tfind
	81	function
	82	searches for a node whose key matches the argument
	83	.Fa key
	84	in the binary tree rooted at
	85	.Fa rootp ,
	86	returning a pointer to the node if it is found and NULL
	87	if it is not.
	88	.Pp
	89	Note that a node is itself a pointer to the key of the node.
	90	Thus, you should generally cast this result to a
	91	double pointer to the data type stored in the tree, for example
	92	(struct myType **), and use double indirection to retrieve the
	93	original key value.
	94	.Pp
	95	The
	96	.Fn tsearch
	97	function is identical to
	98	.Fn tfind
	99	except that, if no match is found,
	100	it inserts a new node for the
	101	.Fa key
	102	into the tree and returns a pointer to the node.
	103	If
	104	.Fa rootp
	105	points to a NULL value, a new binary search tree is created.
	106	.Pp
	107	The
	108	.Fn tdelete
	109	function deletes a node from the specified binary search tree
	110	and returns a pointer to the parent of the node that was deleted.
	111	It takes the same arguments as
	112	.Fn tfind
	113	and
	114	.Fn tsearch .
	115	If the node to be deleted is the root of the binary search tree,
	116	.Fa rootp
	117	will be adjusted.
	118	.Pp
	119	The
	120	.Fn twalk
	121	function walks the binary search tree rooted in
	122	.Fa root
	123	and calls the function
	124	.Fa action
	125	on each node.
	126	The
	127	.Fa action
	128	function is called with three arguments: a pointer to the current node,
	129	a value from the enum
	130	.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
	131	specifying the traversal type, and a node level (where level
	132	zero is the root of the tree).
	133	.Pp
	134	As
	135	.Fn twalk
	136	traverses the tree, it calls the
	137	.Fa action
	138	function with the traversal type "preorder"
	139	before visiting the left subtree of the
	140	.Fa node ,
	141	with the
	142	traversal type "postorder" before visiting the right subtree
	143	of the
	144	.Fa node ,
	145	and with the traversal type "endorder" after
	146	visiting the right subtree of the
	147	.Fa node .
	148	.Pp.
	149	The
	150	.Fa action
	151	function is called only once for a leaf-node, with the
	152	traversal type "leaf."
	153	.Pp
	154	Note: the names for the traversal types differ somewhat from
	155	common parlance. The traversal type "postorder" corresponds
	156	to what would typically be referred to as in-order, and the
	157	traversal type "endorder" corresponds to what would typically
	158	be referred to as post-order.
	159	.Sh RETURN VALUES
	160	The
	161	.Fn tsearch
	162	function returns NULL if allocation of a new node fails (usually
	163	due to a lack of free memory).
	164	.Pp
	165	The
	166	.Fn tfind ,
	167	.Fn tsearch ,
	168	and
	169	.Fn tdelete
	170	functions
	171	return NULL if
	172	.Fa rootp
	173	is NULL or the node cannot be found.
	174	.Pp
	175	The
	176	.Fn twalk
	177	function returns no value.
	178	.Sh SEE ALSO
	179	.Xr bsearch 3 ,
	180	.Xr hsearch 3 ,
	181	.Xr lsearch 3