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 January 23, 2016 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 106.Fn hashinit_flags 107function is allowed to wait for memory. 108This is also the behavior of 109.Fn hashinit . 110.El 111.Sh IMPLEMENTATION NOTES 112The largest prime hash value chosen by 113.Fn phashinit 114is 32749. 115.Sh RETURN VALUES 116The 117.Fn hashinit 118function returns a pointer to an allocated hash table and sets the 119location pointed to by 120.Fa hashmask 121to the bit mask to be used for computing the correct slot in the 122hash table. 123.Pp 124The 125.Fn phashinit 126function returns a pointer to an allocated hash table and sets the 127location pointed to by 128.Fa nentries 129to the number of rows in the hash table. 130.Sh EXAMPLES 131A typical example is shown below: 132.Bd -literal -offset indent 133\&... 134static LIST_HEAD(foo, foo) *footable; 135static u_long foomask; 136\&... 137footable = hashinit(32, M_FOO, &foomask); 138.Ed 139.Pp 140Here we allocate a hash table with 32 entries from the malloc arena 141pointed to by 142.Dv M_FOO . 143The mask for the allocated hash table is returned in 144.Va foomask . 145A subsequent call to 146.Fn hashdestroy 147uses the value in 148.Va foomask : 149.Bd -literal -offset indent 150\&... 151hashdestroy(footable, M_FOO, foomask); 152.Ed 153.Sh DIAGNOSTICS 154The 155.Fn hashinit 156and 157.Fn phashinit 158functions will panic if argument 159.Fa nelements 160is less than or equal to zero. 161.Pp 162The 163.Fn hashdestroy 164function will panic if the hash table 165pointed to by 166.Fa hashtbl 167is not empty. 168.Sh SEE ALSO 169.Xr LIST_HEAD 3 , 170.Xr malloc 9 171.Sh BUGS 172There is no 173.Fn phashdestroy 174function, and using 175.Fn hashdestroy 176to free a hash table allocated by 177.Fn phashinit 178usually has grave consequences. 179