closedhash.h

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

/*
  $Id: ClosedHash.h,v 1.3 1997/02/02 01:31:03 matt Exp $

  Closed hash table.

  (c) July 95 Matt Phillips.
  */

#ifndef _HASHC_H
#define _HASHC_H

#include "Container.h"
#include "Data.h"
#include "LinkedAssocItem.h"

/*
  K is the key type, T is the associated value type
  A is a LinkedAssoc type
  HASH must be a class with a 'int hash (T &)' member
  SIZE is number of hash buckets
  */
template <class K, class T, class A, class HASH, int SIZE>
class ClosedHashImp : public Container<T>
{
public:
  
  typedef ClosedHashImpIter<K, T, A, HASH, SIZE> Iterator;

  ClosedHashImp ();
  virtual ~ClosedHashImp () {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;

  // an array of linked lists
  A *table [SIZE];
};

template <class K, class T, class A, class HASH, int SIZE>
ClosedHashImp<K, T, A, HASH, SIZE>::ClosedHashImp ()
{
  for (int c = 0; c < SIZE; c++)
    table [c] = 0;
}

template <class K, class T, class A, class HASH, int SIZE>
void ClosedHashImp<K, T, A, HASH, SIZE>::clear ()
{
  for (int c = 0; c < SIZE; c++)
  {
    for (A *e = table [c], *next; e; e = next)
    {
      next = e->next;
      delete e;
    }
  }

  _nItems = 0;
}

template <class K, class T, class A, class HASH, int SIZE>
T &ClosedHashImp<K, T, A, HASH, SIZE>::add (const K &key, T &value)
{
  int hash = HASH::hash (key);
  A **bucket = table + hash;

  CHECK (hash >= 0 && hash < SIZE, "hash out of bounds");
   
  *bucket = new A (key, value, *bucket);

  _nItems++;

  return (*bucket)->ref ();
}

template <class K, class T, class A, class HASH, int SIZE>
int ClosedHashImp<K, T, A, HASH, SIZE>::remove (const K &key)
{
  int hash = HASH::hash (key);

  CHECK (hash >= 0 && hash < SIZE, "hash out of bounds");

  // search the linked list for matching value
  for (A *e = table [hash], *prev = 0; e; prev = e, e = e->next)
  {
    if (e->refKey () == key)
    {
      if (prev)
	prev->next = e->next;
      else
	table [hash] = e->next;
	 
      delete e;
      _nItems--;
	 
      return 1;
    }
  }

  return 0;			// not found
}

template <class K, class T, class A, class HASH, int SIZE>
T *ClosedHashImp<K, T, A, HASH, SIZE>::get (const K &key) const
{
  int hash = HASH::hash (key);

  CHECK (hash >= 0 && hash < SIZE, "hash out of bounds");

  // search the linked list for matching value
  for (A *e = table [hash]; e; e = e->next)
  {
    if (e->refKey () == key)
      return &(e->ref ());
  }

  return 0;			// not found
}

template <class K, class T, class A, class HASH, int SIZE>
class ClosedHashImpIter : public ContainerIter<T>
{
public:

  ClosedHashImpIter (const ClosedHashImp<K, T, A, HASH, SIZE> &h) :
    hashTable (h) {reset ();}
   
  virtual void reset () {row = hashTable.table + (SIZE - 1); cueNext ();}
  virtual operator int () const {return int (row >= hashTable.table);}
  virtual void operator ++ (int)
  {ITER_BOUND (row >= hashTable.table);
  col = col->next; if (!col) {row--; cueNext ();}}
  virtual T &ref () const
  {ITER_CURRENT (row >= hashTable.table); return col->ref ();}
  const K &refKey () const
  {ITER_CURRENT (row >= hashTable.table); return col->refKey ();}

protected:

  A * const *row, *col;	// col must be valid unless row is null
  const ClosedHashImp<K, T, A, HASH, SIZE> &hashTable;

  void cueNext ();
};

template <class K, class T, class A, class HASH, int SIZE>
void ClosedHashImpIter<K, T, A, HASH, SIZE>::cueNext ()
{
  for ( ; row >= hashTable.table; row--)
  {
    col = row [0];
    if (col) return;
  }
}

#define TypeDClosedHash(K, T, HASH, SIZE) \
ClosedHashImp<K, T, DLinkedAssocItem<K, T>, HASH, SIZE>

#define TypeIClosedHash(K, T, HASH, SIZE) \
ClosedHashImp<K, T, ITLinkedAssocItem<K, T, 0>, HASH, SIZE>

#define TypeIClosedHashIter(K, T, HASH, SIZE) \
ClosedHashImpIter<K, T, ITLinkedAssocItem<K, T, 0>, HASH, SIZE>

#define TypeIOClosedHash(K, T, HASH, SIZE) \
ClosedHashImp<K, T, ITLinkedAssocItem<K, T, 1>, HASH, SIZE>

#endif