share/man/man9/hashinit.9

   1 .\"     $NetBSD: hashinit.9,v 1.6 2008/05/27 22:03:52 hubertf Exp $
   2 .\"
   3 .\" Copyright (c) 2006 The NetBSD Foundation, Inc.
   4 .\" All rights reserved.
   5 .\"
   6 .\" This code is derived from software contributed to The NetBSD Foundation
   7 .\" by Chapman Flack.
   8 .\"
   9 .\" Redistribution and use in source and binary forms, with or without
  10 .\" modification, are permitted provided that the following conditions
  11 .\" are met:
  12 .\" 1. Redistributions of source code must retain the above copyright
  13 .\"    notice, this list of conditions and the following disclaimer.
  14 .\" 2. Redistributions in binary form must reproduce the above copyright
  15 .\"    notice, this list of conditions and the following disclaimer in the
  16 .\"    documentation and/or other materials provided with the distribution.
  17 .\"
  18 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  19 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  20 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  21 .\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  22 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  23 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  24 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  25 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  26 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  27 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28 .\" POSSIBILITY OF SUCH DAMAGE.
  29 .\"
  30 .Dd July 1, 2008
  31 .Dt HASHINIT 9
  32 .Os
  33 .Sh NAME
  34 .Nm hashinit ,
  35 .Nm hashdone
  36 .Nd kernel hash table construction and destruction
  37 .Sh SYNOPSIS
  38 .In sys/systm.h
  39 .Ft "void *"
  40 .Fo hashinit
  41 .Fa "u_int chains"
  42 .Fa "enum hashtype htype"
  43 .Fa "bool waitok"
  44 .Fa "u_long *hashmask"
  45 .Fc
  46 .Ft void
  47 .Fn hashdone "void *hashtbl" "enum hashtype htype" "u_long hashmask"
  48 .Sh DESCRIPTION
  49 The
  50 .Fn hashinit
  51 function allocates and initializes space for a simple chaining hash table.
  52 The number of slots will be the least power of two not smaller than
  53 .Fa chains .
  54 The customary choice for
  55 .Fa chains
  56 is the maximum number of elements you intend to store divided by
  57 your intended load factor.
  58 The
  59 .Dv LIST...
  60 or
  61 .Dv TAILQ...
  62 macros of
  63 .Xr queue 3
  64 can be used to manipulate the chains; pass
  65 .Dv HASH_LIST
  66 or
  67 .Dv HASH_TAILQ
  68 as
  69 .Fa htype
  70 to indicate which. Each slot will be initialized as the head of an empty
  71 chain of the proper type. Because different data structures from
  72 .Xr queue 3
  73 can define head structures of different sizes, the total size of the
  74 allocated table can vary with the choice of
  75 .Fa htype .
  76 .Pp
  77 If
  78 .Fa waitok
  79 is true,
  80 .Fa hashinit
  81 can wait until enough memory is available.
  82 Otherwise, it immediately fails if there is not enough memory is available.
  83 .Pp
  84 A value will be stored into
  85 .Fa *hashmask
  86 suitable for masking any computed hash, to obtain the index of a chain
  87 head in the allocated table.
  88 .Pp
  89 The
  90 .Fn hashdone
  91 function deallocates the storage allocated by
  92 .Fn hashinit
  93 and pointed to by
  94 .Fa hashtbl ,
  95 given the same
  96 .Fa htype
  97 and
  98 .Fa hashmask
  99 that were passed to and returned from
 100 .Fn hashinit .
 101 If the table contains any nonempty chain when
 102 .Fn hashdone
 103 is called, the result is undefined.
 104 .Sh RETURN VALUES
 105 The value returned by
 106 .Fn hashinit
 107 should be cast as pointer to an array of
 108 .Dv LIST_HEAD
 109 or
 110 .Dv TAILQ_HEAD
 111 as appropriate.
 112 .Fn hashinit
 113 returns
 114 .Dv NULL
 115 on failure.
 116 .Sh SEE ALSO
 117 .Xr queue 3 ,
 118 .Xr hash 9 ,
 119 .Xr malloc 9
 120 .Sh CODE REFERENCES
 121 These functions are implemented in
 122 .Pa sys/kern/subr_hash.c .
 123 .Sh HISTORY
 124 A
 125 .Fn hashinit
 126 function was present, without the
 127 .Fa htype
 128 or
 129 .Fa mflags
 130 arguments, in
 131 .Bx 4.4 alpha .
 132 It was independent of
 133 .Xr queue 3
 134 and simply allocated and nulled a table of pointer-sized slots.
 135 It sized the table to the
 136 .Em largest
 137 power of two
 138 .Em not greater than
 139 .Fa chains ;
 140 that is, it built in a load factor between 1 and 2.
 141 .Pp
 142 .Nx 1.0
 143 was the first
 144 .Nx
 145 release to have a
 146 .Fn hashinit
 147 function.
 148 It resembled that from
 149 .Bx 4.4
 150 but made each slot a
 151 .Dv LIST_HEAD
 152 from
 153 .Xr queue 3 .
 154 For
 155 .Nx 1.3.3
 156 it had been changed to size the table to the least power of two
 157 not less than
 158 .Em or equal to
 159 .Fa chains .
 160 By
 161 .Nx 1.4
 162 it had the
 163 .Fa mflags
 164 argument and the current sizing rule.
 165 .Pp
 166 .Nx 1.5
 167 had the
 168 .Fn hashdone
 169 function.
 170 By
 171 .Nx 1.6
 172 .Fn hashinit
 173 supported
 174 .Dv LIST
 175 or
 176 .Dv TAILQ
 177 chains selected with
 178 .Fa htype .
 179 .Pp
 180 .Fx
 181 has a
 182 .Fn hashinit
 183 with behavior equivalent (as of
 184 .Fx 6.1 )
 185 to that in
 186 .Nx 1.0 ,
 187 and a
 188 .Fn hashdestroy
 189 that behaves as
 190 .Fn hashdone
 191 but checks that all chains are empty first.
 192 .Ox
 193 has a
 194 .Fn hashinit
 195 comparable (as of
 196 .Ox 3.9 )
 197 to that of
 198 .Nx 1.4 .
 199 This manual page was added for
 200 .Nx 4.0 .
 201 .Sh BUGS
 202 The only part of the work of implementing a hash table that these functions
 203 relieve is the part that isn't much work.