1.\" $NetBSD: hashinit.9,v 1.7 2008/07/01 15:37:04 pooka 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. Each slot will be initialized as the head of an empty 71chain of the proper type. Because different data structures from 72.Xr queue 3 73can define head structures of different sizes, the total size of the 74allocated table can vary with the choice of 75.Fa htype . 76.Pp 77If 78.Fa waitok 79is true, 80.Fa hashinit 81can wait until enough memory is available. 82Otherwise, it immediately fails if there is not enough memory is available. 83.Pp 84A value will be stored into 85.Fa *hashmask 86suitable for masking any computed hash, to obtain the index of a chain 87head in the allocated table. 88.Pp 89The 90.Fn hashdone 91function deallocates the storage allocated by 92.Fn hashinit 93and pointed to by 94.Fa hashtbl , 95given the same 96.Fa htype 97and 98.Fa hashmask 99that were passed to and returned from 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. 112.Fn hashinit 113returns 114.Dv NULL 115on failure. 116.Sh SEE ALSO 117.Xr queue 3 , 118.Xr hash 9 , 119.Xr malloc 9 120.Sh CODE REFERENCES 121These functions are implemented in 122.Pa sys/kern/subr_hash.c . 123.Sh HISTORY 124A 125.Fn hashinit 126function was present, without the 127.Fa htype 128or 129.Fa mflags 130arguments, in 131.Bx 4.4 alpha . 132It was independent of 133.Xr queue 3 134and simply allocated and nulled a table of pointer-sized slots. 135It sized the table to the 136.Em largest 137power of two 138.Em not greater than 139.Fa chains ; 140that is, it built in a load factor between 1 and 2. 141.Pp 142.Nx 1.0 143was the first 144.Nx 145release to have a 146.Fn hashinit 147function. 148It resembled that from 149.Bx 4.4 150but made each slot a 151.Dv LIST_HEAD 152from 153.Xr queue 3 . 154For 155.Nx 1.3.3 156it had been changed to size the table to the least power of two 157not less than 158.Em or equal to 159.Fa chains . 160By 161.Nx 1.4 162it had the 163.Fa mflags 164argument and the current sizing rule. 165.Pp 166.Nx 1.5 167had the 168.Fn hashdone 169function. 170By 171.Nx 1.6 172.Fn hashinit 173supported 174.Dv LIST 175or 176.Dv TAILQ 177chains selected with 178.Fa htype . 179.Pp 180.Fx 181has a 182.Fn hashinit 183with behavior equivalent (as of 184.Fx 6.1 ) 185to that in 186.Nx 1.0 , 187and a 188.Fn hashdestroy 189that behaves as 190.Fn hashdone 191but checks that all chains are empty first. 192.Ox 193has a 194.Fn hashinit 195comparable (as of 196.Ox 3.9 ) 197to that of 198.Nx 1.4 . 199This manual page was added for 200.Nx 4.0 . 201.Sh BUGS 202The only part of the work of implementing a hash table that these functions 203relieve is the part that isn't much work. 204