__HashMapT-MSC.h

Go to the documentation of this file.

 
/*
Visual C++ 의 경우 템클레이트 클래스의 맴버 클래스의 맴버들에 
대하여 코드를 생성하지 못하는 버그가 있다.
 
BUG: LNK2001 on Member Function When Use Nested Class Template
Last reviewed: July 24, 1997
Article ID: Q128789  
The information in this article applies to: 
The Microsoft C/C++ Compiler (CL.EXE) included with:
    - Microsoft Visual C++, 32-bit Edition, versions 2.0, 2.1, 4.0, 4.1, 4.2, 5.0
*/
 
#ifndef __DCL_HASH_MAP_T_H__
#error "Never include <dcl/__HashMapT-MSC.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-MSC.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)
        {
            __pNode = _pNode;
            __pMap = _pMap;
        }
 
        Iterator& operator=(const Iterator& _it)
        {
            __pNode = _it.__pNode;
            __pMap = _it.__pMap;
            return *this;
        }
 
        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;
        }
 
        Iterator operator++(int)
        {
            Iterator itTemp = *this;
            ++(*this);
            return itTemp;
        }
 
        bool operator==(const Iterator& _it) const
        {
            return __pNode != _it.__pNode;
        }
 
        bool operator!=(const Iterator& _it) const
        {
            return __pNode != _it.__pNode;
        }
 
        Assoc& operator*() const
        {
            return *__pNode;
        }
 
    protected:
        HashMap* __pMap;
        HashNode*   __pNode;
        friend typename ConstIterator;
    };
 
    class ConstIterator
    {
    public:
        ConstIterator(const HashNode* _pNode, const HashMap* _pMap)
        {
            __pNode = _pNode;
            __pMap = _pMap;
        }
 
        ConstIterator(const ConstIterator& _it)
        {
            __pNode = _it.__pNode;
            __pMap = _it.__pMap;
        }
 
        ConstIterator(const Iterator& _it)
        {
            __pNode = _it.__pNode;
            __pMap = _it.__pMap;
        }
 
        ConstIterator& operator=(const ConstIterator& _it)
        {
            __pNode = _it.__pNode;
            __pMap = _it.__pMap;
            return *this;
        }
 
        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;
        }
 
        ConstIterator operator++(int)
        {
            ConstIterator itTemp = *this;
            ++(*this);
            return itTemp;
        }
 
        bool operator==(const ConstIterator& _it) const
        {
            return __pNode == _it.__pNode;
        }
 
        bool operator!=(const ConstIterator& _it) const
        {
            return __pNode != _it.__pNode;
        }
 
        const Assoc& operator*() const
        {
            return *__pNode;
        }
 
    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);
    size_t erase(const Iterator& _it);
    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
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;
}

 
// 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>
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(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