Logo Search packages:      
Sourcecode: blender version File versions

btHashMap.h

#ifndef BT_HASH_MAP_H
#define BT_HASH_MAP_H

#include "btAlignedObjectArray.h"

const int BT_HASH_NULL=0xffffffff;

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

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

      int   getUid() const
      {
            return m_uid;
      }

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

      btHashKey   getKey(const Value& value) const
      {
            return btHashKey(value.getUid());
      }
};


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

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

      int   getUid() const
      {
            return m_uid;
      }

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

      btHashKeyPtr      getKey(const Value& value) const
      {
            return btHashKeyPtr(value->getUid());
      }
};

///The btHashMap template class implements a generic and lightweight hashmap.
///A basic sample of how to use btHashMap is located in Demos\BasicDemo\main.cpp
template <class Key, class Value>
00084 class btHashMap
{

      btAlignedObjectArray<int>           m_hashTable;
      btAlignedObjectArray<int>           m_next;
      btAlignedObjectArray<Value>         m_valueArray;



      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];

                        int   hashValue = key.getKey(value).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);
            //don't add it if it is already there
            if (find(key))
            {
                  return;
            }
            int count = m_valueArray.size();
            int oldCapacity = m_valueArray.capacity();
            m_valueArray.push_back(value);
            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();
                  return;
            }

            // Remove the last pair from the hash table.
            const Value* lastValue = &m_valueArray[lastPairIndex];
            int lastHash = key.getKey(*lastValue).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];

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

            m_valueArray.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
      {
            int hash = key.getHash() & (m_valueArray.capacity()-1);

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

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

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

};

#endif //BT_HASH_MAP_H

Generated by  Doxygen 1.6.0   Back to index