GNU Info

Info Node: (libc.info)Hash Search Function

(libc.info)Hash Search Function


Next: Tree Search Function Prev: Search/Sort Example Up: Searching and Sorting
Enter node , (file) or (file)node

The `hsearch' function.
=======================

   The functions mentioned so far in this chapter are 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.

 - Function: int hcreate (size_t NEL)
     The `hcreate' function creates a hashing table which can contain at
     least NEL elements.  There is no possibility to grow this table so
     it is necessary to choose the value for NEL wisely.  The used
     methods 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
     inefficient 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.

     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.

     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 `hdestroy'.

     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.

 - Function: void hdestroy (void)
     The `hdestroy' function can be used to free all the resources
     allocated in a previous call of `hcreate'.  After a call to this
     function it is again possible to call `hcreate' and allocate a new
     table with possibly different size.

     It is important to remember that the elements contained in the
     hashing table at the time `hdestroy' is called are _not_ 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 `hdestroy' 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.

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

 - Data type: struct ENTRY
     Both elements of this structure are pointers to zero-terminated
     strings.  This is a limiting restriction of the functionality of
     the `hsearch' 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.

    `char *key'
          Pointer to a zero-terminated string of characters describing
          the key for the search or the element in the hashing table.

    `char *data'
          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.

 - Function: ENTRY * hsearch (ENTRY ITEM, ACTION ACTION)
     To search in a hashing table created using `hcreate' the `hsearch'
     function must be used.  This function can perform simple search
     for an element (if ACTION has the `FIND') or it can alternatively
     insert the key element into the hashing table, possibly replacing
     a previous value (if ACTION is `ENTER').

     The key is denoted by a pointer to an object of type `ENTRY'.  For
     locating the corresponding position in the hashing table only the
     `key' element of the structure is used.

     The return value depends on the ACTION parameter value.  If it is
     `FIND' the value is a pointer to the matching element in the
     hashing table or `NULL' if no matching element exists.  If ACTION
     is `ENTER' the return value is only `NULL' if the programs runs
     out of memory while adding the new element to the table.
     Otherwise the return value is a pointer to the element in the
     hashing table which contains newly added element based on the data
     in KEY.

   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 `struct hsearch_data'.  This type should be treated
as opaque, none of its members should be changed directly.

 - Function: int hcreate_r (size_t NEL, struct hsearch_data *HTAB)
     The `hcreate_r' function initializes the object pointed to by HTAB
     to contain a hashing table with at least NEL elements.  So this
     function is equivalent to the `hcreate' function except that the
     initialized data structure is controlled by the user.

     This allows having more than one hashing table at one time.  The
     memory necessary for the `struct hsearch_data' object can be
     allocated dynamically.

     The return value is non-zero if the operation were successful.  if
     the return value is zero something went wrong which probably means
     the programs runs out of memory.

 - Function: void hdestroy_r (struct hsearch_data *HTAB)
     The `hdestroy_r' function frees all resources allocated by the
     `hcreate_r' function for this very same object HTAB.  As for
     `hdestroy' it is the programs responsibility to free the strings
     for the elements of the table.

 - Function: int hsearch_r (ENTRY ITEM, ACTION ACTION, ENTRY **RETVAL,
          struct hsearch_data *HTAB)
     The `hsearch_r' function is equivalent to `hsearch'.  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 HTAB (which is initialized
     by a call to `hcreate_r').

     Another difference to `hcreate' 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
     RETVAL 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 ERRNO signals the
     reason for the failure.

    `ENOMEM'
          The table is filled and `hsearch_r' was called with an so far
          unknown key and ACTION set to `ENTER'.

    `ESRCH'
          The ACTION parameter is `FIND' and no corresponding element
          is found in the table.


automatically generated by info2www version 1.2.2.9