2fe8fb192f
There is important information about booting non-ack images in docs/UPDATING. ack/aout-format images can't be built any more, and booting clang/ELF-format ones is a little different. Updating to the new boot monitor is recommended. Changes in this commit: . drop boot monitor -> allowing dropping ack support . facility to copy ELF boot files to /boot so that old boot monitor can still boot fairly easily, see UPDATING . no more ack-format libraries -> single-case libraries . some cleanup of OBJECT_FMT, COMPILER_TYPE, etc cases . drop several ack toolchain commands, but not all support commands (e.g. aal is gone but acksize is not yet). . a few libc files moved to netbsd libc dir . new /bin/date as minix date used code in libc/ . test compile fix . harmonize includes . /usr/lib is no longer special: without ack, /usr/lib plays no kind of special bootstrapping role any more and bootstrapping is done exclusively through packages, so releases depend even less on the state of the machine making them now. . rename nbsd_lib* to lib* . reduce mtree
142 lines
4.3 KiB
Groff
142 lines
4.3 KiB
Groff
.\" $NetBSD: tsearch.3,v 1.12 2010/04/30 10:09:23 jruoho Exp $
|
|
.\" Copyright (c) 1997 Todd C. Miller <Todd.Miller@courtesan.com>
|
|
.\" All rights reserved.
|
|
.\"
|
|
.\" Redistribution and use in source and binary forms, with or without
|
|
.\" modification, are permitted provided that the following conditions
|
|
.\" are met:
|
|
.\" 1. Redistributions of source code must retain the above copyright
|
|
.\" notice, this list of conditions and the following disclaimer.
|
|
.\" 2. Redistributions in binary form must reproduce the above copyright
|
|
.\" notice, this list of conditions and the following disclaimer in the
|
|
.\" documentation and/or other materials provided with the distribution.
|
|
.\" 3. The name of the author may not be used to endorse or promote products
|
|
.\" derived from this software without specific prior written permission.
|
|
.\"
|
|
.\" THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
|
|
.\" INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
|
|
.\" AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
|
|
.\" THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
.\" EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
.\" PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
|
|
.\" OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
|
|
.\" WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
|
|
.\" OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
|
|
.\" ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
.\"
|
|
.\" OpenBSD: tsearch.3,v 1.2 1998/06/21 22:13:49 millert Exp
|
|
.\"
|
|
.Dd April 30, 2010
|
|
.Dt TSEARCH 3
|
|
.Os
|
|
.Sh NAME
|
|
.Nm tsearch, tfind, tdelete, twalk
|
|
.Nd manipulate binary search trees
|
|
.Sh SYNOPSIS
|
|
.In search.h
|
|
.Ft void *
|
|
.Fn tdelete "const void * restrict key" "void ** restrict rootp" "int (*compar) (const void *, const void *)"
|
|
.Ft void *
|
|
.Fn tfind "const void *key" "const void * const *rootp" "int (*compar) (const void *, const void *)"
|
|
.Ft void *
|
|
.Fn tsearch "const void *key" "void **rootp" "int (*compar) (const void *, const void *)"
|
|
.Ft void
|
|
.Fn twalk "const void *root" "void (*action) (const void *, VISIT, int)"
|
|
.Sh DESCRIPTION
|
|
The
|
|
.Fn tdelete ,
|
|
.Fn tfind ,
|
|
.Fn tsearch ,
|
|
and
|
|
.Fn twalk
|
|
functions manage binary search trees based on algorithms T and D
|
|
from Knuth (6.2.2).
|
|
The comparison function passed in by
|
|
the user has the same style of return values as
|
|
.Xr strcmp 3 .
|
|
.Pp
|
|
.Fn tfind
|
|
searches for the datum matched by the argument
|
|
.Fa key
|
|
in the binary tree rooted at
|
|
.Fa rootp ,
|
|
returning a pointer to the datum if it is found and NULL
|
|
if it is not.
|
|
.Pp
|
|
.Fn tsearch
|
|
is identical to
|
|
.Fn tfind
|
|
except that if no match is found,
|
|
.Fa key
|
|
is inserted into the tree and a pointer to it is returned.
|
|
If
|
|
.Fa rootp
|
|
points to a NULL value a new binary search tree is created.
|
|
.Pp
|
|
.Fn tdelete
|
|
deletes a node from the specified binary search tree and returns
|
|
a pointer to the parent of the node to be deleted.
|
|
It takes the same arguments as
|
|
.Fn tfind
|
|
and
|
|
.Fn tsearch .
|
|
If the node to be deleted is the root of the binary search tree,
|
|
.Fa rootp
|
|
will be adjusted.
|
|
.Pp
|
|
.Fn twalk
|
|
walks the binary search tree rooted in
|
|
.Va root
|
|
and calls the function
|
|
.Fa action
|
|
on each node.
|
|
.Fa Action
|
|
is called with three arguments: a pointer to the current node,
|
|
a value from the enum
|
|
.Sy "typedef enum { preorder, postorder, endorder, leaf } VISIT;"
|
|
specifying the traversal type, and a node level (where level
|
|
zero is the root of the tree).
|
|
.Sh RETURN VALUES
|
|
The
|
|
.Fn tsearch
|
|
function returns NULL if allocation of a new node fails (usually
|
|
due to a lack of free memory).
|
|
.Pp
|
|
.Fn tfind ,
|
|
.Fn tsearch ,
|
|
and
|
|
.Fn tdelete
|
|
return NULL if
|
|
.Fa rootp
|
|
is NULL or the datum cannot be found.
|
|
.Pp
|
|
The
|
|
.Fn twalk
|
|
function returns no value.
|
|
.Sh SEE ALSO
|
|
.Xr bsearch 3 ,
|
|
.Xr hsearch 3 ,
|
|
.Xr lsearch 3
|
|
.Sh STANDARDS
|
|
These functions conform to
|
|
.St -p1003.1-2001 .
|
|
.Sh CAVEATS
|
|
The
|
|
.St -p1003.1-2001
|
|
standard does not specify what value should be returned when deleting
|
|
the root node.
|
|
Since implementations vary, user of
|
|
.Fn tdelete
|
|
should not rely on any specific behaviour.
|
|
The
|
|
.St -p1003.1-2008
|
|
revision tried to clarify the issue with the following wording:
|
|
.Do
|
|
the
|
|
.Fn tdelete
|
|
function shall return a pointer to the parent of the deleted node,
|
|
or an unspecified non-NULL pointer if the deleted node was the root node, or a
|
|
.Dv NULL
|
|
pointer if the node is not found
|
|
.Dc .
|