1.\" $NetBSD: hashinit.9,v 1.4 2008/04/30 13:10:58 martin 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 June 3, 2006 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/malloc.h 39.In sys/systm.h 40.Ft "void *" 41.Fo hashinit 42.Fa "u_int chains" 43.Fa "enum hashtype htype" 44.Fa "struct malloc_type *mtype" 45.Fa "int mflags" 46.Fa "u_long *hashmask" 47.Fc 48.Ft void 49.Fn hashdone "void *hashtbl" "struct malloc_type *mtype" 50.Sh DESCRIPTION 51The 52.Fn hashinit 53function allocates and initializes space for a simple chaining hash table. 54The number of slots will be the least power of two not smaller than 55.Fa chains . 56The customary choice for 57.Fa chains 58is the maximum number of elements you intend to store divided by 59your intended load factor. 60The 61.Dv LIST... 62or 63.Dv TAILQ... 64macros of 65.Xr queue 3 66can be used to manipulate the chains; pass 67.Dv HASH_LIST 68or 69.Dv HASH_TAILQ 70as 71.Fa htype 72to indicate which. Each slot will be initialized as the head of an empty 73chain of the proper type. Because different data structures from 74.Xr queue 3 75can define head structures of different sizes, the total size of the 76allocated table can vary with the choice of 77.Fa htype . 78.Pp 79The 80.Fa mtype 81and 82.Fa mflags 83arguments have the meanings of the corresponding arguments to 84.Xr malloc 9 . 85.Pp 86A value will be stored into 87.Fa *hashmask 88suitable for masking any computed hash, to obtain the index of a chain 89head in the allocated table. 90.Pp 91The 92.Fn hashdone 93function deallocates the storage allocated by 94.Fn hashinit 95and pointed to by 96.Fa hashtbl , 97given the same 98.Fa mtype 99that was passed to 100.Fn hashinit . 101If the table contains any nonempty chain when 102.Fn hashdone 103is called, the result is undefined. 104.Sh RETURN VALUES 105The value returned by 106.Fn hashinit 107should be cast as pointer to an array of 108.Dv LIST_HEAD 109or 110.Dv TAILQ_HEAD 111as appropriate. 112It can be 113.Dv NULL 114only if the specified 115.Fa mflags 116allow it. 117.Sh SEE ALSO 118.Xr queue 3 , 119.Xr hash 9 , 120.Xr malloc 9 121.Sh CODE REFERENCES 122These functions are implemented in 123.Pa sys/kern/kern_subr.c . 124.Sh HISTORY 125A 126.Fn hashinit 127function was present, without the 128.Fa htype 129or 130.Fa mflags 131arguments, in 132.Bx 4.4 alpha . 133It was independent of 134.Xr queue 3 135and simply allocated and nulled a table of pointer-sized slots. 136It sized the table to the 137.Em largest 138power of two 139.Em not greater than 140.Fa chains ; 141that is, it built in a load factor between 1 and 2. 142.Pp 143.Nx 1.0 144was the first 145.Nx 146release to have a 147.Fn hashinit 148function. 149It resembled that from 150.Bx 4.4 151but made each slot a 152.Dv LIST_HEAD 153from 154.Xr queue 3 . 155For 156.Nx 1.3.3 157it had been changed to size the table to the least power of two 158not less than 159.Em or equal to 160.Fa chains . 161By 162.Nx 1.4 163it had the 164.Fa mflags 165argument and the current sizing rule. 166.Pp 167.Nx 1.5 168had the 169.Fn hashdone 170function. 171By 172.Nx 1.6 173.Fn hashinit 174supported 175.Dv LIST 176or 177.Dv TAILQ 178chains selected with 179.Fa htype . 180.Pp 181.Fx 182has a 183.Fn hashinit 184with behavior equivalent (as of 185.Fx 6.1 ) 186to that in 187.Nx 1.0 , 188and a 189.Fn hashdestroy 190that behaves as 191.Fn hashdone 192but checks that all chains are empty first. 193.Ox 194has a 195.Fn hashinit 196comparable (as of 197.Ox 3.9 ) 198to that of 199.Nx 1.4 . 200This manual page was added for 201.Nx 4.0 . 202.Sh BUGS 203The only part of the work of implementing a hash table that these functions 204relieve is the part that isn't much work. 205