.\"     $NetBSD: hashinit.9,v 1.9 2013/09/17 19:58:03 wiz Exp $
.\"
.\" 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.
.\"
.\" 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 July 1, 2008
.Dt HASHINIT 9
.Os
.Sh NAME
.Nm hashinit ,
.Nm hashdone
.Nd kernel hash table construction and destruction
.Sh SYNOPSIS
.In sys/systm.h
.Ft "void *"
.Fo hashinit
.Fa "u_int chains"
.Fa "enum hashtype htype"
.Fa "bool waitok"
.Fa "u_long *hashmask"
.Fc
.Ft void
.Fn hashdone "void *hashtbl" "enum hashtype htype" "u_long hashmask"
.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 .
The customary choice for
.Fa chains
is the maximum number of elements you intend to store divided by
your intended load factor.
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.
Because different data structures from
.Xr queue 3
can define head structures of different sizes, the total size of the
allocated table can vary with the choice of
.Fa htype .
.Pp
If
.Fa waitok
is true,
.Fa hashinit
can wait until enough memory is available.
Otherwise, it immediately fails if there is not enough memory is available.
.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 ,
given the same
.Fa htype
and
.Fa hashmask
that were passed to and returned from
.Fn hashinit .
If the table contains any nonempty chain when
.Fn hashdone
is called, the result is undefined.
.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.
.Fn hashinit
returns
.Dv NULL
on failure.
.Sh CODE REFERENCES
These functions are implemented in
.Pa sys/kern/subr_hash.c .
.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 between 1 and 2.
.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 4.0 .
.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.