2 .\" Copyright (c) 2004 Joseph Koshy
3 .\" All rights reserved.
5 .\" Redistribution and use in source and binary forms, with or without
6 .\" modification, are permitted provided that the following conditions
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.
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.
32 .Nm hashinit , hashinit_flags , hashdestroy , phashinit , phashinit_flags
33 .Nd manage kernel hash tables
39 .Fn hashinit "int nelements" "struct malloc_type *type" "u_long *hashmask"
42 .Fa "int nelements" "struct malloc_type *type" "u_long *hashmask" "int flags"
45 .Fn hashdestroy "void *hashtbl" "struct malloc_type *type" "u_long hashmask"
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"
56 functions allocate space for hash tables of size given by the argument
61 function allocates hash tables that are sized to largest power of two
62 less than or equal to argument
66 function allocates hash tables that are sized to the largest prime
67 number less than or equal to argument
71 function operates like
73 but also accepts an additional argument
75 which control various options during allocation.
77 function operates like
79 but also accepts an additional argument
81 which control various options during allocation.
82 Allocated hash tables are contiguous arrays of
84 entries, allocated using
88 The malloc arena to be used for allocation is pointed to by argument
93 function frees the space occupied by the hash table pointed to by argument
97 determines the malloc arena to use when freeing space.
100 should be the bit mask returned by the call to
102 that allocated the hash table.
105 must be used with one of the following values.
107 .Bl -tag -width ".Dv HASH_NOWAIT" -offset indent -compact
109 Any malloc performed by the
113 function will not be allowed to wait, and therefore may fail.
115 Any malloc performed by
119 function is allowed to wait for memory.
120 This is also the behavior of
125 .Sh IMPLEMENTATION NOTES
126 The largest prime hash value chosen by
132 function returns a pointer to an allocated hash table and sets the
133 location pointed to by
135 to the bit mask to be used for computing the correct slot in the
140 function returns a pointer to an allocated hash table and sets the
141 location pointed to by
143 to the number of rows in the hash table.
145 A typical example is shown below:
146 .Bd -literal -offset indent
148 static LIST_HEAD(foo, foo) *footable;
149 static u_long foomask;
151 footable = hashinit(32, M_FOO, &foomask);
154 Here we allocate a hash table with 32 entries from the malloc arena
157 The mask for the allocated hash table is returned in
163 .Bd -literal -offset indent
165 hashdestroy(footable, M_FOO, foomask);
172 functions will panic if argument
174 is less than or equal to zero.
178 function will panic if the hash table
190 to free a hash table allocated by
192 usually has grave consequences.