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.Dd April 29, 2016 27.Dt HASHINIT 9 28.Os 29.Sh NAME 30.Nm hashinit , hashinit_flags , hashdestroy , phashinit , phashinit_flags 31.Nd manage kernel hash tables 32.Sh SYNOPSIS 33.In sys/malloc.h 34.In sys/systm.h 35.In sys/queue.h 36.Ft "void *" 37.Fn hashinit "int nelements" "struct malloc_type *type" "u_long *hashmask" 38.Ft void 39.Fo hashinit_flags 40.Fa "int nelements" "struct malloc_type *type" "u_long *hashmask" "int flags" 41.Fc 42.Ft void 43.Fn hashdestroy "void *hashtbl" "struct malloc_type *type" "u_long hashmask" 44.Ft "void *" 45.Fn phashinit "int nelements" "struct malloc_type *type" "u_long *nentries" 46.Fn phashinit_flags "int nelements" "struct malloc_type *type" "u_long *nentries" "int flags" 47.Sh DESCRIPTION 48The 49.Fn hashinit , 50.Fn hashinit_flags , 51.Fn phashinit 52and 53.Fn phashinit_flags 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. 74.Fn phashinit_flags 75function operates like 76.Fn phashinit 77but also accepts an additional argument 78.Fa flags 79which control various options during allocation. 80Allocated hash tables are contiguous arrays of 81.Xr LIST_HEAD 3 82entries, allocated using 83.Xr malloc 9 , 84and initialized using 85.Xr LIST_INIT 3 . 86The malloc arena to be used for allocation is pointed to by argument 87.Fa type . 88.Pp 89The 90.Fn hashdestroy 91function frees the space occupied by the hash table pointed to by argument 92.Fa hashtbl . 93Argument 94.Fa type 95determines the malloc arena to use when freeing space. 96The argument 97.Fa hashmask 98should be the bit mask returned by the call to 99.Fn hashinit 100that allocated the hash table. 101The argument 102.Fa flags 103must be used with one of the following values. 104.Pp 105.Bl -tag -width ".Dv HASH_NOWAIT" -offset indent -compact 106.It Dv HASH_NOWAIT 107Any malloc performed by the 108.Fn hashinit_flags 109and 110.Fn phashinit_flags 111function will not be allowed to wait, and therefore may fail. 112.It Dv HASH_WAITOK 113Any malloc performed by 114.Fn hashinit_flags 115and 116.Fn phashinit_flags 117function is allowed to wait for memory. 118This is also the behavior of 119.Fn hashinit 120and 121.Fn phashinit . 122.El 123.Sh IMPLEMENTATION NOTES 124The largest prime hash value chosen by 125.Fn phashinit 126is 32749. 127.Sh RETURN VALUES 128The 129.Fn hashinit 130function returns a pointer to an allocated hash table and sets the 131location pointed to by 132.Fa hashmask 133to the bit mask to be used for computing the correct slot in the 134hash table. 135.Pp 136The 137.Fn phashinit 138function returns a pointer to an allocated hash table and sets the 139location pointed to by 140.Fa nentries 141to the number of rows in the hash table. 142.Sh EXAMPLES 143A typical example is shown below: 144.Bd -literal -offset indent 145\&... 146static LIST_HEAD(foo, foo) *footable; 147static u_long foomask; 148\&... 149footable = hashinit(32, M_FOO, &foomask); 150.Ed 151.Pp 152Here we allocate a hash table with 32 entries from the malloc arena 153pointed to by 154.Dv M_FOO . 155The mask for the allocated hash table is returned in 156.Va foomask . 157A subsequent call to 158.Fn hashdestroy 159uses the value in 160.Va foomask : 161.Bd -literal -offset indent 162\&... 163hashdestroy(footable, M_FOO, foomask); 164.Ed 165.Sh DIAGNOSTICS 166The 167.Fn hashinit 168and 169.Fn phashinit 170functions will panic if argument 171.Fa nelements 172is less than or equal to zero. 173.Pp 174The 175.Fn hashdestroy 176function will panic if the hash table 177pointed to by 178.Fa hashtbl 179is not empty. 180.Sh SEE ALSO 181.Xr LIST_HEAD 3 , 182.Xr malloc 9 183.Sh BUGS 184There is no 185.Fn phashdestroy 186function, and using 187.Fn hashdestroy 188to free a hash table allocated by 189.Fn phashinit 190usually has grave consequences. 191