btHashMap.h

Go to the documentation of this file.

#ifndef BT_HASH_MAP_H
#define BT_HASH_MAP_H

#include "btAlignedObjectArray.h"

struct btHashString
{
    const char* m_string;
    unsigned int    m_hash;

    SIMD_FORCE_INLINE   unsigned int getHash()const
    {
        return m_hash;
    }

    btHashString(const char* name)
        :m_string(name)
    {
        /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
        static const unsigned int  InitialFNV = 2166136261u;
        static const unsigned int FNVMultiple = 16777619u;

        /* Fowler / Noll / Vo (FNV) Hash */
        unsigned int hash = InitialFNV;
        
        for(int i = 0; m_string[i]; i++)
        {
            hash = hash ^ (m_string[i]);       /* xor  the low 8 bits */
            hash = hash * FNVMultiple;  /* multiply by the magic number */
        }
        m_hash = hash;
    }

    int portableStringCompare(const char* src,  const char* dst) const
    {
            int ret = 0 ;

            while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                    ++src, ++dst;

            if ( ret < 0 )
                    ret = -1 ;
            else if ( ret > 0 )
                    ret = 1 ;

            return( ret );
    }

    bool equals(const btHashString& other) const
    {
        return (m_string == other.m_string) ||
            (0==portableStringCompare(m_string,other.m_string));

    }

};

const int BT_HASH_NULL=0xffffffff;


class btHashInt
{
    int m_uid;
public:
    btHashInt(int uid)  :m_uid(uid)
    {
    }

    int getUid1() const
    {
        return m_uid;
    }

    void    setUid1(int uid)
    {
        m_uid = uid;
    }

    bool equals(const btHashInt& other) const
    {
        return getUid1() == other.getUid1();
    }
    //to our success
    SIMD_FORCE_INLINE   unsigned int getHash()const
    {
        int key = m_uid;
        // Thomas Wang's hash
        key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3); key ^=  (key >> 6); key += ~(key << 11);    key ^=  (key >> 16);
        return key;
    }
};



class btHashPtr
{

    union
    {
        const void* m_pointer;
        int m_hashValues[2];
    };

public:

    btHashPtr(const void* ptr)
        :m_pointer(ptr)
    {
    }

    const void* getPointer() const
    {
        return m_pointer;
    }

    bool equals(const btHashPtr& other) const
    {
        return getPointer() == other.getPointer();
    }

    //to our success
    SIMD_FORCE_INLINE   unsigned int getHash()const
    {
        const bool VOID_IS_8 = ((sizeof(void*)==8));
        
        int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0];
    
        // Thomas Wang's hash
        key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3); key ^=  (key >> 6); key += ~(key << 11);    key ^=  (key >> 16);
        return key;
    }

    
};


template <class Value>
class btHashKeyPtr
{
        int     m_uid;
public:

        btHashKeyPtr(int uid)    :m_uid(uid)
        {
        }

        int     getUid1() const
        {
                return m_uid;
        }

        bool equals(const btHashKeyPtr<Value>& other) const
        {
                return getUid1() == other.getUid1();
        }

        //to our success
        SIMD_FORCE_INLINE       unsigned int getHash()const
        {
                int key = m_uid;
                // Thomas Wang's hash
                key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3); key ^=  (key >> 6); key += ~(key << 11);    key ^=  (key >> 16);
                return key;
        }

        
};


template <class Value>
class btHashKey
{
    int m_uid;
public:

    btHashKey(int uid)  :m_uid(uid)
    {
    }

    int getUid1() const
    {
        return m_uid;
    }

    bool equals(const btHashKey<Value>& other) const
    {
        return getUid1() == other.getUid1();
    }
    //to our success
    SIMD_FORCE_INLINE   unsigned int getHash()const
    {
        int key = m_uid;
        // Thomas Wang's hash
        key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3); key ^=  (key >> 6); key += ~(key << 11);    key ^=  (key >> 16);
        return key;
    }
};


template <class Key, class Value>
class btHashMap
{

protected:
    btAlignedObjectArray<int>       m_hashTable;
    btAlignedObjectArray<int>       m_next;
    
    btAlignedObjectArray<Value>     m_valueArray;
    btAlignedObjectArray<Key>       m_keyArray;

    void    growTables(const Key& /*key*/)
    {
        int newCapacity = m_valueArray.capacity();

        if (m_hashTable.size() < newCapacity)
        {
            //grow hashtable and next table
            int curHashtableSize = m_hashTable.size();

            m_hashTable.resize(newCapacity);
            m_next.resize(newCapacity);

            int i;

            for (i= 0; i < newCapacity; ++i)
            {
                m_hashTable[i] = BT_HASH_NULL;
            }
            for (i = 0; i < newCapacity; ++i)
            {
                m_next[i] = BT_HASH_NULL;
            }

            for(i=0;i<curHashtableSize;i++)
            {
                //const Value& value = m_valueArray[i];
                //const Key& key = m_keyArray[i];

                int hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity()-1);  // New hash value with new mask
                m_next[i] = m_hashTable[hashValue];
                m_hashTable[hashValue] = i;
            }


        }
    }

    public:

    void insert(const Key& key, const Value& value) {
        int hash = key.getHash() & (m_valueArray.capacity()-1);

        //replace value if the key is already there
        int index = findIndex(key);
        if (index != BT_HASH_NULL)
        {
            m_valueArray[index]=value;
            return;
        }

        int count = m_valueArray.size();
        int oldCapacity = m_valueArray.capacity();
        m_valueArray.push_back(value);
        m_keyArray.push_back(key);

        int newCapacity = m_valueArray.capacity();
        if (oldCapacity < newCapacity)
        {
            growTables(key);
            //hash with new capacity
            hash = key.getHash() & (m_valueArray.capacity()-1);
        }
        m_next[count] = m_hashTable[hash];
        m_hashTable[hash] = count;
    }

    void remove(const Key& key) {

        int hash = key.getHash() & (m_valueArray.capacity()-1);

        int pairIndex = findIndex(key);
        
        if (pairIndex ==BT_HASH_NULL)
        {
            return;
        }

        // Remove the pair from the hash table.
        int index = m_hashTable[hash];
        btAssert(index != BT_HASH_NULL);

        int previous = BT_HASH_NULL;
        while (index != pairIndex)
        {
            previous = index;
            index = m_next[index];
        }

        if (previous != BT_HASH_NULL)
        {
            btAssert(m_next[previous] == pairIndex);
            m_next[previous] = m_next[pairIndex];
        }
        else
        {
            m_hashTable[hash] = m_next[pairIndex];
        }

        // We now move the last pair into spot of the
        // pair being removed. We need to fix the hash
        // table indices to support the move.

        int lastPairIndex = m_valueArray.size() - 1;

        // If the removed pair is the last pair, we are done.
        if (lastPairIndex == pairIndex)
        {
            m_valueArray.pop_back();
            m_keyArray.pop_back();
            return;
        }

        // Remove the last pair from the hash table.
        int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1);

        index = m_hashTable[lastHash];
        btAssert(index != BT_HASH_NULL);

        previous = BT_HASH_NULL;
        while (index != lastPairIndex)
        {
            previous = index;
            index = m_next[index];
        }

        if (previous != BT_HASH_NULL)
        {
            btAssert(m_next[previous] == lastPairIndex);
            m_next[previous] = m_next[lastPairIndex];
        }
        else
        {
            m_hashTable[lastHash] = m_next[lastPairIndex];
        }

        // Copy the last pair into the remove pair's spot.
        m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
        m_keyArray[pairIndex] = m_keyArray[lastPairIndex];

        // Insert the last pair into the hash table
        m_next[pairIndex] = m_hashTable[lastHash];
        m_hashTable[lastHash] = pairIndex;

        m_valueArray.pop_back();
        m_keyArray.pop_back();

    }


    int size() const
    {
        return m_valueArray.size();
    }

    const Value* getAtIndex(int index) const
    {
        btAssert(index < m_valueArray.size());

        return &m_valueArray[index];
    }

    Value* getAtIndex(int index)
    {
        btAssert(index < m_valueArray.size());

        return &m_valueArray[index];
    }

    Value* operator[](const Key& key) {
        return find(key);
    }

    const Value*    find(const Key& key) const
    {
        int index = findIndex(key);
        if (index == BT_HASH_NULL)
        {
            return NULL;
        }
        return &m_valueArray[index];
    }

    Value*  find(const Key& key)
    {
        int index = findIndex(key);
        if (index == BT_HASH_NULL)
        {
            return NULL;
        }
        return &m_valueArray[index];
    }


    int findIndex(const Key& key) const
    {
        unsigned int hash = key.getHash() & (m_valueArray.capacity()-1);

        if (hash >= (unsigned int)m_hashTable.size())
        {
            return BT_HASH_NULL;
        }

        int index = m_hashTable[hash];
        while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
        {
            index = m_next[index];
        }
        return index;
    }

    void    clear()
    {
        m_hashTable.clear();
        m_next.clear();
        m_valueArray.clear();
        m_keyArray.clear();
    }

};

#endif //BT_HASH_MAP_H