hashtab.h

/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

/***************************************************************************/
/*                                                                         */
/*  File name:  hashtab.h                                                  */
/*  Purpose:    Definition of the HashTable template class.                */
/*                                                                         */
/***************************************************************************/

#include "cs2/allocator.h"
#ifndef CS2_HASHTAB_H
#define CS2_HASHTAB_H

#include "cs2/cs2.h"
#include "cs2/bitmanip.h"

#ifdef CS2_ALLOCINFO
#define allocate(x) allocate(x, __FILE__, __LINE__)
#define deallocate(x,y) deallocate(x, y, __FILE__, __LINE__)
#define reallocate(x,y,z) reallocate(x, y, z, __FILE__, __LINE__)
#endif

namespace CS2 {

// ------------------------------------------------------------------------
// HashTable
//
// An extensible hash table with arbitrary key and data types.  This
// template provides the basic functions of a hash table for given key
// and data types.  A specialization of struct HashInfo can be defined
// to customize the hash table for specific key-types.
// ------------------------------------------------------------------------

typedef uint32_t HashIndex;
typedef uint32_t HashValue; // If this is changed, then the Hash_FNV constants *must* be updated

const uint32_t kMinimumHashTableSize = 16;

#define CS2_HT_TEMPARGS <AKeyType, ADataType, Allocator, AHashInfo>
#define CS2_HT_TEMP template <typename AKeyType, typename ADataType, class Allocator, class AHashInfo>
#define CS2_HT_DECL HashTable <AKeyType, ADataType, Allocator, AHashInfo>
#define CS2_HTC_DECL HashTable <AKeyType, ADataType, Allocator, AHashInfo>::Cursor


/*
   An implementation of the public domain FNV 1a (Fowler/Noll/Vo) 32-bit hash function.
   For information on this hash see the IETF draft:
    Fowler, et al. "The FNV Non-Cryptographic Hash Algorithm"
    Last known URL: http://tools.ietf.org/html/draft-eastlake-fnv-06
*/
const HashValue CS2_FNV_PRIME = 0x01000193u;
const HashValue CS2_FNV_OFFSETBASIS = 0x811C9DC5u;
inline HashValue  Hash_FNV (const unsigned char *s, uint32_t len, HashValue v = CS2_FNV_OFFSETBASIS) {
  for (uint32_t i=0; i<len; i++) {
    v = v ^ s[i];
    v = v * CS2_FNV_PRIME;
  }

  if (v==0) v = (s[0] ^ len)|HashValue(1); // ensure it is non-zero
  return v;
}

/*
  A note on using and/or specializing HashInfo.

  The 'hv' parameter of HashInfo::Hash() is intended to provide a way to iteratively
  build up a hash from complex data that does not lend itself to encapsulation in
  a packed aggregate (ex: from info acquired during a tree traversal).

  Example usage:
  HashValue hv = CS2_DEFAULT_INITIALHASHVALUE
  For each node, N, in a pre-order traversal of an expression tree:
     hv = HashInfo::Hash( N.somefield, hv );
     hv = HashInfo::Hash( N.someotherfield, hv );
     /// ... and so on
  return hv;
 */

// The value here should match what's expected by the default hash function used in HashInfo.
const HashValue CS2_DEFAULT_INITIALHASHVALUE = CS2_FNV_OFFSETBASIS;

template <class AKeyType>
struct HashInfo {
  static HashValue  Hash  (const AKeyType &v1, const HashValue hv=CS2_DEFAULT_INITIALHASHVALUE) {
       return Hash_FNV((const unsigned char *)&v1, sizeof(v1), hv);
  }
  static bool       Equal (const AKeyType &v1, const AKeyType &v2) { return v1==v2;}
};

template <>
struct HashInfo<const char *> {
  static HashValue  Hash (const char * const &v1, const HashValue hv = CS2_FNV_OFFSETBASIS) {
    uint32_t i;
    const unsigned char *lv1 = (const unsigned char *)(v1);
    for (i=0; lv1[i]; i++) ;
    return Hash_FNV (lv1, i, hv);
  }

  static bool       Equal (const char * const &v1, const char * const &v2) {
    const char *lv1(v1), *lv2(v2);
    while (*lv1 == *lv2) {
      if (*lv1==0) return true;
      lv1+=1; lv2+=1;
    }
    return false;
  }
};

template <>
  struct HashInfo<char *> : public HashInfo<const char *> { };

template <typename First, typename Second>
struct CompoundHashKey {
  First  fFirst;
  Second fSecond;

  CompoundHashKey(const First &f, const Second &s):fFirst(f),fSecond(s){}
};

template <typename First, typename Second>
struct HashInfo<CompoundHashKey<First, Second> > {
  typedef CompoundHashKey<First, Second> Key;
  static HashValue  Hash (const Key &v1, const HashValue hv = CS2_DEFAULT_INITIALHASHVALUE) {
    HashValue h1 = HashInfo<First>::Hash(v1.fFirst, hv);
    HashValue h2 = HashInfo<Second>::Hash(v1.fSecond, h1);
    return h2;
  }

  static bool       Equal (const Key &v1, const Key &v2) {
    return HashInfo<First>::Equal(v1.fFirst, v2.fFirst) && HashInfo<Second>::Equal(v1.fSecond, v2.fSecond);
  }
};

template <typename AKeyType, typename ADataType,
          class Allocator,
          class AHashInfo = CS2::HashInfo<AKeyType> >
class HashTable : private Allocator {
 private:
  void init(HashIndex numElements);
  public:

 static  const uint32_t DefaultSize = 0; // for backward compat

  HashTable (uint32_t ignored, const Allocator &a = Allocator()) : Allocator(a),
    fTable(NULL),
    fMask(0),
    fNextFree(0),
    fTableSize(0),
    fHighestIndex(0)
    {
    }

  HashTable (const Allocator &a = Allocator()) : Allocator(a),
    fTable(NULL),
    fMask(0),
    fNextFree(0),
    fTableSize(0),
    fHighestIndex(0)
    {
    }

  ~HashTable();
  HashTable (const CS2_HT_DECL &);

  const Allocator& allocator() const { return *this;}

  CS2_HT_DECL &operator= (const CS2_HT_DECL &);

  // Return the data value at the given index
  const ADataType & operator[] (HashIndex) const;
  ADataType & operator[] (HashIndex);
  const ADataType &DataAt (HashIndex) const;
  ADataType &DataAt (HashIndex);

  // Set the data value at the given index
  void SetDataAt (HashIndex, const ADataType &);

  // Return the key value at the given index
  const AKeyType &KeyAt (HashIndex) const;

  // Return the data value for the given key. It is considered a program
  // error for the key not to exist given a call to this function. An assert
  // will occur in development builds.
  const ADataType& Get(const AKeyType&) const;

  // Locate a record with the given key.  Return true iff a record is
  // found.  If the record is found, set the index reference parameter.
  // If a hash value is given, use it instead of computing a new value.
  bool Locate(const AKeyType&) const;
  bool Locate(const AKeyType&, HashIndex&) const;
  bool Locate(const AKeyType&, HashIndex&, HashValue& hashValue) const;

  // Add a record given a key and data record.  Return true iff the record
  // is successfully added.  If a record with the given key already exists,
  // the add will fail.  If the add succeeds, the index reference parameter
  // is set to the index at which the record was added.  If a hash value is
  // given, it is used instead of recomputing the value based on the key.
  bool Add(const AKeyType&, const ADataType&, HashIndex&, HashValue hashValue = 0, bool noLocate = false);
  bool Add(const AKeyType&, const ADataType&);

  // Remove the record at the given index.
  void Remove (HashIndex);

  // Return the highest allocated index in the hash table
  HashIndex HighestIndex() const;

  // Return the number of bytes of memory used by the hash table
  unsigned long MemoryUsage() const;

  // Check is empty
  bool IsEmpty() const;

  // Clear the hashtab
  void MakeEmpty();

  // For preemptive growth of table.
  void GrowTo(uint32_t);

  // Dump hash table statistics to cout
  template <class str>
    void DumpStatistics(str &out);

  template <class ostr>
  friend ostr &operator << (ostr &out, CS2_HT_DECL &table) {

    typename CS2_HTC_DECL c(table);
    for (c.SetToFirst(); c.Valid(); c.SetToNext())
      out << "[" << table.KeyAt(c) << "]:" << table.DataAt(c) << "\n";
    return out;
  }

  class Cursor {
    public:

    Cursor (const CS2_HT_DECL &);
    Cursor (const Cursor &);
    // ~Cursor();

    // Set the cursor position
    HashIndex SetToFirst();
    HashIndex SetToNext();

    // Determine if the cursor points at a valid position
    bool Valid() const;

    // Convert the cursor to a table index.
    operator HashIndex() const;

    private:

    Cursor &operator= (const Cursor &);
    const CS2_HT_DECL &fTable;
    uint32_t         fIndex;
  };

  friend class Cursor ;

 protected:

  #define CS2_HTE_DECL CS2_HT_DECL::HashTableEntry

  class HashTableEntry {
    public:

    void *operator new (size_t, void *);

    HashTableEntry();
    ~HashTableEntry();
    HashTableEntry (const AKeyType &, const ADataType &, HashValue, HashIndex);
    HashTableEntry (const HashTableEntry &);
    HashTableEntry &operator= (const HashTableEntry &);

    const AKeyType  &Key() const;
    void             SetKey (const AKeyType &);

    ADataType       &Data();
    const ADataType &Data() const;
    void             SetData (const ADataType &);

    HashValue HashCode() const;
    void      SetHashCode (HashValue);

    bool   Valid() const;
    void      Invalidate();

    HashIndex CollisionChain() const;
    void      SetCollisionChain (HashIndex);

    private:

    AKeyType   fKey;
    ADataType  fData;
    HashValue  fHashCode;    // unmasked hash value
    HashIndex  fChain;       // collision chain

  };

  void Grow();
                            // handle growth of internal tables
  void GrowAndRehash( HashIndex, HashTableEntry *, HashIndex, HashIndex);

  HashTableEntry *fTable;
  uint32_t fTableSize;        // Total table size (closed + open)
  uint32_t fMask;             // Mask to compute modulus for closed area
  uint32_t fNextFree;         // Next free slot in the open area
  HashIndex fHighestIndex;  // Highest allocated index

};

// -----------------------------------------------------------------------
// HashTableEntry methods
// -----------------------------------------------------------------------

// HashTableEntry::operator new
//
// new operator that does not allocate storage.

CS2_HT_TEMP inline void *CS2_HTE_DECL::operator new (size_t, void *ptr) {
  return ptr;
}

// HashTableEntry::HashTableEntry
//
// Construct a hash table entry.

CS2_HT_TEMP inline CS2_HTE_DECL::HashTableEntry() :
fHashCode(0) { }

// HashTableEntry::HashTableEntry (...)
//
// Construct a hash table entry from parts.

CS2_HT_TEMP inline CS2_HTE_DECL::HashTableEntry (const AKeyType &key,
                                             const ADataType &data,
                                             HashValue value, HashIndex chain) :
fKey(key), fData(data), fHashCode(value), fChain(chain) { }

// HashTableEntry::~HashTableEntry
//
// Destroy a hash table entry.

CS2_HT_TEMP inline CS2_HTE_DECL::~HashTableEntry() {
  Invalidate();
}

// HashTableEntry::HashTableEntry (const HashTableEntry &)
//
// Copy construct a hash table entry.

CS2_HT_TEMP inline CS2_HTE_DECL::HashTableEntry (const typename CS2_HTE_DECL &entry) :
fKey(entry.fKey),
fData(entry.fData),
fHashCode(entry.fHashCode),
fChain(entry.fChain) { }

// HashTableEntry::operator=
//
// Assign a hash table entry to another.

CS2_HT_TEMP inline typename CS2_HTE_DECL &CS2_HTE_DECL::operator= (const typename CS2_HTE_DECL &entry) {
  fKey = entry.fKey;
  fData = entry.fData;
  fHashCode = entry.fHashCode;
  fChain = entry.fChain;

  return *this;
}

// HashTableEntry::Key
//
// Return a handle to the key.

CS2_HT_TEMP inline const AKeyType &CS2_HTE_DECL::Key() const {
  return fKey;
}

// HashTableEntry::SetKey
//
// Set the key value.

CS2_HT_TEMP inline void CS2_HTE_DECL::SetKey (const AKeyType &key) {
  fKey = key;
}

// HashTableEntry::Data
//
// Return a handle to the data.

CS2_HT_TEMP inline const ADataType &CS2_HTE_DECL::Data() const {
  return fData;
}

CS2_HT_TEMP inline ADataType &CS2_HTE_DECL::Data() {
  return fData;
}

// HashTableEntry::SetData
//
// Set the data value.

CS2_HT_TEMP inline void CS2_HTE_DECL::SetData (const ADataType &data) {
  fData = data;
}

// HashTableEntry::HashCode
//
// Return the hash code.

CS2_HT_TEMP inline HashValue CS2_HTE_DECL::HashCode() const {
  return fHashCode;
}

// HashTableEntry::SetHashCode
//
// Set the hash code.

CS2_HT_TEMP inline void CS2_HTE_DECL::SetHashCode (HashValue value) {
  fHashCode = value;
}

// HashTableEntry::Valid
//
// Predicate to determine if the entry is valid.

CS2_HT_TEMP inline bool CS2_HTE_DECL::Valid() const {
  return (fHashCode != 0);
}

// HashTableEntry::Invalidate
//
// Invalidate the entry.

CS2_HT_TEMP inline void CS2_HTE_DECL::Invalidate() {
  fHashCode = 0;
}

// HashTableEntry::CollisionChain
//
// Return the collision chain index.

CS2_HT_TEMP inline HashIndex CS2_HTE_DECL::CollisionChain() const {
  return fChain;
}

// HashTableEntry::SetCollisionChain
//
// Set the collision chain index.

CS2_HT_TEMP inline void CS2_HTE_DECL::SetCollisionChain (HashIndex chainIndex) {
  fChain = chainIndex;
}

// -----------------------------------------------------------------------
// HashTable methods
// -----------------------------------------------------------------------

// HashTable::operator[]
//
// Return a reference to the data at the given index.

CS2_HT_TEMP inline const ADataType &CS2_HT_DECL::operator[] (HashIndex index) const {
  return DataAt(index);
}

CS2_HT_TEMP inline ADataType &CS2_HT_DECL::operator[] (HashIndex index) {
  return DataAt(index);
}

// HashTable::DataAt
//
// Return a reference to the data at the given index.

CS2_HT_TEMP inline const ADataType &CS2_HT_DECL::DataAt (HashIndex index) const {
  CS2Assert (index < fTableSize, ("Hash index %d out of range", index));
  CS2Assert (fTable[index].Valid(), ("Invalid hash table entry"));

  return fTable[index].Data();
}

CS2_HT_TEMP inline ADataType &CS2_HT_DECL::DataAt (HashIndex index) {
  CS2Assert (index < fTableSize, ("Hash index %d out of range", index));
  CS2Assert (fTable[index].Valid(), ("Invalid hash table entry"));

  return fTable[index].Data();
}

// HashTable::SetDataAt
//
// Set the data at the given index.

CS2_HT_TEMP inline void CS2_HT_DECL::SetDataAt (HashIndex index, const ADataType & data) {
  CS2Assert (index < fTableSize, ("Hash index %d out of range", index));
  CS2Assert (fTable[index].Valid(), ("Invalid hash table entry"));

  fTable[index].SetData (data);
}

// HashTable::KeyAt
//
// Return a reference to the key at the given index.

CS2_HT_TEMP inline const AKeyType &CS2_HT_DECL::KeyAt (HashIndex index) const {
  CS2Assert (index < fTableSize, ("Hash index %d out of range", index));
  CS2Assert (fTable[index].Valid(), ("Invalid hash table entry"));

  return fTable[index].Key();
}

// HashTable::Locate
//
// Locate an entry in the hash table.

CS2_HT_TEMP inline bool CS2_HT_DECL::Locate(const AKeyType& key) const
{
  HashIndex tempIdx = 0;
  HashValue tempVal = 0;
  return Locate(key, tempIdx, tempVal);
}

CS2_HT_TEMP inline bool CS2_HT_DECL::Locate(const AKeyType& key, HashIndex& index) const
{
  HashValue tempVal = 0;
  return Locate(key, index, tempVal);
}

CS2_HT_TEMP inline bool CS2_HT_DECL::Add(const AKeyType& key, const ADataType& data)
{
  HashIndex hashIndex;
  return Add(key, data, hashIndex);
}

CS2_HT_TEMP inline const ADataType& CS2_HT_DECL::Get(const AKeyType& key) const
{
  HashIndex hashIndex;
  if(false == Locate(key, hashIndex))
    CS2Assert(false, ("Key was not found."));
  return DataAt(hashIndex);
}

// HashTable::HighestIndex
//
// Return the highest allocated index in the hash table

CS2_HT_TEMP inline HashIndex CS2_HT_DECL::HighestIndex() const {
  return fHighestIndex;
}

// HashTable::IsEmpty
//
// Predicate to determine if the hash table is empty.

CS2_HT_TEMP inline bool CS2_HT_DECL::IsEmpty() const {
  return (fHighestIndex == 0);
}

// -----------------------------------------------------------------------
// HashTable::Cursor methods
// -----------------------------------------------------------------------

// HashTable::Cursor::Cursor
//
// Construct a hash table cursor.

CS2_HT_TEMP inline CS2_HTC_DECL::Cursor (const CS2_HT_DECL &inputTable) :
fTable(inputTable),
fIndex(0) { }

CS2_HT_TEMP inline CS2_HTC_DECL::Cursor (const typename CS2_HTC_DECL &other) :
fTable(other.fTable),
fIndex(other.fIndex) { }

// HashTable::Cursor::SetToFirst
//
// Set the cursor to point to the first valid entry.

CS2_HT_TEMP inline HashIndex CS2_HTC_DECL::SetToFirst() {
  fIndex = 0;
  return SetToNext();
}

// HashTable::Cursor::SetToNext
//
// Set the cursor to point to the next valid entry.

CS2_HT_TEMP inline HashIndex CS2_HTC_DECL::SetToNext() {
  for (++fIndex; fIndex < fTable.fTableSize; ++fIndex) {
    if (Valid()) return fIndex;
  }

  return (fIndex = 0);
}

// HashTable::Cursor::Valid
//
// Predicate to determine if the entry currently pointed to is valid.

CS2_HT_TEMP inline bool CS2_HTC_DECL::Valid() const {
  return (fIndex != 0) && (fTable.fTable[fIndex].Valid() != 0);
}

// HashTable::Cursor::operator HashIndex
//
// Return the index of the entry currently pointed to.

CS2_HT_TEMP inline CS2_HTC_DECL::operator HashIndex() const {
  return fIndex;
}

// -----------------------------------------------------------------------
// HashTable methods
// -----------------------------------------------------------------------

CS2_HT_TEMP void
inline CS2_HT_DECL::init(HashIndex numElements) {
  HashIndex freeIndex, hashIndex;

  HashIndex const closedAreaSize =
    BitManipulator::CeilingPowerOfTwo(numElements) < kMinimumHashTableSize ?
      kMinimumHashTableSize :
      BitManipulator::CeilingPowerOfTwo(numElements);

  HashIndex const openAreaSize = closedAreaSize / 4;

  HashIndex const newSize = closedAreaSize + openAreaSize;
  HashTableEntry * const newTable = (HashTableEntry *) Allocator::allocate(newSize * sizeof(HashTableEntry));
  if (newTable == NULL)
    SystemResourceError::Memory();

  fTable = newTable;
  fTableSize = newSize;
  fMask = closedAreaSize - 1;
  fNextFree = closedAreaSize + 1;
  fHighestIndex = 0;

  // Invalidate all of the hash table entries.
  for (hashIndex = 0; hashIndex < fNextFree; ++hashIndex) {
    fTable[hashIndex].Invalidate();
  }

  // Initialize the rehash area to link up the free chain
  for (freeIndex = fNextFree;
       freeIndex < fTableSize - 1;
       ++freeIndex) {
    fTable[freeIndex].Invalidate();
    fTable[freeIndex].SetCollisionChain (freeIndex + 1);
  }
  fTable[fTableSize - 1].Invalidate();
  fTable[fTableSize - 1].SetCollisionChain (0);
}

// HashTable::~HashTable
//
// Destroy a hash table.

CS2_HT_TEMP inline CS2_HT_DECL::~HashTable () {
  MakeEmpty();
}

// HashTable::HashTable (const HashTable &)
//
// Copy construct a hash table.

CS2_HT_TEMP
inline CS2_HT_DECL::HashTable (const CS2_HT_DECL &table) :
Allocator(table),
fTable(
  table.fTableSize > 0 ?
    (HashTableEntry *) Allocator::allocate(table.fTableSize * sizeof(HashTableEntry)) :
    NULL),
fTableSize(table.fTableSize),
fMask(table.fMask),
fNextFree(table.fNextFree),
fHighestIndex(table.fHighestIndex) {

   if (fTableSize > 0) {
    for (HashIndex hashIndex = 0; hashIndex < fTableSize; ++hashIndex) {
      HashTableEntry &entry = table.fTable[hashIndex];

      if (entry.Valid()) {
        new (fTable + hashIndex) HashTableEntry (entry);
      } else {
        fTable[hashIndex].Invalidate();
              fTable[hashIndex].SetCollisionChain (entry.CollisionChain());
      }
    }
  }

}

// HashTable::operator=
//
// Assign a hash table to another.

CS2_HT_TEMP
inline CS2_HT_DECL &CS2_HT_DECL::operator= (const CS2_HT_DECL &table) {

  if (fTableSize < table.fTableSize) {
    HashTableEntry *newTable = (HashTableEntry *)Allocator::allocate(table.fTableSize * sizeof(HashTableEntry));
    if (newTable == NULL)
      SystemResourceError::Memory();
    memcpy(newTable, fTable, fTableSize * sizeof(HashTableEntry));
    Allocator::deallocate(fTable, fTableSize * sizeof(HashTableEntry));
    fTable = newTable;
  } else if (fTableSize > table.fTableSize) {
    for (HashIndex hashIndex = table.fTableSize; hashIndex < fTableSize; ++hashIndex) {
      if (fTable[hashIndex].Valid()) {
        // Destroy this entry.
        fTable[hashIndex].~HashTableEntry();
        fTable[hashIndex].Invalidate();
      }
    }
  }

  for (HashIndex hashIndex = 0; hashIndex < table.fTableSize; ++hashIndex) {
    const HashTableEntry &entry = table.fTable[hashIndex];
    bool thisEntryValid;

    thisEntryValid = (hashIndex < fTableSize && fTable[hashIndex].Valid());

    if (entry.Valid()) {
      if (thisEntryValid) {
        fTable[hashIndex] = entry;
      } else {
        new (fTable + hashIndex) HashTableEntry (entry);
      }
    } else {
      if (thisEntryValid) {
        // Destroy this entry.
        fTable[hashIndex].~HashTableEntry();
      }

      fTable[hashIndex].Invalidate();
      fTable[hashIndex].SetCollisionChain (entry.CollisionChain());
    }
  }

  fTableSize = table.fTableSize;
  fMask = table.fMask;
  fNextFree = table.fNextFree;

  return *this;
}

// HashTable::GrowTo(n)
// Grow table to handle at least newSize elements
CS2_HT_TEMP void
inline CS2_HT_DECL::GrowTo(uint32_t newSize) {
  uint32_t    closedAreaSize, openAreaSize;
  HashIndex   oldSize;
  HashTableEntry *oldBase;

  closedAreaSize = BitManipulator::CeilingPowerOfTwo(newSize);
  if (closedAreaSize < kMinimumHashTableSize)
      closedAreaSize = kMinimumHashTableSize;
  openAreaSize = closedAreaSize / 4;

  if((closedAreaSize + openAreaSize) < fTableSize ) return;

  // Record old base and size
  oldBase = fTable;
  oldSize = fTableSize;

  GrowAndRehash(oldSize,oldBase,closedAreaSize,openAreaSize);
}


// HashTable::Grow
//
// Grow the hash table to double the current size and rehash entries in
// the new table.

CS2_HT_TEMP void
inline CS2_HT_DECL::Grow() {
  HashTableEntry *oldBase;
  HashIndex       oldSize, closedAreaSize, openAreaSize,newSize;

  // Record old base and size
  oldBase = fTable;
  oldSize = fTableSize;

  // Calculate the new mask value and table size
  if (oldSize==0) newSize = kMinimumHashTableSize - 1;
  else
    newSize =  (fMask << 1) | 1;     // double the size
  closedAreaSize = newSize  + 1;    // make it even
  openAreaSize = closedAreaSize / 4;

  GrowAndRehash(oldSize,oldBase,closedAreaSize,openAreaSize);
}

// Grow and rehash table
CS2_HT_TEMP void
inline CS2_HT_DECL::GrowAndRehash(HashIndex oldSize,
                              HashTableEntry *oldBase,
                              HashIndex closedAreaSize,
                              HashIndex openAreaSize) {
  HashIndex      freeIndex, oldIndex, hashIndex;
  //DumpStatistics();
  CS2Assert(closedAreaSize,("closedAreaSize not set"));
  CS2Assert(openAreaSize,("openAreaSize is 0"));

  HashIndex const newTableSize = closedAreaSize + openAreaSize;
  HashTableEntry * newTable = (HashTableEntry *) Allocator::allocate(newTableSize * sizeof(HashTableEntry));
  if (newTable == NULL)
    SystemResourceError::Memory();

  fTable = newTable;
  fTableSize = newTableSize;
  fMask = closedAreaSize - 1;
  fNextFree = closedAreaSize + 1;
  fHighestIndex = 0; // Let Add figure out the new highest index

  // Invalidate all of the hash table entries.
  for (hashIndex = 0; hashIndex < fNextFree; ++hashIndex) {
    fTable[hashIndex].Invalidate();
  }

  // Initialize the rehash area to link up the free chain
  for (freeIndex = fNextFree; freeIndex < fTableSize - 1; ++freeIndex) {
    fTable[freeIndex].Invalidate();
    fTable[freeIndex].SetCollisionChain (freeIndex + 1);
  }
  fTable[fTableSize - 1].Invalidate();
  fTable[fTableSize - 1].SetCollisionChain (0);

  // Rehash everything since the hash function is based on the table size.
  for (oldIndex = 0; oldIndex < oldSize; ++oldIndex) {
    if (oldBase[oldIndex].Valid()) {   // this is a valid entry
      bool found;
      HashValue oldHash = oldBase[oldIndex].HashCode();

      // Attempt to locate a position for this entry in the new table.
      found = Locate (oldBase[oldIndex].Key(), hashIndex, oldHash);
      CS2Assert (! found, ("Unable to rehash entry %d", oldIndex));

      // hashIndex points at either an invalid hash table entry or the last
      // entry in a collision chain for this key

      if (fTable[hashIndex].Valid()) {
        fTable[hashIndex].SetCollisionChain(fNextFree);
        CS2Assert (fNextFree != 0 && fNextFree<fTableSize, ("1:Invalid hash index %d %d", (int)hashIndex, (int)fNextFree));
        hashIndex = fNextFree;
        fNextFree = fTable[fNextFree].CollisionChain();
      }

      if (hashIndex > fHighestIndex)
        fHighestIndex = hashIndex;

      // Just bitwise copy the old element to the new.
      memcpy (fTable + hashIndex, oldBase + oldIndex, sizeof(HashTableEntry));
      fTable[hashIndex].SetCollisionChain (0);
    }
  }

  if (oldBase)
    Allocator::deallocate(oldBase, oldSize * sizeof(HashTableEntry));
}

// HashTable::DumpStatistics
//
// Dump hash table statistics
CS2_HT_TEMP
template <class str>
void
inline CS2_HT_DECL::DumpStatistics (str &out) {
  int32_t nentries, partsize, low, high, cnt, tcnt;

  Cursor hi(*this);
  nentries = fTableSize;
  partsize = nentries/5;
  nentries = partsize*5;
  low = 0;
  high = partsize;
  cnt = 0;
  tcnt = 0;
  for (hi.SetToFirst(); hi.Valid(); hi.SetToNext()) {
    if (hi >= high) {
      out << low << " --> " << high << " cnt = " << cnt << "\n";
      tcnt += cnt;
      low = high;
      high = low + partsize;
      cnt = 0;
    }
    ++cnt;
  }
  if (cnt > 0) {
    out << low << " --> " << high << " cnt = " << cnt << "\n";
    tcnt += cnt;
    if (high < nentries) cnt = 0;
  }
  if (tcnt == 0)
    out << "** empty **" << "\n";
  else {
    out << "collisions = " << cnt << " total cnt = " << tcnt;
    out << " percent col = " << (cnt * 100)/tcnt << "\n";
  }
}

// HashTable::Locate
//
// Search the hash table for an entry matching the given key.  Return
// true iff an entry is found.  If an entry is found, also set the hash
// index parameter to the hash table index where the entry is located.

CS2_HT_TEMP bool
inline CS2_HT_DECL::Locate (const AKeyType &key, HashIndex &hashIndex,
                            HashValue &hashValue) const {

  if (fTableSize==0) return false;

  if (hashValue == 0) {
    hashValue = AHashInfo::Hash (key);
    CS2Assert (hashValue != 0, ("Invalid hash value"));
  }

  hashIndex = (hashValue & fMask) + 1;
  CS2Assert (hashIndex != 0 && hashIndex<fTableSize, ("Invalid hash index %d", (int)hashIndex));

  // Search the hash table
  if (! fTable[hashIndex].Valid()) return false;

  while ((fTable[hashIndex].HashCode() != hashValue) ||
         ! AHashInfo::Equal (key, fTable[hashIndex].Key())){

    // Set index to next entry in the collision chain or, if empty, end search.
    if (fTable[hashIndex].CollisionChain() != 0) {
      HashIndex hi2 = fTable[hashIndex].CollisionChain();
      CS2Assert (hi2 != 0 && hi2<fTableSize, ("2:Invalid hash index %d %d %p", (int)hi2, (int)hashIndex, (void *)&fTable[0]));
      hashIndex = hi2;
    } else {
      return false;
    }
  }
  return true;
}

// HashTable::Add
//
// Add the given entry to the hash table.  Return true iff the entry is
// successfully added (ie. the entry did not already exists).  If the
// entry is successfully added, set the hash index parameter to the hash
// table index where the entry is located.  If the entry is not successfully
// added, set the hash index parameter to the entry that matched the given
// key.

CS2_HT_TEMP bool

inline CS2_HT_DECL::Add (const AKeyType &key, const ADataType &data,
              HashIndex &hashIndex, HashValue hashValue, bool noLocate) {
  // Search the table for a record matching this key.
  // If a matching record is found, then fail.

  if (!noLocate && Locate (key, hashIndex, hashValue)) {
    return false;
  }

  // If the hash table is full, then we need to grow.
  if (fNextFree == 0) {
    Grow();

  // The grow routine rehashes everything, so we need to rehash this key.
  if(false == Locate (key, hashIndex, hashValue))
    CS2Assert (false, ("Failed to relocate entry to an empty record\n"));
  }

  // hashIndex points at either an invalid hash table entry or the last
  // entry in a collision chain for this key

  if (fTable[hashIndex].Valid()) {
    fTable[hashIndex].SetCollisionChain(fNextFree);
    hashIndex = fNextFree;
    fNextFree = fTable[fNextFree].CollisionChain();  // maintain free chain
  }

  if (hashIndex > fHighestIndex)
    fHighestIndex = hashIndex;

  new (fTable + hashIndex) HashTableEntry (key, data, hashValue, 0);
  return true;  // record was successfully added
}

// HashTable::Remove
//
// Remove the given entry from the hash table.

CS2_HT_TEMP void
inline CS2_HT_DECL::Remove (HashIndex hashIndex) {
  CS2Assert (fTable[hashIndex].Valid(),
          ("Attempt to remove invalid hash table entry\n"));

  // If the entry is in the rehash area, locate the head of the hash chain and
  // follow it to unlink this entry from the chain.  Then return the rehash area
  // space to the free pool.

  if (hashIndex > (fMask+1)) {
    HashIndex headOfChain = (fTable[hashIndex].HashCode() & fMask) + 1;
    HashIndex collisionIndex;

    for (collisionIndex = headOfChain;
         fTable[collisionIndex].CollisionChain() != hashIndex;
         collisionIndex = fTable[collisionIndex].CollisionChain()) {
      CS2Assert (collisionIndex != 0,
		 ("Cannot find record on expected hash chain\n"));
    }

    fTable[collisionIndex].SetCollisionChain (fTable[hashIndex].CollisionChain());
    fTable[hashIndex].SetCollisionChain (fNextFree);
    fTable[hashIndex].~HashTableEntry();

    fNextFree = hashIndex;
  } else {
    HashIndex collisionChain = fTable[hashIndex].CollisionChain();
    fTable[hashIndex].~HashTableEntry();

    // The entry is in the closed hash table section.
    // If it has any chained entries in the rehash area, then choose one
    // to put in its place.
    if (collisionChain) {
      HashIndex firstCollision = collisionChain;

      memcpy (fTable + hashIndex, fTable + firstCollision,
              sizeof(HashTableEntry));
      fTable[firstCollision].SetCollisionChain (fNextFree);
      fTable[firstCollision].Invalidate();
      fNextFree = firstCollision;
      if (firstCollision > hashIndex) hashIndex = firstCollision;
    }
  }

  // If we are deleting the highest allocated index, then walk backward to
  // determine the next highest index
  if (hashIndex == fHighestIndex) {
    HashIndex maxIndex;

    for (maxIndex = hashIndex - 1; maxIndex > 0; --maxIndex) {
      if (fTable[maxIndex].Valid()) break;
    }

    fHighestIndex = maxIndex;
  }
}

// HashTable::MemoryUsage
//
// Return the number of bytes of memory used by the hash table.

CS2_HT_TEMP unsigned long
inline CS2_HT_DECL::MemoryUsage() const {
  unsigned long sizeInBytes;

  sizeInBytes = sizeof(CS2_HT_DECL);
  sizeInBytes += fTableSize * sizeof(HashTableEntry);

  return sizeInBytes;
}

// HashTable::MakeEmpty
//
// Destroy all valid entries in the table.

CS2_HT_TEMP void
inline CS2_HT_DECL::MakeEmpty() {
  HashIndex hashIndex;

  // Destroy valid entries.
  for (hashIndex = 0; hashIndex < fTableSize; ++hashIndex) {
    if (fTable[hashIndex].Valid())
      fTable[hashIndex].~HashTableEntry();
  }

  if (fTable)
    Allocator::deallocate(fTable, fTableSize * sizeof(HashTableEntry));

  fMask = fNextFree = fTableSize = fHighestIndex = 0;
  fTable = NULL;
}

}

#undef CS2_HT_TEMPARGS
#undef CS2_HT_TEMP
#undef CS2_HT_DECL
#undef CS2_HTC_DECL
#undef CS2_HTE_DECL

#ifdef CS2_ALLOCINFO
#undef allocate
#undef deallocate
#undef reallocate
#endif

#endif