man3/hsearch.3

   1 .\" Hey Emacs! This file is -*- nroff -*- source.
   2 .\" Copyright 1993 Ulrich Drepper (drepper@karlsruhe.gmd.de)
   3 .\"
   4 .\" This is free documentation; you can redistribute it and/or
   5 .\" modify it under the terms of the GNU General Public License as
   6 .\" published by the Free Software Foundation; either version 2 of
   7 .\" the License, or (at your option) any later version.
   8 .\"
   9 .\" The GNU General Public License's references to "object code"
  10 .\" and "executables" are to be interpreted as the output of any
  11 .\" document formatting or typesetting system, including
  12 .\" intermediate and printed output.
  13 .\"
  14 .\" This manual is distributed in the hope that it will be useful,
  15 .\" but WITHOUT ANY WARRANTY; without even the implied warranty of
  16 .\" MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17 .\" GNU General Public License for more details.
  18 .\"
  19 .\" You should have received a copy of the GNU General Public
  20 .\" License along with this manual; if not, write to the Free
  21 .\" Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111,
  22 .\" USA.
  23 .\"
  24 .\" References consulted:
  25 .\"     SunOS 4.1.1 man pages
  26 .\" Modified Sat Sep 30 21:52:01 1995 by Jim Van Zandt <jrv@vanzandt.mv.com>
  27 .\" Remarks from dhw@gamgee.acad.emich.edu Fri Jun 19 06:46:31 1998
  28 .\" Modified 2001-12-26, 2003-11-28, 2004-05-20, aeb
  29 .\"
  30 .TH HSEARCH 3 2004-05-20 "GNU" "Linux Programmer's Manual"
  31 .SH NAME
  32 hcreate, hdestroy, hsearch \- hash table management
  33 .SH SYNOPSIS
  34 .B #include <search.h>
  35 .sp
  36 .BI "int hcreate(size_t " nel );
  37 .sp
  38 .BI "ENTRY *hsearch(ENTRY " item ", ACTION " action );
  39 .sp
  40 .B "void hdestroy(void);"
  41 .sp 2
  42 .B #define _GNU_SOURCE
  43 .br
  44 .B #include <search.h>
  45 .sp
  46 .BI "int hcreate_r(size_t " nel ", struct hsearch_data *" tab );
  47 .sp
  48 .BI "int *hsearch_r(ENTRY " item ", ACTION " action ,
  49 .BI "ENTRY **" ret ", struct hsearch_data *" tab );
  50 .sp
  51 .BI "void hdestroy_r(struct hsearch_data *" tab );
  52 .SH DESCRIPTION
  53 The three functions
  54 .BR hcreate ,
  55 .BR hsearch ,
  56 and
  57 .BR hdestroy
  58 allow the user to create a hash table (only one at a time)
  59 which associates a key with any data.
  60 .PP
  61 First the table must be created with the function \fBhcreate()\fP.
  62 The argument \fInel\fP is an estimate of the maximum number of entries
  63 in the table.
  64 The function \fBhcreate()\fP may adjust this value upward to improve the
  65 performance of the resulting hash table.
  66 .PP
  67 The corresponding function \fBhdestroy()\fP frees the memory occupied by
  68 the hash table so that a new table can be constructed.
  69 .PP
  70 The argument \fIitem\fP is of type \fBENTRY\fP, which is a typedef defined in
  71 \fI<search.h>\fP and includes these elements:
  72 .sp
  73 .nf
  74         typedef struct entry {
  75             char *\fIkey\fP;
  76             void *\fIdata\fP;
  77         } ENTRY;
  78 .fi
  79 .sp
  80 The field \fIkey\fP points to the NUL-terminated string which is the
  81 search key.
  82 The field \fIdata\fP points to the data associated with that key.
  83 The function \fBhsearch()\fP searches the hash table for an
  84 item with the same key as \fIitem\fP (where "the same" is determined using
  85 .BR strcmp (3)),
  86 and if successful returns a pointer to it.
  87 The argument \fIaction\fP determines what \fBhsearch()\fP does
  88 after an unsuccessful search.  A value of \fBENTER\fP instructs it to
  89 insert a copy of \fIitem\fP, while a value of \fBFIND\fP means to return
  90 \fBNULL\fP.
  91 .PP
  92 The three functions
  93 .BR hcreate_r ,
  94 .BR hsearch_r ,
  95 .BR hdestroy_r
  96 are reentrant versions that allow the use of more than one table.
  97 The last argument used identifies the table. The struct it points to
  98 must be zeroed before the first call to
  99 .BR hcreate_r() .
 100 .SH "RETURN VALUE"
 101 \fBhcreate()\fP and \fBhcreate_r()\fP return 0 when allocation of the memory
 102 for the hash table fails, non-zero otherwise.
 103 .LP
 104 \fBhsearch()\fP returns \fBNULL\fP if \fIaction\fP is \fBENTER\fP and
 105 the hash table is full, or \fIaction\fP is \fBFIND\fP and \fIitem\fP
 106 cannot be found in the hash table.
 107 .LP
 108 \fBhsearch_r()\fP returns 0 if \fIaction\fP is \fBENTER\fP and
 109 the hash table is full, and non-zero otherwise.
 110 .SH ERRORS
 111 POSIX documents
 112 .TP
 113 .B ENOMEM
 114 Out of memory.
 115 .LP
 116 The glibc implementation will return the following two errors.
 117 .TP
 118 .B ENOMEM
 119 Table full with \fIaction\fP set to \fBENTER\fP.
 120 .TP
 121 .B ESRCH
 122 The \fIaction\fP parameter is \fBFIND\fP and no corresponding element
 123 is found in the table.
 124 .SH "CONFORMS TO"
 125 The functions
 126 .BR hcreate ,
 127 .BR hsearch ,
 128 and
 129 .BR hdestroy
 130 are from SVID, and are described in POSIX 1003.1-2001.
 131 The functions
 132 .BR hcreate_r ,
 133 .BR hsearch_r ,
 134 .BR hdestroy_r
 135 are GNU extensions.
 136 .SH BUGS
 137 SVID and POSIX 1003.1-2001 specify that \fIaction\fP
 138 is significant only for unsuccessful searches, so that an ENTER
 139 should not do anything for a successful search. The libc and glibc
 140 implementations update the \fIdata\fP for the given \fIkey\fP
 141 in this case.
 142 .\" Tue Jan 29 09:27:40 2002: fixed in latest glibc snapshot
 143 .LP
 144 Individual hash table entries can be added, but not deleted.
 145 .SH EXAMPLE
 146 .PP
 147 The following program inserts 24 items in to a hash table, then prints
 148 some of them.
 149 .nf
 150
 151     #include <stdio.h>
 152     #include <stdlib.h>
 153     #include <search.h>
 154
 155     char *data[] = { "alpha", "bravo", "charlie", "delta",
 156          "echo", "foxtrot", "golf", "hotel", "india", "juliet",
 157          "kilo", "lima", "mike", "november", "oscar", "papa",
 158          "quebec", "romeo", "sierra", "tango", "uniform",
 159          "victor", "whisky", "x-ray", "yankee", "zulu"
 160     };
 161
 162     int main() {
 163       ENTRY e, *ep;
 164       int i;
 165
 166       /* starting with small table, and letting it grow does not work */
 167       hcreate(30);
 168       for (i = 0; i < 24; i++) {
 169           e.key = data[i];
 170           /* data is just an integer, instead of a
 171              pointer to something */
 172           e.data = (void *)i;
 173           ep = hsearch(e, ENTER);
 174           /* there should be no failures */
 175           if (ep == NULL) {
 176             fprintf(stderr, "entry failed\\n");
 177             exit(1);
 178           }
 179       }
 180       for (i = 22; i < 26; i++) {
 181           /* print two entries from the table, and
 182              show that two are not in the table */
 183           e.key = data[i];
 184           ep = hsearch(e, FIND);
 185           printf("%9.9s \-> %9.9s:%d\\n", e.key,
 186                  ep ? ep\->key : "NULL",
 187                  ep ? (int)(ep->data) : 0);
 188       }
 189       return 0;
 190     }
 191
 192 .fi
 193 .SH "SEE ALSO"
 194 .BR bsearch (3),
 195 .BR lsearch (3),
 196 .BR malloc (3),
 197 .BR tsearch (3)