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