1.\" 2.\" Copyright (c) 2004 Joseph Koshy 3.\" All rights reserved. 4.\" 5.\" Redistribution and use in source and binary forms, with or without 6.\" modification, are permitted provided that the following conditions 7.\" are met: 8.\" 1. Redistributions of source code must retain the above copyright 9.\" notice, this list of conditions and the following disclaimer. 10.\" 2. Redistributions in binary form must reproduce the above copyright 11.\" notice, this list of conditions and the following disclaimer in the 12.\" documentation and/or other materials provided with the distribution. 13.\" 14.\" THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' 15.\" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 16.\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 17.\" PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE 18.\" LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 19.\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 20.\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 21.\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 22.\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 23.\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 24.\" POSSIBILITY OF SUCH DAMAGE. 25.\" 26.\" $FreeBSD$ 27.\" 28.Dd October 10, 2004 29.Dt HASHINIT 9 30.Os 31.Sh NAME 32.Nm hashinit , hashinit_flags, hashdestroy , phashinit 33.Nd manage kernel hash tables 34.Sh SYNOPSIS 35.In sys/malloc.h 36.In sys/systm.h 37.In sys/queue.h 38.Ft "void *" 39.Fn hashinit "int nelements" "struct malloc_type *type" "u_long *hashmask" 40.Ft void 41.Fo hashinit_flags 42.Fa "int nelements" "struct malloc_type *type" "u_long *hashmask" "int flags" 43.Fc 44.Ft void 45.Fn hashdestroy "void *hashtbl" "struct malloc_type *type" "u_long hashmask" 46.Ft "void *" 47.Fn phashinit "int nelements" "struct malloc_type *type" "u_long *nentries" 48.Sh DESCRIPTION 49The 50.Fn hashinit , 51.Fn hashinit_flags 52and 53.Fn phashinit 54functions allocate space for hash tables of size given by the argument 55.Fa nelements . 56.Pp 57The 58.Fn hashinit 59function allocates hash tables that are sized to largest power of two 60less than or equal to argument 61.Fa nelements . 62The 63.Fn phashinit 64function allocates hash tables that are sized to the largest prime 65number less than or equal to argument 66.Fa nelements . 67The 68.Fn hashinit_flags 69function operates like 70.Fn hashinit 71but also accepts an additional argument 72.Fa flags 73which control various options during allocation. 74Allocated hash tables are contiguous arrays of 75.Xr LIST_HEAD 3 76entries, allocated using 77.Xr malloc 9 , 78and initialized using 79.Xr LIST_INIT 3 . 80The malloc arena to be used for allocation is pointed to by argument 81.Fa type . 82.Pp 83The 84.Fn hashdestroy 85function frees the space occupied by the hash table pointed to by argument 86.Fa hashtbl . 87Argument 88.Fa type 89determines the malloc arena to use when freeing space. 90The argument 91.Fa hashmask 92should be the bit mask returned by the call to 93.Fn hashinit 94that allocated the hash table. 95The argument 96.Fa flags 97must be used with one of the following values. 98.Pp 99.Bl -tag -width ".Dv HASH_NOWAIT" -offset indent -compact 100.It Dv HASH_NOWAIT 101Any malloc performed by the 102.Fn hashinit_flags 103function will not be allowed to wait, and therefore may fail. 104.It Dv HASH_WAITOK 105Any malloc performed by the 106.Fn hashinit_flags 107function is allowed to wait for memory. 108.El 109.Sh IMPLEMENTATION NOTES 110The largest prime hash value chosen by 111.Fn phashinit 112is 32749. 113.Sh RETURN VALUES 114The 115.Fn hashinit 116function returns a pointer to an allocated hash table and sets the 117location pointed to by 118.Fa hashmask 119to the bit mask to be used for computing the correct slot in the 120hash table. 121.Pp 122The 123.Fn phashinit 124function returns a pointer to an allocated hash table and sets the 125location pointed to by 126.Fa nentries 127to the number of rows in the hash table. 128.Sh EXAMPLES 129A typical example is shown below: 130.Bd -literal -offset indent 131\&... 132static LIST_HEAD(foo, foo) *footable; 133static u_long foomask; 134\&... 135footable = hashinit(32, M_FOO, &foomask); 136.Ed 137.Pp 138Here we allocate a hash table with 32 entries from the malloc arena 139pointed to by 140.Dv M_FOO . 141The mask for the allocated hash table is returned in 142.Va foomask . 143A subsequent call to 144.Fn hashdestroy 145uses the value in 146.Va foomask : 147.Bd -literal -offset indent 148\&... 149hashdestroy(footable, M_FOO, foomask); 150.Ed 151.Sh DIAGNOSTICS 152The 153.Fn hashinit 154and 155.Fn phashinit 156functions will panic if argument 157.Fa nelements 158is less than or equal to zero. 159.Pp 160The 161.Fn hashdestroy 162function will panic if the hash table 163pointed to by 164.Fa hashtbl 165is not empty. 166.Sh SEE ALSO 167.Xr LIST_HEAD 3 , 168.Xr malloc 9 169.Sh BUGS 170There is no 171.Fn phashdestroy 172function, and using 173.Fn hashdestroy 174to free a hash table allocated by 175.Fn phashinit 176usually has grave consequences. 177