unixdev.net


Switch to SpeakEasy.net DSL

The Modular Manual Browser

Home Page
Manual: (SunOS-4.1.3)
Page:
Section:
Apropos / Subsearch:
optional field

HSEARCH(3)                 Library Functions Manual                 HSEARCH(3)



NAME
       hsearch, hcreate, hdestroy - manage hash search tables

SYNOPSIS
       #include <&lt;search.h>&gt;

       ENTRY *hsearch (item, action)
       ENTRY item;
       ACTION action;

       int hcreate (nel)
       unsigned nel;

       void hdestroy ( )

DESCRIPTION
       hsearch()  is  a hash-table search routine generalized from Knuth (6.4)
       Algorithm D.  It returns a pointer into a  hash  table  indicating  the
       location  at  which an entry can be found.  item is a structure of type
       ENTRY (defined in the <&lt;search.h>&gt; header file) containing two  pointers:
       item.key  points  to  the  comparison  key, and item.data points to any
       other data to be associated with that key.  (Pointers  to  types  other
       than  character  should  be cast to pointer-to-character.)  action is a
       member of an enumeration type ACTION indicating the disposition of  the
       entry  if  it  cannot  be found in the table.  ENTER indicates that the
       item should be inserted in the table at  an  appropriate  point.   FIND
       indicates  that  no  entry  should be made.  Unsuccessful resolution is
       indicated by the return of a NULL pointer.

       hcreate() allocates sufficient space for the table, and must be  called
       before  hsearch() is used.  nel is an estimate of the maximum number of
       entries that the table will  contain.   This  number  may  be  adjusted
       upward  by  the  algorithm  in  order  to obtain certain mathematically
       favorable circumstances.

       hdestroy() destroys the search table, and may be  followed  by  another
       call to hcreate.

NOTES
       hsearch() uses open addressing with a multiplicative hash function.

EXAMPLE
       The  following example will read in strings followed by two numbers and
       store them in a hash table, discarding duplicates.  It will  then  read
       in  strings  and find the matching entry in the hash table and print it
       out.

              #include <&lt;stdio.h>&gt;
              #include <&lt;search.h>&gt;
              struct info {       /* this is the info stored in the table */
                   int age, room; /* other than the key. */
              };
              #define
              NUM_EMPL    5000    /* # of elements in search table */
              main( )
              {
                   /* space to store strings */
                   char string_space[NUM_EMPL*20];
                   /* space to store employee info */
                   struct info info_space[NUM_EMPL];
                   /* next avail space in string_space */
                   char *str_ptr = string_space;
                   /* next avail space in info_space */
                   struct info *info_ptr = info_space;
                   ENTRY item, *found_item, *hsearch( );
                   /* name to look for in table */
                   char name_to_find[30];
                   int i = 0;
                   /* create table */
                   (void) hcreate(NUM_EMPL);
                   while (scanf("%s%d%d", str_ptr, &&amp;info_ptr->&gt;age,
                          &&amp;info_ptr->&gt;room) !=
              EOF &&amp;&&amp; i++ <&lt;
              NUM_EMPL) {
                        /* put info in structure, and structure in item */
                        item.key = str_ptr;
                        item.data = (char *)info_ptr;
                        str_ptr += strlen(str_ptr) + 1;
                        info_ptr++;
                        /* put item into table */
                        (void) hsearch(item,
              ENTER);
                   }
                   /* access table */
                   item.key = name_to_find;
                   while (scanf("%s", item.key) != EOF) {
                       if ((found_item = hsearch(item,
              FIND)) != NULL) {
                        /* if item is in the table */
                         (void)printf("found %s, age = %d, room = %d\n",
                             found_item->&gt;key,
                             ((struct info *)found_item->&gt;data)->&gt;age,
                             ((struct info *)found_item->&gt;data)->&gt;room);
                       } else {
                         (void)printf("no such employee %s\n",
                             name_to_find);
                       }
                   }
              }

SEE ALSO
       bsearch(3), lsearch(3), malloc(3V), string(3), tsearch(3)

DIAGNOSTICS
       hsearch() returns a NULL pointer if either the action is FIND  and  the
       item could not be found or the action is ENTER and the table is full.

       hcreate()  returns  zero if it cannot allocate sufficient space for the
       table.

WARNING
       hsearch() and hcreate() use malloc(3V) to allocate space.

BUGS
       Only one hash search table may be active at any given time.



                               7 September 1988                     HSEARCH(3)