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