Subject: Re: 1. uiopeek? 2. hashinit/hashdone?
To: None <tech-kern@NetBSD.org>
From: Chapman Flack <email@example.com>
Date: 06/04/2006 00:54:38
This is a multi-part message in MIME format.
Content-Type: text/plain; charset=us-ascii; format=flowed
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?
.\" 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
.Nm hashinit ,
.Nd kernel hash table construction and destruction
.Ft "void *"
.Fa "u_int chains"
.Fa "enum hashtype htype"
.Fa "struct malloc_type *mtype"
.Fa "int mflags"
.Fa "u_long *hashmask"
.Fn hashdone "void *hashtbl" "struct malloc_type *mtype"
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 ,
should be the product of the intended load factor and the expected number
of elements to be stored.
.Xr queue 3
can be used to manipulate the chains; pass
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.
arguments are passed to
.Xr malloc 9
to control the allocation.
A value will be stored into
suitable for masking any computed hash, to obtain the index of a chain
head in the allocated table.
function deallocates the storage allocated by
and pointed to by
.Fa hashtbl ,
passing it and
.Xr free 9 .
.Em does not
walk the table and deallocate anything in it, or check that the caller has
.Sh RETURN VALUES
The value returned by
should be cast as pointer to an array of
It can be
only if the specified
.Sh SEE ALSO
.Xr queue 3 ,
.Xr hash 9 ,
.Xr malloc 9
function was present, without the
.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
power of two
.Em not greater than
.Fa chains ;
that is, it built in a load factor usually less than 1.
was the first
release to have a
It resembled that from
but made each slot a
.Xr queue 3 .
it had been changed to size the table to the least power of two
not less than
.Em or equal to
.Fa chains .
it had the
argument and the current sizing rule.
chains selected with
.Fa htype .
with behavior equivalent (as of
.Fx 6.1 )
to that in
.Nx 1.0 ,
that behaves as
but checks that all chains are empty first.
comparable (as of
.Ox 3.9 )
to that of
.Nx 1.4 .
This manual page was added for
.Nx 3.99 .
The only part of the work of implementing a hash table that these functions
relieve is the part that isn't much work.