CStringHash.h

#ifndef __LDK_CSTRINGHASH_H__
#define __LDK_CSTRINGHASH_H__

//   Copyright (C) 2003-2007 Lorien Dunn.
//
//   Contact: loriendunn AT users DOT sourceforge DOT net
//
//   This software is provided 'as-is', without any express or implied warranty.
//   In no event will the authors be held liable for any damages arising from
//   the use of this software.
//
//   Permission is granted to anyone to use this software for any purpose,
//   including commercial applications, and to alter it and redistribute it
//   freely, subject to the following restrictions:
//
//   1. The origin of this software must not be misrepresented; you must not
//   claim that you wrote the original software. If you use this software in a
//   product, an acknowledgment in the product documentation would be
//   appreciated but is not required.
//
//   2. Altered source versions must be plainly marked as such, and must not be
//   misrepresented as being the original software.
//
//   3. This notice may not be removed or altered from any source distribution.
//

#include "LDK/Hash.h"

namespace LDK
{

//Nasty partial specialisation for Key==const char* .
//Pair holds copies of the strings
template
<
    class Data,
    template <class> class Alloc
>
class Hash<const char*,Data,Alloc> : public Object
{
public:
    class Pair
    {
    private:
        void operator=(const Pair& rhs) {}
        typedef Alloc<char> CharAlloc;
        CharAlloc mCharAlloc;
    public:
    const char* mKey;
    Data mData;
        inline Pair(const char* k, const Data& d) : mKey(NULL), mData(d)
        {
            size_t len = strlen(k);
            if(len > 1024)
                throw LDK_ARGUMENT_ERROR("CStringHash key too long");
            mKey = (const char*) mCharAlloc.allocate(len+1);
            strncpy(const_cast<char*>(mKey),k,len+1);
        }
        inline Pair(const Pair& rhs)
        {
            size_t len = strlen(rhs.mKey);
            mKey = (const char*) mCharAlloc.allocate(len+1);
            strcpy(const_cast<char*>(mKey),rhs.mKey);
        }
        inline ~Pair()
        {
            mCharAlloc.deallocate((void*)mKey,1);
            mKey = NULL;
        }
    };
protected:
    typedef Alloc<Pair> PairAlloc;
    PairAlloc mPairAlloc;
    typedef Alloc<Pair*> PairPtrAlloc;
    PairPtrAlloc mPairPtrAlloc;
    Pair**  mArray;
    size_t  mAllocated;
    size_t  mFreeSlots;
    size_t  mSize;
    static const int cIncBy = 7;

    static size_t primeGreaterThan(size_t size)
    {
        const size_t* prime = PrimeConsts;

        while(prime)
        {
            if((*prime) == size)
            {
                prime++;
                break;
            }
            if((*prime) > size)
                break;
            prime++;
        }

        assert((*prime) != 0);

        return (*prime);
    }

    static size_t newSize(size_t currentSize, size_t freeSlots)
    {
    size_t newSize = currentSize;

        //Make sure at least 10% slots are free.
        while (freeSlots <= (newSize/10))
        {
            newSize =  primeGreaterThan(newSize);
            // As the array grows more slots will be available
            freeSlots = freeSlots + (newSize-currentSize);
        }
        return newSize;
    }

    size_t hash(const char* k, size_t allocated) const
    {
        Hasher<const char*> hasher;
        return hasher(k, allocated);
    }

    void rehash(size_t newAlloc)
    {
        size_t oldAllocated = mAllocated;
        Pair** newArray = (Pair**) mPairPtrAlloc.allocate(newAlloc+1);
        memset(newArray, 0, sizeof(newArray[0])*(newAlloc+1));

        size_t newFreeSlots = newAlloc;

        for(size_t i=0; i<oldAllocated; ++i)
        {
            Pair* element = mArray[i];
            if(element)
            {
                size_t newHashValue = hash(element->mKey, newAlloc);
                size_t index = newHashValue;
                Pair* newElement = newArray[newHashValue];

                while(newElement!=0)
                {
                    index = (index + cIncBy) % newAlloc;
                    newElement = newArray[index];
                }

                // Move the element to the new array
                newArray[index] = element;
                newFreeSlots--;
            }
        }

        // Elements from the old array have been moved to the new array. Hence no realloc.
        if(mArray!=0)
            mPairPtrAlloc.deallocate(mArray,1);
        mArray = newArray;
        mAllocated = newAlloc;
        mFreeSlots = newFreeSlots;
    }

    void assign(const Hash& rhs)
    {
        mArray = (Pair**) mPairPtrAlloc.allocate(rhs.mAllocated+1);
        mAllocated = rhs.mAllocated;
        mFreeSlots = rhs.mFreeSlots;
        mSize = rhs.mSize;
        for(size_t i=0;i<=mAllocated;i++)
        {
            if(rhs.mArray[i])
            {
                mArray[i] = mPairAlloc.allocate(1);
                mPairAlloc.construct(mArray[i],*(rhs.mArray[i]));
            }
            else
                mArray[i] = NULL;
        }
    }

public:

    class Iterator
    {
    private:
        friend class Hash;
        Hash* mHash;
        size_t mIndex;
    public:

        inline Iterator(Hash* ht=NULL, size_t index=0) : mHash(ht),
         mIndex(index)
        {
            if(mHash)
                if(index<mHash->allocated() && mHash->element(index)==0)
                    ++(*this);
        }

        inline Iterator(const Iterator& rhs) : mHash(rhs.mHash),
         mIndex(rhs.mIndex)
        {
        }

        inline Iterator& operator=(const Iterator& rhs)
        {
            mHash = rhs.mHash;
            mIndex = rhs.mIndex;
            return *this;
        }
        inline bool operator==(const Iterator& rhs) const
        {
            return mHash == rhs.mHash && mIndex == rhs.mIndex;
        }
        inline bool operator!=(const Iterator& rhs) const { return !(*this == rhs); }
        inline Pair& operator*() { return *(mHash->element(mIndex)); }
        inline size_t index() const { return mIndex; }

        inline Iterator& operator++()
        {
            mIndex++;
            while (mIndex<mHash->allocated() && mHash->element(mIndex)==NULL)
            {
                mIndex++;
            }
            return (*this);
        }
        inline Iterator& operator++(int)
        {
            mIndex++;
            while (mIndex<mHash->allocated() && mHash->element(mIndex)==NULL)
            {
                mIndex++;
            }
            return (*this);
        }

        inline Iterator& operator--()
        {
            if(mIndex > 0)
            {
                mIndex--;
                while (mIndex>0 && mHash->element(mIndex)==NULL)
                {
                    mIndex--;
                }
            }
            return (*this);
        }
        inline Iterator& operator--(int)
        {
            if(mIndex > 0)
            {
                mIndex--;
                while (mIndex>0 && mHash->element(mIndex)==NULL)
                {
                    mIndex--;
                }
            }
            return (*this);
        }
    };

    typedef Iterator iterator;

    class ConstIterator
    {
    private:
        friend class Hash;
        Hash* mHash;
        size_t mIndex;
    public:

        inline ConstIterator(const Hash* ht=NULL, size_t index=0) : mHash(const_cast<Hash*>(ht)),
         mIndex(index)
        {
            if(mHash)
                if(index<mHash->allocated() && mHash->element(index)==0)
                    ++(*this);
        }

        inline ConstIterator(const ConstIterator& rhs) : mHash(rhs.mHash),
         mIndex(rhs.mIndex)
        {
        }

        inline ConstIterator& operator=(const ConstIterator& rhs)
        {
            mHash = rhs.mHash;
            mIndex = rhs.mIndex;
            return *this;
        }
        inline bool operator==(const ConstIterator& rhs) const
        {
            return mHash == rhs.mHash && mIndex == rhs.mIndex;
        }
        inline bool operator!=(const ConstIterator& rhs) const { return !(*this == rhs); }
        inline const Pair& operator*() { return *(mHash->element(mIndex)); }
        inline size_t index() const { return mIndex; }

        inline ConstIterator& operator++()
        {
            mIndex++;
            while (mIndex<mHash->allocated() && mHash->element(mIndex)==NULL)
            {
                mIndex++;
            }
            return (*this);
        }
        inline ConstIterator& operator++(int junk)
        {
            mIndex++;
            while (mIndex<mHash->allocated() && mHash->element(mIndex)==NULL)
            {
                mIndex++;
            }
            return (*this);
        }

        inline ConstIterator& operator--()
        {
            if(mIndex > 0)
            {
                mIndex--;
                while (mIndex>0 && mHash->element(mIndex)==NULL)
                {
                    mIndex--;
                }
            }
            return (*this);
        }
        inline ConstIterator& operator--(int)
        {
            if(mIndex > 0)
            {
                mIndex--;
                while (mIndex>0 && mHash->element(mIndex)==NULL)
                {
                    mIndex--;
                }
            }
            return (*this);
        }
    };

    typedef ConstIterator const_iterator;

    class DataProxy
    {
    private:
        Hash& mHash;
        const char* mKey;
        DataProxy();
    public:
        inline DataProxy(Hash& h, const char* k) : mHash(h), mKey(k) {}
        inline void operator=(const Data& value) { mHash.set(mKey,value); }
        inline operator Data()
        {
            Iterator i = mHash.find(mKey);

            if(i==mHash.end())
                throw LDK_INDEX_ERROR("cannot find key");
            return (*i).mData;
        }
    };

    Hash(size_t initialSize=100) : mArray(NULL),
     mAllocated(0),
     mFreeSlots(0),
     mSize(0)
    {
        size_t newAlloc = primeGreaterThan(initialSize);
        mArray = (Pair**) mPairPtrAlloc.allocate(newAlloc+1);
        mAllocated = newAlloc;
        mFreeSlots = mAllocated;
        memset(mArray, 0, newAlloc);
        mSize = 0;
    }
    //todo: store length of string in pair
    inline Hash(const Hash& rhs)
    {
        assign(rhs);
    }

    ~Hash() throw()
    {
        clear();
        mPairPtrAlloc.deallocate(mArray,mAllocated);
        mArray = NULL;
        mAllocated = 0;
        mFreeSlots = 0;
        mSize = 0;
    }

    inline Hash& operator=(const Hash& rhs)
    {
        size_t i;
        for(i=0;i<mAllocated;i++)
        {
            if(mArray[i])
            {
                mPairAlloc.destroy(mArray[i]);
                mPairAlloc.deallocate(mArray[i],1);
            }
        }
        assign(rhs);
        return *this;
    }

    ConstIterator find(const char* key) const
    {
        size_t hashValue = hash(key, mAllocated);
        size_t index = hashValue;

        const Pair* element = mArray[index];
        const Data* v = NULL;

        bool searchedAll = false;

        while (!searchedAll)
        {
            if (element!=0 && !strcmp(element->mKey, key))
            {
                v = &element->mData;
                break;
            }

            index = (index + cIncBy) % mAllocated;
            searchedAll = index==hashValue;
            element = mArray[index];
        }
        if(v == 0)
            return end();
        else
            return ConstIterator(this,index);
    }

    inline Iterator find(const char* key)
    {
        size_t hashValue = hash(key, mAllocated);
        size_t index = hashValue;

        Pair* element = mArray[index];
        Data* v=0;

        bool searchedAll = false;

        while (!searchedAll)
        {
            if (element!=0 && !strcmp(element->mKey, key))
            {
                v = &element->mData;
                break;
            }

            index = (index + cIncBy) % mAllocated;
            searchedAll = index==hashValue;
            element = mArray[index];
        }
        if(v == 0)
            return end();
        else
            return Iterator(this,index);
    }

    inline Pair* element(size_t idx)
    {
        if(idx >= mAllocated)
            throw LDK_INDEX_ERROR("Hash index out of range");
        return mArray[idx];

    }

    inline const Pair* element(size_t idx) const
    {
        if(idx >= mAllocated)
            throw LDK_INDEX_ERROR("Hash index out of range");
        return mArray[idx];
    }

    inline void set(const char* k, const Data& d)
    {
        Iterator i = find(k);
        if(i == end())
        {
            if (!insert(k, d))
                throw LDK_RUNTIME_ERROR("cannot find key");
        }
        else
            (*i).mData = d;
    }

    inline bool insert(const Pair& p) { return insert(p.mKey, p.mData); }

    inline bool insert(const char* key, const Data& data)
    {
        if(find(key) != end())
            return false;

        size_t newAlloc = newSize(mAllocated, mFreeSlots);
        bool allSearched=false;
        if(newAlloc > mAllocated)
            rehash(newAlloc);

        size_t hashValue = hash(key, mAllocated);
        size_t index = hashValue;
        Pair*  element = mArray[hashValue];

        while(element && !allSearched)
        {
            index = (index + cIncBy) % mAllocated;
            element = mArray[index];
            allSearched = index == hashValue;
        }

        if(allSearched)
            return false;
        else if(!element)
        {
            Pair *mem = mPairAlloc.allocate(1);
            mArray[index] = new(mem) Pair(key, data);
            mFreeSlots--;
            mSize++;
            return true;
        }
        return false;
    }

    inline Iterator erase(const char* key)
    {
        Iterator it = find(key);

        if(it == end())
            return it;
        size_t index = it.index();
        it++;
        mPairAlloc.destroy(mArray[index]);
        mPairAlloc.deallocate(mArray[index]);
        mArray[index] = NULL;
        mFreeSlots++;
        mSize--;
        return it;
    }

    inline Iterator erase(Iterator it)
    {
        assert(it.mHash == this);
        if(it == end())
            return it;
        size_t index = it.index();
        it++;
        mPairAlloc.destroy(mArray[index]);
        mPairAlloc.deallocate(mArray[index],1);
        mArray[index] = NULL;
        mFreeSlots++;
        mSize--;
        return it;
    }

    inline size_t size() const { return mSize; }

    inline size_t allocated() const { return mAllocated; }

    inline Iterator        begin() { return Iterator(this, 0); }
    inline ConstIterator   begin() const { return ConstIterator(this, 0); }
    inline Iterator        end() { return Iterator(this, mAllocated); }
    inline ConstIterator   end() const { return ConstIterator(this, mAllocated); }

    inline void clear()
    {
        Iterator i = begin();
        Iterator e = end();
        size_t idx;
        while(i != e)
        {
            idx = i.index();
            mPairAlloc.destroy(mArray[idx]);
            mPairAlloc.deallocate(mArray[idx],1);
            i++;
        }
        mFreeSlots = mAllocated;
        memset(mArray, 0, mAllocated);

    }

    inline DataProxy operator[](const char* k) { return DataProxy(*this, k); }
    inline const Data& operator[](const char* k) const
    {
        ConstIterator i = find(k);
        if(i == end())
            throw LDK_INDEX_ERROR("cannot find key");
        return (*i).mData;
    }
};

}//namespace LDK

#endif //__LDK_CSTRINGHASH_H__

---