490 lines
12 KiB
HTML
490 lines
12 KiB
HTML
|
|
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
|
|
<HTML><HEAD><TITLE>Man page of HSEARCH</TITLE>
|
|
</HEAD><BODY>
|
|
<H1>HSEARCH</H1>
|
|
Section: Linux Programmer's Manual (3)<BR>Updated: 2019-03-06<BR><A HREF="#index">Index</A>
|
|
<A HREF="/cgi-bin/man/man2html">Return to Main Contents</A><HR>
|
|
|
|
<A NAME="lbAB"> </A>
|
|
<H2>NAME</H2>
|
|
|
|
hcreate, hdestroy, hsearch, hcreate_r, hdestroy_r,
|
|
hsearch_r - hash table management
|
|
<A NAME="lbAC"> </A>
|
|
<H2>SYNOPSIS</H2>
|
|
|
|
<PRE>
|
|
<B>#include <<A HREF="file:///usr/include/search.h">search.h</A>></B>
|
|
|
|
<B>int hcreate(size_t </B><I>nel</I><B>);</B>
|
|
|
|
<B>ENTRY *hsearch(ENTRY </B><I>item</I><B>, ACTION </B><I>action</I><B>);</B>
|
|
|
|
<B>void hdestroy(void);</B>
|
|
|
|
<B>#define _GNU_SOURCE</B> /* See <A HREF="/cgi-bin/man/man2html?7+feature_test_macros">feature_test_macros</A>(7) */
|
|
<B>#include <<A HREF="file:///usr/include/search.h">search.h</A>></B>
|
|
|
|
<B>int hcreate_r(size_t </B><I>nel</I><B>, struct hsearch_data *</B><I>htab</I><B>);</B>
|
|
|
|
<B>int hsearch_r(ENTRY </B><I>item</I><B>, ACTION </B><I>action</I><B>, ENTRY **</B><I>retval</I><B>,</B>
|
|
<B> struct hsearch_data *</B><I>htab</I><B>);</B>
|
|
|
|
<B>void hdestroy_r(struct hsearch_data *</B><I>htab</I><B>);</B>
|
|
</PRE>
|
|
|
|
<A NAME="lbAD"> </A>
|
|
<H2>DESCRIPTION</H2>
|
|
|
|
The three functions
|
|
<B>hcreate</B>(),
|
|
|
|
<B>hsearch</B>(),
|
|
|
|
and
|
|
<B>hdestroy</B>()
|
|
|
|
allow the caller to create and manage a hash search table
|
|
containing entries consisting of a key (a string) and associated data.
|
|
Using these functions, only one hash table can be used at a time.
|
|
<P>
|
|
|
|
The three functions
|
|
<B>hcreate_r</B>(),
|
|
|
|
<B>hsearch_r</B>(),
|
|
|
|
<B>hdestroy_r</B>()
|
|
|
|
are reentrant versions that allow a program to use
|
|
more than one hash search table at the same time.
|
|
The last argument,
|
|
<I>htab</I>,
|
|
|
|
points to a structure that describes the table
|
|
on which the function is to operate.
|
|
The programmer should treat this structure as opaque
|
|
(i.e., do not attempt to directly access or modify
|
|
the fields in this structure).
|
|
<P>
|
|
|
|
First a hash table must be created using
|
|
<B>hcreate</B>().
|
|
|
|
The argument <I>nel</I> specifies the maximum number of entries
|
|
in the table.
|
|
(This maximum cannot be changed later, so choose it wisely.)
|
|
The implementation may adjust this value upward to improve the
|
|
performance of the resulting hash table.
|
|
|
|
<P>
|
|
|
|
The
|
|
<B>hcreate_r</B>()
|
|
|
|
function performs the same task as
|
|
<B>hcreate</B>(),
|
|
|
|
but for the table described by the structure
|
|
<I>*htab</I>.
|
|
|
|
The structure pointed to by
|
|
<I>htab</I>
|
|
|
|
must be zeroed before the first call to
|
|
<B>hcreate_r</B>().
|
|
|
|
<P>
|
|
|
|
The function
|
|
<B>hdestroy</B>()
|
|
|
|
frees the memory occupied by the hash table that was created by
|
|
<B>hcreate</B>().
|
|
|
|
After calling
|
|
<B>hdestroy</B>(),
|
|
|
|
a new hash table can be created using
|
|
<B>hcreate</B>().
|
|
|
|
The
|
|
<B>hdestroy_r</B>()
|
|
|
|
function performs the analogous task for a hash table described by
|
|
<I>*htab</I>,
|
|
|
|
which was previously created using
|
|
<B>hcreate_r</B>().
|
|
|
|
<P>
|
|
|
|
The
|
|
<B>hsearch</B>()
|
|
|
|
function searches the hash table for an
|
|
item with the same key as <I>item</I> (where "the same" is determined using
|
|
<B><A HREF="/cgi-bin/man/man2html?3+strcmp">strcmp</A></B>(3)),
|
|
|
|
and if successful returns a pointer to it.
|
|
<P>
|
|
|
|
The argument <I>item</I> is of type <I>ENTRY</I>, which is defined in
|
|
<I><<A HREF="file:///usr/include/search.h">search.h</A>></I> as follows:
|
|
<P>
|
|
|
|
|
|
|
|
typedef struct entry {
|
|
<BR> char *key;
|
|
<BR> void *data;
|
|
} ENTRY;
|
|
|
|
|
|
<P>
|
|
|
|
The field <I>key</I> points to a null-terminated string which is the
|
|
search key.
|
|
The field <I>data</I> points to data that is associated with that key.
|
|
<P>
|
|
|
|
The argument <I>action</I> determines what
|
|
<B>hsearch</B>()
|
|
|
|
does after an unsuccessful search.
|
|
This argument must either have the value
|
|
<B>ENTER</B>,
|
|
|
|
meaning insert a copy of
|
|
<I>item</I>
|
|
|
|
(and return a pointer to the new hash table entry as the function result),
|
|
or the value
|
|
<B>FIND</B>,
|
|
|
|
meaning that NULL should be returned.
|
|
(If
|
|
<I>action</I>
|
|
|
|
is
|
|
<B>FIND</B>,
|
|
|
|
then
|
|
<I>data</I>
|
|
|
|
is ignored.)
|
|
<P>
|
|
|
|
The
|
|
<B>hsearch_r</B>()
|
|
|
|
function is like
|
|
<B>hsearch</B>()
|
|
|
|
but operates on the hash table described by
|
|
<I>*htab</I>.
|
|
|
|
The
|
|
<B>hsearch_r</B>()
|
|
|
|
function differs from
|
|
<B>hsearch</B>()
|
|
|
|
in that a pointer to the found item is returned in
|
|
<I>*retval</I>,
|
|
|
|
rather than as the function result.
|
|
<A NAME="lbAE"> </A>
|
|
<H2>RETURN VALUE</H2>
|
|
|
|
<B>hcreate</B>()
|
|
|
|
and
|
|
<B>hcreate_r</B>()
|
|
|
|
return nonzero on success.
|
|
They return 0 on error, with
|
|
<I>errno</I>
|
|
|
|
set to indicate the cause of the error.
|
|
<P>
|
|
|
|
On success,
|
|
<B>hsearch</B>()
|
|
|
|
returns a pointer to an entry in the hash table.
|
|
<B>hsearch</B>()
|
|
|
|
returns NULL on error, that is,
|
|
if <I>action</I> is <B>ENTER</B> and
|
|
the hash table is full, or <I>action</I> is <B>FIND</B> and <I>item</I>
|
|
cannot be found in the hash table.
|
|
<B>hsearch_r</B>()
|
|
|
|
returns nonzero on success, and 0 on error.
|
|
In the event of an error, these two functions set
|
|
<I>errno</I>
|
|
|
|
to indicate the cause of the error.
|
|
<A NAME="lbAF"> </A>
|
|
<H2>ERRORS</H2>
|
|
|
|
<P>
|
|
|
|
<B>hcreate_r</B>()
|
|
|
|
and
|
|
<B>hdestroy_r</B>()
|
|
|
|
can fail for the following reasons:
|
|
<DL COMPACT>
|
|
<DT id="1"><B>EINVAL</B>
|
|
|
|
<DD>
|
|
<I>htab</I>
|
|
|
|
is NULL.
|
|
</DL>
|
|
<P>
|
|
|
|
<B>hsearch</B>()
|
|
|
|
and
|
|
<B>hsearch_r</B>()
|
|
|
|
can fail for the following reasons:
|
|
<DL COMPACT>
|
|
<DT id="2"><B>ENOMEM</B>
|
|
|
|
<DD>
|
|
<I>action</I>
|
|
|
|
was
|
|
<B>ENTER</B>,
|
|
|
|
<I>key</I>
|
|
|
|
was not found in the table,
|
|
and there was no room in the table to add a new entry.
|
|
<DT id="3"><B>ESRCH</B>
|
|
|
|
<DD>
|
|
<I>action</I>
|
|
|
|
was
|
|
<B>FIND</B>,
|
|
|
|
and
|
|
<I>key</I>
|
|
|
|
was not found in the table.
|
|
</DL>
|
|
<P>
|
|
|
|
POSIX.1 specifies only the
|
|
|
|
<B>ENOMEM</B>
|
|
|
|
error.
|
|
<A NAME="lbAG"> </A>
|
|
<H2>ATTRIBUTES</H2>
|
|
|
|
For an explanation of the terms used in this section, see
|
|
<B><A HREF="/cgi-bin/man/man2html?7+attributes">attributes</A></B>(7).
|
|
|
|
<TABLE BORDER>
|
|
<TR VALIGN=top><TD><B>Interface</B></TD><TD><B>Attribute</B></TD><TD><B>Value</B><BR></TD></TR>
|
|
<TR VALIGN=top><TD>
|
|
<B>hcreate</B>(),
|
|
|
|
<B>hsearch</B>(),
|
|
|
|
<BR>
|
|
|
|
<B>hdestroy</B>()
|
|
|
|
</TD><TD>Thread safety</TD><TD>MT-Unsafe race:hsearch<BR></TD></TR>
|
|
<TR VALIGN=top><TD>
|
|
<B>hcreate_r</B>(),
|
|
|
|
<B>hsearch_r</B>(),
|
|
|
|
<BR>
|
|
|
|
<B>hdestroy_r</B>()
|
|
|
|
</TD><TD>Thread safety</TD><TD>MT-Safe race:htab<BR></TD></TR>
|
|
</TABLE>
|
|
|
|
<A NAME="lbAH"> </A>
|
|
<H2>CONFORMING TO</H2>
|
|
|
|
The functions
|
|
<B>hcreate</B>(),
|
|
|
|
<B>hsearch</B>(),
|
|
|
|
and
|
|
<B>hdestroy</B>()
|
|
|
|
are from SVr4, and are described in POSIX.1-2001 and POSIX.1-2008.
|
|
<P>
|
|
|
|
The functions
|
|
<B>hcreate_r</B>(),
|
|
|
|
<B>hsearch_r</B>(),
|
|
|
|
and
|
|
<B>hdestroy_r</B>()
|
|
|
|
are GNU extensions.
|
|
<A NAME="lbAI"> </A>
|
|
<H2>NOTES</H2>
|
|
|
|
Hash table implementations are usually more efficient when the
|
|
table contains enough free space to minimize collisions.
|
|
Typically, this means that
|
|
<I>nel</I>
|
|
|
|
should be at least 25% larger than the maximum number of elements
|
|
that the caller expects to store in the table.
|
|
<P>
|
|
|
|
The
|
|
<B>hdestroy</B>()
|
|
|
|
and
|
|
<B>hdestroy_r</B>()
|
|
|
|
functions do not free the buffers pointed to by the
|
|
<I>key</I>
|
|
|
|
and
|
|
<I>data</I>
|
|
|
|
elements of the hash table entries.
|
|
(It can't do this because it doesn't know
|
|
whether these buffers were allocated dynamically.)
|
|
If these buffers need to be freed (perhaps because the program
|
|
is repeatedly creating and destroying hash tables,
|
|
rather than creating a single table whose lifetime
|
|
matches that of the program),
|
|
then the program must maintain bookkeeping data structures that
|
|
allow it to free them.
|
|
<A NAME="lbAJ"> </A>
|
|
<H2>BUGS</H2>
|
|
|
|
SVr4 and POSIX.1-2001 specify that <I>action</I>
|
|
is significant only for unsuccessful searches, so that an <B>ENTER</B>
|
|
should not do anything for a successful search.
|
|
In libc and glibc (before version 2.3), the
|
|
implementation violates the specification,
|
|
updating the <I>data</I> for the given <I>key</I> in this case.
|
|
<P>
|
|
|
|
Individual hash table entries can be added, but not deleted.
|
|
<A NAME="lbAK"> </A>
|
|
<H2>EXAMPLE</H2>
|
|
|
|
<P>
|
|
|
|
The following program inserts 24 items into a hash table, then prints
|
|
some of them.
|
|
<P>
|
|
|
|
|
|
#include <<A HREF="file:///usr/include/stdio.h">stdio.h</A>>
|
|
#include <<A HREF="file:///usr/include/stdlib.h">stdlib.h</A>>
|
|
#include <<A HREF="file:///usr/include/search.h">search.h</A>>
|
|
<P>
|
|
static char *data[] = { "alpha", "bravo", "charlie", "delta",
|
|
<BR> "echo", "foxtrot", "golf", "hotel", "india", "juliet",
|
|
<BR> "kilo", "lima", "mike", "november", "oscar", "papa",
|
|
<BR> "quebec", "romeo", "sierra", "tango", "uniform",
|
|
<BR> "victor", "whisky", "x-ray", "yankee", "zulu"
|
|
};
|
|
<P>
|
|
int
|
|
main(void)
|
|
{
|
|
<BR> ENTRY e, *ep;
|
|
<BR> int i;
|
|
<P>
|
|
<BR> hcreate(30);
|
|
<P>
|
|
<BR> for (i = 0; i < 24; i++) {
|
|
<BR> e.key = data[i];
|
|
<BR> /* data is just an integer, instead of a
|
|
<BR> pointer to something */
|
|
<BR> e.data = (void *) i;
|
|
<BR> ep = hsearch(e, ENTER);
|
|
<BR> /* there should be no failures */
|
|
<BR> if (ep == NULL) {
|
|
<BR> fprintf(stderr, "entry failed\n");
|
|
<BR> exit(EXIT_FAILURE);
|
|
<BR> }
|
|
<BR> }
|
|
<P>
|
|
<BR> for (i = 22; i < 26; i++) {
|
|
<BR> /* print two entries from the table, and
|
|
<BR> show that two are not in the table */
|
|
<BR> e.key = data[i];
|
|
<BR> ep = hsearch(e, FIND);
|
|
<BR> printf("%9.9s -> %9.9s:%d\n", e.key,
|
|
<BR> ep ? ep->key : "NULL", ep ? (int)(ep->data) : 0);
|
|
<BR> }
|
|
<BR> hdestroy();
|
|
<BR> exit(EXIT_SUCCESS);
|
|
}
|
|
|
|
<A NAME="lbAL"> </A>
|
|
<H2>SEE ALSO</H2>
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+bsearch">bsearch</A></B>(3),
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+lsearch">lsearch</A></B>(3),
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+malloc">malloc</A></B>(3),
|
|
|
|
<B><A HREF="/cgi-bin/man/man2html?3+tsearch">tsearch</A></B>(3)
|
|
|
|
<A NAME="lbAM"> </A>
|
|
<H2>COLOPHON</H2>
|
|
|
|
This page is part of release 5.05 of the Linux
|
|
<I>man-pages</I>
|
|
|
|
project.
|
|
A description of the project,
|
|
information about reporting bugs,
|
|
and the latest version of this page,
|
|
can be found at
|
|
<A HREF="https://www.kernel.org/doc/man-pages/.">https://www.kernel.org/doc/man-pages/.</A>
|
|
<P>
|
|
|
|
<HR>
|
|
<A NAME="index"> </A><H2>Index</H2>
|
|
<DL>
|
|
<DT id="4"><A HREF="#lbAB">NAME</A><DD>
|
|
<DT id="5"><A HREF="#lbAC">SYNOPSIS</A><DD>
|
|
<DT id="6"><A HREF="#lbAD">DESCRIPTION</A><DD>
|
|
<DT id="7"><A HREF="#lbAE">RETURN VALUE</A><DD>
|
|
<DT id="8"><A HREF="#lbAF">ERRORS</A><DD>
|
|
<DT id="9"><A HREF="#lbAG">ATTRIBUTES</A><DD>
|
|
<DT id="10"><A HREF="#lbAH">CONFORMING TO</A><DD>
|
|
<DT id="11"><A HREF="#lbAI">NOTES</A><DD>
|
|
<DT id="12"><A HREF="#lbAJ">BUGS</A><DD>
|
|
<DT id="13"><A HREF="#lbAK">EXAMPLE</A><DD>
|
|
<DT id="14"><A HREF="#lbAL">SEE ALSO</A><DD>
|
|
<DT id="15"><A HREF="#lbAM">COLOPHON</A><DD>
|
|
</DL>
|
|
<HR>
|
|
This document was created by
|
|
<A HREF="/cgi-bin/man/man2html">man2html</A>,
|
|
using the manual pages.<BR>
|
|
Time: 00:05:45 GMT, March 31, 2021
|
|
</BODY>
|
|
</HTML>
|