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