---

     

---

CHMrefHashTable.h

#ifndef __CHM_REF_HASH_TABLE__
#define __CHM_REF_HASH_TABLE__
#include <CHM/CHMvector.h>
#include <CHM/CHMstring.h>

template<class PKey, class PValue>
class CHMpair : public CHMinstanceHeap
{
public:
   CHMpair() {}
   CHMpair(const PKey& nKey, const PValue& nValue)
           : Key(nKey), Value(nValue) {}
   ~CHMpair() {}
   PKey   Key;
   PValue Value;
};

size_t CHMhashFunc(size_t Item);

template<class PKey, class PValue> class CHMrefHashTableIterator;

template<class PKey, class PValue>
class CHMrefHashTable : public CHMinstanceHeap
{
public:
   CHMrefHashTable(size_t CountOfBucket=10);
   virtual ~CHMrefHashTable();

   //void showBuckets() const;

   PValue& operator[](const PKey& Key);
   const PValue& operator[](const PKey& Key) const;

   CHMpair<PKey,PValue>* findPair(const PKey& Key) const;
   CHMboolean has(const PKey& Key) const;

   PValue* getValue(const PKey& Key) const;
   void clear();

   void remove(const PKey& Key);

   void insert(const PKey& Key, const PValue& Value);

   size_t size() const { return m_Size; }

   friend class CHMrefHashTableIterator<PKey, PValue>;
   typedef CHMrefHashTableIterator<PKey, PValue> Iterator;
private:
   void removeAll();
   void init(size_t CountOfBucket);

   typedef CHMvector< CHMpair<PKey, PValue>* > CHMbucket;

   CHMvector<CHMbucket*> m_Bucket;

   void findIndex(const PKey& Key, size_t& BucketIndex, size_t& ItemIndex) const;
   size_t m_Size;

   CHMrefHashTable(const CHMrefHashTable<PKey,PValue>& Original) {}
   CHMrefHashTable<PKey,PValue>& operator=(const CHMrefHashTable<PKey,PValue>& Original) { return *this;}
};

template<class PKey, class PValue>
class CHMrefHashTableIterator
{
public:
   CHMrefHashTableIterator(const CHMrefHashTable<PKey, PValue>& Table);
   ~CHMrefHashTableIterator() {}

   void resetIterator();
   CHMboolean iterateNext(PKey& Key, PValue& Value);
private:
   size_t m_IterBucketIndex;
   size_t m_IterItemIndex;
   const CHMrefHashTable<PKey, PValue>* m_pTable;
};

template<class PKey, class PValue>
CHMrefHashTableIterator<PKey, PValue>::CHMrefHashTableIterator
(
   const CHMrefHashTable<PKey, PValue>& Table
)
{
   m_pTable = &Table;
   resetIterator();
}

template<class PKey, class PValue>
void CHMrefHashTableIterator<PKey, PValue>::resetIterator()
{
   m_IterBucketIndex=npos;
   m_IterItemIndex=0;
}

template<class PKey, class PValue>
CHMboolean CHMrefHashTableIterator<PKey,PValue>::iterateNext
(
    PKey& Key, 
    PValue& Value
)
{
   if (m_IterBucketIndex == npos)
   {
      m_IterBucketIndex = 0;
   }
   while (m_IterBucketIndex < m_pTable->m_Bucket.size() && 
           m_pTable->m_Bucket[m_IterBucketIndex]->size() <= m_IterItemIndex )
   {
      m_IterBucketIndex++;
      m_IterItemIndex = 0;
   }
   if (m_IterBucketIndex == m_pTable->m_Bucket.size())
   {
      return false;
   }
   else
   {
      Key = m_pTable->m_Bucket[m_IterBucketIndex]->operator[](m_IterItemIndex)->Key;
      Value = m_pTable->m_Bucket[m_IterBucketIndex]->operator[](m_IterItemIndex)->Value;
      m_IterItemIndex++;
      return true;
   }
}

size_t CHMhashFunc(const CHMstring& String);

template<class PKey, class PValue>
CHMrefHashTable<PKey, PValue>::CHMrefHashTable
(
   size_t CountOfBucket
) : m_Bucket(CountOfBucket)
{
   init(CountOfBucket);
}

template<class PKey, class PValue>
void CHMrefHashTable<PKey, PValue>::init(size_t CountOfBucket)
{
   removeAll();
   m_Size = 0;
   m_Bucket.resize(CountOfBucket);
   for(size_t BucketIndex=0; BucketIndex < m_Bucket.size(); ++BucketIndex)
   {
      m_Bucket[BucketIndex] = new CHMvector< CHMpair<PKey,PValue>* >(2, 0, true);
      // initial size of 0 grow by doubling.
   }
}

template<class PKey, class PValue>
CHMrefHashTable<PKey, PValue>::~CHMrefHashTable()
{
   removeAll();
}

template<class PKey, class PValue>
void CHMrefHashTable<PKey, PValue>::removeAll()
{
   for(size_t BucketIndex = 0;
       BucketIndex < m_Bucket.size();
       ++BucketIndex)
   {
      for(size_t ItemIndex = 0; ItemIndex < m_Bucket[BucketIndex]->size();
          ++ItemIndex)
      {
         delete m_Bucket[BucketIndex]->operator[](ItemIndex);
      }
      delete m_Bucket[BucketIndex];
   }
   m_Size = 0;
}

template<class PKey, class PValue>
CHMpair<PKey,PValue>* CHMrefHashTable<PKey, PValue>::findPair(const PKey& Key) const
{
   size_t BucketIndex;
   size_t ItemIndex;
   findIndex(Key, BucketIndex, ItemIndex);

   if (ItemIndex == npos)
   {
      return NULL;
   }
   else
   {
      return m_Bucket[BucketIndex]->operator[](ItemIndex);
   }
}

template<class PKey, class PValue>
PValue& CHMrefHashTable<PKey, PValue>::operator[](const PKey& Key)
{
   CHMpair<PKey, PValue>* pPair = findPair(Key);

   if (!pPair)
   {
      insert(Key, PValue());
      pPair = findPair(Key);
   }
   CHMPRECONDITION(pPair != NULL)
   return pPair->Value;
}

template<class PKey, class PValue>
const PValue& CHMrefHashTable<PKey, PValue>::operator[](const PKey& Key) const
{
   CHMpair<PKey, PValue>* pPair = findPair(Key);

   if (!pPair)
   {
      throw CHMerror(CHM_TEXT("Key does not exist."),0);
   }

   return pPair->Value;
}


template<class PKey, class PValue>
CHMboolean CHMrefHashTable<PKey, PValue>::has(const PKey& Key) const
{
   CHMpair<PKey, PValue>* pPair = findPair(Key);
   if (!pPair)
      return false;
   else
      return true;
}

template<class PKey, class PValue>
PValue* CHMrefHashTable<PKey, PValue>::getValue(const PKey& Key) const
{
   CHMpair<PKey, PValue>* pPair = findPair(Key);
   if (pPair)
      return &pPair->Value;
   else
      return NULL;
}

template<class PKey, class PValue>
void CHMrefHashTable<PKey, PValue>::clear()
{
   size_t CountOfBucket = m_Bucket.size();
   init(CountOfBucket);
}

template<class PKey, class PValue>
void CHMrefHashTable<PKey, PValue>::findIndex
(
   const PKey& Key,
   size_t& BucketIndex,
   size_t& ItemIndex
) const
{
   BucketIndex = CHMhashFunc(Key) % m_Bucket.size();
   ItemIndex = 0;
   while (ItemIndex < m_Bucket[BucketIndex]->size()
          && Key != m_Bucket[BucketIndex]->operator[](ItemIndex)->Key)
   {
      ItemIndex++;
   }
   if (m_Bucket[BucketIndex]->size() == ItemIndex)
   {
      ItemIndex = npos;
   }
}

template<class PKey, class PValue>
void CHMrefHashTable<PKey, PValue>::remove(const PKey& Key)
{
   size_t BucketIndex;
   size_t ItemIndex;
   findIndex(Key, BucketIndex, ItemIndex);

   if (ItemIndex == npos)
   {
      return;
   }
   else
   {
      delete m_Bucket[BucketIndex]->operator[](ItemIndex);
      m_Bucket[BucketIndex]->remove(ItemIndex);
      m_Size--;
   }
}

template<class PKey, class PValue>
void CHMrefHashTable<PKey,PValue>::insert(const PKey& Key, const PValue& Value)
{
   size_t BucketIndex;
   size_t ItemIndex;
   findIndex(Key, BucketIndex, ItemIndex);
   if (ItemIndex != npos)
   {
      //CHM_LOG3("Over-riding old entry " << Key);
      m_Bucket[BucketIndex]->operator[](ItemIndex)->Value = Value;
   }
   else
   {
      m_Size +=1;
      m_Bucket[BucketIndex]->push_back(new CHMpair<PKey,PValue>(Key,Value));
   }
}
/*
template<class PKey, class PValue>
void CHMrefHashTable<PKey,PValue>::showBuckets() const
{
   for (size_t BucketIndex = 0; BucketIndex < m_Bucket.size(); BucketIndex++)
   {
      cout << "Bucket " << BucketIndex << " contains " << m_Bucket[BucketIndex]->size() << " entries\n";
   }
}*/

#endif // end of defensive include

---