0029302: Foundation Classes, NCollection - optimize iteration of indexed maps
authorkgv <kgv@opencascade.com>
Wed, 8 Nov 2017 12:25:51 +0000 (15:25 +0300)
committerbugmaster <bugmaster@opencascade.com>
Thu, 9 Nov 2017 15:08:18 +0000 (18:08 +0300)
NCollection_IndexedMap and NCollection_IndexedDataMap
now access Key by Index number without computing Hash code.
IndexedMapNode::myNext2 and IndexedDataMapNode::myNext2 fields
have been removed, so that indexed map now may utilize less memory.

TCollection::NextPrimeForMap() has been extended upto 2038431745
(almost full signed 32-bit integer range),
and NCollection_BaseMap::mySaturated property has been removed.

NCollection_IndexedDataMap::RemoveFromIndex(), FindKey(), FindFromIndex(),
ChangeFromIndex() - removed duplicating checks for out of range input.

src/NCollection/NCollection_BaseMap.cxx
src/NCollection/NCollection_BaseMap.hxx
src/NCollection/NCollection_IndexedDataMap.hxx
src/NCollection/NCollection_IndexedMap.hxx
src/TCollection/TCollection.cxx

index 71c499d..7001ae5 100644 (file)
@@ -29,7 +29,6 @@ Standard_Boolean  NCollection_BaseMap::BeginResize
    NCollection_ListNode**& data1,
    NCollection_ListNode**& data2) const 
 {
-  if (mySaturated) return Standard_False;
   N = NextPrimeForMap(NbBuckets);
   if (N <= myNbBuckets) {
     if (!myData1)
@@ -57,17 +56,17 @@ Standard_Boolean  NCollection_BaseMap::BeginResize
 //=======================================================================
 
 void  NCollection_BaseMap::EndResize
-  (const Standard_Integer NbBuckets,
+  (const Standard_Integer theNbBuckets,
    const Standard_Integer N,
    NCollection_ListNode** data1,
    NCollection_ListNode** data2)
 {
+  (void )theNbBuckets; // obsolete parameter
   if (myData1) 
     myAllocator->Free(myData1);
   if (myData2) 
     myAllocator->Free(myData2);
   myNbBuckets = N;
-  mySaturated = (myNbBuckets <= NbBuckets);
   myData1 = data1;
   myData2 = data2;
 }
@@ -105,7 +104,6 @@ void  NCollection_BaseMap::Destroy (NCollection_DelMapNode fDel,
   mySize = 0;
   if (doReleaseMemory)
   {
-    mySaturated = Standard_False;
     if (myData1) 
       myAllocator->Free(myData1);
     if (isDouble && myData2) 
@@ -124,7 +122,6 @@ void NCollection_BaseMap::Statistics(Standard_OStream& S) const
 {
   S <<"\nMap Statistics\n---------------\n\n";
   S <<"This Map has "<<myNbBuckets<<" Buckets and "<<mySize<<" Keys\n\n";
-  if (mySaturated) S<<"The maximum number of Buckets is reached\n";
   
   if (mySize == 0) return;
 
index 652cc0a..62b3453 100644 (file)
@@ -162,10 +162,9 @@ public:
                        const Handle(NCollection_BaseAllocator)& theAllocator)
   : myData1(NULL),
     myData2(NULL),
-    isDouble(!single),
-    mySaturated(Standard_False),
     myNbBuckets(NbBuckets),
-    mySize(0)
+    mySize(0),
+    isDouble(!single)
   {
     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
   }
@@ -189,15 +188,13 @@ public:
 
   //! Resizable
   Standard_Boolean Resizable() const
-  { return IsEmpty() || (!mySaturated && (mySize > myNbBuckets)); }
+  { return IsEmpty() || (mySize > myNbBuckets); }
 
   //! Increment
-  void Increment()
-  { mySize++; }
+  Standard_Integer Increment() { return ++mySize; }
 
   //! Decrement
-  void Decrement() 
-  { mySize--; }
+  Standard_Integer Decrement()  { return --mySize; }
 
   //! Destroy
   Standard_EXPORT void Destroy(NCollection_DelMapNode fDel,
@@ -213,10 +210,9 @@ public:
     std::swap (myAllocator, theOther.myAllocator);
     std::swap (myData1,     theOther.myData1);
     std::swap (myData2,     theOther.myData2);
-    //std::swap (isDouble,    theOther.isDouble);
-    std::swap (mySaturated, theOther.mySaturated);
     std::swap (myNbBuckets, theOther.myNbBuckets);
     std::swap (mySize,      theOther.mySize);
+    //std::swap (isDouble,    theOther.isDouble);
   }
 
  protected:
@@ -227,10 +223,9 @@ public:
 
  private: 
   // ---------- PRIVATE FIELDS ------------
-  Standard_Boolean isDouble;
-  Standard_Boolean mySaturated;
   Standard_Integer myNbBuckets;
   Standard_Integer mySize;
+  Standard_Boolean isDouble;
 
   // ---------- FRIEND CLASSES ------------
   friend class Iterator;
index 6b8574f..da2c685 100644 (file)
@@ -62,26 +62,19 @@ private:
   public:
     //! Constructor with 'Next'
     IndexedDataMapNode (const TheKeyType&      theKey1, 
-                        const Standard_Integer theKey2,
+                        const Standard_Integer theIndex,
                         const TheItemType&     theItem,
-                        NCollection_ListNode*  theNext1, 
-                        NCollection_ListNode*  theNext2) :
-      NCollection_TListNode<TheItemType>(theItem,theNext1),
-      myKey1(theKey1),
-      myKey2(theKey2),
-      myNext2((IndexedDataMapNode*)theNext2)
+                        NCollection_ListNode*  theNext1)
+    : NCollection_TListNode<TheItemType>(theItem,theNext1),
+      myKey1  (theKey1),
+      myIndex (theIndex)
     { 
     }
     //! Key1
-    TheKeyType& Key1 (void)
-    { return myKey1; }
-    //! Key2
-    Standard_Integer& Key2 (void)
-    { return myKey2; }
-    //! Next2
-    IndexedDataMapNode*& Next2 (void)
-    { return myNext2; }
-    
+    TheKeyType& Key1() { return myKey1; }
+    //! Index
+    Standard_Integer& Index() { return myIndex; }
+
     //! Static deleter to be passed to BaseList
     static void delNode (NCollection_ListNode * theNode, 
                          Handle(NCollection_BaseAllocator)& theAl)
@@ -90,9 +83,8 @@ private:
       theAl->Free(theNode);
     }
   private:
-    TheKeyType           myKey1;
-    Standard_Integer     myKey2;
-    IndexedDataMapNode * myNext2;
+    TheKeyType       myKey1;
+    Standard_Integer myIndex;
   };
 
  public:
@@ -101,13 +93,14 @@ private:
   {
   public:
     //! Empty constructor
-    Iterator (void) :
-      myMap(NULL),
-      myIndex(0) {}
+    Iterator()
+    : myMap (NULL),
+      myNode (NULL),
+      myIndex (0) {}
     //! Constructor
     Iterator (const NCollection_IndexedDataMap& theMap)
     : myMap  ((NCollection_IndexedDataMap* )&theMap),
-      myNode (myMap->nodeFromIndex (1)),
+      myNode (!theMap.IsEmpty() ? (IndexedDataMapNode* )myMap->myData2[0] : NULL),
       myIndex (1) {}
     //! Query if the end of collection is reached by iterator
     Standard_Boolean More(void) const
@@ -115,7 +108,7 @@ private:
     //! Make a step along the collection
     void Next(void)
     {
-      myNode = myMap->nodeFromIndex (++myIndex);
+      myNode = (IndexedDataMapNode* )myMap->myData2[++myIndex - 1];
     }
     //! Value access
     const TheItemType& Value(void) const
@@ -195,18 +188,14 @@ private:
 
     Clear();
     ReSize (theOther.Extent()-1);
-    Standard_Integer i;
-    for (i=1; i<=theOther.Extent(); i++)
+    for (Standard_Integer anIndexIter = 1; anIndexIter <= theOther.Extent(); ++anIndexIter)
     {
-      TheKeyType aKey1 = theOther.FindKey(i);
-      TheItemType anItem = theOther.FindFromIndex(i);
-      Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
-      Standard_Integer iK2 = ::HashCode (i, NbBuckets());
-      IndexedDataMapNode * pNode = 
-        new (this->myAllocator) IndexedDataMapNode (aKey1, i, anItem,
-                                              myData1[iK1], myData2[iK2]);
-      myData1[iK1] = pNode;
-      myData2[iK2] = pNode;
+      const TheKeyType&  aKey1  = theOther.FindKey      (anIndexIter);
+      const TheItemType& anItem = theOther.FindFromIndex(anIndexIter);
+      const Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
+      IndexedDataMapNode* pNode = new (this->myAllocator) IndexedDataMapNode (aKey1, anIndexIter, anItem, myData1[iK1]);
+      myData1[iK1]             = pNode;
+      myData2[anIndexIter - 1] = pNode;
       Increment();
     }
     return *this;
@@ -228,22 +217,18 @@ private:
     {
       if (myData1) 
       {
-        IndexedDataMapNode *p, *q;
-        Standard_Integer i, iK1, iK2;
-        for (i = 0; i <= NbBuckets(); i++) 
+        memcpy (ppNewData2, myData2, sizeof(IndexedDataMapNode*) * Extent());
+        for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
         {
-          if (myData1[i]) 
+          if (myData1[aBucketIter])
           {
-            p = (IndexedDataMapNode *) myData1[i];
+            IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[aBucketIter];
             while (p) 
             {
-              iK1 = Hasher::HashCode (p->Key1(), newBuck);
-              iK2 = ::HashCode (p->Key2(), newBuck);
-              q = (IndexedDataMapNode*) p->Next();
-              p->Next()  = ppNewData1[iK1];
-              p->Next2() = (IndexedDataMapNode*)ppNewData2[iK2];
+              const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), newBuck);
+              IndexedDataMapNode* q = (IndexedDataMapNode* )p->Next();
+              p->Next() = ppNewData1[iK1];
               ppNewData1[iK1] = p;
-              ppNewData2[iK2] = p;
               p = q;
             }
           }
@@ -256,24 +241,27 @@ private:
   //! Add
   Standard_Integer Add (const TheKeyType& theKey1, const TheItemType& theItem)
   {
-    if (Resizable()) 
+    if (Resizable())
+    {
       ReSize(Extent());
-    Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
-    IndexedDataMapNode * pNode;
-    pNode = (IndexedDataMapNode *) myData1[iK1];
+    }
+
+    const Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
+    IndexedDataMapNode* pNode = (IndexedDataMapNode* )myData1[iK1];
     while (pNode)
     {
       if (Hasher::IsEqual (pNode->Key1(), theKey1))
-        return pNode->Key2();
+      {
+        return pNode->Index();
+      }
       pNode = (IndexedDataMapNode *) pNode->Next();
     }
-    Increment();
-    Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
-    pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, Extent(), theItem,
-                                                  myData1[iK1], myData2[iK2]);
-    myData1[iK1] = pNode;
-    myData2[iK2] = pNode;
-    return Extent();
+
+    const Standard_Integer aNewIndex = Increment();
+    pNode = new (this->myAllocator) IndexedDataMapNode (theKey1, aNewIndex, theItem, myData1[iK1]);
+    myData1[iK1]           = pNode;
+    myData2[aNewIndex - 1] = pNode;
+    return aNewIndex;
   }
 
   //! Contains
@@ -302,15 +290,14 @@ private:
                                   "NCollection_IndexedDataMap::Substitute : "
                                   "Index is out of range");
 
-    IndexedDataMapNode * p;
     // check if theKey1 is not already in the map
-    Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
-    p = (IndexedDataMapNode *) myData1[iK1];
+    const Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
+    IndexedDataMapNode* p = (IndexedDataMapNode *) myData1[iK1];
     while (p)
     {
       if (Hasher::IsEqual (p->Key1(), theKey1))
       {
-        if (p->Key2() != theIndex)
+        if (p->Index() != theIndex)
         {
           throw Standard_DomainError ("NCollection_IndexedDataMap::Substitute : "
                                       "Attempt to substitute existing key");
@@ -323,17 +310,10 @@ private:
     }
 
     // Find the node for the index I
-    Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
-    p = (IndexedDataMapNode *) myData2[iK2];
-    while (p) 
-    {
-      if (p->Key2() == theIndex) 
-        break;
-      p = (IndexedDataMapNode*) p->Next2();
-    }
+    p = (IndexedDataMapNode* )myData2[theIndex - 1];
     
     // remove the old key
-    Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
+    const Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
     IndexedDataMapNode * q = (IndexedDataMapNode *) myData1[iK];
     if (q == p)
       myData1[iK] = (IndexedDataMapNode *) p->Next();
@@ -363,71 +343,26 @@ private:
       return;
     }
 
-    const Standard_Integer aK1 = ::HashCode (theIndex1, NbBuckets());
-    const Standard_Integer aK2 = ::HashCode (theIndex2, NbBuckets());
-
-    IndexedDataMapNode* aP1 = (IndexedDataMapNode*) myData2[aK1];
-    IndexedDataMapNode* aP2 = (IndexedDataMapNode*) myData2[aK2];
-
-    if (aP1->Key2() == theIndex1)
-    {
-      myData2[aK1] = (IndexedDataMapNode *) aP1->Next2();
-    }
-    else
-    {
-      IndexedDataMapNode* aQ = aP1;
-      for (aP1 = aQ->Next2(); aP1->Key2() != theIndex1; aQ = aP1, aP1 = aQ->Next2()) { }
-
-      aQ->Next2() = aP1->Next2();
-    }
-
-    if (aP2->Key2() == theIndex2)
-    {
-      myData2[aK2] = (IndexedDataMapNode *) aP2->Next2();
-    }
-    else
-    {
-      IndexedDataMapNode* aQ = aP2;
-      for (aP2 = aQ->Next2(); aP2->Key2() != theIndex2; aQ = aP2, aP2 = aQ->Next2()) { }
-
-      aQ->Next2() = aP2->Next2();
-    }
-
-    std::swap (aP1->Key2(),
-               aP2->Key2());
-
-    aP1->Next2() = (IndexedDataMapNode*) myData2[aK2];
-    myData2[aK2] = aP1;
-
-    aP2->Next2() = (IndexedDataMapNode*) myData2[aK1];
-    myData2[aK1] = aP2;
+    IndexedDataMapNode* aP1 = (IndexedDataMapNode* )myData2[theIndex1 - 1];
+    IndexedDataMapNode* aP2 = (IndexedDataMapNode* )myData2[theIndex2 - 1];
+    std::swap (aP1->Index(), aP2->Index());
+    myData2[theIndex2 - 1] = aP1;
+    myData2[theIndex1 - 1] = aP2;
   }
 
   //! RemoveLast
   void RemoveLast (void)
   {
-    Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedDataMap::RemoveLast");
+    const Standard_Integer aLastIndex = Extent();
+    Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedDataMap::RemoveLast");
 
-    IndexedDataMapNode * p, * q;
     // Find the node for the last index and remove it
-    Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
-    p = (IndexedDataMapNode *) myData2[iK2];
-    q = NULL;
-    while (p) 
-    {
-      if (p->Key2() == Extent()) 
-        break;
-      q = p;
-      p = (IndexedDataMapNode*) p->Next2();
-    }
-    if (q == NULL) 
-      myData2[iK2] = (IndexedDataMapNode *) p->Next2();
-    else 
-      q->Next2() = p->Next2();
+    IndexedDataMapNode* p = (IndexedDataMapNode* )myData2[aLastIndex - 1];
+    myData2[aLastIndex - 1] = NULL;
     
     // remove the key
-    Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
-    q = (IndexedDataMapNode *) myData1[iK1];
+    const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
+    IndexedDataMapNode* q = (IndexedDataMapNode *) myData1[iK1];
     if (q == p)
       myData1[iK1] = (IndexedDataMapNode *) p->Next();
     else 
@@ -443,12 +378,14 @@ private:
 
   //! Remove the key of the given index.
   //! Caution! The index of the last key can be changed.
-  void RemoveFromIndex(const Standard_Integer theKey2)
+  void RemoveFromIndex(const Standard_Integer theIndex)
   {
-    Standard_OutOfRange_Raise_if(theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::Remove");
-    Standard_Integer aLastInd = Extent();
-    if (theKey2 != aLastInd)
-      Swap(theKey2, aLastInd);
+    const Standard_Integer aLastInd = Extent();
+    Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > aLastInd, "NCollection_IndexedDataMap::Remove");
+    if (theIndex != aLastInd)
+    {
+      Swap (theIndex, aLastInd);
+    }
     RemoveLast();
   }
 
@@ -463,62 +400,46 @@ private:
   }
 
   //! FindKey
-  const TheKeyType& FindKey (const Standard_Integer theKey2) const
+  const TheKeyType& FindKey (const Standard_Integer theIndex) const
   {
-    Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindKey");
-
-    IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
-    if (aNode == NULL)
-    {
-      throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindKey");
-    }
+    Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindKey");
+    IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
     return aNode->Key1();
   }
 
   //! FindFromIndex
-  const TheItemType& FindFromIndex (const Standard_Integer theKey2) const
+  const TheItemType& FindFromIndex (const Standard_Integer theIndex) const
   {
-    Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
-
-    IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
-    if (aNode == NULL)
-    {
-      throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromIndex");
-    }
+    Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::FindFromIndex");
+    IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
     return aNode->Value();
   }
 
   //! operator ()
-  const TheItemType& operator() (const Standard_Integer theKey2) const
-  { return FindFromIndex (theKey2); }
+  const TheItemType& operator() (const Standard_Integer theIndex) const { return FindFromIndex (theIndex); }
 
   //! ChangeFromIndex
-  TheItemType& ChangeFromIndex (const Standard_Integer theKey2)
+  TheItemType& ChangeFromIndex (const Standard_Integer theIndex)
   {
-    Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
-
-    IndexedDataMapNode* aNode = nodeFromIndex (theKey2);
-    if (aNode == NULL)
-    {
-      throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromIndex");
-    }
+    Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedDataMap::ChangeFromIndex");
+    IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[theIndex - 1];
     return aNode->ChangeValue();
   }
 
   //! operator ()
-  TheItemType& operator() (const Standard_Integer theKey2)
-  { return ChangeFromIndex (theKey2); }
+  TheItemType& operator() (const Standard_Integer theIndex) { return ChangeFromIndex (theIndex); }
 
   //! FindIndex
   Standard_Integer FindIndex(const TheKeyType& theKey1) const
   {
     if (IsEmpty()) return 0;
-    IndexedDataMapNode * pNode1 = 
-      (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
+    IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
     while (pNode1)
     {
-      if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
-        return pNode1->Key2();
+      if (Hasher::IsEqual (pNode1->Key1(), theKey1))
+      {
+        return pNode1->Index();
+      }
       pNode1 = (IndexedDataMapNode*) pNode1->Next();
     }
     return 0;
@@ -529,12 +450,13 @@ private:
   {
     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::FindFromKey");
 
-    IndexedDataMapNode * pNode1 = 
-      (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
+    IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
     while (pNode1)
     {
-      if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
+      if (Hasher::IsEqual (pNode1->Key1(), theKey1))
+      {
         return pNode1->Value();
+      }
       pNode1 = (IndexedDataMapNode*) pNode1->Next();
     }
     throw Standard_NoSuchObject("NCollection_IndexedDataMap::FindFromKey");
@@ -545,12 +467,13 @@ private:
   {
     Standard_NoSuchObject_Raise_if (IsEmpty(), "NCollection_IndexedDataMap::ChangeFromKey");
 
-    IndexedDataMapNode * pNode1 = 
-      (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
+    IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
     while (pNode1)
     {
-      if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
+      if (Hasher::IsEqual (pNode1->Key1(), theKey1))
+      {
         return pNode1->ChangeValue();
+      }
       pNode1 = (IndexedDataMapNode*) pNode1->Next();
     }
     throw Standard_NoSuchObject("NCollection_IndexedDataMap::ChangeFromKey");
@@ -571,12 +494,13 @@ private:
   {
     if (!IsEmpty()) 
     {
-      IndexedDataMapNode * pNode1 = 
-        (IndexedDataMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
+      IndexedDataMapNode* pNode1 = (IndexedDataMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
       while (pNode1)
       {
-        if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
+        if (Hasher::IsEqual (pNode1->Key1(), theKey1))
+        {
           return &pNode1->ChangeValue();
+        }
         pNode1 = (IndexedDataMapNode*) pNode1->Next();
       }
     }
@@ -628,25 +552,6 @@ private:
  private:
   // ----------- PRIVATE METHODS -----------
 
-  //! Find map node associated with specified index.
-  //! Return NULL if not found (exception-free internal implementation).
-  IndexedDataMapNode* nodeFromIndex (const Standard_Integer theKey2) const
-  {
-    if (Extent() == 0)
-    {
-      return NULL;
-    }
-    for (IndexedDataMapNode* aNode = (IndexedDataMapNode* )myData2[::HashCode (theKey2, NbBuckets())];
-         aNode != NULL; aNode = (IndexedDataMapNode* )aNode->Next2())
-    {
-      if (aNode->Key2() == theKey2)
-      {
-        return aNode;
-      }
-    }
-    return NULL;
-  }
-
 };
 
 #endif
index f9a150c..fe3c4a7 100644 (file)
@@ -44,30 +44,24 @@ public:
   //! STL-compliant typedef for key type
   typedef TheKeyType key_type;
 
- private:
-   // **************** Adaptation of the TListNode to the INDEXEDmap
-   class IndexedMapNode : public NCollection_TListNode<TheKeyType>
+private:
+  //! Adaptation of the TListNode to the INDEXEDmap
+  class IndexedMapNode : public NCollection_TListNode<TheKeyType>
   {
   public:
     //! Constructor with 'Next'
     IndexedMapNode (const TheKeyType&      theKey1, 
-                    const Standard_Integer theKey2, 
-                    NCollection_ListNode*  theNext1, 
-                    NCollection_ListNode*  theNext2) :
-      NCollection_TListNode<TheKeyType> (theKey1, theNext1),
-      myKey2(theKey2),
-      myNext2((IndexedMapNode*)theNext2)
-    { 
+                    const Standard_Integer theIndex,
+                    NCollection_ListNode*  theNext1)
+    : NCollection_TListNode<TheKeyType> (theKey1, theNext1),
+      myIndex (theIndex)
+    {
     }
     //! Key1
-    TheKeyType& Key1 (void)
-    { return this->ChangeValue(); }
-    //! Key2
-    Standard_Integer& Key2 (void)
-    { return myKey2; }
-    //! Next2
-    IndexedMapNode*& Next2 (void)
-    { return myNext2; }
+    TheKeyType& Key1() { return this->ChangeValue(); }
+
+    //! Index
+    Standard_Integer& Index() { return myIndex; }
     
     //! Static deleter to be passed to BaseList
     static void delNode (NCollection_ListNode * theNode, 
@@ -78,8 +72,7 @@ public:
     }
 
   private:
-    Standard_Integer myKey2;
-    IndexedMapNode * myNext2;
+    Standard_Integer myIndex;
   };
 
  public:
@@ -157,17 +150,14 @@ public:
 
     Clear();
     ReSize (theOther.Extent()-1);
-    Standard_Integer i, iLength=theOther.Extent();
-    for (i=1; i<=iLength; i++)
+    const Standard_Integer iLength = theOther.Extent();
+    for (Standard_Integer anIndexIter = 1; anIndexIter <= iLength; ++anIndexIter)
     {
-      TheKeyType aKey1 = theOther(i);
-      Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
-      Standard_Integer iK2 = ::HashCode (i, NbBuckets());
-      IndexedMapNode * pNode = new (this->myAllocator) IndexedMapNode (aKey1, i, 
-                                                                       myData1[iK1], 
-                                                                       myData2[iK2]);
-      myData1[iK1] = pNode;
-      myData2[iK2] = pNode;
+      const TheKeyType& aKey1 = theOther.FindKey (anIndexIter);
+      const Standard_Integer iK1 = Hasher::HashCode (aKey1, NbBuckets());
+      IndexedMapNode* pNode = new (this->myAllocator) IndexedMapNode (aKey1, anIndexIter, myData1[iK1]);
+      myData1[iK1]             = pNode;
+      myData2[anIndexIter - 1] = pNode;
       Increment();
     }
     return *this;
@@ -180,64 +170,60 @@ public:
   }
 
   //! ReSize
-  void ReSize (const Standard_Integer N)
+  void ReSize (const Standard_Integer theExtent)
   {
     NCollection_ListNode** ppNewData1 = NULL;
     NCollection_ListNode** ppNewData2 = NULL;
     Standard_Integer newBuck;
-    if (BeginResize (N, newBuck, ppNewData1, ppNewData2))
+    if (BeginResize (theExtent, newBuck, ppNewData1, ppNewData2))
     {
       if (myData1) 
       {
-        IndexedMapNode *p, *q;
-        Standard_Integer i, iK1, iK2;
-        for (i = 0; i <= NbBuckets(); i++) 
+        memcpy (ppNewData2, myData2, sizeof(IndexedMapNode*) * Extent());
+        for (Standard_Integer aBucketIter = 0; aBucketIter <= NbBuckets(); ++aBucketIter)
         {
-          if (myData1[i]) 
+          if (myData1[aBucketIter])
           {
-            p = (IndexedMapNode *) myData1[i];
+            IndexedMapNode* p = (IndexedMapNode* )myData1[aBucketIter];
             while (p) 
             {
-              iK1 =Hasher::HashCode(p->Key1(), newBuck);
-              q = (IndexedMapNode*) p->Next();
-              p->Next()  = ppNewData1[iK1];
+              const Standard_Integer iK1 = Hasher::HashCode (p->Key1(), newBuck);
+              IndexedMapNode* q = (IndexedMapNode* )p->Next();
+              p->Next() = ppNewData1[iK1];
               ppNewData1[iK1] = p;
-              if (p->Key2() > 0) 
-              {
-                iK2 = ::HashCode (p->Key2(), newBuck);
-                p->Next2() = (IndexedMapNode*)ppNewData2[iK2];
-                ppNewData2[iK2] = p;
-              }
               p = q;
             }
           }
         }
       }
-      EndResize (N, newBuck, ppNewData1, ppNewData2);
+      EndResize (theExtent, newBuck, ppNewData1, ppNewData2);
     }
   }
 
   //! Add
   Standard_Integer Add (const TheKeyType& theKey1)
   {
-    if (Resizable()) 
-      ReSize(Extent());
+    if (Resizable())
+    {
+      ReSize (Extent());
+    }
+
     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
-    IndexedMapNode * pNode;
-    pNode = (IndexedMapNode *) myData1[iK1];
+    IndexedMapNode* pNode = (IndexedMapNode* )myData1[iK1];
     while (pNode)
     {
       if (Hasher::IsEqual (pNode->Key1(), theKey1))
-        return pNode->Key2();
+      {
+        return pNode->Index();
+      }
       pNode = (IndexedMapNode *) pNode->Next();
     }
-    Increment();
-    Standard_Integer iK2 = ::HashCode(Extent(),NbBuckets());
-    pNode = new (this->myAllocator) IndexedMapNode (theKey1, Extent(), 
-                                                    myData1[iK1], myData2[iK2]);
-    myData1[iK1] = pNode;
-    myData2[iK2] = pNode;
-    return Extent();
+
+    const Standard_Integer aNewIndex = Increment();
+    pNode = new (this->myAllocator) IndexedMapNode (theKey1, aNewIndex, myData1[iK1]);
+    myData1[iK1]           = pNode;
+    myData2[aNewIndex - 1] = pNode;
+    return aNewIndex;
   }
 
   //! Contains
@@ -265,15 +251,14 @@ public:
                                   "NCollection_IndexedMap::Substitute : "
                                   "Index is out of range");
 
-    IndexedMapNode * p;
     // check if theKey1 is not already in the map
     Standard_Integer iK1 = Hasher::HashCode (theKey1, NbBuckets());
-    p = (IndexedMapNode *) myData1[iK1];
+    IndexedMapNode* p = (IndexedMapNode *) myData1[iK1];
     while (p)
     {
       if (Hasher::IsEqual (p->Key1(), theKey1))
       {
-        if (p->Key2() != theIndex)
+        if (p->Index() != theIndex)
         {
           throw Standard_DomainError ("NCollection_IndexedMap::Substitute : "
                                       "Attempt to substitute existing key");
@@ -285,14 +270,7 @@ public:
     }
 
     // Find the node for the index I
-    Standard_Integer iK2 = ::HashCode (theIndex, NbBuckets());
-    p = (IndexedMapNode *) myData2[iK2];
-    while (p) 
-    {
-      if (p->Key2() == theIndex) 
-        break;
-      p = (IndexedMapNode*) p->Next2();
-    }
+    p = (IndexedMapNode* )myData2[theIndex - 1];
     
     // remove the old key
     Standard_Integer iK = Hasher::HashCode (p->Key1(), NbBuckets());
@@ -324,71 +302,26 @@ public:
       return;
     }
 
-    const Standard_Integer aK1 = ::HashCode (theIndex1, NbBuckets());
-    const Standard_Integer aK2 = ::HashCode (theIndex2, NbBuckets());
-
-    IndexedMapNode* aP1 = (IndexedMapNode*) myData2[aK1];
-    IndexedMapNode* aP2 = (IndexedMapNode*) myData2[aK2];
-
-    if (aP1->Key2() == theIndex1)
-    {
-      myData2[aK1] = (IndexedMapNode *) aP1->Next2();
-    }
-    else
-    {
-      IndexedMapNode* aQ = aP1;
-      for (aP1 = aQ->Next2(); aP1->Key2() != theIndex1; aQ = aP1, aP1 = aQ->Next2()) { }
-
-      aQ->Next2() = aP1->Next2();
-    }
-
-    if (aP2->Key2() == theIndex2)
-    {
-      myData2[aK2] = (IndexedMapNode *) aP2->Next2();
-    }
-    else
-    {
-      IndexedMapNode* aQ = aP2;
-      for (aP2 = aQ->Next2(); aP2->Key2() != theIndex2; aQ = aP2, aP2 = aQ->Next2()) { }
-
-      aQ->Next2() = aP2->Next2();
-    }
-
-    std::swap (aP1->Key2(),
-               aP2->Key2());
-
-    aP1->Next2() = (IndexedMapNode*) myData2[aK2];
-    myData2[aK2] = aP1;
-
-    aP2->Next2() = (IndexedMapNode*) myData2[aK1];
-    myData2[aK1] = aP2;
+    IndexedMapNode* aP1 = (IndexedMapNode* )myData2[theIndex1 - 1];
+    IndexedMapNode* aP2 = (IndexedMapNode* )myData2[theIndex2 - 1];
+    std::swap (aP1->Index(), aP2->Index());
+    myData2[theIndex2 - 1] = aP1;
+    myData2[theIndex1 - 1] = aP2;
   }
 
   //! RemoveLast
   void RemoveLast (void)
   {
-    Standard_OutOfRange_Raise_if (Extent() == 0, "NCollection_IndexedMap::RemoveLast");
+    const Standard_Integer aLastIndex = Extent();
+    Standard_OutOfRange_Raise_if (aLastIndex == 0, "NCollection_IndexedMap::RemoveLast");
 
-    IndexedMapNode * p, * q;
     // Find the node for the last index and remove it
-    Standard_Integer iK2 = ::HashCode (Extent(), NbBuckets());
-    p = (IndexedMapNode *) myData2[iK2];
-    q = NULL;
-    while (p) 
-    {
-      if (p->Key2() == Extent()) 
-        break;
-      q = p;
-      p = (IndexedMapNode*) p->Next2();
-    }
-    if (q == NULL) 
-      myData2[iK2] = (IndexedMapNode *) p->Next2();
-    else 
-      q->Next2() = p->Next2();
-    
+    IndexedMapNode* p = (IndexedMapNode* )myData2[aLastIndex - 1];
+    myData2[aLastIndex - 1] = NULL;
+
     // remove the key
     Standard_Integer iK1 = Hasher::HashCode (p->Key1(), NbBuckets());
-    q = (IndexedMapNode *) myData1[iK1];
+    IndexedMapNode* q = (IndexedMapNode *) myData1[iK1];
     if (q == p)
       myData1[iK1] = (IndexedMapNode *) p->Next();
     else 
@@ -404,12 +337,14 @@ public:
 
   //! Remove the key of the given index.
   //! Caution! The index of the last key can be changed.
-  void RemoveFromIndex(const Standard_Integer theKey2)
+  void RemoveFromIndex(const Standard_Integer theIndex)
   {
-    Standard_OutOfRange_Raise_if(theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedMap::Remove");
-    Standard_Integer aLastInd = Extent();
-    if (theKey2 != aLastInd)
-      Swap(theKey2, aLastInd);
+    Standard_OutOfRange_Raise_if(theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::RemoveFromIndex");
+    const Standard_Integer aLastInd = Extent();
+    if (theIndex != aLastInd)
+    {
+      Swap(theIndex, aLastInd);
+    }
     RemoveLast();
   }
 
@@ -428,35 +363,28 @@ public:
   }
 
   //! FindKey
-  const TheKeyType& FindKey (const Standard_Integer theKey2) const
+  const TheKeyType& FindKey (const Standard_Integer theIndex) const
   {
-    Standard_OutOfRange_Raise_if (theKey2 < 1 || theKey2 > Extent(), "NCollection_IndexedMap::FindKey");
-
-    IndexedMapNode * pNode2 =
-      (IndexedMapNode *) myData2[::HashCode(theKey2,NbBuckets())];
-    while (pNode2)
-    {
-      if (pNode2->Key2() == theKey2) 
-        return pNode2->Key1();
-      pNode2 = (IndexedMapNode*) pNode2->Next2();
-    }
-    throw Standard_NoSuchObject("NCollection_IndexedMap::FindKey");
+    Standard_OutOfRange_Raise_if (theIndex < 1 || theIndex > Extent(), "NCollection_IndexedMap::FindKey");
+    IndexedMapNode* pNode2 = (IndexedMapNode* )myData2[theIndex - 1];
+    return pNode2->Key1();
   }
 
   //! operator ()
-  const TheKeyType& operator() (const Standard_Integer theKey2) const
-  { return FindKey (theKey2); }
+  const TheKeyType& operator() (const Standard_Integer theIndex) const
+  { return FindKey (theIndex); }
 
   //! FindIndex
   Standard_Integer FindIndex(const TheKeyType& theKey1) const
   {
     if (IsEmpty()) return 0;
-    IndexedMapNode * pNode1 = 
-      (IndexedMapNode *) myData1[Hasher::HashCode(theKey1,NbBuckets())];
+    IndexedMapNode* pNode1 = (IndexedMapNode* )myData1[Hasher::HashCode(theKey1,NbBuckets())];
     while (pNode1)
     {
-      if (Hasher::IsEqual (pNode1->Key1(), theKey1)) 
-        return pNode1->Key2();
+      if (Hasher::IsEqual (pNode1->Key1(), theKey1))
+      {
+        return pNode1->Index();
+      }
       pNode1 = (IndexedMapNode*) pNode1->Next();
     }
     return 0;
index cede6e4..667b058 100644 (file)
 // Alternatively, this file may be used under the terms of Open CASCADE
 // commercial license or contractual agreement.
 
-
 #include <TCollection.hxx>
 
+#include <Standard_OutOfRange.hxx>
+
 // The array of prime numbers used as consequtive steps for 
 // size of array of buckets in the map.
 // The prime numbers are used for array size with the hope that this will 
 // memory overhead in that case is only ~15% as compared with total size of
 // all auxiliary data structures (each map node takes ~24 bytes), 
 // and this proves to pay off in performance (see OCC13189).
-#define NB_PRIMES 12
-static const Standard_Integer Primes[NB_PRIMES+1] = {
-     101,
-    1009,
-    2003,
-    5003,
-   10007,
-   20011,
-   37003,
-   57037,
-   65003,
-  100019,
-  209953,   // The following are Pierpont primes taken from Wikipedia [List of prime numbers]
-  472393,
-  995329
-};  
+#define THE_NB_PRIMES 24
+static const Standard_Integer THE_TCollection_Primes[THE_NB_PRIMES] =
+{
+         101,
+        1009,
+        2003,
+        5003,
+       10007,
+       20011,
+       37003,
+       57037,
+       65003,
+      100019,
+      209953, // The following are Pierpont primes [List of prime numbers]
+      472393,
+      995329,
+     2359297,
+     4478977,
+     9437185,
+    17915905,
+    35831809,
+    71663617,
+   150994945,
+   301989889,
+   573308929,
+  1019215873,
+  2038431745
+};
 
+// =======================================================================
+// function : NextPrimeForMap
+// purpose  :
+// =======================================================================
 Standard_Integer TCollection::NextPrimeForMap(const Standard_Integer N)
 {
-  Standard_Integer i;
-  for (i = 0; i < NB_PRIMES; i++) 
-    if (Primes[i] > N) break;
-  return Primes[i];
+  for (Standard_Integer aPrimeIter = 0; aPrimeIter < THE_NB_PRIMES; ++aPrimeIter)
+  {
+    if (THE_TCollection_Primes[aPrimeIter] > N)
+    {
+      return THE_TCollection_Primes[aPrimeIter];
+    }
+  }
+  throw Standard_OutOfRange ("TCollection::NextPrimeForMap() - requested too big size");
 }