Hash.h

Go to the documentation of this file.

#ifndef __LDK_HASH_HH__
#define __LDK_HASH_HH__

//   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/Memory.h"
#include "LDK/String.h"
#include <string.h>


namespace LDK
{

//Table of prime numbers 2^n+a, 2<=n<=30.
//from st.c in the ruby source
extern const LDK_API size_t PrimeConsts[];


template <class Key> class Hasher;


template <>
class LDK_API Hasher<int>
{
public:
    size_t operator()(int key, size_t size)
    {
        return (static_cast<size_t>(key)) % size;
    }
};

template <>
class LDK_API Hasher<int64>
{
public:
    size_t operator()(int64 key, size_t size)
    {
        return (static_cast<size_t>(key % size));
    }
};

template <>
class LDK_API Hasher<const char*>
{
public:
    size_t operator()(const char* key, size_t size)
    {
        size_t h = 0;
        size_t g;
        while(*key)
        {
            h = (h << 4) + *key++;

            if((g = h & 0xF0000000)!=0)
                h ^= g >> 24;
            h &= ~g;
        }
        return (h % size);
    }
};

template<>
class LDK_API Hasher<std::string>
{
public:
    size_t operator()(const std::string& key, size_t size)
    {
        size_t h = 0;
        size_t g;
        const char* k = key.c_str();
        while(*k)
        {
            h = (h << 4) + *k++;

            if((g = h & 0xF0000000)!=0)
                h ^= g >> 24;
            h &= ~g;
        }
        return (h % size);
    }
};

template<>
class LDK_API Hasher<String>
{
public:
    size_t operator()(const String& key, size_t size)
    {
        size_t h = 0;
        size_t g;
        const char* k = key.c_str();
        while(*k)
        {
            h = (h << 4) + *k++;

            if((g = h & 0xF0000000)!=0)
                h ^= g >> 24;
            h &= ~g;
        }
        return (h % size);
    }
};

template
<
    class Key,
    class Data,
    template <class> class Alloc=Allocator
>
class Hash : public Object
{
public:
    class Pair
    {
    private:
        void operator=(const Pair& rhs) {}
    public:
        Key mKey;
        Data mData;
        inline Pair(const Key& k, const Data& d) : mKey(k), mData(d) {}
        inline Pair(const Pair& rhs) : mKey(rhs.mKey), mData(rhs.mData) {}
    };
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 Key& k, size_t allocated) const
    {
        Hasher<Key> 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, mAllocated);
        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 Key& mKey;
        DataProxy();
    public:
        inline DataProxy(Hash& h, const Key&k) : mHash(h), mKey(k) {} //does this need to be public???
        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;
        }
    };



    inline 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;
    }

    inline Hash(const Hash& rhs)
    {
        assign(rhs);
    }

    inline ~Hash() throw()
    {
        clear();
        mPairPtrAlloc.deallocate(((Pair*)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 Key& 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 && 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 Key& 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 && 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 Key& k, const Data& d)
    {
        Iterator i = find(k);
        if(i == end())
        {
            if(!insert(k, d)) //slightly slow because it calls find again
                throw LDK_INDEX_ERROR("cannot find key");
        }
        else
            (*i).mData = d;
    }

    bool insert(const Key& 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 bool insert(const Pair& p) { return insert(p.mKey, p.mData); }

    inline Iterator erase(const Key& 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 Key& k) { return DataProxy(*this, k); }

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

}//namespace LDK

#include "LDK/CStringHash.h"

#endif //__LDK_HASH_HH__

---