cHashTable.h

Go to the documentation of this file.

//
//
 
#ifndef _INC_cHashTable_H
#define _INC_cHashTable_H
#ifndef NO_PRAGMA_ONCE
#pragma once
#endif
 
#include "cArraySortRef.h"
#include "cBits.h"
#include "cUnitTestDecl.h"
 
namespace Gray
{
        class cHashIterator     // inline
        {
        public:
                ITERATE_t m_i;  
                ITERATE_t m_j;  
        public:
                cHashIterator(ITERATE_t nBucket = 0, ITERATE_t jj = 0) noexcept
                        : m_i(nBucket)
                        , m_j(jj)
                {
                }
                void SkipRemoved() noexcept
                {
                        m_j--;
                }
                ITERATE_t get_ArrayNum() const noexcept
                {
                        return m_i;
                }
                bool isValid() const noexcept
                {
                        return(m_j >= 0);
                }
        };
 
        template<class _TYPEARRAY, class TYPE, typename TYPE_HASHCODE = HASHCODE_t, int TYPE_HASHBITS = 5 >
        class cHashTableT
        {
 
        public:
                static const ITERATE_t k_HASH_ARRAY_QTY = _1BITMASK(TYPE_HASHBITS);
                typedef cHashIterator iterator; // like STL.
                _TYPEARRAY m_aTable[k_HASH_ARRAY_QTY];
 
        public:
                int get_HashBits() const
                {
                        return TYPE_HASHBITS;
                }
                ITERATE_t get_HashArrayQty() const
                {
                        return k_HASH_ARRAY_QTY;
                }
                ITERATE_t GetHashArray(TYPE_HASHCODE rid) const
                {
                        return((ITERATE_t)(rid & (k_HASH_ARRAY_QTY - 1)));
                }
                ITERATE_t GetArraySize(ITERATE_t iArray) const
                {
                        ASSERT(IS_INDEX_GOOD(iArray, k_HASH_ARRAY_QTY));
                        return(m_aTable[iArray].GetSize());
                }
                iterator FindIForKey(TYPE_HASHCODE rid) const
                {
                        ITERATE_t iBucket = GetHashArray(rid);
                        return(cHashIterator(iBucket, m_aTable[iBucket].FindIForKey(rid)));
                }
                TYPE_HASHCODE FindKeyFree(TYPE_HASHCODE rid) const
                {
                        while (FindIForKey(rid).isValid())      // found it ?
                        {
                                rid++;
                        }
                        return rid;
                }
                bool DeleteKey(TYPE_HASHCODE rid)
                {
                        return m_aTable[GetHashArray(rid)].RemoveKey(rid);
                }
                bool IsEmpty() const
                {
                        for (ITERATE_t i = 0; i < k_HASH_ARRAY_QTY; i++)
                        {
                                if (!m_aTable[i].IsEmpty())
                                        return false;
                        }
                        return true;
                }
                ITERATE_t get_TotalCount() const
                {
                        ITERATE_t iTotalCount = 0;
                        for (ITERATE_t i = 0; i < k_HASH_ARRAY_QTY; i++)
                        {
                                iTotalCount += m_aTable[i].GetSize();
                        }
                        return iTotalCount;
                }
                void RemoveAt(iterator& i)
                {
                        ASSERT(IS_INDEX_GOOD(i.m_i, k_HASH_ARRAY_QTY));
                        m_aTable[i.m_i].RemoveAt(i.m_j);
                        i.SkipRemoved();
                }
 
                void RemoveAll()
                {
                        for (ITERATE_t i = 0; i < k_HASH_ARRAY_QTY; i++)
                        {
                                this->m_aTable[i].RemoveAll();
                        }
                }
 
                void Empty()
                {
                        RemoveAll();
                }
 
                UNITTEST_FRIEND(cHashTable);
        };
 
        template<class TYPE, typename TYPE_HASHCODE = HASHCODE_t, int TYPE_HASHBITS = 5 >
        class cHashTableStruct : public cHashTableT < cArraySortStructHash<TYPE, TYPE_HASHCODE>, TYPE, TYPE_HASHCODE, TYPE_HASHBITS >
        {
        public:
                typedef cHashTableT< cArraySortStructHash<TYPE, TYPE_HASHCODE>, TYPE, TYPE_HASHCODE, TYPE_HASHBITS > SUPER_t;
                typedef const TYPE& REF_t;              // How to refer to this? value or ref or pointer?
 
        public:
                const TYPE* FindArgForKey(TYPE_HASHCODE rid) const
                {
                        ITERATE_t iBucket = this->GetHashArray(rid);
                        return this->m_aTable[iBucket].FindArgForKey(rid);
                }
                const TYPE& GetAtHash(const cHashIterator& i) const
                {
                        ASSERT(IS_INDEX_GOOD_ARRAY(i.m_i, this->m_aTable));
                        return(this->m_aTable[i.m_i].ConstElementAt(i.m_j));
                }
                cHashIterator FindHash(TYPE_HASHCODE rid) const
                {
                        ITERATE_t iBucket = this->GetHashArray(rid);
                        ITERATE_t index = this->m_aTable[iBucket].FindArgForKey(rid);
                        return cHashIterator(iBucket, index);
                }
                const TYPE& Add(REF_t rNew)
                {
                        ITERATE_t iBucket = this->GetHashArray(rNew.get_HashCode());
                        ITERATE_t index = this->m_aTable[iBucket].Add(rNew);
                        return this->m_aTable[iBucket].GetAt(index);
                }
                TYPE* AddSpecial(REF_t rNew)
                {
                        // Add only new hash node. return index ONLY if existing hash node.
                        ITERATE_t iBucket = this->GetHashArray(rNew.get_HashCode());
                        COMPARE_t iCompareRes;
                        ITERATE_t index = this->m_aTable[iBucket].FindINear(rNew, iCompareRes);
                        if (iCompareRes == COMPARE_Equal)
                        {
                                return &this->m_aTable[iBucket].ElementAt(index);       // special return that says it already was here.
                        }
 
                        // not duplicate. must add
                        index = this->m_aTable[iBucket].AddPresorted(index, iCompareRes, rNew);
                        return nullptr; // special return that says i added it.
                }
        };
 
        template<class TYPE, typename TYPE_HASHCODE = HASHCODE_t, int TYPE_HASHBITS = 5 >
        class cHashTableRef : public cHashTableT < cArraySortHash<TYPE, TYPE_HASHCODE>, TYPE, TYPE_HASHCODE, TYPE_HASHBITS >
        {
        protected:
                typedef cRefPtr<TYPE> PTR_t;
        public:
                PTR_t FindArgForKey(TYPE_HASHCODE rid) const
                {
                        ITERATE_t i = this->GetHashArray(rid);
                        return this->m_aTable[i].FindArgForKey(rid);
                }
                ITERATE_t Add(TYPE* pNew)
                {
                        ASSERT(pNew != nullptr);
                        return this->m_aTable[this->GetHashArray(pNew->get_HashCode())].Add(pNew);
                }
                bool DeleteArg(TYPE* pObj)
                {
                        if (pObj == nullptr)
                                return false;
                        return this->m_aTable[this->GetHashArray(pObj->get_HashCode())].RemoveArgKey(pObj);
                }
                PTR_t GetAtHash(const cHashIterator& i) const
                {
                        ASSERT(IS_INDEX_GOOD_ARRAY(i.m_i, this->m_aTable));
                        return(this->m_aTable[i.m_i].ConstElementAt(i.m_j));
                }
 
                PTR_t GetAt(TYPE_HASHCODE rid, ITERATE_t index) const
                {
                        return(this->m_aTable[this->GetHashArray(rid)].ConstElementAt(index));
                }
                void DisposeAll()
                {
                        for (ITERATE_t i = 0; i < this->k_HASH_ARRAY_QTY; i++)
                        {
                                this->m_aTable[i].DisposeAll();
                        }
                }
        };
 
        // Iterate through all members. iterator i;
#define FOR_HASH_TABLE(h,i)     for ( ; i.m_i<h.k_HASH_ARRAY_QTY; i.m_i++ ) for ( i.m_j=0; i.m_j<h.m_aTable[i.m_i].GetSize(); i.m_j++ )
};
 
#endif // _INC_CHASH_H