#include <Standard_Type.hxx>
// 5 lower bits
-#define MASK_LOW 0x001f
+#define MASK_LOW 0x001F
// 27 upper bits
#define MASK_HIGH (~MASK_LOW)
+namespace
+{
+ //! Returns the key with applied mask to it
+ //! @param theKey the given key
+ //! @return the key with the applied mask to it
+ unsigned int maskedKey (const unsigned int theKey)
+ {
+ return theKey & MASK_HIGH;
+ }
+
+ //! Computes a hash code for the given key (using only masked bits) in the range [1, theUpperBound]
+ //! @param theKey the given key
+ //! @param theUpperBound the upper bound of the range a computing hash code must be within
+ //! @return a computed hash code, in the range [1, theUpperBound]
+ Standard_Integer hashCodeForKey (const unsigned int theKey, const Standard_Integer theUpperBound)
+ {
+ return HashCode (theKey >> 5, theUpperBound);
+ }
+
+ //! Computes a hash code for the given key (using only masked bits) in the range [1, theUpperBound]
+ //! @param theKey the given key
+ //! @param theUpperBound the upper bound of the range a computing hash code must be within
+ //! @return a computed hash code, in the range [1, theUpperBound]
+ Standard_Integer hashCodeForKey (const Standard_Integer theKey, const Standard_Integer theUpperBound)
+ {
+ return hashCodeForKey (static_cast<unsigned int> (theKey), theUpperBound);
+ }
+} // namespace
+
//! Class implementing a block of 32 consecutive integer values as a node of a Map collection.
class TColStd_PackedMapOfInteger::TColStd_intMapNode : public TCollection_MapNode
{
public:
- inline TColStd_intMapNode (TCollection_MapNode * ptr = 0L)
+ explicit inline TColStd_intMapNode (TCollection_MapNode * ptr = 0L)
: TCollection_MapNode (ptr),
myMask (0),
myData (0) {}
inline unsigned int& ChangeData ()
{ return myData; }
- inline Standard_Integer Key () const
- { return Standard_Integer (myMask & MASK_HIGH); }
+ inline Standard_Integer Key() const
+ {
+ return static_cast<Standard_Integer> (maskedKey());
+ }
inline size_t NbValues () const
{ return size_t(myMask & MASK_LOW) + 1; }
//! @return a computed hash code, in the range [1, theUpperBound]
inline Standard_Integer HashCode (const Standard_Integer theUpperBound) const
{
- return ::HashCode (myMask >> 5, theUpperBound);
+ return hashCodeForKey (myMask, theUpperBound);
}
- /**
- * Support of Map interface.
- */
- inline Standard_Boolean IsEqual (const Standard_Integer theOther) const
+ //! Checks this node's key on equality with some other key
+ //! @param theOtherKey the given unmasked key
+ //! @return true if this node's masked key is equal to the given key with applied mask, or false otherwise
+ inline Standard_Boolean IsEqual (const Standard_Integer theOtherKey) const
+ {
+ return isEqual (::maskedKey (static_cast<unsigned int> (theOtherKey)));
+ }
+
+ //! Checks this node's key on equality with some other node's key
+ //! @param theOtherMapNode the given other map node
+ //! @return true if this node's masked key is equal to the given other map node's masked key, or false otherwise
+ bool IsEqual (const TColStd_intMapNode& theOtherMapNode) const
{
- return ((myMask >> 5) == (unsigned)theOther);
+ return isEqual (theOtherMapNode.maskedKey());
+ }
+
+private:
+ //! Returns the key of this map node with the mask applied to it
+ unsigned int maskedKey() const
+ {
+ return ::maskedKey (myMask);
+ }
+
+ //! Checks this node's key on equality with some other masked key
+ //! @param theOtherMaskedKey the given masked key
+ //! @return true if this node's masked key is equal to the given masked key, or false otherwise
+ bool isEqual (const unsigned int theOtherMaskedKey) const
+ {
+ return maskedKey() == theOtherMaskedKey;
}
private:
Standard_Boolean aResult (Standard_False);
TColStd_intMapNode ** data =
reinterpret_cast <TColStd_intMapNode**> (myData1);
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = hashCodeForKey (aKey, NbBuckets());
TCollection_MapNodePtr aBucketHead = data[aHashCode];
TColStd_intMapNode * p = static_cast<TColStd_intMapNode*> (aBucketHead);
while (p) {
- if (p->IsEqual(aKeyInt)) {
+ if (p->IsEqual(aKey)) {
aResult = p->AddValue (aKey);
// break;
goto finish; // goto saves us 4 CPU clocks or 4% performance
Standard_Boolean aResult (Standard_False);
if (!IsEmpty()) {
TColStd_intMapNode** data = (TColStd_intMapNode**) myData1;
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
- TColStd_intMapNode * p = data[HashCode (aKeyInt, NbBuckets())];
+ TColStd_intMapNode * p = data[hashCodeForKey (aKey, NbBuckets())];
while (p) {
- if (p->IsEqual(aKeyInt)) {
+ if (p->IsEqual(aKey)) {
aResult = (p->HasValue (aKey) != 0);
break;
}
if (!IsEmpty()) {
TColStd_intMapNode** data =
reinterpret_cast <TColStd_intMapNode**> (myData1);
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
- TColStd_intMapNode*& aBucketHead = data[HashCode(aKeyInt, NbBuckets())];
+ TColStd_intMapNode*& aBucketHead = data[hashCodeForKey(aKey, NbBuckets())];
TColStd_intMapNode* p = aBucketHead;
TColStd_intMapNode* q = 0L;
while (p) {
- if (p->IsEqual(aKeyInt)) {
+ if (p->IsEqual(aKey)) {
aResult = p->DelValue (aKey);
if (aResult) {
myExtent--;
for (i = 0; i <= nBuckets1; i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
unsigned int aNewMask = p1->Mask();
unsigned int aNewData = p1->Data();
size_t nValues (p1->NbValues());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode(nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
aNewData |= p2->Data();
nValues = TColStd_Population (aNewMask, aNewData);
break;
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
aData[aHashCode] = new TColStd_intMapNode (aNewMask, aNewData,
aData[aHashCode]);
Increment();
for (i = 0; i <= nBuckets2; i++) {
const TColStd_intMapNode * p2 = aData2[i];
while (p2 != 0L) {
- // Find aKey - the base address of currently iterated block
- const Standard_Integer aKey = p2->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
// Find the corresponding block in the 1st map
const TColStd_intMapNode * p1 =
- aData1 [HashCode (aKeyInt, nBuckets1)];
+ aData1 [p2->HashCode (nBuckets1)];
while (p1) {
- if (p1->IsEqual(aKeyInt))
+ if (p1->IsEqual(*p2))
break;
p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
}
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = p2->HashCode (NbBuckets());
aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
aData[aHashCode]);
Increment();
for (Standard_Integer i = 0; i <= nBuckets2; i++) {
const TColStd_intMapNode * p2 = aData2[i];
while (p2 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p2->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
// Find the corresponding block in the 1st (this) map
- Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ Standard_Integer aHashCode = p2->HashCode (NbBuckets());
TColStd_intMapNode * p1 = aData[aHashCode];
while (p1) {
- if (p1->IsEqual(aKeyInt)) {
+ if (p1->IsEqual(*p2)) {
const size_t anOldPop = p1->NbValues();
unsigned int newData = p1->Data() | p2->Data();
if ( newData != p1->Data() ) {
if (Resizable()) {
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
- aHashCode = HashCode (aKeyInt, NbBuckets());
+ aHashCode = p2->HashCode (NbBuckets());
}
aData[aHashCode] = new TColStd_intMapNode (p2->Mask(), p2->Data(),
aData[aHashCode]);
for (Standard_Integer i = 0; i <= nBuckets1; i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
const unsigned int aNewData = p1->Data() & p2->Data();
// Store the block - result of operation
if (aNewData) {
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt,
- NbBuckets());
+ const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
unsigned int aNewMask = p1->Mask();
myExtent += TColStd_Population (aNewMask, aNewData);
aData[aHashCode]= new TColStd_intMapNode(aNewMask, aNewData,
TColStd_intMapNode * q = 0L;
TColStd_intMapNode * p1 = aData[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
const unsigned int aNewData = p1->Data() & p2->Data();
// Store the block - result of operation
if (aNewData == 0)
for (Standard_Integer i = 0; i <= nBuckets1; i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
unsigned int aNewMask = p1->Mask();
unsigned int aNewData = p1->Data();
size_t nValues (p1->NbValues());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
aNewData &= ~p2->Data();
nValues = TColStd_Population (aNewMask, aNewData);
break;
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
aData[aHashCode]);
Increment();
TColStd_intMapNode * q = 0L;
TColStd_intMapNode * p1 = aData[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
TColStd_intMapNode* pNext =
reinterpret_cast <TColStd_intMapNode*> (p1->Next());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
const unsigned int aNewData = p1->Data() & ~p2->Data();
// Store the block - result of operation
if (aNewData == 0) {
for (i = 0; i <= nBuckets1; i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
unsigned int aNewMask = p1->Mask();
unsigned int aNewData = p1->Data();
size_t nValues (p1->NbValues());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
aNewData ^= p2->Data();
nValues = TColStd_Population (aNewMask, aNewData);
break;
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = p1->HashCode (NbBuckets());
aData[aHashCode]= new TColStd_intMapNode (aNewMask, aNewData,
aData[aHashCode]);
Increment();
for (i = 0; i <= nBuckets2; i++) {
const TColStd_intMapNode * p2 = aData2[i];
while (p2 != 0L) {
- // Find aKey - the base address of currently iterated block
- const Standard_Integer aKey = p2->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
// Find the corresponding block in the 1st map
const TColStd_intMapNode * p1 =
- aData1 [HashCode (aKeyInt, nBuckets1)];
+ aData1 [p2->HashCode (nBuckets1)];
while (p1) {
- if (p1->IsEqual(aKeyInt))
+ if (p1->IsEqual(*p2))
break;
p1 = reinterpret_cast <const TColStd_intMapNode*> (p1->Next());
}
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = p2->HashCode (NbBuckets());
aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
aData[aHashCode]);
Increment();
for ( ; i <= nBuckets2; i++) {
TColStd_intMapNode * q = 0L;
const TColStd_intMapNode * p2 = aData2[i];
- while (p2 != 0L) {
- // Find aKey - the base address of currently iterated block
- const Standard_Integer aKey = p2->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
-
+ while (p2 != 0L) {
// Find the corresponding block in the 1st map
TColStd_intMapNode * p1 =
- aData1[HashCode (aKeyInt, NbBuckets())];
+ aData1[p2->HashCode (NbBuckets())];
TColStd_intMapNode* pNext =
reinterpret_cast <TColStd_intMapNode*> (p1->Next());
while (p1) {
- if (p1->IsEqual(aKeyInt)) {
+ if (p1->IsEqual(*p2)) {
const unsigned int aNewData = p1->Data() ^ p2->Data();
// Store the block - result of operation
if (aNewData == 0) {
ReSize(InternalExtent());
aData = (TColStd_intMapNode**) myData1;
}
- const Standard_Integer aHashCode = HashCode (aKeyInt, NbBuckets());
+ const Standard_Integer aHashCode = p2->HashCode (NbBuckets());
aData[aHashCode]= new TColStd_intMapNode (p2->Mask(), p2->Data(),
aData[aHashCode]);
Increment();
for (; i <= NbBuckets(); i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
TColStd_intMapNode* pNext =
reinterpret_cast <TColStd_intMapNode*> (p1->Next());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if ( p2->IsEqual(aKeyInt) ) {
+ if ( p2->IsEqual(*p1) ) {
if ( p1->Data() != p2->Data() )
return Standard_False;
break;
for (; i <= NbBuckets(); i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
TColStd_intMapNode* pNext =
reinterpret_cast <TColStd_intMapNode*> (p1->Next());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
if (!p2)
return Standard_False;
while (p2) {
- if ( p2->IsEqual(aKeyInt) ) {
+ if ( p2->IsEqual(*p1) ) {
if ( p1->Data() & ~p2->Data() ) // at least one bit set in p1 is not set in p2
return Standard_False;
break;
for (; i <= NbBuckets(); i++) {
const TColStd_intMapNode * p1 = aData1[i];
while (p1 != 0L) {
- // Find aKey - the base address of currently iterated block of integers
- const Standard_Integer aKey = p1->Key();
- const Standard_Integer aKeyInt = (unsigned)aKey >> 5;
TColStd_intMapNode* pNext =
reinterpret_cast <TColStd_intMapNode*> (p1->Next());
// Find the corresponding block in the 2nd map
const TColStd_intMapNode * p2 =
- aData2 [HashCode (aKeyInt, nBuckets2)];
+ aData2 [p1->HashCode (nBuckets2)];
while (p2) {
- if (p2->IsEqual(aKeyInt)) {
+ if (p2->IsEqual(*p1)) {
if ( p1->Data() & p2->Data() )
return Standard_True;
break;