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