lib/libc/stdlib/hcreate.3

   1 .\"-
   2 .\" Copyright (c) 1999 The NetBSD Foundation, Inc.
   3 .\" All rights reserved.
   4 .\"
   5 .\" This code is derived from software contributed to The NetBSD Foundation
   6 .\" by Klaus Klein.
   7 .\"
   8 .\" Redistribution and use in source and binary forms, with or without
   9 .\" modification, are permitted provided that the following conditions
  10 .\" are met:
  11 .\" 1. Redistributions of source code must retain the above copyright
  12 .\"    notice, this list of conditions and the following disclaimer.
  13 .\" 2. Redistributions in binary form must reproduce the above copyright
  14 .\"    notice, this list of conditions and the following disclaimer in the
  15 .\"    documentation and/or other materials provided with the distribution.
  16 .\"
  17 .\" THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  18 .\" ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  19 .\" TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  20 .\" PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  21 .\" BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  22 .\" CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  23 .\" SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  24 .\" INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  25 .\" CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  26 .\" ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  27 .\" POSSIBILITY OF SUCH DAMAGE.
  28 .\"
  29 .\" $FreeBSD: src/lib/libc/stdlib/hcreate.3,v 1.7 2008/07/06 17:03:37 danger Exp $
  30 .\" $DragonFly: src/lib/libc/stdlib/hcreate.3,v 1.5 2006/05/26 19:39:37 swildner Exp $
  31 .\"
  32 .Dd July 6, 2008
  33 .Os
  34 .Dt HCREATE 3
  35 .Sh NAME
  36 .Nm hcreate ,
  37 .Nm hdestroy ,
  38 .Nm hsearch
  39 .Nd manage hash search table
  40 .Sh LIBRARY
  41 .Lb libc
  42 .Sh SYNOPSIS
  43 .In search.h
  44 .Ft int
  45 .Fn hcreate "size_t nel"
  46 .Ft void
  47 .Fn hdestroy void
  48 .Ft ENTRY *
  49 .Fn hsearch "ENTRY item" "ACTION action"
  50 .Sh DESCRIPTION
  51 The
  52 .Fn hcreate ,
  53 .Fn hdestroy ,
  54 and
  55 .Fn hsearch
  56 functions manage hash search tables.
  57 .Pp
  58 The
  59 .Fn hcreate
  60 function allocates sufficient space for the table, and the application should
  61 ensure it is called before
  62 .Fn hsearch
  63 is used.
  64 The
  65 .Fa nel
  66 argument is an estimate of the maximum
  67 number of entries that the table should contain.
  68 This number may be adjusted upward by the
  69 algorithm in order to obtain certain mathematically favorable circumstances.
  70 .Pp
  71 The
  72 .Fn hdestroy
  73 function disposes of the search table, and may be followed by another call to
  74 .Fn hcreate .
  75 After the call to
  76 .Fn hdestroy ,
  77 the data can no longer be considered accessible.
  78 The
  79 .Fn hdestroy
  80 function calls
  81 .Xr free 3
  82 for each comparison key in the search table
  83 but not the data item associated with the key.
  84 .Pp
  85 The
  86 .Fn hsearch
  87 function is a hash-table search routine.
  88 It returns a pointer into a hash table
  89 indicating the location at which an entry can be found.
  90 The
  91 .Fa item
  92 argument is a structure of type
  93 .Vt ENTRY
  94 (defined in the
  95 .In search.h
  96 header) containing two pointers:
  97 .Fa item.key
  98 points to the comparison key (a
  99 .Vt "char *" ) ,
 100 and
 101 .Fa item.data
 102 (a
 103 .Vt "void *" )
 104 points to any other data to be associated with
 105 that key.
 106 The comparison function used by
 107 .Fn hsearch
 108 is
 109 .Xr strcmp 3 .
 110 The
 111 .Fa action
 112 argument is a
 113 member of an enumeration type
 114 .Vt ACTION
 115 indicating the disposition of the entry if it cannot be
 116 found in the table.
 117 .Dv ENTER
 118 indicates that the
 119 .Fa item
 120 should be inserted in the table at an
 121 appropriate point.
 122 .Dv FIND
 123 indicates that no entry should be made.
 124 Unsuccessful resolution is
 125 indicated by the return of a
 126 .Dv NULL
 127 pointer.
 128 .Pp
 129 The comparison key (passed to
 130 .Fn hsearch
 131 as
 132 .Fa item.key )
 133 must be allocated using
 134 .Xr malloc 3
 135 if
 136 .Fa action
 137 is
 138 .Dv ENTER
 139 and
 140 .Fn hdestroy
 141 is called.
 142 .Sh RETURN VALUES
 143 The
 144 .Fn hcreate
 145 function returns 0 if the table creation failed and the global variable
 146 .Va errno
 147 is set to indicate the error;
 148 otherwise, a non-zero value is returned.
 149 .Pp
 150 The
 151 .Fn hdestroy
 152 function does not return a value.
 153 .Pp
 154 The
 155 .Fn hsearch
 156 function returns a
 157 .Dv NULL
 158 pointer if either the
 159 .Fa action
 160 is
 161 .Dv FIND
 162 and the
 163 .Fa item
 164 could not be found or the
 165 .Fa action
 166 is
 167 .Dv ENTER
 168 and the table is full.
 169 .Sh EXAMPLES
 170 The following example reads in strings followed by two numbers
 171 and stores them in a hash table, discarding duplicates.
 172 It then reads in strings and finds the matching entry in the hash
 173 table and prints it out.
 174 .Bd -literal
 175 #include <stdio.h>
 176 #include <search.h>
 177 #include <string.h>
 178 #include <stdlib.h>
 179
 180 struct info {                   /* This is the info stored in the table */
 181         int age, room;          /* other than the key. */
 182 };
 183
 184 #define NUM_EMPL        5000    /* # of elements in search table. */
 185
 186 int
 187 main(void)
 188 {
 189         char str[BUFSIZ]; /* Space to read string */
 190         struct info info_space[NUM_EMPL]; /* Space to store employee info. */
 191         struct info *info_ptr = info_space; /* Next space in info_space. */
 192         ENTRY item;
 193         ENTRY *found_item; /* Name to look for in table. */
 194         char name_to_find[30];
 195         int i = 0;
 196
 197         /* Create table; no error checking is performed. */
 198         (void) hcreate(NUM_EMPL);
 199
 200         while (scanf("%s%d%d", str, &info_ptr->age,
 201             &info_ptr->room) != EOF && i++ < NUM_EMPL) {
 202                 /* Put information in structure, and structure in item. */
 203                 item.key = strdup(str);
 204                 item.data = info_ptr;
 205                 info_ptr++;
 206                 /* Put item into table. */
 207                 (void) hsearch(item, ENTER);
 208         }
 209
 210         /* Access table. */
 211         item.key = name_to_find;
 212         while (scanf("%s", item.key) != EOF) {
 213                 if ((found_item = hsearch(item, FIND)) != NULL) {
 214                         /* If item is in the table. */
 215                         (void)printf("found %s, age = %d, room = %d\en",
 216                             found_item->key,
 217                             ((struct info *)found_item->data)->age,
 218                             ((struct info *)found_item->data)->room);
 219                 } else
 220                         (void)printf("no such employee %s\en", name_to_find);
 221         }
 222         hdestroy();
 223         return 0;
 224 }
 225 .Ed
 226 .Sh ERRORS
 227 The
 228 .Fn hcreate
 229 and
 230 .Fn hsearch
 231 functions may fail if:
 232 .Bl -tag -width Er
 233 .It Bq Er ENOMEM
 234 Insufficient storage space is available.
 235 .It Bq Er EINVAL
 236 A table already exists.
 237 .El
 238 .Sh SEE ALSO
 239 .Xr bsearch 3 ,
 240 .Xr lsearch 3 ,
 241 .Xr malloc 3 ,
 242 .Xr strcmp 3 ,
 243 .Xr tsearch 3
 244 .Sh STANDARDS
 245 The
 246 .Fn hcreate ,
 247 .Fn hdestroy ,
 248 and
 249 .Fn hsearch
 250 functions conform to
 251 .St -xpg4.2 .
 252 .Sh HISTORY
 253 The
 254 .Fn hcreate ,
 255 .Fn hdestroy ,
 256 and
 257 .Fn hsearch
 258 functions first appeared in
 259 .At V .
 260 .Sh BUGS
 261 The interface permits the use of only one hash table at a time.