__HashMapT-GCC.h

Go to the documentation of this file.

#ifndef __DCL_HASH_MAP_T_H__
#error "Never include <dcl/__HashMapT-GCC.h> directly; use <dcl/HashMapT.h> instead."
#endif
 
__DCL_BEGIN_NAMESPACE
 
#if __DCL_HAVE_THIS_FILE__
    static const char_t __szHashMap_h__[] = __T("dcl/__HashMapT-GCC.h");
    #undef __THIS_FILE__
    #define __THIS_FILE__ __szHashMap_h__
#endif
 
template<typename KEY, typename VALUE, typename HASH_FUN = HashFun<KEY> >
class HashMap : public Object
{
    DECLARE_CLASSINFO(HashMap)
public:
    struct Assoc
    {
        KEY     key;
        VALUE       value;
 
        Assoc() {}
        Assoc(const KEY& _key, const VALUE& _value)
        {
            this->key = _key;
            this->value = _value;
        }
    };
 
    struct HashNode : public Assoc
    {
        HashNode* pNext;
    };
 
    class ConstIterator;
    class Iterator
    {
    public:
        Iterator(HashNode* _pNode, HashMap* _pMap);
        Iterator& operator=(const Iterator& _it);
        Iterator& operator++();
        Iterator operator++(int);
        bool operator==(const Iterator& _it) const;
        bool operator!=(const Iterator& _it) const;
        Assoc& operator*() const;
    protected:
        HashMap* __pMap;
        HashNode*   __pNode;
        friend class ConstIterator;
    };
 
    class ConstIterator
    {
    public:
        ConstIterator(const HashNode* _pNode, const HashMap* _pMap);
        ConstIterator(const ConstIterator& _it);
        ConstIterator(const Iterator& _it);
        ConstIterator& operator=(const ConstIterator& _it);
        ConstIterator& operator++();
        ConstIterator operator++(int);
        bool operator==(const ConstIterator& _it) const;
        bool operator!=(const ConstIterator& _it) const;
        const Assoc& operator*() const;
    protected:
        const HashMap*   __pMap;
        const HashNode* __pNode;
    };
 
public:
    virtual ~HashMap();
    void initBuckets(size_t _bucketSize);
    HashMap(size_t _bucketSize = 21);
 
    HashMap(const HashMap& _src);
    const HashMap& operator=(const HashMap& _src);
 
    ConstIterator begin() const;
    ConstIterator end() const;
    Iterator begin();
    Iterator end();
 
    size_t bucketSize() const;
    size_t size() const;
    size_t sizeOfBucket(size_t _index) const;
    bool isEmpty() const;
    Iterator find(const KEY& _key);
    ConstIterator find(const KEY& _key) const;
    bool lookup(const KEY& _key, VALUE& _rValue) const;
    VALUE& operator[](const KEY&  _key);
    size_t erase(const KEY& _key);
    void clear();
 
protected:
    size_t bucketIndex(const KEY& _key) const;
    HashNode* createNode(const KEY& _key);
    void destroyNode(HashNode* _pNode);
 
protected:
    HASH_FUN        __hashFun;
    size_t              __size;           // count of all elements
    PointerArray        __buckets;
 
    friend class Iterator;
    friend class ConstIterator;
};

 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
HashMap<KEY, VALUE, HASH_FUN>
::Iterator::Iterator(
        HashNode* _pNode,
        HashMap<KEY, VALUE, HASH_FUN>* _pMap
        )
{
    __pNode = _pNode;
    __pMap = _pMap;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
typename HashMap<KEY, VALUE, HASH_FUN>::Iterator&
HashMap<KEY, VALUE, HASH_FUN>
::Iterator::operator = (const Iterator& _it)
{
    __pNode = _it.__pNode;
    __pMap = _it.__pMap;
    return *this;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
bool 
HashMap<KEY, VALUE, HASH_FUN>
::Iterator::operator == (const Iterator& _it) const
{
    return __pNode == _it.__pNode;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
bool
HashMap<KEY, VALUE, HASH_FUN>
::Iterator::operator != (const Iterator& _it) const
{
    return __pNode != _it.__pNode;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
typename HashMap<KEY, VALUE, HASH_FUN>::Assoc& 
HashMap<KEY, VALUE, HASH_FUN>::Iterator::operator*()const
{
    return *__pNode;
}

 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::ConstIterator(
            const HashNode* _pNode,
            const HashMap<KEY, VALUE, HASH_FUN>* _pMap
            )
{
    __pNode = _pNode;
    __pMap = _pMap;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::ConstIterator(const ConstIterator& _it)
{
    __pNode = _it.__pNode;
    __pMap = _it.__pMap;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::ConstIterator(const Iterator& _it)
{
    __pNode = _it.__pNode;
    __pMap = _it.__pMap;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
typename HashMap<KEY, VALUE, HASH_FUN>::ConstIterator&
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::operator=(const ConstIterator& _it)
{
    __pNode = _it.__pNode;
    __pMap = _it.__pMap;
    return *this;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
bool
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::operator == (const ConstIterator& _it) const
{
    return __pNode == _it.__pNode;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
bool
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::operator != (const ConstIterator& _it) const
{
    return __pNode != _it.__pNode;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
const typename HashMap<KEY, VALUE, HASH_FUN>::Assoc&
HashMap<KEY, VALUE, HASH_FUN>
::ConstIterator::operator*() const
{
    return *__pNode;
}

 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
typename HashMap<KEY, VALUE, HASH_FUN>::Iterator
HashMap<KEY, VALUE, HASH_FUN>::end()
{
    return Iterator(NULL, this);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
typename HashMap<KEY, VALUE, HASH_FUN>::ConstIterator
HashMap<KEY, VALUE, HASH_FUN>::end() const
{
    return ConstIterator(NULL, this);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
size_t
HashMap<KEY, VALUE, HASH_FUN>::bucketSize() const
{
    return __buckets.size();
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
size_t
HashMap<KEY, VALUE, HASH_FUN>::size() const
{
    return __size;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
bool
HashMap<KEY, VALUE, HASH_FUN>::isEmpty() const
{
    return __size == 0;
}

 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::Iterator&
HashMap<KEY, VALUE, HASH_FUN>::Iterator::operator++()
{
    __DCL_ASSERT(__pNode != NULL);
    __DCL_ASSERT(__pMap != NULL);
 
    const HashNode* pOldNode = __pNode;
    __pNode = __pNode->pNext;
    if (__pNode == NULL)
    {
        size_t index = __pMap->bucketIndex(pOldNode->key);
        while((__pNode == NULL) && (++index < __pMap->__buckets.size()))
            __pNode = (HashNode*)__pMap->__buckets[index];
    }
    return *this;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::Iterator
HashMap<KEY, VALUE, HASH_FUN>::Iterator::operator++(int)
{
    Iterator itTemp = *this;
    ++(*this);
    return itTemp;
}

 
// IMPLEMENT_CLASSINFO(HashMap<KEY, VALUE, HASH_FUN>, Object)
#ifdef __DCL_NO_RTTI
template<typename KEY, typename VALUE, typename HASH_FUN>
const Object::ClassInfo HashMap<KEY, VALUE, HASH_FUN>::m_classInfo =
{
    __DCL_NAMESPACE_STRING __S(HashMap),
    sizeof(class HashMap),
    &Object::m_classInfo
};
 
template<typename KEY, typename VALUE, typename HASH_FUN>
const Object::ClassInfo* HashMap<KEY, VALUE, HASH_FUN>::classInfo() const
{
    return CLASSINFO(class_name);
}
#else
template<typename KEY, typename VALUE, typename HASH_FUN>
const std::type_info& HashMap<KEY, VALUE, HASH_FUN>::typeInfo() const
{
    return typeid(HashMap);
}
#endif
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::ConstIterator&
HashMap<KEY, VALUE, HASH_FUN>::ConstIterator::operator++()
{
    __DCL_ASSERT(__pNode != NULL);
    __DCL_ASSERT(__pMap != NULL);
 
    const HashNode* pOldNode = __pNode;
    __pNode = __pNode->pNext;
    if (__pNode == NULL)
    {
        size_t index = __pMap->bucketIndex(pOldNode->key);
        while((__pNode == NULL) && (++index < __pMap->__buckets.size()))
            __pNode = (HashNode*)__pMap->__buckets[index];
    }
    return *this;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::ConstIterator
HashMap<KEY, VALUE, HASH_FUN>::ConstIterator::operator++(int)
{
    ConstIterator itTemp = *this;
    ++(*this);
    return itTemp;
}

 
template<typename KEY, typename VALUE, typename HASH_FUN>
HashMap<KEY, VALUE, HASH_FUN>::~HashMap()
{
    clear();
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
HashMap<KEY, VALUE, HASH_FUN>::HashMap(size_t _bucketSize /* = 10 */)
    : __buckets(DCLGetNextPrimNumber(_bucketSize))
{
    __size = 0;
//  __buckets.resize(DCLGetNextPrimNumber(_bucketSize));
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
void HashMap<KEY, VALUE, HASH_FUN>::initBuckets(size_t _bucketSize)
{
    clear();
    __buckets.resize(DCLGetNextPrimNumber(_bucketSize));
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
HashMap<KEY, VALUE, HASH_FUN>::HashMap(const HashMap<KEY, VALUE, HASH_FUN>& _src)
{
    *this = _src;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
const HashMap<KEY, VALUE, HASH_FUN>&
HashMap<KEY, VALUE, HASH_FUN>::operator=(const HashMap<KEY, VALUE, HASH_FUN>& _src)
{
    if (&_src != this)
    {
        clear();
        __size = _src.__size;
        __buckets.resize(_src.__buckets.size());
 
        for(size_t index = 0; index < _src.__buckets.size(); index++)
        {
            const HashNode* pNode = (HashNode*) _src.__buckets[index];
            if (pNode != NULL)
            {
                HashNode* pNewNode = createNode(pNode->key);
                pNewNode->value = pNode->value;
                __buckets[index] = pNewNode;
                for(pNode = pNode->pNext; pNode != NULL; pNode = pNode->pNext)
                {
                    pNewNode->pNext = createNode(pNode->key);
                    pNewNode = pNewNode->pNext;
                    pNewNode->value = pNode->value;
                }
            }
        }
    }
    return *this;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::ConstIterator
HashMap<KEY, VALUE, HASH_FUN>::begin() const
{
    for(size_t i = 0; i < __buckets.size(); i++)
    {
        if (__buckets[i] != NULL)
            return ConstIterator((HashNode*)__buckets[i], this);
    }
    return ConstIterator(NULL, this);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::Iterator
HashMap<KEY, VALUE, HASH_FUN>::begin()
{
    for(size_t i = 0; i < __buckets.size(); i++)
    {
        if (__buckets[i] != NULL)
            return Iterator((HashNode*)__buckets[i], this);
    }
    return Iterator(NULL, this);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
size_t
HashMap<KEY, VALUE, HASH_FUN>::sizeOfBucket(size_t _index) const
{
    __DCL_ASSERT(_index < __buckets.size());
 
    size_t nCount = 0;
    HashNode* pNode = (HashNode*)__buckets[_index];
    for(; pNode != NULL; pNode = pNode->pNext)
        nCount++;
    return nCount;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::Iterator
HashMap<KEY, VALUE, HASH_FUN>::find(const KEY& _key)
{
    size_t index = bucketIndex(_key);
    HashNode* pNode = (HashNode*)__buckets[index];
    while (pNode) {
        if (pNode->key == _key) {
            break;
        }
        pNode = pNode->pNext;
    }
    return Iterator(pNode, this);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::ConstIterator
HashMap<KEY, VALUE, HASH_FUN>::find(const KEY& _key) const
{
    size_t index = bucketIndex(_key);
    const HashNode* pNode = (HashNode*)__buckets[index];
    while (pNode) {
        if (pNode->key == _key) {
            break;
        }
        pNode = pNode->pNext;
    }
    return ConstIterator(pNode, this);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
bool
HashMap<KEY, VALUE, HASH_FUN>::lookup(const KEY& _key, VALUE& _rValue) const
{
    size_t index = bucketIndex(_key);
    HashNode* pNode = (HashNode*)__buckets[index];
    while(pNode != NULL) {
        if (pNode->key == _key) {
            _rValue = pNode->value;
            return true;
        }
        pNode = pNode->pNext;
    }
    return false;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
VALUE&
HashMap<KEY, VALUE, HASH_FUN>::operator[](const KEY& _key)
{
    size_t index = bucketIndex(_key);
    HashNode* pFirstNode = (HashNode*)__buckets[index];
    for(HashNode* pCurrentNode = pFirstNode; pCurrentNode!= NULL; 
            pCurrentNode = pCurrentNode->pNext)
    {
        if (pCurrentNode->key == _key)
            return pCurrentNode->value;
    }
    
    HashNode* pNewNode = createNode(_key);
    pNewNode->pNext = pFirstNode;
    __buckets[index] = pNewNode;
    __size++;
    return pNewNode->value;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
inline
size_t
HashMap<KEY, VALUE, HASH_FUN>::bucketIndex(const KEY& _key) const
{
    return __hashFun.hashKey(_key) % __buckets.size();
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
typename HashMap<KEY, VALUE, HASH_FUN>::HashNode* 
HashMap<KEY, VALUE, HASH_FUN>::createNode(const KEY& _key)
{
    HashNode* pNode = (HashNode*) malloc(sizeof(HashNode));
    // FIXME!
    // if (pNode == NULL)
    //      throw new BadAllocException(sizeof(HashNode), __THIS_FILE__, __LINE__);
    __DCL_ASSERT(pNode != NULL);
 
    memset((void*) pNode, 0, sizeof(HashNode));
 
#if __DCL_HAVE_ALLOC_DEBUG
#undef new
#endif
 
    new(&(pNode->key)) KEY;
    new(&(pNode->value)) VALUE;
 
#if __DCL_HAVE_ALLOC_DEBUG
#define new __DCL_DEBUG_NEW
#endif
 
    pNode->key = _key;
    return pNode;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
void
HashMap<KEY, VALUE, HASH_FUN>::destroyNode(HashNode* _pNode)
{
    _pNode->key.~KEY();
    _pNode->value.~VALUE();
    free(_pNode);
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
size_t
HashMap<KEY, VALUE, HASH_FUN>::erase(const KEY& _key)
{
    size_t nErased = 0;
    size_t index = bucketIndex(_key);
    HashNode* pCurrentNode = (HashNode*)__buckets[index];
    if (pCurrentNode != NULL)   
    {
        if (pCurrentNode->key == _key)       // first
        {
            __buckets[index] = pCurrentNode->pNext;
            destroyNode(pCurrentNode);
            nErased++;
            __size--;
        }
        else
        {
            HashNode* pNextNode = pCurrentNode->pNext;
            while(pNextNode != NULL)
            {
                if (pNextNode->key == _key)
                {
                    pCurrentNode->pNext = pNextNode->pNext;
                    destroyNode(pNextNode);
                    nErased++;
                    __size--;
                    break;
                }
                else
                {
                    pCurrentNode = pNextNode;
                    pNextNode = pCurrentNode->pNext;
                }
            }
        }
    }
    return nErased;
}
 
template<typename KEY, typename VALUE, typename HASH_FUN>
void
HashMap<KEY, VALUE, HASH_FUN>::clear()
{
    for(size_t i = 0; i < __buckets.size(); i++)
    {
        HashNode* pNode = (HashNode*)__buckets[i];
        while(pNode)
        {
            HashNode* pNext = pNode->pNext;
            destroyNode(pNode);
            pNode = pNext;
        }
        __buckets[i] = NULL;
    }
    __size = 0;
}
 
#if __DCL_HAVE_THIS_FILE__
    #undef __THIS_FILE__
    #define __THIS_FILE__   __T(__FILE__)
#endif
 
__DCL_END_NAMESPACE