NAME
hashinit, hashdone
— kernel hash table construction
and destruction
SYNOPSIS
#include
<sys/systm.h>
void *
hashinit(u_int chains,
enum hashtype htype, bool
waitok, u_long *hashmask);
void
hashdone(void
*hashtbl, enum hashtype
htype, u_long
hashmask);
DESCRIPTION
Thehashinit()
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
chains. The customary choice for
chains is the maximum number of elements you intend to
store divided by your intended load factor. The
LIST... or TAILQ... macros of
queue(3) can be used to manipulate the chains; pass
HASH_LIST or HASH_TAILQ as
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 queue(3) can define head structures of different sizes, the
total size of the allocated table can vary with the choice of
htype.
If waitok is true, hashinit can wait until enough memory is available. Otherwise, it immediately fails if there is not enough memory is available.
A value will be stored into *hashmask suitable for masking any computed hash, to obtain the index of a chain head in the allocated table.
The
hashdone()
function deallocates the storage allocated by
hashinit() and pointed to by
hashtbl, given the same htype
and hashmask that were passed to and returned from
hashinit(). If the table contains any nonempty chain
when hashdone() is called, the result is
undefined.
RETURN VALUES
The value returned by hashinit() should be
cast as pointer to an array of LIST_HEAD or
TAILQ_HEAD as appropriate.
hashinit() returns NULL on
failure.
CODE REFERENCES
These functions are implemented in sys/kern/subr_hash.c.
SEE ALSO
HISTORY
A hashinit() function was present, without
the htype or mflags arguments,
in 4.4BSD-Alpha. It was independent of
queue(3) and simply allocated and nulled a table of pointer-sized
slots. It sized the table to the
largest
power of two not
greater than chains; that is, it built in a
load factor between 1 and 2.
NetBSD 1.0 was the first
NetBSD release to have a
hashinit() function. It resembled that from
4.4BSD but made each slot a
LIST_HEAD from
queue(3). For NetBSD 1.3.3 it had been
changed to size the table to the least power of two not less than
or equal to
chains. By NetBSD 1.4 it had
the mflags argument and the current sizing rule.
NetBSD 1.5 had the
hashdone() function. By NetBSD
1.6 hashinit() supported
LIST or TAILQ chains
selected with htype.
FreeBSD has a
hashinit() with behavior equivalent (as of
FreeBSD 6.1) to that in NetBSD
1.0, and a hashdestroy() that behaves as
hashdone() but checks that all chains are empty
first. OpenBSD has a
hashinit() comparable (as of
OpenBSD 3.9) to that of NetBSD
1.4. This manual page was added for NetBSD
4.0.
BUGS
The only part of the work of implementing a hash table that these functions relieve is the part that isn't much work.