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