lib/libc/stdlib/hcreate.3

   1 .\"     $NetBSD: hcreate.3,v 1.8 2010/05/01 06:18:03 jruoho Exp $
   2 .\"
   3 .\" Copyright (c) 1999 The NetBSD Foundation, Inc.
   4 .\" All rights reserved.
   5 .\"
   6 .\" This code is derived from software contributed to The NetBSD Foundation
   7 .\" by Klaus Klein.
   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 May 1, 2010
  31 .Dt HCREATE 3
  32 .Os
  33 .Sh NAME
  34 .Nm hcreate ,
  35 .Nm hdestroy ,
  36 .Nm hsearch
  37 .Nd manage hash search table
  38 .Sh LIBRARY
  39 .Lb libc
  40 .Sh SYNOPSIS
  41 .In search.h
  42 .Ft int
  43 .Fn hcreate "size_t nel"
  44 .Ft void
  45 .Fn hdestroy "void"
  46 .Ft ENTRY *
  47 .Fn hsearch "ENTRY item" "ACTION action"
  48 .Sh DESCRIPTION
  49 The
  50 .Fn hcreate ,
  51 .Fn hdestroy
  52 and
  53 .Fn hsearch
  54 functions manage hash search tables.
  55 .Pp
  56 The
  57 .Fn hcreate
  58 function allocates and initializes the table.
  59 The
  60 .Fa nel
  61 argument specifies an estimate of the maximum number of entries to be held
  62 by the table.
  63 Unless further memory allocation fails, supplying an insufficient
  64 .Fa nel
  65 value will not result in functional harm, although a performance degradation
  66 may occur.
  67 Initialization using the
  68 .Fn hcreate
  69 function is mandatory prior to any access operations using
  70 .Fn hsearch .
  71 .Pp
  72 The
  73 .Fn hdestroy
  74 function destroys a table previously created using
  75 .Fn hcreate .
  76 After a call to
  77 .Fn hdestroy ,
  78 the data can no longer be accessed.
  79 .Pp
  80 The
  81 .Fn hsearch
  82 function is used to search to the hash table.
  83 It returns a pointer into the
  84 hash table indicating the address of an item.
  85 The
  86 .Fa item
  87 argument is of type
  88 .Vt ENTRY ,
  89 defined in the
  90 .In search.h
  91 header.
  92 This is a structure type that contains two pointers:
  93 .Pp
  94 .Bl -tag -compact -offset indent -width "void *data "
  95 .It Fa char *key
  96 comparison key
  97 .It Fa void *data
  98 pointer to data associated with
  99 .Fa key
 100 .El
 101 .Pp
 102 The key comparison function used by
 103 .Fn hsearch
 104 is
 105 .Xr strcmp 3 .
 106 .Pp
 107 The
 108 .Fa action
 109 argument is of type
 110 .Vt ACTION ,
 111 an enumeration type which defines the following values:
 112 .Bl -tag -offset indent -width ENTERXX
 113 .It Dv ENTER
 114 Insert
 115 .Fa item
 116 into the hash table.
 117 If an existing item with the same key is found, it is not replaced.
 118 Note that the
 119 .Fa key
 120 and
 121 .Fa data
 122 elements of
 123 .Fa item
 124 are used directly by the new table entry.
 125 The storage for the
 126 key must not be modified during the lifetime of the hash table.
 127 .It Dv FIND
 128 Search the hash table without inserting
 129 .Fa item .
 130 .El
 131 .Pp
 132 Note that the comparison
 133 .Fa key
 134 must be allocated using
 135 .Xr malloc 3
 136 or
 137 .Xr calloc 3
 138 if action is
 139 .Dv ENTER
 140 and
 141 .Fn hdestroy
 142 will be called.
 143 This is because
 144 .Fn hdestroy
 145 will call
 146 .Xr free 3
 147 for each comparison
 148 .Fa key
 149 (but not
 150 .Fa data ) .
 151 Typically the comparison
 152 .Fa key
 153 is allocated by using
 154 .Xr strdup 3 .
 155 .Sh RETURN VALUES
 156 If successful, the
 157 .Fn hcreate
 158 function returns a non-zero value.
 159 Otherwise, a value of 0 is returned and
 160 .Va errno
 161 is set to indicate the error.
 162 .Pp
 163 The
 164 .Fn hdestroy
 165 functions
 166 returns no value.
 167 .Pp
 168 If successful, the
 169 .Fn hsearch
 170 function returns a pointer to hash table entry matching
 171 the provided key.
 172 If the action is
 173 .Dv FIND
 174 and the item was not found, or if the action is
 175 .Dv ENTER
 176 and the insertion failed,
 177 .Dv NULL
 178 is returned and
 179 .Va errno
 180 is set to indicate the error.
 181 If the action is
 182 .Dv ENTER
 183 and an entry already existed in the table matching the given
 184 key, the existing entry is returned and is not replaced.
 185 .Sh ERRORS
 186 The
 187 .Fn hcreate
 188 and
 189 .Fn hsearch
 190 functions will fail if:
 191 .Bl -tag -width Er
 192 .It Bq Er ENOMEM
 193 Insufficient memory is available.
 194 .El
 195 .Sh SEE ALSO
 196 .Xr bsearch 3 ,
 197 .Xr lsearch 3 ,
 198 .Xr malloc 3 ,
 199 .Xr strcmp 3
 200 .Sh STANDARDS
 201 The
 202 .Fn hcreate ,
 203 .Fn hdestroy
 204 and
 205 .Fn hsearch
 206 functions conform to
 207 .St -xpg4.2 .
 208 .Sh HISTORY
 209 The
 210 .Fn hcreate ,
 211 .Fn hdestroy
 212 and
 213 .Fn hsearch
 214 functions first appeared in
 215 .At V .
 216 .Sh CAVEATS
 217 At least the following limitations can be mentioned:
 218 .Bl -bullet
 219 .It
 220 The interface permits the use of only one hash table at a time.
 221 .It
 222 Individual hash table entries can be added, but not deleted.
 223 .It
 224 The standard is indecipherable about the
 225 internal memory usage of the functions,
 226 mentioning only that
 227 .Do
 228 .Fn hcreate
 229 and
 230 .Fn hsearch
 231 functions may use
 232 .Fn malloc
 233 to allocate space
 234 .Dc .
 235 This limits the portability of the functions,
 236 given that other implementations may not
 237 .Xr free 3
 238 the buffer pointed by
 239 .Fa key .
 240 .El