This is a multi-part message in MIME format.
--------------070205010100040808070605
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

To my question about a man page for hashinit/hashdone, I received
one suggestion to import the man page from obsd. However, it turns
out that there are both obvious and subtle differences, so I simply
wrote one to fit. Any objections?

-Chap

--------------070205010100040808070605
Content-Type: text/plain;
 name="hashinit.9"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="hashinit.9"

.\"     $NetBSD$
.\"
.\" Copyright (c) 2006 The NetBSD Foundation, Inc.
.\" All rights reserved.
.\"
.\" This code is derived from software contributed to The NetBSD Foundation
.\" by Chapman Flack.
.\"
.\" 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. Neither the name of The NetBSD Foundation nor the names of its
.\"    contributors may be used to endorse or promote products derived
.\"    from this software without specific prior written permission.
.\"
.\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
.\" ``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 FOUNDATION OR CONTRIBUTORS
.\" 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.
.\"
.Dd June 3, 2006
.Dt HASHINIT 9
.Os
.Sh NAME
.Nm hashinit ,
.Nm hashdone
.Nd kernel hash table construction and destruction
.Sh SYNOPSIS
.In sys/malloc.h
.In sys/systm.h
.Ft "void *"
.Fo hashinit
.Fa "u_int chains"
.Fa "enum hashtype htype"
.Fa "struct malloc_type *mtype"
.Fa "int mflags"
.Fa "u_long *hashmask"
.Fc
.Ft void
.Fn hashdone "void *hashtbl" "struct malloc_type *mtype"
.Sh DESCRIPTION
The
.Fn hashinit
function allocates and initializes space for a simple chaining hash table.
The number of slots will be the least power of two not smaller than
.Fa chains ,
where
.Fa chains
should be the product of the intended load factor and the expected number
of elements to be stored.
The
.Dv LIST...
or
.Dv TAILQ...
macros of
.Xr queue 3
can be used to manipulate the chains; pass
.Dv HASH_LIST
or
.Dv HASH_TAILQ
as
.Fa htype
to indicate which. Each slot will be initialized as the head of an empty
chain of the proper type. Note that the total size of the allocated table
will therefore depend on the head size of the chosen chain type.
.Pp
The
.Fa mtype
and
.Fa mflags
arguments are passed to
.Xr malloc 9
to control the allocation.
.Pp
A value will be stored into
.Fa *hashmask
suitable for masking any computed hash, to obtain the index of a chain
head in the allocated table.
.Pp
The
.Fn hashdone
function deallocates the storage allocated by
.Fn hashinit
and pointed to by
.Fa hashtbl ,
passing it and
.Fa mtype
to
.Xr free 9 .
It
.Em does not
walk the table and deallocate anything in it, or check that the caller has
done so.
.Sh RETURN VALUES
The value returned by
.Fn hashinit
should be cast as pointer to an array of
.Dv LIST_HEAD
or 
.Dv TAILQ_HEAD
as appropriate.
It can be
.Dv NULL
only if the specified
.Fa mflags
allow it.
.Sh SEE ALSO
.Xr queue 3 ,
.Xr hash 9 ,
.Xr malloc 9
.Sh HISTORY
A
.Fn hashinit
function was present, without the
.Fa htype
or
.Fa mflags
arguments, in
.Bx 4.4 alpha .
It was independent of
.Xr queue 3
and simply allocated and nulled a table of pointer-sized slots.
It sized the table to the
.Em largest
power of two
.Em not greater than
.Fa chains ;
that is, it built in a load factor usually less than 1.
.Pp
.Nx 1.0
was the first
.Nx
release to have a
.Fn hashinit
function.
It resembled that from
.Bx 4.4
but made each slot a
.Dv LIST_HEAD
from
.Xr queue 3 .
For
.Nx 1.3.3
it had been changed to size the table to the least power of two
not less than
.Em or equal to
.Fa chains .
By
.Nx 1.4
it had the
.Fa mflags
argument and the current sizing rule.
.Pp
.Nx 1.5
had the
.Fn hashdone
function.
By
.Nx 1.6
.Fn hashinit
supported
.Dv LIST
or
.Dv TAILQ
chains selected with
.Fa htype .
.Pp
.Fx
has a
.Fn hashinit
with behavior equivalent (as of
.Fx 6.1 )
to that in
.Nx 1.0 ,
and a
.Fn hashdestroy
that behaves as
.Fn hashdone
but checks that all chains are empty first.
.Ox
has a
.Fn hashinit
comparable (as of
.Ox 3.9 )
to that of
.Nx 1.4 .
This manual page was added for
.Nx 3.99 .
.Sh BUGS
The only part of the work of implementing a hash table that these functions
relieve is the part that isn't much work.

--------------070205010100040808070605--