| <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: <a rel="next" accesskey="n" href="Tree-Search-Function.html#Tree-Search-Function">Tree Search Function</a>, |
| Previous: <a rel="previous" accesskey="p" href="Search_002fSort-Example.html#Search_002fSort-Example">Search/Sort Example</a>, |
| Up: <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"> |
| — 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 “The Art of |
| Computer Programming, Part 3: Searching and Sorting” 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"> |
| — 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"> |
| — 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"> |
| — 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"> |
| — 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"> |
| — 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"> |
| — 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> |
| |
