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 , 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.Fn hashdestroy "void *hashtbl" "struct malloc_type *type" "u_long hashmask" 42.Ft "void *" 43.Fn phashinit "int nelements" "struct malloc_type *type" "u_long *nentries" 44.Sh DESCRIPTION 45The 46.Fn hashinit 47and 48.Fn phashinit 49functions allocate space for hash tables of size given by the argument 50.Fa nelements . 51.Pp 52The 53.Fn hashinit 54function allocates hash tables that are sized to largest power of two 55less than or equal to argument 56.Fa nelements . 57The 58.Fn phashinit 59function allocates hash tables that are sized to the largest prime 60number less than or equal to argument 61.Fa nelements . 62Allocated hash tables are contiguous arrays of 63.Xr LIST_HEAD 3 64entries, allocated using 65.Xr malloc 9 , 66and initialized using 67.Xr LIST_INIT 3 . 68The malloc arena to be used for allocation is pointed to by argument 69.Fa type . 70.Pp 71The 72.Fn hashdestroy 73function frees the space occupied by the hash table pointed to by argument 74.Fa hashtbl . 75Argument 76.Fa type 77determines the malloc arena to use when freeing space. 78The argument 79.Fa hashmask 80should be the bit mask returned by the call to 81.Fn hashinit 82that allocated the hash table. 83.Sh IMPLEMENTATION NOTES 84The largest prime hash value chosen by 85.Fn phashinit 86is 32749. 87.Sh RETURN VALUES 88The 89.Fn hashinit 90function returns a pointer to an allocated hash table and sets the 91location pointed to by 92.Fa hashmask 93to the bit mask to be used for computing the correct slot in the 94hash table. 95.Pp 96The 97.Fn phashinit 98function returns a pointer to an allocated hash table and sets the 99location pointed to by 100.Fa nentries 101to the number of rows in the hash table. 102.Sh EXAMPLES 103A typical example is shown below: 104.Bd -literal -offset indent 105\&... 106static LIST_HEAD(foo, foo) *footable; 107static u_long foomask; 108\&... 109footable = hashinit(32, M_FOO, &foomask); 110.Ed 111.Pp 112Here we allocate a hash table with 32 entries from the malloc arena 113pointed to by 114.Dv M_FOO . 115The mask for the allocated hash table is returned in 116.Va foomask . 117A subsequent call to 118.Fn hashdestroy 119uses the value in 120.Va foomask : 121.Bd -literal -offset indent 122\&... 123hashdestroy(footable, M_FOO, foomask); 124.Ed 125.Sh DIAGNOSTICS 126The 127.Fn hashinit 128and 129.Fn phashinit 130functions will panic if argument 131.Fa nelements 132is less than or equal to zero. 133.Pp 134The 135.Fn hashdestroy 136function will panic if the hash table 137pointed to by 138.Fa hashtbl 139is not empty. 140.Sh SEE ALSO 141.Xr LIST_HEAD 3 , 142.Xr malloc 9 143.Sh BUGS 144There is no 145.Fn phashdestroy 146function, and using 147.Fn hashdestroy 148to free a hash table allocated by 149.Fn phashinit 150usually has grave consequences. 151