iflHashTable(3)

NAME
     iflHashTable, iflHashElem - base classes from which hash table
     implementations may be derived

INHERITS FROM
     This is a base class.

HEADER FILE
     #include <ifl/iflHashTable.h>

CLASS DESCRIPTION
     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 match() method.  In addition, a hash function must be defined and
     used to fill in the hashIndex field of any hash table elements (derived
     from iflHashElem) that are to be inserted into the table.  The match()
     method is then used to compare elements when a collision occurs on the
     hashIndex 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 hashIndex 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.

CLASS MEMBER FUNCTION SUMMARY
     Constructor

          iflHashTable(int maxEntries=0)

     Manipulating

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


     Query

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

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


     Performance Statistics

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


FUNCTION DESCRIPTIONS
     iflHashTable()

          iflHashTable(int maxEntries=0)


          Creates an empty iflHashTable, with initial size large enough to
          hold maxEntries; 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 setFullFraction() for more
          details.

     clear()

          void clear()


          Removes all elements currently in the hash table.

     find()

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


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

     getFullFraction()

          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%).

     insert()

          void insert(iflHashElem* elem)


          Inserts the hash element, elem, into the hash table.  The hashIndex
          field must already be filled in.

     match()

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


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

     next()

          iflHashElem* next(int& index)


          This function is used to iterate through the filled entries of a
          hash table.  To start iterating, index 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.

     remove()

          void remove(iflHashElem* elem)


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

     setFullFraction()

          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
          frac is 1, the hash table will not grow, and insert() will fail when
          the table is full.

     clearStats()

          void clearStats()

          Resets the lookCount, totalLook, and maxLook member variables to
          zero.  lookCount holds a running total of the number of lookups
          (calls to find() or locate()).  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.

SEE ALSO
     iflDictionary