share/man/man9/hashinit.9

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