IRIX Base Documentation 2001 May/SGI IRIX Base Documentation 2001 May.iso/usr/share/catman/p_man/cat3/ifl/iflHashTable.z/iflHashTable

Text File | 1998-10-20 | 9.2 KB | 265 lines

iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))   IIIImmmmaaaaggggeeee FFFFoooorrrrmmmmaaaatttt LLLLiiiibbbbrrrraaaarrrryyyy CCCC++++++++ RRRReeeeffffeeeerrrreeeennnncccceeee MMMMaaaannnnuuuuaaaallll    iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))



NNNNAAAAMMMMEEEE
     iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee,,,, iiiiffffllllHHHHaaaasssshhhhEEEElllleeeemmmm - base classes from which hash table
     implementations may be derived

IIIINNNNHHHHEEEERRRRIIIITTTTSSSS FFFFRRRROOOOMMMM
     This is a base class.

HHHHEEEEAAAADDDDEEEERRRR FFFFIIIILLLLEEEE
     #include <ifl/iflHashTable.h>

CCCCLLLLAAAASSSSSSSS DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN
     This class implements an abstract hash-based lookup table.  To create a
     hash table, a derived class must be defined that specifies the pure
     virtual mmmmaaaattttcccchhhh() method.  In addition, a hash function must be defined and
     used to fill in the _h_a_s_h_I_n_d_e_x field of any hash table elements (derived
     from iflHashElem) that are to be inserted into the table.  The mmmmaaaattttcccchhhh()
     method is then used to compare elements when a collision occurs on the
     _h_a_s_h_I_n_d_e_x field.

     The iflHashElem class is defined as:

          struct iflHashElem {
              unsigned int hashIndex;
          };

     It is used as a base from which to derive classes of elements to be
     inserted into a hash table derived from iflHashTable.  The constructor of
     the derived class should fill in the _h_a_s_h_I_n_d_e_x field with an appropriate
     unsigned integer value for the hash index.  The hash function used to map
     a hash element to its hash index must be carefully chosed to minimize
     collisions (different elements mapping to the same index) to get the best
     performance from the hash table.

CCCCLLLLAAAASSSSSSSS MMMMEEEEMMMMBBBBEEEERRRR FFFFUUUUNNNNCCCCTTTTIIIIOOOONNNN SSSSUUUUMMMMMMMMAAAARRRRYYYY
     CCCCoooonnnnssssttttrrrruuuuccccttttoooorrrr

          iflHashTable(int maxEntries=0)

     MMMMaaaannnniiiippppuuuullllaaaattttiiiinnnngggg

          void clear()
          int insert(iflHashElem* elem)
          int remove(iflHashElem* elem)


     QQQQuuuueeeerrrryyyy

          iflHashElem* find(unsigned int index, const void* key)
          iflHashElem* next(int& index)
          float getFullFraction() const
          void setFullFraction(const float frac)




                                                                        PPPPaaaaggggeeee 1111






iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))   IIIImmmmaaaaggggeeee FFFFoooorrrrmmmmaaaatttt LLLLiiiibbbbrrrraaaarrrryyyy CCCC++++++++ RRRReeeeffffeeeerrrreeeennnncccceeee MMMMaaaannnnuuuuaaaallll    iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))



     KKKKeeeeyyyy mmmmaaaattttcccchhhhiiiinnnngggg

          virtual int match(const void* key,                   _p_r_o_t_e_c_t_e_d
                            const iflHashElem* elem) = 0


     PPPPeeeerrrrffffoooorrrrmmmmaaaannnncccceeee SSSSttttaaaattttiiiissssttttiiiiccccssss

          int lookCount;
          int totalLook;
          int maxLook;
          void clearStats()


FFFFUUUUNNNNCCCCTTTTIIIIOOOONNNN DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNNSSSS
     iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee(((())))

          iflHashTable(int maxEntries=0)


          Creates an empty iflHashTable, with initial size large enough to
          hold _m_a_x_E_n_t_r_i_e_s; the default value of zero will create a table with
          131 slots.  By default the hash table will automatically grow when
          it gets more than half full.  See sssseeeettttFFFFuuuullllllllFFFFrrrraaaaccccttttiiiioooonnnn() for more
          details.

     cccclllleeeeaaaarrrr(((())))

          void clear()


          Removes all elements currently in the hash table.

     ffffiiiinnnndddd(((())))

          iflHashElem* find(unsigned int index, const void* key)


          Finds the element with hash index, _i_n_d_e_x, and key value, _k_e_y.

     ggggeeeettttFFFFuuuullllllllFFFFrrrraaaaccccttttiiiioooonnnn(((())))

          float getFullFraction() const


          Returns the current fraction of the table, which when filled will
          cause the hash table to be expanded.  The default value is .5 (50%).

     iiiinnnnsssseeeerrrrtttt(((())))






                                                                        PPPPaaaaggggeeee 2222






iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))   IIIImmmmaaaaggggeeee FFFFoooorrrrmmmmaaaatttt LLLLiiiibbbbrrrraaaarrrryyyy CCCC++++++++ RRRReeeeffffeeeerrrreeeennnncccceeee MMMMaaaannnnuuuuaaaallll    iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))



          void insert(iflHashElem* elem)


          Inserts the hash element, _e_l_e_m, into the hash table.  The _h_a_s_h_I_n_d_e_x
          field must already be filled in.

     mmmmaaaattttcccchhhh(((())))

          virtual int match(const void* key,                   _p_r_o_t_e_c_t_e_d
                            const iflHashElem* elem) = 0


          This function is used to compare an element key, _k_e_y, with the key
          of another element, _e_l_e_m.  This function must be defined in any
          class derived from iflHashTable.

     nnnneeeexxxxtttt(((())))

          iflHashElem* next(int& index)


          This function is used to iterate through the filled entries of a
          hash table.  To start iterating, _i_n_d_e_x should be initiliazed to
          zero.  The index should not be altered on subsequent calls, as
          iflHashTable uses it to keep track of where it is in the table.  The
          returned value is a pointer to the next hash element in the table,
          or NULL, when there are no more entries left to iterate on in the
          table.

     rrrreeeemmmmoooovvvveeee(((())))

          void remove(iflHashElem* elem)


          This function is used to remove the hash table element, _e_l_e_m, from
          the table.

     sssseeeettttFFFFuuuullllllllFFFFrrrraaaaccccttttiiiioooonnnn(((())))

          void setFullFraction(const float frac)


          Sets the current fraction of the table, which when filled will cause
          the hash table to be expanded.  The default value is .5 (50%).  If
          _f_r_a_c is 1, the hash table will not grow, and iiiinnnnsssseeeerrrrtttt() will fail when
          the table is full.

     cccclllleeeeaaaarrrrSSSSttttaaaattttssss(((())))

          void clearStats()





                                                                        PPPPaaaaggggeeee 3333






iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))   IIIImmmmaaaaggggeeee FFFFoooorrrrmmmmaaaatttt LLLLiiiibbbbrrrraaaarrrryyyy CCCC++++++++ RRRReeeeffffeeeerrrreeeennnncccceeee MMMMaaaannnnuuuuaaaallll    iiiiffffllllHHHHaaaasssshhhhTTTTaaaabbbblllleeee((((3333))))



          Resets the lookCount, totalLook, and maxLook member variables to
          zero.  lookCount holds a running total of the number of lookups
          (calls to ffffiiiinnnndddd() or llllooooccccaaaatttteeee()).  totalLook holds the number of hashes
          and rehashes accumulated over all lookups.  maxLook holds the
          maximum number of rehashes ever required by a single lookup.

SSSSEEEEEEEE AAAALLLLSSSSOOOO
     iflDictionary















































                                                                        PPPPaaaaggggeeee 4444