Back to index

supertuxkart  0.5+dfsg1
Public Member Functions | Private Member Functions | Private Attributes
btHashMap< Key, Value > Class Template Reference

#include <btHashMap.h>

Collaboration diagram for btHashMap< Key, Value >:
Collaboration graph
[legend]

List of all members.

Public Member Functions

void insert (const Key &key, const Value &value)
void remove (const Key &key)
int size () const
const Value * getAtIndex (int index) const
Value * getAtIndex (int index)
Value * operator[] (const Key &key)
const Value * find (const Key &key) const
Value * find (const Key &key)
int findIndex (const Key &key) const
void clear ()

Private Member Functions

void growTables (const Key &key)

Private Attributes

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

Detailed Description

template<class Key, class Value>
class btHashMap< Key, Value >

Definition at line 82 of file btHashMap.h.


Member Function Documentation

template<class Key , class Value >
void btHashMap< Key, Value >::clear ( ) [inline]

Definition at line 292 of file btHashMap.h.

Here is the call graph for this function:

template<class Key , class Value >
const Value* btHashMap< Key, Value >::find ( const Key &  key) const [inline]

Definition at line 254 of file btHashMap.h.

       {
              int index = findIndex(key);
              if (index == BT_HASH_NULL)
              {
                     return NULL;
              }
              return &m_valueArray[index];
       }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class Key , class Value >
Value* btHashMap< Key, Value >::find ( const Key &  key) [inline]

Definition at line 264 of file btHashMap.h.

       {
              int index = findIndex(key);
              if (index == BT_HASH_NULL)
              {
                     return NULL;
              }
              return &m_valueArray[index];
       }

Here is the call graph for this function:

template<class Key , class Value >
int btHashMap< Key, Value >::findIndex ( const Key &  key) const [inline]

Definition at line 275 of file btHashMap.h.

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

Here is the call graph for this function:

Here is the caller graph for this function:

template<class Key , class Value >
const Value* btHashMap< Key, Value >::getAtIndex ( int  index) const [inline]

Definition at line 236 of file btHashMap.h.

       {
              btAssert(index < m_valueArray.size());

              return &m_valueArray[index];
       }

Here is the call graph for this function:

template<class Key , class Value >
Value* btHashMap< Key, Value >::getAtIndex ( int  index) [inline]

Definition at line 243 of file btHashMap.h.

       {
              btAssert(index < m_valueArray.size());

              return &m_valueArray[index];
       }

Here is the call graph for this function:

template<class Key , class Value >
void btHashMap< Key, Value >::growTables ( const Key &  key) [inline, private]

Definition at line 91 of file btHashMap.h.

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


              }
       }

Here is the call graph for this function:

Here is the caller graph for this function:

template<class Key , class Value >
void btHashMap< Key, Value >::insert ( const Key &  key,
const Value &  value 
) [inline]

Definition at line 129 of file btHashMap.h.

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

Here is the call graph for this function:

template<class Key , class Value >
Value* btHashMap< Key, Value >::operator[] ( const Key &  key) [inline]

Definition at line 250 of file btHashMap.h.

                                         {
              return find(key);
       }

Here is the call graph for this function:

template<class Key , class Value >
void btHashMap< Key, Value >::remove ( const Key &  key) [inline]

Definition at line 150 of file btHashMap.h.

                                   {

              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();

       }

Here is the call graph for this function:

template<class Key , class Value >
int btHashMap< Key, Value >::size ( ) const [inline]

Definition at line 231 of file btHashMap.h.

       {
              return m_valueArray.size();
       }

Here is the call graph for this function:


Member Data Documentation

template<class Key , class Value >
btAlignedObjectArray<int> btHashMap< Key, Value >::m_hashTable [private]

Definition at line 85 of file btHashMap.h.

template<class Key , class Value >
btAlignedObjectArray<int> btHashMap< Key, Value >::m_next [private]

Definition at line 86 of file btHashMap.h.

template<class Key , class Value >
btAlignedObjectArray<Value> btHashMap< Key, Value >::m_valueArray [private]

Definition at line 87 of file btHashMap.h.


The documentation for this class was generated from the following file: