GxMap.h

Go to the documentation of this file.

//===========================================================================
//===========================================================================
#pragma once
 
GX_CORE_NAMESPACE_BEGIN()
 
//===========================================================================
//===========================================================================
template<class K, class V>
class GxMap
{
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    static constexpr u32 DEFAULT_SPLIT_COUNT = 32;
 
    class GxPair;
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GxMap(void) : _splitCount(DEFAULT_SPLIT_COUNT), _invalidKey(0), _invalidValue(0)
    {
        initialize();
    }
    GxMap(K invalidKey, V invalidValue) : _splitCount(DEFAULT_SPLIT_COUNT), _invalidKey(invalidKey), _invalidValue(invalidValue)
    {
        initialize();
    }
    GxMap(K invalidKey, V invalidValue, u32 splitCount) : _splitCount(splitCount), _invalidKey(invalidKey), _invalidValue(invalidValue)
    {
        initialize();
    }
    ~GxMap(void);// override;
private:
    void initialize(void);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    V find(K key) const;
    K findKey(V pObject) const;
    void insert(K key, V pObject);
    void setObject(K key, V pObject);
    void erase(K key);
    void eraseObject(const V pObject);
    void eraseAll(void);
 
private:
    GX_FORCE_INLINE u32 getHashValue(K key) const { return key % _splitCount; }
    GxPair* findPair(K key) const;
    GxPair* allocatePair(K key, V pObject);
    void freePair(GxPair* pPair);
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
public:
    GX_FORCE_INLINE V operator[](K key) const { return find(key); }
    u32 getCount(void) const;
    constexpr u32 getSplitCount(void) const { return _splitCount; }
    GX_FORCE_INLINE const GxArray& getPairArray(void) const { return _pairArray; }
    GX_FORCE_INLINE b32 isInvalidKey(K key) const { return _invalidKey == key; }
    GX_FORCE_INLINE b32 isInvalidValue(V value) const { return _invalidValue == value; }
 
    //-----------------------------------------------------------
    //-----------------------------------------------------------
private:
    GxArrayClassBase    _hashArray;         
    GxArray             _pairArray;         
    GxArray             _pairFreeArray;     
    GxArray             _pairBufferArray;   
    u32                 _splitCount;        
    K                   _invalidKey;        
    V                   _invalidValue;      
 
};
 
//===========================================================================
//===========================================================================
template<class K, class V>
class GxMap<K, V>::GxPair
{
    //-------------------------------------------------------------
    //-------------------------------------------------------------
public:
    GxPair(void) : _key(0), _pObject(0) {}
 
    //-------------------------------------------------------------
    //-------------------------------------------------------------
 
    GX_FORCE_INLINE void set(K key, V pObject) { _key = key; _pObject = pObject; }
    GX_FORCE_INLINE K getKey(void) const { return _key; }
    GX_FORCE_INLINE V getObject(void) const { return _pObject; }
 
    //-------------------------------------------------------------
    //-------------------------------------------------------------
private:
    K   _key;       
    V   _pObject;   
 
};
 
//---------------------------------------------------------------------------
// 初期化
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::initialize(void)
{
    const u32 INITIAL_PAIR_COUNT = 256;
    auto* pBuffer = GX_NEW GxPair[INITIAL_PAIR_COUNT];
    _pairBufferArray.addBottom(pBuffer);
    for (u32 i = 0; i < INITIAL_PAIR_COUNT; i++)
    {
        _pairFreeArray.addBottom(&pBuffer[i]);
    }
 
    _hashArray.setCount(_splitCount);
    auto* pArray = GX_NEW GxArray[_splitCount];
    for (u32 i = 0; i < _splitCount; i++)
    {
        _hashArray[i] = &pArray[i];
    }
}
 
//---------------------------------------------------------------------------
// デストラクタ
//---------------------------------------------------------------------------
template<class K, class V>
GxMap<K, V>::~GxMap(void)
{
    auto* pArray = static_cast<GxArray*>(_hashArray[0]);
    GX_SAFE_DELETE_ARRAY(pArray);
    for (u32 i = 0; i < _pairBufferArray.getCount(); i++)
    {
        auto* pBuffer = static_cast<GxPair*>(_pairBufferArray[i]);
        GX_SAFE_DELETE_ARRAY(pBuffer);
    }
}
 
//---------------------------------------------------------------------------
// 検索
//---------------------------------------------------------------------------
template<class K, class V>
V GxMap<K, V>::find(K key) const
{
    auto* pPair = findPair(key);
    if (pPair)
    {
        return pPair->getObject();
    }
    return _invalidValue;
}
 
//---------------------------------------------------------------------------
// キーを検索
//---------------------------------------------------------------------------
template<class K, class V>
K GxMap<K, V>::findKey(V pObject) const
{
    for (auto* pPair : _pairArray)
    {
        if (static_cast<GxPair*>(pPair)->getObject() == pObject)
        {
            return static_cast<GxPair*>(pPair)->getKey();
        }
    }
    return _invalidKey;
}
 
//---------------------------------------------------------------------------
// 挿入
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::insert(K key, V pObject)
{
    const auto keyValue = getHashValue(key);
    auto* pPair = allocatePair(key, pObject);
    static_cast<GxArray*>(_hashArray[keyValue])->addBottom(pPair);
}
 
//---------------------------------------------------------------------------
// オブジェクトを設定
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::setObject(K key, V pObject)
{
    auto* pPair = findPair(key);
    if (pPair)
    {
        pPair->set(pPair->getKey(), pObject);
    }
}
 
//---------------------------------------------------------------------------
// 削除
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::erase(K key)
{
    const auto keyValue = getHashValue(key);
    auto* pArray = static_cast<GxArray*>(_hashArray[keyValue]);
    for (u32 i = 0; i < pArray->getCount(); i++)
    {
        auto* pPair = static_cast<GxPair*>(pArray->getObject(i));
        if (pPair->getKey() == key)
        {
            freePair(pPair);
            pArray->remove(i);
            break;
        }
    }
}
 
//---------------------------------------------------------------------------
// 削除
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::eraseObject(const V pObject)
{
    for (u32 i = 0; i < _hashArray.getCount(); i++)
    {
        auto* pArray = static_cast<GxArray*>(_hashArray[i]);
        for (u32 j = 0; j < pArray->getCount(); j++)
        {
            auto* pPair = static_cast<GxPair*>(pArray->getObject(j));
            if (pPair->getObject() == pObject)
            {
                pArray->remove(j);
            }
        }
    }
}
 
//---------------------------------------------------------------------------
// 全削除
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::eraseAll(void)
{
    for (u32 i = 0; i < _hashArray.getCount(); i++)
    {
        auto* pArray = static_cast<GxArray*>(_hashArray[i]);
        for (u32 j = 0; j < pArray->getCount(); j++)
        {
            auto* pPair = static_cast<GxPair*>(pArray->getObject(j));
            freePair(pPair);
        }
        pArray->removeAll();
    }
}
 
//---------------------------------------------------------------------------
// ペアを確保
//---------------------------------------------------------------------------
template<class K, class V>
typename GxMap<K, V>::GxPair* GxMap<K, V>::allocatePair(K key, V pObject)
{
    if (_pairFreeArray.getCount() == 0)
    {
        // メモリ追加
        u32 size = _pairArray.getCount() * 2;
        auto* pBuffer = GX_NEW GxPair[size];
        _pairBufferArray.addBottom(pBuffer);
        for (u32 i = 0; i < size; i++)
        {
            _pairFreeArray.addBottom(&pBuffer[i]);
        }
    }
    auto* pPair = static_cast<GxPair*>(_pairFreeArray.pop());
    pPair->set(key, pObject);
    _pairArray.addBottom(pPair);
    return pPair;
}
 
//---------------------------------------------------------------------------
// ペアを解放
//---------------------------------------------------------------------------
template<class K, class V>
void GxMap<K, V>::freePair(GxPair* pPair)
{
    GX_ASSERT(pPair, "pPair is nullptr");
    GX_ASSERT(_pairArray.indexOf(pPair) >= 0, "pPair is invalid");
 
    _pairArray.removeFirst(pPair);
    _pairFreeArray.addBottom(pPair);
}
 
//---------------------------------------------------------------------------
// 要素数を取得
//---------------------------------------------------------------------------
template<class K, class V>
u32 GxMap<K, V>::getCount(void) const
{
    u32 count = 0;
    for (u32 i = 0; i < _hashArray.getCount(); i++)
    {
        count += static_cast<GxArray*>(_hashArray[i])->getCount();
    }
    return count;
}
 
//---------------------------------------------------------------------------
// 検索
//---------------------------------------------------------------------------
template<class K, class V>
typename GxMap<K, V>::GxPair* GxMap<K, V>::findPair(K key) const
{
    const auto keyValue = getHashValue(key);
    auto* pArray = static_cast<GxArray*>(_hashArray[keyValue]);
    for (u32 j = 0; j < pArray->getCount(); j++)
    {
        auto* pPair = static_cast<GxPair*>(pArray->getObject(j));
        if(pPair->getKey() == key)
        {
            return pPair;
        }
    }
    return nullptr;
}
 
GX_CORE_NAMESPACE_END()