1.\" $NetBSD: hashinit.9,v 1.9 2013/09/17 19:58:03 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.\" 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 49The 50.Fn hashinit 51function allocates and initializes space for a simple chaining hash table. 52The number of slots will be the least power of two not smaller than 53.Fa chains . 54The customary choice for 55.Fa chains 56is the maximum number of elements you intend to store divided by 57your intended load factor. 58The 59.Dv LIST... 60or 61.Dv TAILQ... 62macros of 63.Xr queue 3 64can be used to manipulate the chains; pass 65.Dv HASH_LIST 66or 67.Dv HASH_TAILQ 68as 69.Fa htype 70to indicate which. 71Each slot will be initialized as the head of an empty chain of the 72proper type. 73Because 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 79If 80.Fa waitok 81is true, 82.Fa hashinit 83can wait until enough memory is available. 84Otherwise, it immediately fails if there is not enough memory is available. 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 htype 99and 100.Fa hashmask 101that were passed to and returned from 102.Fn hashinit . 103If the table contains any nonempty chain when 104.Fn hashdone 105is called, the result is undefined. 106.Sh RETURN VALUES 107The value returned by 108.Fn hashinit 109should be cast as pointer to an array of 110.Dv LIST_HEAD 111or 112.Dv TAILQ_HEAD 113as appropriate. 114.Fn hashinit 115returns 116.Dv NULL 117on failure. 118.Sh CODE REFERENCES 119These functions are implemented in 120.Pa sys/kern/subr_hash.c . 121.Sh SEE ALSO 122.Xr queue 3 , 123.Xr hash 9 , 124.Xr malloc 9 125.Sh HISTORY 126A 127.Fn hashinit 128function was present, without the 129.Fa htype 130or 131.Fa mflags 132arguments, in 133.Bx 4.4 alpha . 134It was independent of 135.Xr queue 3 136and simply allocated and nulled a table of pointer-sized slots. 137It sized the table to the 138.Em largest 139power of two 140.Em not greater than 141.Fa chains ; 142that is, it built in a load factor between 1 and 2. 143.Pp 144.Nx 1.0 145was the first 146.Nx 147release to have a 148.Fn hashinit 149function. 150It resembled that from 151.Bx 4.4 152but made each slot a 153.Dv LIST_HEAD 154from 155.Xr queue 3 . 156For 157.Nx 1.3.3 158it had been changed to size the table to the least power of two 159not less than 160.Em or equal to 161.Fa chains . 162By 163.Nx 1.4 164it had the 165.Fa mflags 166argument and the current sizing rule. 167.Pp 168.Nx 1.5 169had the 170.Fn hashdone 171function. 172By 173.Nx 1.6 174.Fn hashinit 175supported 176.Dv LIST 177or 178.Dv TAILQ 179chains selected with 180.Fa htype . 181.Pp 182.Fx 183has a 184.Fn hashinit 185with behavior equivalent (as of 186.Fx 6.1 ) 187to that in 188.Nx 1.0 , 189and a 190.Fn hashdestroy 191that behaves as 192.Fn hashdone 193but checks that all chains are empty first. 194.Ox 195has a 196.Fn hashinit 197comparable (as of 198.Ox 3.9 ) 199to that of 200.Nx 1.4 . 201This manual page was added for 202.Nx 4.0 . 203.Sh BUGS 204The only part of the work of implementing a hash table that these functions 205relieve is the part that isn't much work. 206