Back to index

supertuxkart  0.5+dfsg1
btHashMap.h
Go to the documentation of this file.
00001 #ifndef BT_HASH_MAP_H
00002 #define BT_HASH_MAP_H
00003 
00004 #include "btAlignedObjectArray.h"
00005 
00006 const int BT_HASH_NULL=0xffffffff;
00007 
00008 template <class Value>
00009 class btHashKey
00010 {
00011        int    m_uid;
00012 public:
00013 
00014        btHashKey(int uid)
00015               :m_uid(uid)
00016        {
00017        }
00018 
00019        int    getUid() const
00020        {
00021               return m_uid;
00022        }
00023 
00024        //to our success
00025        SIMD_FORCE_INLINE    unsigned int getHash()const
00026        {
00027               int key = m_uid;
00028               // Thomas Wang's hash
00029               key += ~(key << 15);
00030               key ^=  (key >> 10);
00031               key +=  (key << 3);
00032               key ^=  (key >> 6);
00033               key += ~(key << 11);
00034               key ^=  (key >> 16);
00035               return key;
00036        }
00037 
00038        btHashKey     getKey(const Value& value) const
00039        {
00040               return btHashKey(value.getUid());
00041        }
00042 };
00043 
00044 
00045 template <class Value>
00046 class btHashKeyPtr
00047 {
00048        int    m_uid;
00049 public:
00050 
00051        btHashKeyPtr(int uid)
00052               :m_uid(uid)
00053        {
00054        }
00055 
00056        int    getUid() const
00057        {
00058               return m_uid;
00059        }
00060 
00061        //to our success
00062        SIMD_FORCE_INLINE    unsigned int getHash()const
00063        {
00064               int key = m_uid;
00065               // Thomas Wang's hash
00066               key += ~(key << 15);
00067               key ^=  (key >> 10);
00068               key +=  (key << 3);
00069               key ^=  (key >> 6);
00070               key += ~(key << 11);
00071               key ^=  (key >> 16);
00072               return key;
00073        }
00074 
00075        btHashKeyPtr  getKey(const Value& value) const
00076        {
00077               return btHashKeyPtr(value->getUid());
00078        }
00079 };
00080 
00081 template <class Key, class Value>
00082 class btHashMap
00083 {
00084 
00085        btAlignedObjectArray<int>          m_hashTable;
00086        btAlignedObjectArray<int>          m_next;
00087        btAlignedObjectArray<Value>        m_valueArray;
00088 
00089 
00090 
00091        void   growTables(const Key& key)
00092        {
00093               int newCapacity = m_valueArray.capacity();
00094 
00095               if (m_hashTable.size() < newCapacity)
00096               {
00097                      //grow hashtable and next table
00098                      int curHashtableSize = m_hashTable.size();
00099 
00100                      m_hashTable.resize(newCapacity);
00101                      m_next.resize(newCapacity);
00102 
00103                      int i;
00104 
00105                      for (i= 0; i < newCapacity; ++i)
00106                      {
00107                             m_hashTable[i] = BT_HASH_NULL;
00108                      }
00109                      for (i = 0; i < newCapacity; ++i)
00110                      {
00111                             m_next[i] = BT_HASH_NULL;
00112                      }
00113 
00114                      for(i=0;i<curHashtableSize;i++)
00115                      {
00116                             const Value& value = m_valueArray[i];
00117 
00118                             int    hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1);       // New hash value with new mask
00119                             m_next[i] = m_hashTable[hashValue];
00120                             m_hashTable[hashValue] = i;
00121                      }
00122 
00123 
00124               }
00125        }
00126 
00127        public:
00128 
00129        void insert(const Key& key, const Value& value) {
00130               int hash = key.getHash() & (m_valueArray.capacity()-1);
00131               //don't add it if it is already there
00132               if (find(key))
00133               {
00134                      return;
00135               }
00136               int count = m_valueArray.size();
00137               int oldCapacity = m_valueArray.capacity();
00138               m_valueArray.push_back(value);
00139               int newCapacity = m_valueArray.capacity();
00140               if (oldCapacity < newCapacity)
00141               {
00142                      growTables(key);
00143                      //hash with new capacity
00144                      hash = key.getHash() & (m_valueArray.capacity()-1);
00145               }
00146               m_next[count] = m_hashTable[hash];
00147               m_hashTable[hash] = count;
00148        }
00149 
00150        void remove(const Key& key) {
00151 
00152               int hash = key.getHash() & (m_valueArray.capacity()-1);
00153 
00154               int pairIndex = findIndex(key);
00155               
00156               if (pairIndex ==BT_HASH_NULL)
00157               {
00158                      return;
00159               }
00160 
00161               // Remove the pair from the hash table.
00162               int index = m_hashTable[hash];
00163               btAssert(index != BT_HASH_NULL);
00164 
00165               int previous = BT_HASH_NULL;
00166               while (index != pairIndex)
00167               {
00168                      previous = index;
00169                      index = m_next[index];
00170               }
00171 
00172               if (previous != BT_HASH_NULL)
00173               {
00174                      btAssert(m_next[previous] == pairIndex);
00175                      m_next[previous] = m_next[pairIndex];
00176               }
00177               else
00178               {
00179                      m_hashTable[hash] = m_next[pairIndex];
00180               }
00181 
00182               // We now move the last pair into spot of the
00183               // pair being removed. We need to fix the hash
00184               // table indices to support the move.
00185 
00186               int lastPairIndex = m_valueArray.size() - 1;
00187 
00188               // If the removed pair is the last pair, we are done.
00189               if (lastPairIndex == pairIndex)
00190               {
00191                      m_valueArray.pop_back();
00192                      return;
00193               }
00194 
00195               // Remove the last pair from the hash table.
00196               const Value* lastValue = &m_valueArray[lastPairIndex];
00197               int lastHash = key.getKey(*lastValue).getHash() & (m_valueArray.capacity()-1);
00198 
00199               index = m_hashTable[lastHash];
00200               btAssert(index != BT_HASH_NULL);
00201 
00202               previous = BT_HASH_NULL;
00203               while (index != lastPairIndex)
00204               {
00205                      previous = index;
00206                      index = m_next[index];
00207               }
00208 
00209               if (previous != BT_HASH_NULL)
00210               {
00211                      btAssert(m_next[previous] == lastPairIndex);
00212                      m_next[previous] = m_next[lastPairIndex];
00213               }
00214               else
00215               {
00216                      m_hashTable[lastHash] = m_next[lastPairIndex];
00217               }
00218 
00219               // Copy the last pair into the remove pair's spot.
00220               m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
00221 
00222               // Insert the last pair into the hash table
00223               m_next[pairIndex] = m_hashTable[lastHash];
00224               m_hashTable[lastHash] = pairIndex;
00225 
00226               m_valueArray.pop_back();
00227 
00228        }
00229 
00230 
00231        int size() const
00232        {
00233               return m_valueArray.size();
00234        }
00235 
00236        const Value* getAtIndex(int index) const
00237        {
00238               btAssert(index < m_valueArray.size());
00239 
00240               return &m_valueArray[index];
00241        }
00242 
00243        Value* getAtIndex(int index)
00244        {
00245               btAssert(index < m_valueArray.size());
00246 
00247               return &m_valueArray[index];
00248        }
00249 
00250        Value* operator[](const Key& key) {
00251               return find(key);
00252        }
00253 
00254        const Value*  find(const Key& key) const
00255        {
00256               int index = findIndex(key);
00257               if (index == BT_HASH_NULL)
00258               {
00259                      return NULL;
00260               }
00261               return &m_valueArray[index];
00262        }
00263 
00264        Value* find(const Key& key)
00265        {
00266               int index = findIndex(key);
00267               if (index == BT_HASH_NULL)
00268               {
00269                      return NULL;
00270               }
00271               return &m_valueArray[index];
00272        }
00273 
00274 
00275        int    findIndex(const Key& key) const
00276        {
00277               int hash = key.getHash() & (m_valueArray.capacity()-1);
00278 
00279               if (hash >= m_hashTable.size())
00280               {
00281                      return BT_HASH_NULL;
00282               }
00283 
00284               int index = m_hashTable[hash];
00285               while ((index != BT_HASH_NULL) && (key.getUid() == key.getKey(m_valueArray[index]).getUid()) == false)
00286               {
00287                      index = m_next[index];
00288               }
00289               return index;
00290        }
00291 
00292        void   clear()
00293        {
00294               m_hashTable.clear();
00295               m_next.clear();
00296               m_valueArray.clear();
00297        }
00298 
00299 };
00300 
00301 #endif //BT_HASH_MAP_H