KviPointerHashTable.h

Go to the documentation of this file.

#ifndef _KVI_POINTERHASHTABLE_H_
#define _KVI_POINTERHASHTABLE_H_
//============================================================================
//
//   File : KviPointerHashTable.h
//   Creation date : Sat Jan 12 2008 04:53 by Szymon Stefanek
//
//   This file is part of the KVIrc IRC client distribution
//   Copyright (C) 2008 Szymon Stefanek (pragma at kvirc dot net)
//
//   This program is FREE software. You can redistribute it and/or
//   modify it under the terms of the GNU General Public License
//   as published by the Free Software Foundation; either version 2
//   of the License, or (at your option) any later version.
//
//   This program is distributed in the HOPE that it will be USEFUL,
//   but WITHOUT ANY WARRANTY; without even the implied warranty of
//   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
//   See the GNU General Public License for more details.
//
//   You should have received a copy of the GNU General Public License
//   along with this program. If not, write to the Free Software Foundation,
//   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
//
//============================================================================

#include "kvi_settings.h"
#include "KviPointerList.h"
#include "KviCString.h"
#include "KviQString.h"
#include "KviMemory.h"
#include "kvi_debug.h"

#include <ctype.h>


inline unsigned int kvi_hash_hash(const char * szKey, bool bCaseSensitive)
{
        unsigned int uResult = 0;
        if(bCaseSensitive)
        {
                while(*szKey)
                {
                        uResult += (unsigned char)(*(szKey));
                        szKey++;
                }
        }
        else
        {
                while(*szKey)
                {
                        uResult += (unsigned char)tolower(*(szKey));
                        szKey++;
                }
        }
        return uResult;
}

inline bool kvi_hash_key_equal(const char * szKey1, const char * szKey2, bool bCaseSensitive)
{
        if(bCaseSensitive)
        {
                while(*szKey1 && *szKey2)
                {
                        if(*szKey1 != *szKey2)
                                return false;
                        szKey1++;
                        szKey2++;
                }
        }
        else
        {
                while(*szKey1 && *szKey2)
                {
                        if(tolower(*szKey1) != tolower(*szKey2))
                                return false;
                        szKey1++;
                        szKey2++;
                }
        }
        //check if one of the strings is a substring of the other (like "perl" and "perlcore")
        if(*szKey1 || *szKey2)
                return false;
        return true;
}

inline void kvi_hash_key_copy(const char * const & szFrom, const char *& szTo, bool bDeepCopy)
{
        if(bDeepCopy)
        {
#if defined(COMPILE_ON_WINDOWS)
                // strlen() returns size_t under windows, which is 32 bits long on a 32 bits
                // system and 64 bits long on a 64 bits one. cast it to avoid a warning
                int len = (int)kvi_strLen(szFrom);
#else
                int len = kvi_strLen(szFrom);
#endif
                char * dst = (char *)KviMemory::allocate(len + 1);
                KviMemory::copy(dst, szFrom, len + 1);
                szTo = dst;
        }
        else
        {
                szTo = szFrom; // we never modify it anyway
        }
}

inline void kvi_hash_key_destroy(const char *& szKey, bool bDeepCopy)
{
        if(bDeepCopy)
                KviMemory::free((char *)szKey);
}

inline const char *& kvi_hash_key_default(const char **)
{
        static const char * static_null = NULL;
        return static_null;
}

inline unsigned int kvi_hash_hash(const KviCString & szKey, bool bCaseSensitive)
{
        unsigned int uResult = 0;
        const char * p = szKey.ptr();
        if(bCaseSensitive)
        {
                while(*p)
                {
                        uResult += *((const unsigned char *)p);
                        p++;
                }
        }
        else
        {
                while(*p)
                {
                        uResult += tolower(*((const unsigned char *)p));
                        p++;
                }
        }
        return uResult;
}

inline bool kvi_hash_key_equal(const KviCString & szKey1, const KviCString & szKey2)
{
        return kvi_hash_key_equal(szKey1.ptr(), szKey2.ptr());
}

inline void kvi_hash_key_copy(const KviCString & szFrom, KviCString & szTo, bool)
{
        szTo = szFrom;
}

inline void kvi_hash_key_destroy(KviCString &, bool)
{
}

inline const KviCString & kvi_hash_key_default(KviCString *)
{
        return KviCString::emptyString();
}

inline unsigned int kvi_hash_hash(const int & iKey, bool)
{
        return (unsigned int)iKey;
}

inline bool kvi_hash_key_equal(const int & iKey1, const int & iKey2, bool)
{
        return iKey1 == iKey2;
}

inline void kvi_hash_key_copy(const int & iKeyFrom, int & iKeyTo, bool)
{
        iKeyTo = iKeyFrom;
}

inline void kvi_hash_key_destroy(int &, bool)
{
}

inline const int & kvi_hash_key_default(int *)
{
        static int static_default = 0;
        return static_default;
}

inline unsigned int kvi_hash_hash(const unsigned short & iKey, bool)
{
        return (unsigned int)iKey;
}

inline bool kvi_hash_key_equal(const unsigned short & iKey1, const unsigned short & iKey2, bool)
{
        return iKey1 == iKey2;
}

inline void kvi_hash_key_copy(const unsigned short & iKeyFrom, unsigned short & iKeyTo, bool)
{
        iKeyTo = iKeyFrom;
}

inline void kvi_hash_key_destroy(unsigned short &, bool)
{
}

inline const unsigned short & kvi_hash_key_default(unsigned short *)
{
        static unsigned short static_default = 0;
        return static_default;
}

inline unsigned int kvi_hash_hash(void * pKey, bool)
{
        unsigned char * pBytes = (unsigned char *)&(pKey);
        unsigned char * pEnd = pBytes + sizeof(void *);
        unsigned int uSum = 0;
        while(pBytes < pEnd)
        {
                uSum += *pBytes;
                pBytes++;
        }
        return uSum;
}

inline bool kvi_hash_key_equal(void * pKey1, void * pKey2, bool)
{
        return pKey1 == pKey2;
}

inline void kvi_hash_key_copy(void * const & pKeyFrom, void *& pKeyTo, bool)
{
        pKeyTo = pKeyFrom;
}

inline void kvi_hash_key_destroy(void *, bool)
{
}

inline void *& kvi_hash_key_default(void *)
{
        static void * static_default = NULL;
        return static_default;
}

inline unsigned int kvi_hash_hash(const QString & szKey, bool bCaseSensitive)
{
        unsigned int uResult = 0;
        const QChar * p = szKey.constData();
        if(!p)
                return 0;
        if(bCaseSensitive)
        {
                while(p->unicode())
                {
                        uResult += p->unicode();
                        p++;
                }
        }
        else
        {
                while(p->unicode())
                {
                        uResult += p->toLower().unicode();
                        p++;
                }
        }
        return uResult;
}

inline bool kvi_hash_key_equal(const QString & szKey1, const QString & szKey2, bool bCaseSensitive)
{
        if(bCaseSensitive)
                return KviQString::equalCS(szKey1, szKey2);
        return KviQString::equalCI(szKey1, szKey2);
}

inline void kvi_hash_key_copy(const QString & szFrom, QString & szTo, bool)
{
        szTo = szFrom;
}

inline void kvi_hash_key_destroy(QString &, bool)
{
}

inline const QString & kvi_hash_key_default(QString *)
{
        return KviQString::Empty;
}

template <typename Key, typename T>
class KviPointerHashTable;
template <typename Key, typename T>
class KviPointerHashTableIterator;

template <typename Key, typename T>
class KviPointerHashTableEntry
{
        friend class KviPointerHashTable<Key, T>;

protected:
        T * pData;
        Key hKey;

public:
        Key & key() { return hKey; };
        T * data() { return pData; };
};

template <class Key, class T>
class KviPointerHashTable
{
        friend class KviPointerHashTableIterator<Key, T>;

protected:
        KviPointerList<KviPointerHashTableEntry<Key, T>> ** m_pDataArray;
        bool m_bAutoDelete;
        unsigned int m_uSize;
        unsigned int m_uCount;
        bool m_bCaseSensitive;
        bool m_bDeepCopyKeys;
        unsigned int m_uIteratorIdx;

public:
        T * find(const Key & hKey)
        {
                m_uIteratorIdx = kvi_hash_hash(hKey, m_bCaseSensitive) % m_uSize;
                if(!m_pDataArray[m_uIteratorIdx])
                        return 0;
                for(KviPointerHashTableEntry<Key, T> * e = m_pDataArray[m_uIteratorIdx]->first(); e; e = m_pDataArray[m_uIteratorIdx]->next())
                {
                        if(kvi_hash_key_equal(e->hKey, hKey, m_bCaseSensitive))
                                return (T *)e->pData;
                }
                return 0;
        }

        T * operator[](const Key & hKey)
        {
                return find(hKey);
        }

        unsigned int count() const
        {
                return m_uCount;
        }

        bool isEmpty() const
        {
                return m_uCount == 0;
        }

        void insert(const Key & hKey, T * pData)
        {
                if(!pData)
                        return;
                unsigned int uEntry = kvi_hash_hash(hKey, m_bCaseSensitive) % m_uSize;
                if(!m_pDataArray[uEntry])
                        m_pDataArray[uEntry] = new KviPointerList<KviPointerHashTableEntry<Key, T>>(true);
                for(KviPointerHashTableEntry<Key, T> * e = m_pDataArray[uEntry]->first(); e; e = m_pDataArray[uEntry]->next())
                {
                        if(kvi_hash_key_equal(e->hKey, hKey, m_bCaseSensitive))
                        {
                                if(!m_bCaseSensitive)
                                {
                                        // must change the key too
                                        kvi_hash_key_destroy(e->hKey, m_bDeepCopyKeys);
                                        kvi_hash_key_copy(hKey, e->hKey, m_bDeepCopyKeys);
                                }
                                if(m_bAutoDelete)
                                        delete e->pData;
                                e->pData = pData;
                                return;
                        }
                }
                KviPointerHashTableEntry<Key, T> * n = new KviPointerHashTableEntry<Key, T>;
                kvi_hash_key_copy(hKey, n->hKey, m_bDeepCopyKeys);
                n->pData = pData;
                m_pDataArray[uEntry]->append(n);
                m_uCount++;
        }

        void replace(const Key & hKey, T * pData)
        {
                insert(hKey, pData);
        }

        bool remove(const Key & hKey)
        {
                unsigned int uEntry = kvi_hash_hash(hKey, m_bCaseSensitive) % m_uSize;
                if(!m_pDataArray[uEntry])
                        return false;
                for(KviPointerHashTableEntry<Key, T> * e = m_pDataArray[uEntry]->first(); e; e = m_pDataArray[uEntry]->next())
                {
                        if(kvi_hash_key_equal(e->hKey, hKey, m_bCaseSensitive))
                        {
                                kvi_hash_key_destroy(e->hKey, m_bDeepCopyKeys);
                                if(m_bAutoDelete)
                                        delete((T *)(e->pData));
                                m_pDataArray[uEntry]->removeRef(e);
                                if(m_pDataArray[uEntry]->isEmpty())
                                {
                                        delete m_pDataArray[uEntry];
                                        m_pDataArray[uEntry] = 0;
                                }
                                m_uCount--;
                                return true;
                        }
                }
                return false;
        }

        bool removeRef(const T * pRef)
        {
                for(unsigned int i = 0; i < m_uSize; i++)
                {
                        if(m_pDataArray[i])
                        {
                                for(KviPointerHashTableEntry<Key, T> * e = m_pDataArray[i]->first(); e; e = m_pDataArray[i]->next())
                                {
                                        if(e->pData == pRef)
                                        {
                                                kvi_hash_key_destroy(e->hKey, m_bDeepCopyKeys);
                                                if(m_bAutoDelete)
                                                        delete((T *)(e->pData));
                                                m_pDataArray[i]->removeRef(e);
                                                if(m_pDataArray[i]->isEmpty())
                                                {
                                                        delete m_pDataArray[i];
                                                        m_pDataArray[i] = 0;
                                                }
                                                m_uCount--;
                                                return true;
                                        }
                                }
                        }
                }
                return false;
        }

        void clear()
        {
                for(unsigned int i = 0; i < m_uSize; i++)
                {
                        if(!m_pDataArray[i])
                                continue;

                        while(KviPointerHashTableEntry<Key, T> * e = m_pDataArray[i]->takeFirst())
                        {
                                kvi_hash_key_destroy(e->hKey, m_bDeepCopyKeys);

                                if(m_bAutoDelete)
                                        delete((T *)(e->pData));

                                delete e;

                                if(!m_pDataArray[i])
                                        break; // emptied in the meantime
                        }

                        if(m_pDataArray[i])
                        {
                                delete m_pDataArray[i];
                                m_pDataArray[i] = 0;
                        }
                }
                m_uCount = 0;
        }

        KviPointerHashTableEntry<Key, T> * findRef(const T * pRef)
        {
                for(m_uIteratorIdx = 0; m_uIteratorIdx < m_uSize; m_uIteratorIdx++)
                {
                        if(m_pDataArray[m_uIteratorIdx])
                        {
                                for(KviPointerHashTableEntry<Key, T> * e = m_pDataArray[m_uIteratorIdx]->first(); e; e = m_pDataArray[m_uIteratorIdx]->next())
                                {
                                        if(e->pData == pRef)
                                                return e;
                                }
                        }
                }
                return 0;
        }

        KviPointerHashTableEntry<Key, T> * currentEntry()
        {
                if(m_uIteratorIdx >= m_uSize)
                        return 0;
                if(m_pDataArray[m_uIteratorIdx])
                        return m_pDataArray[m_uIteratorIdx]->current();
                return 0;
        }

        KviPointerHashTableEntry<Key, T> * firstEntry()
        {
                m_uIteratorIdx = 0;
                while(m_uIteratorIdx < m_uSize && (!m_pDataArray[m_uIteratorIdx]))
                {
                        m_uIteratorIdx++;
                }
                if(m_uIteratorIdx == m_uSize)
                        return 0;
                return m_pDataArray[m_uIteratorIdx]->first();
        }

        KviPointerHashTableEntry<Key, T> * nextEntry()
        {
                if(m_uIteratorIdx >= m_uSize)
                        return 0;

                if(m_uIteratorIdx < m_uSize)
                {
                        KviPointerHashTableEntry<Key, T> * t = m_pDataArray[m_uIteratorIdx]->next();
                        if(t)
                                return t;
                }

                m_uIteratorIdx++;

                while(m_uIteratorIdx < m_uSize && (!m_pDataArray[m_uIteratorIdx]))
                {
                        m_uIteratorIdx++;
                }

                if(m_uIteratorIdx == m_uSize)
                        return 0;

                return m_pDataArray[m_uIteratorIdx]->first();
        }

        T * current()
        {
                if(m_uIteratorIdx >= m_uSize)
                        return 0;
                if(m_pDataArray[m_uIteratorIdx])
                {
                        KviPointerHashTableEntry<Key, T> * e = m_pDataArray[m_uIteratorIdx]->current();
                        if(!e)
                                return 0;
                        return e->data();
                }
                return 0;
        }

        const Key & currentKey()
        {
                if(m_uIteratorIdx >= m_uSize)
                        return kvi_hash_key_default(((Key *)NULL));
                if(m_pDataArray[m_uIteratorIdx])
                {
                        KviPointerHashTableEntry<Key, T> * e = m_pDataArray[m_uIteratorIdx]->current();
                        if(!e)
                                return kvi_hash_key_default(((Key *)NULL));
                        return e->key();
                }
                return kvi_hash_key_default(((Key *)NULL));
        }

        T * first()
        {
                m_uIteratorIdx = 0;
                while(m_uIteratorIdx < m_uSize && (!m_pDataArray[m_uIteratorIdx]))
                {
                        m_uIteratorIdx++;
                }
                if(m_uIteratorIdx == m_uSize)
                        return 0;
                KviPointerHashTableEntry<Key, T> * e = m_pDataArray[m_uIteratorIdx]->first();
                if(!e)
                        return 0;
                return e->data();
        }

        T * next()
        {
                if(m_uIteratorIdx >= m_uSize)
                        return 0;

                if(m_uIteratorIdx < m_uSize)
                {
                        KviPointerHashTableEntry<Key, T> * t = m_pDataArray[m_uIteratorIdx]->next();
                        if(t)
                        {
                                return t->data();
                        }
                }

                m_uIteratorIdx++;

                while(m_uIteratorIdx < m_uSize && (!m_pDataArray[m_uIteratorIdx]))
                {
                        m_uIteratorIdx++;
                }

                if(m_uIteratorIdx == m_uSize)
                        return 0;

                KviPointerHashTableEntry<Key, T> * e = m_pDataArray[m_uIteratorIdx]->first();
                if(!e)
                        return 0;
                return e->data();
        }

        void copyFrom(KviPointerHashTable<Key, T> & t)
        {
                clear();
                for(KviPointerHashTableEntry<Key, T> * e = t.firstEntry(); e; e = t.nextEntry())
                        insert(e->key(), e->data());
        }

        void insert(KviPointerHashTable<Key, T> & t)
        {
                for(KviPointerHashTableEntry<Key, T> * e = t.firstEntry(); e; e = t.nextEntry())
                        insert(e->key(), e->data());
        }

        void setAutoDelete(bool bAutoDelete)
        {
                m_bAutoDelete = bAutoDelete;
        }

        KviPointerHashTable(unsigned int uSize = 32, bool bCaseSensitive = true, bool bDeepCopyKeys = true)
        {
                m_uCount = 0;
                m_bCaseSensitive = bCaseSensitive;
                m_bAutoDelete = true;
                m_bDeepCopyKeys = bDeepCopyKeys;
                m_uSize = uSize > 0 ? uSize : 32;
                m_pDataArray = new KviPointerList<KviPointerHashTableEntry<Key, T>> *[m_uSize];
                for(unsigned int i = 0; i < m_uSize; i++)
                        m_pDataArray[i] = NULL;
        }

        KviPointerHashTable(KviPointerHashTable<Key, T> & t)
        {
                m_uCount = 0;
                m_bAutoDelete = false;
                m_bCaseSensitive = t.m_bCaseSensitive;
                m_bDeepCopyKeys = t.m_bDeepCopyKeys;
                m_uSize = t.m_uSize;
                m_pDataArray = new KviPointerList<KviPointerHashTableEntry<Key, T>> *[m_uSize];
                for(unsigned int i = 0; i < m_uSize; i++)
                        m_pDataArray[i] = NULL;
                copyFrom(t);
        }

        ~KviPointerHashTable()
        {
                clear();
                delete[] m_pDataArray;
        }
};

template <typename Key, typename T>
class KviPointerHashTableIterator
{
protected:
        const KviPointerHashTable<Key, T> * m_pHashTable;
        unsigned int m_uEntryIndex;
        KviPointerListIterator<KviPointerHashTableEntry<Key, T>> * m_pIterator;

public:
        void operator=(const KviPointerHashTableIterator<Key, T> & src)
        {
                m_pHashTable = src.m_pHashTable;
                m_uEntryIndex = src.m_uEntryIndex;
                if(src.m_pIterator)
                        m_pIterator = new KviPointerListIterator<KviPointerHashTableEntry<Key, T>>(*(src.m_pIterator));
                else
                        m_pIterator = NULL;
        }

        bool moveFirst()
        {
                if(m_pIterator)
                {
                        delete m_pIterator;
                        m_pIterator = NULL;
                }

                m_uEntryIndex = 0;
                while((m_uEntryIndex < m_pHashTable->m_uSize) && (!(m_pHashTable->m_pDataArray[m_uEntryIndex])))
                {
                        m_uEntryIndex++;
                }

                if(m_uEntryIndex == m_pHashTable->m_uSize)
                        return false;

                m_pIterator = new KviPointerListIterator<KviPointerHashTableEntry<Key, T>>(*(m_pHashTable->m_pDataArray[m_uEntryIndex]));
                bool bRet = m_pIterator->moveFirst();
                if(!bRet)
                {
                        delete m_pIterator;
                        m_pIterator = NULL;
                }
                return bRet;
        }

        bool moveLast()
        {
                if(m_pIterator)
                {
                        delete m_pIterator;
                        m_pIterator = NULL;
                }

                m_uEntryIndex = m_pHashTable->m_uSize;
                while(m_uEntryIndex > 0)
                {
                        m_uEntryIndex--;
                        if(m_pHashTable->m_pDataArray[m_uEntryIndex])
                        {
                                m_pIterator = new KviPointerListIterator<KviPointerHashTableEntry<Key, T>>(*(m_pHashTable->m_pDataArray[m_uEntryIndex]));
                                bool bRet = m_pIterator->moveLast();
                                if(!bRet)
                                {
                                        delete m_pIterator;
                                        m_pIterator = NULL;
                                }
                                return bRet;
                        }
                }
                return false;
        }

        bool moveNext()
        {
                if(!m_pIterator)
                        return false;
                if(m_pIterator->moveNext())
                        return true;
                if(m_pIterator)
                {
                        delete m_pIterator;
                        m_pIterator = NULL;
                }
                m_uEntryIndex++;
                while((m_uEntryIndex < m_pHashTable->m_uSize) && (!(m_pHashTable->m_pDataArray[m_uEntryIndex])))
                {
                        m_uEntryIndex++;
                }
                if(m_uEntryIndex == m_pHashTable->m_uSize)
                        return false;
                m_pIterator = new KviPointerListIterator<KviPointerHashTableEntry<Key, T>>(*(m_pHashTable->m_pDataArray[m_uEntryIndex]));
                bool bRet = m_pIterator->moveFirst();
                if(!bRet)
                {
                        delete m_pIterator;
                        m_pIterator = NULL;
                }
                return bRet;
        }

        bool operator++()
        {
                return moveNext();
        }

        bool movePrev()
        {
                if(!m_pIterator)
                        return false;
                if(m_pIterator->movePrev())
                        return true;
                if(m_pIterator)
                {
                        delete m_pIterator;
                        m_pIterator = NULL;
                }
                if(m_uEntryIndex >= m_pHashTable->m_uSize)
                        return false;
                while(m_uEntryIndex > 0)
                {
                        m_uEntryIndex--;
                        if(m_pHashTable->m_pDataArray[m_uEntryIndex])
                        {
                                m_pIterator = new KviPointerListIterator<KviPointerHashTableEntry<Key, T>>(*(m_pHashTable->m_pDataArray[m_uEntryIndex]));
                                bool bRet = m_pIterator->moveLast();
                                if(!bRet)
                                {
                                        delete m_pIterator;
                                        m_pIterator = NULL;
                                }
                                return bRet;
                        }
                }
                return false;
        }

        bool operator--()
        {
                return movePrev();
        }

        T * current() const
        {
                return m_pIterator ? m_pIterator->current()->data() : NULL;
        }

        T * operator*() const
        {
                return m_pIterator ? m_pIterator->current()->data() : NULL;
        }

        const Key & currentKey() const
        {
                if(m_pIterator)
                        return m_pIterator->current()->key();
                return kvi_hash_key_default(((Key *)NULL));
        }

        T * toFirst()
        {
                if(!moveFirst())
                        return NULL;
                return current();
        }

public:
        KviPointerHashTableIterator(const KviPointerHashTable<Key, T> & hTable)
        {
                m_pHashTable = &hTable;
                m_uEntryIndex = 0;
                m_pIterator = NULL;
                moveFirst();
        }

        ~KviPointerHashTableIterator()
        {
                if(m_pIterator)
                        delete m_pIterator;
        }
};

#endif //_KVI_POINTERHASHTABLE_H_