__HASHMAP.cpp

Go to the documentation of this file.

#ifdef __DCL_INTERNAL__
 
#ifdef __COMPILE_StringToStringMap__
    #define THIS_NAME                       __szStringToStringMap_cpp__
    #define THIS_VALUE                      __T("dcl/__HASHMAP.cpp/StringToStringMap")
    #define HASHMAP_T                       StringToStringMap
    #define HASHFUN_T                       HashFun<String>
    #define KEY_T                           String
    #define VALUE_T                         String
    #define HAVE_CONSTRUCTOR_KEY            1
    #define HAVE_CONSTRUCTOR_VALUE          1
#elif defined(__COMPILE_StringToPointerMap__)
    #define THIS_NAME                       __szStringToPointerMap_cpp__
    #define THIS_VALUE                      __T("dcl/__HASHMAP.cpp/StringToPointerMap")
    #define HASHMAP_T                       StringToPointerMap
    #define HASHFUN_T                       HashFun<String>
    #define KEY_T                           String
    #define VALUE_T                         void*
    #define HAVE_CONSTRUCTOR_KEY            1
    #define HAVE_CONSTRUCTOR_VALUE          0
#elif defined(__COMPILE_IntToPointerMap__)
    #define THIS_NAME                       __szIntToPointerMap_cpp__
    #define THIS_VALUE                      __T("dcl/__HASHMAP.cpp/IntToPointerMap")
    #define HASHMAP_T                       IntToPointerMap
    #define HASHFUN_T                       HashFun<int>
    #define KEY_T                           int
    #define VALUE_T                         void*
    #define HAVE_CONSTRUCTOR_KEY            0
    #define HAVE_CONSTRUCTOR_VALUE          0
#endif
 
#if __DCL_HAVE_THIS_FILE__
    static const char_t THIS_NAME[] = THIS_VALUE;
    #undef __THIS_FILE__
    #define __THIS_FILE__ THIS_NAME
#endif
 
#if __DCL_HAVE_ALLOC_DEBUG
    #undef __DCL_ALLOC_LEVEL
    #define __DCL_ALLOC_LEVEL   __DCL_ALLOC_INTERNAL
#endif

 
HASHMAP_T::Iterator&
HASHMAP_T::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;
}
 
HASHMAP_T::Iterator
HASHMAP_T::Iterator::operator++(int)
{
    Iterator itTemp = *this;
    ++(*this);
    return itTemp;
}

 
HASHMAP_T::ConstIterator&
HASHMAP_T::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;
}
 
HASHMAP_T::ConstIterator
HASHMAP_T::ConstIterator::operator++(int)
{
    ConstIterator itTemp = *this;
    ++(*this);
    return itTemp;
}

 
IMPLEMENT_CLASSINFO(HASHMAP_T, Object)
 
String HASHMAP_T::toString() const
{
    StringBuilder r = __T("{");
    for (ConstIterator it = begin(); it != end(); it++)
    {
        if (it != begin())
            r += __T(", ");
        r.format(
#ifdef __COMPILE_StringToStringMap__
            __T("{\"%ls\", \"%ls\"}"), (*it).key.data(), (*it).value.data()
#elif defined(__COMPILE_StringToPointerMap__)
            __T("{\"%ls\", %p}"), (*it).key.data(), (*it).value
#elif defined(__COMPILE_IntToPointerMap__)
            __T("{%d, %p}"), (*it).key, (*it).value
#endif
            );
    }
    r += __T("}");
    return r;
}
 
HASHMAP_T::~HASHMAP_T()
{
    clear();
}
 
HASHMAP_T::HASHMAP_T(size_t _bucketSize)
    : __buckets(DCLGetNextPrimNumber(_bucketSize))
{
    __size = 0;
//  __buckets.resize(DCLGetNextPrimNumber(_bucketSize));
}
 
void HASHMAP_T::initBuckets(size_t _bucketSize)
{
    clear();
    __buckets.resize(DCLGetNextPrimNumber(_bucketSize));
}
 
HASHMAP_T::HASHMAP_T(const HASHMAP_T& _src)
{
    *this = _src;
}
 
const HASHMAP_T&
HASHMAP_T::operator=(const HASHMAP_T& _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;
}
 
HASHMAP_T::ConstIterator
HASHMAP_T::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);
}
 
HASHMAP_T::Iterator
HASHMAP_T::begin()
{
    for(size_t i = 0; i < __buckets.size(); i++)
    {
        if (__buckets[i] != NULL)
            return Iterator((HashNode*)__buckets[i], this);
    }
    return Iterator(NULL, this);
}
 
size_t
HASHMAP_T::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;
}
 
HASHMAP_T::Iterator
HASHMAP_T::find(const KEY_T& _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);
}
 
HASHMAP_T::ConstIterator
HASHMAP_T::find(const KEY_T& _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);
}
 
bool
HASHMAP_T::lookup(const KEY_T& _key, VALUE_T& _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;
}
 
VALUE_T&
HASHMAP_T::operator[](const KEY_T& _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;
}
 
inline
size_t
HASHMAP_T::bucketIndex(const KEY_T& _key) const
{
    return __hashFun.hashKey(_key) % __buckets.size();
}
 
HASHMAP_T::HashNode* 
HASHMAP_T   ::createNode(const KEY_T& _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
 
#if HAVE_CONSTRUCTOR_KEY
    new(&(pNode->key)) KEY_T;
#endif
#if HAVE_CONSTRUCTOR_VALUE
    new(&(pNode->value)) VALUE_T;
#endif
 
#if __DCL_HAVE_ALLOC_DEBUG
#define new __DCL_DEBUG_NEW
#endif
 
    pNode->key = _key;
    return pNode;
}
 
void
HASHMAP_T::destroyNode(HashNode* _pNode)
{
#if HAVE_CONSTRUCTOR_KEY
    _pNode->key.~KEY_T();
#endif
#if HAVE_CONSTRUCTOR_VALUE
    _pNode->value.~VALUE_T();
#endif
    free(_pNode);
}
 
size_t
HASHMAP_T::erase(const KEY_T& _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;
}
 
void
HASHMAP_T::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
 
#undef THIS_NAME
#undef THIS_VALUE
#undef HASHMAP_T
#undef HASHFUN_T
#undef KEY_T
#undef VALUE_T
#undef HAVE_CONSTRUCTOR_KEY
#undef HAVE_CONSTRUCTOR_VALUE
 
#endif          // __DCL_INTERNAL_