hashinit(9) [netbsd man page]

HASHINIT(9)						   BSD Kernel Developer's Manual					       HASHINIT(9)

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

     The 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 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.

SEE ALSO

     queue(3), hash(9), malloc(9)

CODE REFERENCES

     These functions are implemented in sys/kern/subr_hash.c.

HISTORY

     A hashinit() function was present, without the htype or mflags arguments, in 4.4BSD alpha.  It was independent of queue(3) and simply allo-
     cated 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.

BSD
								   July 1, 2008 							       BSD

HASHINIT(9)						   BSD Kernel Developer's Manual					       HASHINIT(9)

NAME

     hashinit, hashinit_flags, hashdestroy, phashinit -- manage kernel hash tables

SYNOPSIS

     #include <sys/malloc.h>
     #include <sys/systm.h>
     #include <sys/queue.h>

     void *
     hashinit(int nelements, struct malloc_type *type, u_long *hashmask);

     void
     hashinit_flags(int nelements, struct malloc_type *type, u_long *hashmask, int flags);

     void
     hashdestroy(void *hashtbl, struct malloc_type *type, u_long hashmask);

     void *
     phashinit(int nelements, struct malloc_type *type, u_long *nentries);

DESCRIPTION

     The hashinit(), hashinit_flags() and phashinit() functions allocate space for hash tables of size given by the argument nelements.

     The hashinit() function allocates hash tables that are sized to largest power of two less than or equal to argument nelements.  The
     phashinit() function allocates hash tables that are sized to the largest prime number less than or equal to argument nelements.  The
     hashinit_flags() function operates like hashinit() but also accepts an additional argument flags which control various options during alloca-
     tion.  Allocated hash tables are contiguous arrays of LIST_HEAD(3) entries, allocated using malloc(9), and initialized using LIST_INIT(3).
     The malloc arena to be used for allocation is pointed to by argument type.

     The hashdestroy() function frees the space occupied by the hash table pointed to by argument hashtbl.  Argument type determines the malloc
     arena to use when freeing space.  The argument hashmask should be the bit mask returned by the call to hashinit() that allocated the hash ta-
     ble.  The argument flags must be used with one of the following values.

	   HASH_NOWAIT	Any malloc performed by the hashinit_flags() function will not be allowed to wait, and therefore may fail.
	   HASH_WAITOK	Any malloc performed by the hashinit_flags() function is allowed to wait for memory.

IMPLEMENTATION NOTES

     The largest prime hash value chosen by phashinit() is 32749.

RETURN VALUES

     The hashinit() function returns a pointer to an allocated hash table and sets the location pointed to by hashmask to the bit mask to be used
     for computing the correct slot in the hash table.

     The phashinit() function returns a pointer to an allocated hash table and sets the location pointed to by nentries to the number of rows in
     the hash table.

EXAMPLES

     A typical example is shown below:

	   ...
	   static LIST_HEAD(foo, foo) *footable;
	   static u_long foomask;
	   ...
	   footable = hashinit(32, M_FOO, &foomask);

     Here we allocate a hash table with 32 entries from the malloc arena pointed to by M_FOO.  The mask for the allocated hash table is returned
     in foomask.  A subsequent call to hashdestroy() uses the value in foomask:

	   ...
	   hashdestroy(footable, M_FOO, foomask);

DIAGNOSTICS

     The hashinit() and phashinit() functions will panic if argument nelements is less than or equal to zero.

     The hashdestroy() function will panic if the hash table pointed to by hashtbl is not empty.

SEE ALSO

     LIST_HEAD(3), malloc(9)

BUGS

     There is no phashdestroy() function, and using hashdestroy() to free a hash table allocated by phashinit() usually has grave consequences.

BSD
								 October 10, 2004							       BSD