Bullet Collision Detection & Physics Library
btHashedSimplePairCache.cpp
Go to the documentation of this file.
1/*
2Bullet Continuous Collision Detection and Physics Library
3Copyright (c) 2003-2006 Erwin Coumans https://bulletphysics.org
4
5This software is provided 'as-is', without any express or implied warranty.
6In no event will the authors be held liable for any damages arising from the use of this software.
7Permission is granted to anyone to use this software for any purpose,
8including commercial applications, and to alter it and redistribute it freely,
9subject to the following restrictions:
10
111. 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.
122. Altered source versions must be plainly marked as such, and must not be misrepresented as being the original software.
133. This notice may not be removed or altered from any source distribution.
14*/
15
17
18#include <stdio.h>
19
20#ifdef BT_DEBUG_COLLISION_PAIRS
22int gRemoveSimplePairs = 0;
23int gAddedSimplePairs = 0;
24int gFindSimplePairs = 0;
25#endif //BT_DEBUG_COLLISION_PAIRS
26
28{
31 growTables();
32}
33
35{
36}
37
39{
42 m_next.clear();
43
46 growTables();
47}
48
50{
51#ifdef BT_DEBUG_COLLISION_PAIRS
53#endif
54
55 /*if (indexA > indexB)
56 btSwap(indexA, indexB);*/
57
58 int hash = static_cast<int>(getHash(static_cast<unsigned int>(indexA), static_cast<unsigned int>(indexB)) & (m_overlappingPairArray.capacity() - 1));
59
60 if (hash >= m_hashTable.size())
61 {
62 return NULL;
63 }
64
65 int index = m_hashTable[hash];
66 while (index != BT_SIMPLE_NULL_PAIR && equalsPair(m_overlappingPairArray[index], indexA, indexB) == false)
67 {
68 index = m_next[index];
69 }
70
71 if (index == BT_SIMPLE_NULL_PAIR)
72 {
73 return NULL;
74 }
75
77
78 return &m_overlappingPairArray[index];
79}
80
81//#include <stdio.h>
82
84{
86
88 {
89 //grow hashtable and next table
91
94
95 int i;
96
97 for (i = 0; i < newCapacity; ++i)
98 {
100 }
101 for (i = 0; i < newCapacity; ++i)
102 {
104 }
105
106 for (i = 0; i < curHashtableSize; i++)
107 {
109 int indexA = pair.m_indexA;
110 int indexB = pair.m_indexB;
111
112 int hashValue = static_cast<int>(getHash(static_cast<unsigned int>(indexA), static_cast<unsigned int>(indexB)) & (m_overlappingPairArray.capacity() - 1)); // New hash value with new mask
115 }
116 }
117}
118
120{
121 int hash = static_cast<int>(getHash(static_cast<unsigned int>(indexA), static_cast<unsigned int>(indexB)) & (m_overlappingPairArray.capacity() - 1)); // New hash value with new mask
122
124 if (pair != NULL)
125 {
126 return pair;
127 }
128
129 int count = m_overlappingPairArray.size();
132
134
136 {
137 growTables();
138 //hash with new capacity
139 hash = static_cast<int>(getHash(static_cast<unsigned int>(indexA), static_cast<unsigned int>(indexB)) & (m_overlappingPairArray.capacity() - 1));
140 }
141
143
144 pair->m_userPointer = 0;
145
146 m_next[count] = m_hashTable[hash];
147 m_hashTable[hash] = count;
148
149 return pair;
150}
151
153{
154#ifdef BT_DEBUG_COLLISION_PAIRS
156#endif
157
158 /*if (indexA > indexB)
159 btSwap(indexA, indexB);*/
160
161 int hash = static_cast<int>(getHash(static_cast<unsigned int>(indexA), static_cast<unsigned int>(indexB)) & (m_overlappingPairArray.capacity() - 1));
162
164 if (pair == NULL)
165 {
166 return 0;
167 }
168
169 void* userData = pair->m_userPointer;
170
173
174 // Remove the pair from the hash table.
175 int index = m_hashTable[hash];
177
178 int previous = BT_SIMPLE_NULL_PAIR;
179 while (index != pairIndex)
180 {
181 previous = index;
182 index = m_next[index];
183 }
184
185 if (previous != BT_SIMPLE_NULL_PAIR)
186 {
187 btAssert(m_next[previous] == pairIndex);
188 m_next[previous] = m_next[pairIndex];
189 }
190 else
191 {
193 }
194
195 // We now move the last pair into spot of the
196 // pair being removed. We need to fix the hash
197 // table indices to support the move.
198
200
201 // If the removed pair is the last pair, we are done.
203 {
205 return userData;
206 }
207
208 // Remove the last pair from the hash table.
210 /* missing swap here too, Nat. */
211 int lastHash = static_cast<int>(getHash(static_cast<unsigned int>(last->m_indexA), static_cast<unsigned int>(last->m_indexB)) & (m_overlappingPairArray.capacity() - 1));
212
213 index = m_hashTable[lastHash];
215
216 previous = BT_SIMPLE_NULL_PAIR;
217 while (index != lastPairIndex)
218 {
219 previous = index;
220 index = m_next[index];
221 }
222
223 if (previous != BT_SIMPLE_NULL_PAIR)
224 {
225 btAssert(m_next[previous] == lastPairIndex);
226 m_next[previous] = m_next[lastPairIndex];
227 }
228 else
229 {
231 }
232
233 // Copy the last pair into the remove pair's spot.
235
236 // Insert the last pair into the hash table
239
241
242 return userData;
243}
244//#include <stdio.h>
const int BT_SIMPLE_NULL_PAIR
const T & btMax(const T &a, const T &b)
Definition btMinMax.h:27
#define btAssert(x)
Definition btScalar.h:153
int size() const
return the number of elements in the array
void resize(int newsize, const T &fillData=T())
void clear()
clear the array, deallocated memory. Generally it is better to use array.resize(0),...
int capacity() const
return the pre-allocated (reserved) elements, this is at least as large as the total number of elemen...
btSimplePair * internalFindPair(int proxyIdA, int proxyIdB, int hash)
unsigned int getHash(unsigned int indexA, unsigned int indexB)
btSimplePair * internalAddPair(int indexA, int indexB)
btAlignedObjectArray< int > m_hashTable
btAlignedObjectArray< int > m_next
btSimplePairArray m_overlappingPairArray
btSimplePair * findPair(int indexA, int indexB)
bool equalsPair(const btSimplePair &pair, int indexA, int indexB)
virtual void * removeOverlappingPair(int indexA, int indexB)