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 October 10, 2004
  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 the
 106 .Fn hashinit_flags
 107 function is allowed to wait for memory.
 108 .El
 109 .Sh IMPLEMENTATION NOTES
 110 The largest prime hash value chosen by
 111 .Fn phashinit
 112 is 32749.
 113 .Sh RETURN VALUES
 114 The
 115 .Fn hashinit
 116 function returns a pointer to an allocated hash table and sets the
 117 location pointed to by
 118 .Fa hashmask
 119 to the bit mask to be used for computing the correct slot in the
 120 hash table.
 121 .Pp
 122 The
 123 .Fn phashinit
 124 function returns a pointer to an allocated hash table and sets the
 125 location pointed to by
 126 .Fa nentries
 127 to the number of rows in the hash table.
 128 .Sh EXAMPLES
 129 A typical example is shown below:
 130 .Bd -literal -offset indent
 131 \&...
 132 static LIST_HEAD(foo, foo) *footable;
 133 static u_long foomask;
 134 \&...
 135 footable = hashinit(32, M_FOO, &foomask);
 136 .Ed
 137 .Pp
 138 Here we allocate a hash table with 32 entries from the malloc arena
 139 pointed to by
 140 .Dv M_FOO .
 141 The mask for the allocated hash table is returned in
 142 .Va foomask .
 143 A subsequent call to
 144 .Fn hashdestroy
 145 uses the value in
 146 .Va foomask :
 147 .Bd -literal -offset indent
 148 \&...
 149 hashdestroy(footable, M_FOO, foomask);
 150 .Ed
 151 .Sh DIAGNOSTICS
 152 The
 153 .Fn hashinit
 154 and
 155 .Fn phashinit
 156 functions will panic if argument
 157 .Fa nelements
 158 is less than or equal to zero.
 159 .Pp
 160 The
 161 .Fn hashdestroy
 162 function will panic if the hash table
 163 pointed to by
 164 .Fa hashtbl
 165 is not empty.
 166 .Sh SEE ALSO
 167 .Xr LIST_HEAD 3 ,
 168 .Xr malloc 9
 169 .Sh BUGS
 170 There is no
 171 .Fn phashdestroy
 172 function, and using
 173 .Fn hashdestroy
 174 to free a hash table allocated by
 175 .Fn phashinit
 176 usually has grave consequences.