Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

Ignore:
Timestamp:
Apr 21, 2011, 6:58:23 PM (14 years ago)
Author:
rgrieder
Message:

Merged revisions 7978 - 8096 from kicklib to kicklib2.

Location:
code/branches/kicklib2
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • code/branches/kicklib2

  • code/branches/kicklib2/src/external/bullet/LinearMath/btHashMap.h

    r5781 r8284  
    44#include "btAlignedObjectArray.h"
    55
     6///very basic hashable string implementation, compatible with btHashMap
     7struct btHashString
     8{
     9        const char* m_string;
     10        unsigned int    m_hash;
     11
     12        SIMD_FORCE_INLINE       unsigned int getHash()const
     13        {
     14                return m_hash;
     15        }
     16
     17        btHashString(const char* name)
     18                :m_string(name)
     19        {
     20                /* magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/ */
     21                static const unsigned int  InitialFNV = 2166136261u;
     22                static const unsigned int FNVMultiple = 16777619u;
     23
     24                /* Fowler / Noll / Vo (FNV) Hash */
     25                unsigned int hash = InitialFNV;
     26               
     27                for(int i = 0; m_string[i]; i++)
     28                {
     29                        hash = hash ^ (m_string[i]);       /* xor  the low 8 bits */
     30                        hash = hash * FNVMultiple;  /* multiply by the magic number */
     31                }
     32                m_hash = hash;
     33        }
     34
     35        int portableStringCompare(const char* src,      const char* dst) const
     36        {
     37                        int ret = 0 ;
     38
     39                        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
     40                                        ++src, ++dst;
     41
     42                        if ( ret < 0 )
     43                                        ret = -1 ;
     44                        else if ( ret > 0 )
     45                                        ret = 1 ;
     46
     47                        return( ret );
     48        }
     49
     50        bool equals(const btHashString& other) const
     51        {
     52                return (m_string == other.m_string) ||
     53                        (0==portableStringCompare(m_string,other.m_string));
     54
     55        }
     56
     57};
     58
    659const int BT_HASH_NULL=0xffffffff;
     60
     61
     62class btHashInt
     63{
     64        int     m_uid;
     65public:
     66        btHashInt(int uid)      :m_uid(uid)
     67        {
     68        }
     69
     70        int     getUid1() const
     71        {
     72                return m_uid;
     73        }
     74
     75        void    setUid1(int uid)
     76        {
     77                m_uid = uid;
     78        }
     79
     80        bool equals(const btHashInt& other) const
     81        {
     82                return getUid1() == other.getUid1();
     83        }
     84        //to our success
     85        SIMD_FORCE_INLINE       unsigned int getHash()const
     86        {
     87                int key = m_uid;
     88                // Thomas Wang's hash
     89                key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3);     key ^=  (key >> 6);     key += ~(key << 11);    key ^=  (key >> 16);
     90                return key;
     91        }
     92};
     93
     94
     95
     96class btHashPtr
     97{
     98
     99        union
     100        {
     101                const void*     m_pointer;
     102                int     m_hashValues[2];
     103        };
     104
     105public:
     106
     107        btHashPtr(const void* ptr)
     108                :m_pointer(ptr)
     109        {
     110        }
     111
     112        const void*     getPointer() const
     113        {
     114                return m_pointer;
     115        }
     116
     117        bool equals(const btHashPtr& other) const
     118        {
     119                return getPointer() == other.getPointer();
     120        }
     121
     122        //to our success
     123        SIMD_FORCE_INLINE       unsigned int getHash()const
     124        {
     125                const bool VOID_IS_8 = ((sizeof(void*)==8));
     126               
     127                int key = VOID_IS_8? m_hashValues[0]+m_hashValues[1] : m_hashValues[0];
     128       
     129                // Thomas Wang's hash
     130                key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3);     key ^=  (key >> 6);     key += ~(key << 11);    key ^=  (key >> 16);
     131                return key;
     132        }
     133
     134       
     135};
     136
     137
     138template <class Value>
     139class btHashKeyPtr
     140{
     141        int     m_uid;
     142public:
     143
     144        btHashKeyPtr(int uid)    :m_uid(uid)
     145        {
     146        }
     147
     148        int     getUid1() const
     149        {
     150                return m_uid;
     151        }
     152
     153        bool equals(const btHashKeyPtr<Value>& other) const
     154        {
     155                return getUid1() == other.getUid1();
     156        }
     157
     158        //to our success
     159        SIMD_FORCE_INLINE       unsigned int getHash()const
     160        {
     161                int key = m_uid;
     162                // Thomas Wang's hash
     163                key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3);     key ^=  (key >> 6);     key += ~(key << 11);    key ^=  (key >> 16);
     164                return key;
     165        }
     166
     167       
     168};
     169
    7170
    8171template <class Value>
    … …  
    12175public:
    13176
    14         btHashKey(int uid)
    15                 :m_uid(uid)
    16         {
    17         }
    18 
    19         int     getUid() const
     177        btHashKey(int uid)      :m_uid(uid)
     178        {
     179        }
     180
     181        int     getUid1() const
    20182        {
    21183                return m_uid;
    22184        }
    23185
     186        bool equals(const btHashKey<Value>& other) const
     187        {
     188                return getUid1() == other.getUid1();
     189        }
    24190        //to our success
    25191        SIMD_FORCE_INLINE       unsigned int getHash()const
    … …  
    27193                int key = m_uid;
    28194                // Thomas Wang's hash
    29                 key += ~(key << 15);
    30                 key ^=  (key >> 10);
    31                 key +=  (key << 3);
    32                 key ^=  (key >> 6);
    33                 key += ~(key << 11);
    34                 key ^=  (key >> 16);
     195                key += ~(key << 15);    key ^=  (key >> 10);    key +=  (key << 3);     key ^=  (key >> 6);     key += ~(key << 11);    key ^=  (key >> 16);
    35196                return key;
    36197        }
    37 
    38         btHashKey       getKey(const Value& value) const
    39         {
    40                 return btHashKey(value.getUid());
    41         }
    42 };
    43 
    44 
    45 template <class Value>
    46 class btHashKeyPtr
    47 {
    48         int     m_uid;
    49 public:
    50 
    51         btHashKeyPtr(int uid)
    52                 :m_uid(uid)
    53         {
    54         }
    55 
    56         int     getUid() const
    57         {
    58                 return m_uid;
    59         }
    60 
    61         //to our success
    62         SIMD_FORCE_INLINE       unsigned int getHash()const
    63         {
    64                 int key = m_uid;
    65                 // Thomas Wang's hash
    66                 key += ~(key << 15);
    67                 key ^=  (key >> 10);
    68                 key +=  (key << 3);
    69                 key ^=  (key >> 6);
    70                 key += ~(key << 11);
    71                 key ^=  (key >> 16);
    72                 return key;
    73         }
    74 
    75         btHashKeyPtr    getKey(const Value& value) const
    76         {
    77                 return btHashKeyPtr(value->getUid());
    78         }
    79 };
     198};
     199
    80200
    81201///The btHashMap template class implements a generic and lightweight hashmap.
    … …  
    85205{
    86206
     207protected:
    87208        btAlignedObjectArray<int>               m_hashTable;
    88209        btAlignedObjectArray<int>               m_next;
     210       
    89211        btAlignedObjectArray<Value>             m_valueArray;
    90 
    91 
    92 
    93         void    growTables(const Key& key)
     212        btAlignedObjectArray<Key>               m_keyArray;
     213
     214        void    growTables(const Key& /*key*/)
    94215        {
    95216                int newCapacity = m_valueArray.capacity();
    … …  
    116237                        for(i=0;i<curHashtableSize;i++)
    117238                        {
    118                                 const Value& value = m_valueArray[i];
    119 
    120                                 int     hashValue = key.getKey(value).getHash() & (m_valueArray.capacity()-1);  // New hash value with new mask
     239                                //const Value& value = m_valueArray[i];
     240                                //const Key& key = m_keyArray[i];
     241
     242                                int     hashValue = m_keyArray[i].getHash() & (m_valueArray.capacity()-1);      // New hash value with new mask
    121243                                m_next[i] = m_hashTable[hashValue];
    122244                                m_hashTable[hashValue] = i;
    … …  
    131253        void insert(const Key& key, const Value& value) {
    132254                int hash = key.getHash() & (m_valueArray.capacity()-1);
    133                 //don't add it if it is already there
    134                 if (find(key))
    135                 {
     255
     256                //replace value if the key is already there
     257                int index = findIndex(key);
     258                if (index != BT_HASH_NULL)
     259                {
     260                        m_valueArray[index]=value;
    136261                        return;
    137262                }
     263
    138264                int count = m_valueArray.size();
    139265                int oldCapacity = m_valueArray.capacity();
    140266                m_valueArray.push_back(value);
     267                m_keyArray.push_back(key);
     268
    141269                int newCapacity = m_valueArray.capacity();
    142270                if (oldCapacity < newCapacity)
    … …  
    192320                {
    193321                        m_valueArray.pop_back();
     322                        m_keyArray.pop_back();
    194323                        return;
    195324                }
    196325
    197326                // Remove the last pair from the hash table.
    198                 const Value* lastValue = &m_valueArray[lastPairIndex];
    199                 int lastHash = key.getKey(*lastValue).getHash() & (m_valueArray.capacity()-1);
     327                int lastHash = m_keyArray[lastPairIndex].getHash() & (m_valueArray.capacity()-1);
    200328
    201329                index = m_hashTable[lastHash];
    … …  
    221349                // Copy the last pair into the remove pair's spot.
    222350                m_valueArray[pairIndex] = m_valueArray[lastPairIndex];
     351                m_keyArray[pairIndex] = m_keyArray[lastPairIndex];
    223352
    224353                // Insert the last pair into the hash table
    … …  
    227356
    228357                m_valueArray.pop_back();
     358                m_keyArray.pop_back();
    229359
    230360        }
    … …  
    277407        int     findIndex(const Key& key) const
    278408        {
    279                 int hash = key.getHash() & (m_valueArray.capacity()-1);
    280 
    281                 if (hash >= m_hashTable.size())
     409                unsigned int hash = key.getHash() & (m_valueArray.capacity()-1);
     410
     411                if (hash >= (unsigned int)m_hashTable.size())
    282412                {
    283413                        return BT_HASH_NULL;
    … …  
    285415
    286416                int index = m_hashTable[hash];
    287                 while ((index != BT_HASH_NULL) && (key.getUid() == key.getKey(m_valueArray[index]).getUid()) == false)
     417                while ((index != BT_HASH_NULL) && key.equals(m_keyArray[index]) == false)
    288418                {
    289419                        index = m_next[index];
    … …  
    297427                m_next.clear();
    298428                m_valueArray.clear();
     429                m_keyArray.clear();
    299430        }
    300431
Note: See TracChangeset for help on using the changeset viewer.