openhash.h

用于词法分析的词法分析器

/* $Id: OpenHash.h,v 1.3 1997/02/02 01:31:04 matt Exp $
   
   Open expanding hash table.
   
   Current strategy is to expand the hash table by powers of 2 (0, 16,
   32, 64...) when a hash fails and the table is at least 33% full.
   If a hash fails and the table is < 33% full, a fatal error occurs:
   either a better hash method or a better hash table design is needed
   in this case :(.

   (c) July 96 Matt Phillips. */

#ifndef _HASH_OPEN_H
#define _HASH_OPEN_H

#include "Container.h"
#include "AssociationItem.h"

// invoked when no place can be found for an item in the hash table.
#define HASH_FAIL ABORT ("OpenHash hash failure")

/* K is the key type, T is the associated value type A is a Assoc type
   from associtm.h.  HASH must be a class with an 'int hash (const K
   &)' member */
template <class K, class T, class A, class HASH>
class OpenHashImp : public Container<T>
{
public:
  
  typedef OpenHashImpIter<K, T, A, HASH> Iterator;

  OpenHashImp ();
  virtual ~OpenHashImp () {clear ();}

  virtual const char *name () const {return "HashTable";}

  // add (key, value) to the hash table and return reference to value
  // in table.
  T &add (const K &key, T &value);

  // returns true if pair with <key> was removed.
  int remove (const K &key);

  // returns value associated with <key> or null if not found.
  T *get (const K &key) const;

  // return true if pair with <key> exists.
  int exists (const K &key) const {return get (key) != 0;}

  // removes all values from table.
  void clear ();

  virtual Iterator *makeIter () const {return new Iterator (*this);}

protected:

  friend Iterator;

  enum {InitTableSize = 16};

  // true if hash table is full.
  int full () const {return _nItems >= tableSize;}
  // add item to tabke under key.  returns false if item could not be
  // added.
  int addItem (const K &key, A *item);
  // expand hash table to next size increment.
  void expand ();
  // find item with key in table and return pointer to the bucket it
  // resides in.
  A **findItem (const K &key) const;

  A **table;			// the hash table 
  int tableSize;		// the current size of table
};

template <class K, class T, class A, class HASH>
OpenHashImp<K, T, A, HASH>::OpenHashImp () :
  tableSize (0), table (0)
{
}

template <class K, class T, class A, class HASH>
void OpenHashImp<K, T, A, HASH>::clear ()
{
  for (int c = 0; c < tableSize; c++)
  {
    delete table [c];
    table [c] = 0;
  }

  tableSize = 0;
  delete table;

  _nItems = 0;
}

template <class K, class T, class A, class HASH>
T &OpenHashImp<K, T, A, HASH>::add (const K &key, T &value)
{
  A *item = new A (key, value);

  if (full ())
    expand ();

  if (!addItem (key, item))
  {
    if (nItems () * 3 > tableSize)
    {				// expand if table is > 33% full
      expand ();
      if (!addItem (key, item))
	HASH_FAIL;
    } else
      HASH_FAIL;
  }

  _nItems++;

  return item->ref ();
}

template <class K, class T, class A, class HASH>
int OpenHashImp<K, T, A, HASH>::addItem (const K &key, A *item)
{
  static int steps [] = {1, 3, 7, 11, 13, 17, -1};

  int hash = HASH::hash (key) % tableSize;
  A **bucket = table + hash;

  if (*bucket == 0)
  {
    *bucket = item;
    return 1;
  } else if ((*bucket)->refKey () == key)
  {
    delete *bucket;
    *bucket = item;
    return 1;
  }

  // ideal location not available, look for others
  for (int *step = steps; *step != -1; step++)
  {
    hash = (hash + *step) % tableSize;
    bucket = table + hash;

    if (*bucket == 0)
    {
      *bucket = item;
      return 1;
    } else if ((*bucket)->refKey () == key)
    {
      delete *bucket;
      *bucket = item;
      return 1;
    }
  }

  return 0;
}

template <class K, class T, class A, class HASH>
void OpenHashImp<K, T, A, HASH>::expand ()
{
  int newTableSize = tableSize == 0 ? InitTableSize : tableSize * 2;
  A **newTable = new A * [newTableSize];
  int i;

  // null all entries
  for (i = 0; i < newTableSize; i++)
    newTable [i] = 0;

  // rehash
  for (i = 0; i < tableSize; i++)
  {
    A *item = table [i];
    if (item)
    {
      int hash = HASH::hash (item->refKey ()) % newTableSize;
      if (!addItem (item->refKey (), item))
	HASH_FAIL;
    }
  }

  // replace old table with new
  delete table;
  table = newTable;
  tableSize = newTableSize;
}

template <class K, class T, class A, class HASH>
int OpenHashImp<K, T, A, HASH>::remove (const K &key)
{
  A **bucket = findItem (key);

  if (bucket)
  {
    delete *bucket;
    *bucket = 0;
    _nItems--;
    return 1;
  } else
    return 0;
}

template <class K, class T, class A, class HASH>
T *OpenHashImp<K, T, A, HASH>::get (const K &key) const
{
  A **bucket = findItem (key);

  if (bucket)
    return &((*bucket)->ref ());
  else
    return 0;
}

template <class K, class T, class A, class HASH>
A **OpenHashImp<K, T, A, HASH>::findItem (const K &key) const
{
  static int steps [] = {1, 3, 7, 11, 13, 17, -1};

  if (tableSize == 0)
    return 0;

  int hash = HASH::hash (key) % tableSize;
  A **bucket = table + hash;

  if (*bucket != 0 && (*bucket)->refKey () == key)
  {
    return bucket;
  }

  for (int *step = steps; *step != -1; step++)
  {
    hash = (hash + *step) % tableSize;
    bucket = table + hash;

    if (*bucket != 0 && (*bucket)->refKey () == key)
    {
      return bucket;
    }
  }

  return 0;
}

template <class K, class T, class A, class HASH>
class OpenHashImpIter : public ContainerIter<T>
{
public:

  OpenHashImpIter (const OpenHashImp<K, T, A, HASH> &h) :
    hashTable (&h) {reset ();}

  OpenHashImpIter (const OpenHashImpIter<K, T, A, HASH> &i) :
    hashTable (i.hashTable), row (i.row) {}

  void reset (const OpenHashImp<K, T, A, HASH> &h)
  {
    hashTable = &h;
    reset ();
  }

  virtual void reset ()
  {
    row = hashTable->table + (hashTable->tableSize - 1);
    cueNext ();
  }

  virtual operator int () const {return int (row >= hashTable->table);}

  virtual void operator ++ (int)
  {
    ITER_BOUND (row >= hashTable->table);
    row--;
    cueNext ();
  }

  virtual T &ref () const
  {
    ITER_CURRENT (row >= hashTable->table);
    return (*row)->ref ();
  }

  const K &refKey () const
  {
    ITER_CURRENT (row >= hashTable->table);
    return (*row)->refKey ();
  }

protected:

  A **row;
  const OpenHashImp<K, T, A, HASH> *hashTable;

  void cueNext ();
};

template <class K, class T, class A, class HASH>
void OpenHashImpIter<K, T, A, HASH>::cueNext ()
{
  while (row >= hashTable->table)
  {
    if (*row)
      break;
    row--;
  } 
}

#define TypeDOpenHash(K, T, HASH) \
OpenHashImp<K, T, DAssocItem<K, T>, HASH>

#define TypeIOpenHash(K, T, HASH) \
OpenHashImp<K, T, ITAssocItem<K, T, 0>, HASH>

#define TypeIOpenHashIter(K, T, HASH) \
OpenHashImpIter<K, T, ITAssocItem<K, T, 0>, HASH>

#define TypeIOOpenHash(K, T, HASH) \
OpenHashImp<K, T, ITAssocItem<K, T, 1>, HASH>

#endif