1 /* 2 Bullet Continuous Collision Detection and Physics Library 3 Copyright (c) 2003-2006 Erwin Coumans http://continuousphysics.com/Bullet/ 4 5 This software is provided 'as-is', without any express or implied warranty. 6 In no event will the authors be held liable for any damages arising from the use of this software. 7 Permission is granted to anyone to use this software for any purpose, 8 including commercial applications, and to alter it and redistribute it freely, 9 subject to the following restrictions: 10 11 1. The origin of this software must not be misrepresented; you must not claim that you wrote the original software. If you use this software in a product, an acknowledgment in the product documentation would be appreciated but is not required. 12 2. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software. 13 3. This notice may not be removed or altered from any source distribution. 14 */ 15 16 #ifndef BT_HASHED_SIMPLE_PAIR_CACHE_H 17 #define BT_HASHED_SIMPLE_PAIR_CACHE_H 18 19 20 21 #include "LinearMath/btAlignedObjectArray.h" 22 23 const int BT_SIMPLE_NULL_PAIR=0xffffffff; 24 25 struct btSimplePair 26 { btSimplePairbtSimplePair27 btSimplePair(int indexA,int indexB) 28 :m_indexA(indexA), 29 m_indexB(indexB), 30 m_userPointer(0) 31 { 32 } 33 34 int m_indexA; 35 int m_indexB; 36 union 37 { 38 void* m_userPointer; 39 int m_userValue; 40 }; 41 }; 42 43 typedef btAlignedObjectArray<btSimplePair> btSimplePairArray; 44 45 46 47 extern int gOverlappingSimplePairs; 48 extern int gRemoveSimplePairs; 49 extern int gAddedSimplePairs; 50 extern int gFindSimplePairs; 51 52 53 54 55 class btHashedSimplePairCache 56 { 57 btSimplePairArray m_overlappingPairArray; 58 59 bool m_blockedForChanges; 60 61 62 protected: 63 64 btAlignedObjectArray<int> m_hashTable; 65 btAlignedObjectArray<int> m_next; 66 67 68 public: 69 btHashedSimplePairCache(); 70 virtual ~btHashedSimplePairCache(); 71 72 void removeAllPairs(); 73 74 virtual void* removeOverlappingPair(int indexA,int indexB); 75 76 // Add a pair and return the new pair. If the pair already exists, 77 // no new pair is created and the old one is returned. addOverlappingPair(int indexA,int indexB)78 virtual btSimplePair* addOverlappingPair(int indexA,int indexB) 79 { 80 gAddedSimplePairs++; 81 82 return internalAddPair(indexA,indexB); 83 } 84 85 getOverlappingPairArrayPtr()86 virtual btSimplePair* getOverlappingPairArrayPtr() 87 { 88 return &m_overlappingPairArray[0]; 89 } 90 getOverlappingPairArrayPtr()91 const btSimplePair* getOverlappingPairArrayPtr() const 92 { 93 return &m_overlappingPairArray[0]; 94 } 95 getOverlappingPairArray()96 btSimplePairArray& getOverlappingPairArray() 97 { 98 return m_overlappingPairArray; 99 } 100 getOverlappingPairArray()101 const btSimplePairArray& getOverlappingPairArray() const 102 { 103 return m_overlappingPairArray; 104 } 105 106 107 btSimplePair* findPair(int indexA,int indexB); 108 GetCount()109 int GetCount() const { return m_overlappingPairArray.size(); } 110 getNumOverlappingPairs()111 int getNumOverlappingPairs() const 112 { 113 return m_overlappingPairArray.size(); 114 } 115 private: 116 117 btSimplePair* internalAddPair(int indexA, int indexB); 118 119 void growTables(); 120 equalsPair(const btSimplePair & pair,int indexA,int indexB)121 SIMD_FORCE_INLINE bool equalsPair(const btSimplePair& pair, int indexA, int indexB) 122 { 123 return pair.m_indexA == indexA && pair.m_indexB == indexB; 124 } 125 126 127 getHash(unsigned int indexA,unsigned int indexB)128 SIMD_FORCE_INLINE unsigned int getHash(unsigned int indexA, unsigned int indexB) 129 { 130 int key = static_cast<int>(((unsigned int)indexA) | (((unsigned int)indexB) <<16)); 131 // Thomas Wang's hash 132 133 key += ~(key << 15); 134 key ^= (key >> 10); 135 key += (key << 3); 136 key ^= (key >> 6); 137 key += ~(key << 11); 138 key ^= (key >> 16); 139 return static_cast<unsigned int>(key); 140 } 141 142 143 144 145 internalFindPair(int proxyIdA,int proxyIdB,int hash)146 SIMD_FORCE_INLINE btSimplePair* internalFindPair(int proxyIdA , int proxyIdB, int hash) 147 { 148 149 int index = m_hashTable[hash]; 150 151 while( index != BT_SIMPLE_NULL_PAIR && equalsPair(m_overlappingPairArray[index], proxyIdA, proxyIdB) == false) 152 { 153 index = m_next[index]; 154 } 155 156 if ( index == BT_SIMPLE_NULL_PAIR ) 157 { 158 return NULL; 159 } 160 161 btAssert(index < m_overlappingPairArray.size()); 162 163 return &m_overlappingPairArray[index]; 164 } 165 166 167 }; 168 169 170 171 172 #endif //BT_HASHED_SIMPLE_PAIR_CACHE_H 173 174 175