<html lang="en">
<head>
<title>Hash Search Function - The GNU C Library</title>
<meta http-equiv="Content-Type" content="text/html">
<meta name="description" content="The GNU C Library">
<meta name="generator" content="makeinfo 4.13">
<link title="Top" rel="start" href="index.html#Top">
<link rel="up" href="Searching-and-Sorting.html#Searching-and-Sorting" title="Searching and Sorting">
<link rel="prev" href="Search_002fSort-Example.html#Search_002fSort-Example" title="Search/Sort Example">
<link rel="next" href="Tree-Search-Function.html#Tree-Search-Function" title="Tree Search Function">
<link href="http://www.gnu.org/software/texinfo/" rel="generator-home" title="Texinfo Homepage">
<!--
This file documents the GNU C library.

This is Edition 0.12, last updated 2007-10-27,
of `The GNU C Library Reference Manual', for version
2.8 (Sourcery G++ Lite 2011.03-41).

Copyright (C) 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2001, 2002,
2003, 2007, 2008, 2010 Free Software Foundation, Inc.

Permission is granted to copy, distribute and/or modify this document
under the terms of the GNU Free Documentation License, Version 1.3 or
any later version published by the Free Software Foundation; with the
Invariant Sections being ``Free Software Needs Free Documentation''
and ``GNU Lesser General Public License'', the Front-Cover texts being
``A GNU Manual'', and with the Back-Cover Texts as in (a) below.  A
copy of the license is included in the section entitled "GNU Free
Documentation License".

(a) The FSF's Back-Cover Text is: ``You have the freedom to
copy and modify this GNU manual.  Buying copies from the FSF
supports it in developing GNU and promoting software freedom.''-->
<meta http-equiv="Content-Style-Type" content="text/css">
<style type="text/css"><!--
  pre.display { font-family:inherit }
  pre.format  { font-family:inherit }
  pre.smalldisplay { font-family:inherit; font-size:smaller }
  pre.smallformat  { font-family:inherit; font-size:smaller }
  pre.smallexample { font-size:smaller }
  pre.smalllisp    { font-size:smaller }
  span.sc    { font-variant:small-caps }
  span.roman { font-family:serif; font-weight:normal; } 
  span.sansserif { font-family:sans-serif; font-weight:normal; } 
--></style>
<link rel="stylesheet" type="text/css" href="../cs.css">
</head>
<body>
<div class="node">
<a name="Hash-Search-Function"></a>
<p>
Next:&nbsp;<a rel="next" accesskey="n" href="Tree-Search-Function.html#Tree-Search-Function">Tree Search Function</a>,
Previous:&nbsp;<a rel="previous" accesskey="p" href="Search_002fSort-Example.html#Search_002fSort-Example">Search/Sort Example</a>,
Up:&nbsp;<a rel="up" accesskey="u" href="Searching-and-Sorting.html#Searching-and-Sorting">Searching and Sorting</a>
<hr>
</div>

<h3 class="section">9.5 The <code>hsearch</code> function.</h3>

<p>The functions mentioned so far in this chapter are for searching in a sorted
or unsorted array.  There are other methods to organize information
which later should be searched.  The costs of insert, delete and search
differ.  One possible implementation is using hashing tables. 
The following functions are declared in the header file <samp><span class="file">search.h</span></samp>.

<!-- search.h -->
<!-- SVID -->
<div class="defun">
&mdash; Function: int <b>hcreate</b> (<var>size_t nel</var>)<var><a name="index-hcreate-835"></a></var><br>
<blockquote><p>The <code>hcreate</code> function creates a hashing table which can contain at
least <var>nel</var> elements.  There is no possibility to grow this table so
it is necessary to choose the value for <var>nel</var> wisely.  The method
used to implement this function might make it necessary to make the
number of elements in the hashing table larger than the expected maximal
number of elements.  Hashing tables usually work inefficiently if they are
filled 80% or more.  The constant access time guaranteed by hashing can
only be achieved if few collisions exist.  See Knuth's &ldquo;The Art of
Computer Programming, Part 3: Searching and Sorting&rdquo; for more
information.

        <p>The weakest aspect of this function is that there can be at most one
hashing table used through the whole program.  The table is allocated
in local memory out of control of the programmer.  As an extension the
GNU C library provides an additional set of functions with an reentrant
interface which provide a similar interface but which allow to keep
arbitrarily many hashing tables.

        <p>It is possible to use more than one hashing table in the program run if
the former table is first destroyed by a call to <code>hdestroy</code>.

        <p>The function returns a non-zero value if successful.  If it return zero
something went wrong.  This could either mean there is already a hashing
table in use or the program runs out of memory. 
</p></blockquote></div>

<!-- search.h -->
<!-- SVID -->
<div class="defun">
&mdash; Function: void <b>hdestroy</b> (<var>void</var>)<var><a name="index-hdestroy-836"></a></var><br>
<blockquote><p>The <code>hdestroy</code> function can be used to free all the resources
allocated in a previous call of <code>hcreate</code>.  After a call to this
function it is again possible to call <code>hcreate</code> and allocate a new
table with possibly different size.

        <p>It is important to remember that the elements contained in the hashing
table at the time <code>hdestroy</code> is called are <em>not</em> freed by this
function.  It is the responsibility of the program code to free those
strings (if necessary at all).  Freeing all the element memory is not
possible without extra, separately kept information since there is no
function to iterate through all available elements in the hashing table. 
If it is really necessary to free a table and all elements the
programmer has to keep a list of all table elements and before calling
<code>hdestroy</code> s/he has to free all element's data using this list. 
This is a very unpleasant mechanism and it also shows that this kind of
hashing tables is mainly meant for tables which are created once and
used until the end of the program run. 
</p></blockquote></div>

   <p>Entries of the hashing table and keys for the search are defined using
this type:

<div class="defun">
&mdash; Data type: <b>struct ENTRY</b><var><a name="index-struct-ENTRY-837"></a></var><br>
<blockquote><p>Both elements of this structure are pointers to zero-terminated strings. 
This is a limiting restriction of the functionality of the
<code>hsearch</code> functions.  They can only be used for data sets which use
the NUL character always and solely to terminate the records.  It is not
possible to handle general binary data.

          <dl>
<dt><code>char *key</code><dd>Pointer to a zero-terminated string of characters describing the key for
the search or the element in the hashing table. 
<br><dt><code>char *data</code><dd>Pointer to a zero-terminated string of characters describing the data. 
If the functions will be called only for searching an existing entry
this element might stay undefined since it is not used. 
</dl>
        </p></blockquote></div>

<!-- search.h -->
<!-- SVID -->
<div class="defun">
&mdash; Function: ENTRY * <b>hsearch</b> (<var>ENTRY item, ACTION action</var>)<var><a name="index-hsearch-838"></a></var><br>
<blockquote><p>To search in a hashing table created using <code>hcreate</code> the
<code>hsearch</code> function must be used.  This function can perform simple
search for an element (if <var>action</var> has the <code>FIND</code>) or it can
alternatively insert the key element into the hashing table.  Entries
are never replaced.

        <p>The key is denoted by a pointer to an object of type <code>ENTRY</code>.  For
locating the corresponding position in the hashing table only the
<code>key</code> element of the structure is used.

        <p>If an entry with matching key is found the <var>action</var> parameter is
irrelevant.  The found entry is returned.  If no matching entry is found
and the <var>action</var> parameter has the value <code>FIND</code> the function
returns a <code>NULL</code> pointer.  If no entry is found and the
<var>action</var> parameter has the value <code>ENTER</code> a new entry is added
to the hashing table which is initialized with the parameter <var>item</var>. 
A pointer to the newly added entry is returned. 
</p></blockquote></div>

   <p>As mentioned before the hashing table used by the functions described so
far is global and there can be at any time at most one hashing table in
the program.  A solution is to use the following functions which are a
GNU extension.  All have in common that they operate on a hashing table
which is described by the content of an object of the type <code>struct
hsearch_data</code>.  This type should be treated as opaque, none of its
members should be changed directly.

<!-- search.h -->
<!-- GNU -->
<div class="defun">
&mdash; Function: int <b>hcreate_r</b> (<var>size_t nel, struct hsearch_data *htab</var>)<var><a name="index-hcreate_005fr-839"></a></var><br>
<blockquote><p>The <code>hcreate_r</code> function initializes the object pointed to by
<var>htab</var> to contain a hashing table with at least <var>nel</var> elements. 
So this function is equivalent to the <code>hcreate</code> function except
that the initialized data structure is controlled by the user.

        <p>This allows having more than one hashing table at one time.  The memory
necessary for the <code>struct hsearch_data</code> object can be allocated
dynamically.  It must be initialized with zero before calling this
function.

        <p>The return value is non-zero if the operation was successful.  If the
return value is zero, something went wrong, which probably means the
programs ran out of memory. 
</p></blockquote></div>

<!-- search.h -->
<!-- GNU -->
<div class="defun">
&mdash; Function: void <b>hdestroy_r</b> (<var>struct hsearch_data *htab</var>)<var><a name="index-hdestroy_005fr-840"></a></var><br>
<blockquote><p>The <code>hdestroy_r</code> function frees all resources allocated by the
<code>hcreate_r</code> function for this very same object <var>htab</var>.  As for
<code>hdestroy</code> it is the programs responsibility to free the strings
for the elements of the table. 
</p></blockquote></div>

<!-- search.h -->
<!-- GNU -->
<div class="defun">
&mdash; Function: int <b>hsearch_r</b> (<var>ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab</var>)<var><a name="index-hsearch_005fr-841"></a></var><br>
<blockquote><p>The <code>hsearch_r</code> function is equivalent to <code>hsearch</code>.  The
meaning of the first two arguments is identical.  But instead of
operating on a single global hashing table the function works on the
table described by the object pointed to by <var>htab</var> (which is
initialized by a call to <code>hcreate_r</code>).

        <p>Another difference to <code>hcreate</code> is that the pointer to the found
entry in the table is not the return value of the functions.  It is
returned by storing it in a pointer variables pointed to by the
<var>retval</var> parameter.  The return value of the function is an integer
value indicating success if it is non-zero and failure if it is zero. 
In the latter case the global variable <var>errno</var> signals the reason for
the failure.

          <dl>
<dt><code>ENOMEM</code><dd>The table is filled and <code>hsearch_r</code> was called with an so far
unknown key and <var>action</var> set to <code>ENTER</code>. 
<br><dt><code>ESRCH</code><dd>The <var>action</var> parameter is <code>FIND</code> and no corresponding element
is found in the table. 
</dl>
        </p></blockquote></div>

   </body></html>