OCC22143 Optimization of memory usage and developing tools for catching memory leaks...
[occt.git] / src / NCollection / NCollection_BaseVector.cxx
1 // File:      NCollection_BaseVector.cxx
2 // Created:   24.04.02 10:07:15
3 // Author:    Alexander GRIGORIEV
4 // Copyright: Open Cascade 2002
5
6 #include <NCollection_BaseVector.hxx>
7 #include <Standard_RangeError.hxx>
8 #ifdef DEB
9 #include <Standard_OutOfRange.hxx>
10 #endif
11 #include <stdlib.h>
12
13 //=======================================================================
14 //function : GetIndexV
15 //purpose  : 
16 //=======================================================================
17
18 Standard_Integer NCollection_BaseVector::MemBlock::GetIndexV
19                    (void * theItem, const size_t theItemSize) const
20 {
21   const ptrdiff_t anOffset = (char *) theItem - (char *) myData;
22   const Standard_Integer anIndex = anOffset / theItemSize;
23 #ifdef DEB
24   if (anOffset < 0 || anOffset != Standard_Integer (anIndex * theItemSize)
25       || anIndex > Standard_Integer (myLength))
26     Standard_OutOfRange::Raise ("NCollection_BaseVector: "
27                                 "Wrong object passed to GetIndex");
28 #endif
29   return anIndex + myFirstInd;
30 }
31
32 //=======================================================================
33 //function : ~NCollection_BaseVector
34 //purpose  : Destructor
35 //=======================================================================
36
37 NCollection_BaseVector::~NCollection_BaseVector()
38 {
39   for (Standard_Integer i = 0; i < myCapacity; i++)
40     myData[i].Reinit (0, 0);
41   myDataFree (* this, myData);
42 }
43
44 //=======================================================================
45 //function : Clear
46 //purpose  : 
47 //=======================================================================
48
49 void NCollection_BaseVector::Clear()
50 {
51   if (myLength > 0) {
52     for (Standard_Integer i = 0; i < myCapacity; i++)
53       myData[i].Reinit (0, 0);
54     myLength = 0;
55     myNBlocks = 0;
56   }
57 }
58
59 //=======================================================================
60 //function : NCollection_BaseVector::Iterator::CopyV
61 //purpose  : Copy from another iterator
62 //=======================================================================
63
64 void NCollection_BaseVector::Iterator::CopyV
65                                 (const NCollection_BaseVector::Iterator& theOth)
66 {
67   myVector      = theOth.myVector;
68   myICurBlock   = theOth.myICurBlock;
69   myIEndBlock   = theOth.myIEndBlock;
70   myCurIndex    = theOth.myCurIndex;
71   myEndIndex    = theOth.myEndIndex;
72 }
73
74 //=======================================================================
75 //function : InitV
76 //purpose  : Initialisation of iterator by a vector
77 //=======================================================================
78
79 void NCollection_BaseVector::Iterator::InitV
80                                       (const NCollection_BaseVector& theVector)
81 {
82   myVector      = &theVector;
83   myICurBlock   = 0;
84   myCurIndex    = 0;
85   if (theVector.myNBlocks == 0) {
86     myIEndBlock   = 0;
87     myEndIndex    = 0;
88   } else {
89     myIEndBlock   = theVector.myNBlocks - 1;
90     myEndIndex    = theVector.myData[myIEndBlock].Length();
91   }
92 }
93
94 //=======================================================================
95 //function : operator =
96 //purpose  : assignment
97 //=======================================================================
98
99 NCollection_BaseVector& NCollection_BaseVector::operator =
100                                         (const NCollection_BaseVector& theOther)
101 {
102 //    if (this != &theOther) {
103   myIncrement = theOther.myIncrement;
104   myLength    = theOther.Length();
105   myNBlocks   = (myLength == 0) ? 0 : (1 + (myLength - 1)/myIncrement);
106   for (Standard_Integer i = 0; i < myCapacity; i++)
107     myData[i].Reinit (0, 0);
108   myDataFree (* this, myData);
109   myCapacity  = GetCapacity(myIncrement) + myLength / myIncrement;
110   myData = myDataInit (* this, myCapacity, NULL, 0);
111 //    }
112   return * this;
113 }
114
115 //=======================================================================
116 //function : ExpandV
117 //purpose  : returns the pointer where the new data item is supposed to be put
118 //=======================================================================
119
120 void * NCollection_BaseVector::ExpandV (const Standard_Integer theIndex)
121 {
122   const Standard_Integer aNewLength = theIndex + 1;
123   if (myNBlocks) {
124     //  Take the last array in the vector of arrays
125     MemBlock& aLastBlock = myData [myNBlocks - 1];
126     Standard_RangeError_Raise_if (theIndex < aLastBlock.FirstIndex(),
127                                   "NColelction_BaseVector::ExpandV");
128     const unsigned int anIndLastBlock = theIndex - aLastBlock.FirstIndex();
129     //  Is there still room for 1 item in the last array?
130     if (anIndLastBlock < aLastBlock.Size()) {
131       myLength = aNewLength;
132       aLastBlock.SetLength (anIndLastBlock + 1);
133       return aLastBlock.Find (anIndLastBlock, myItemSize);
134     }
135     myLength = aLastBlock.FirstIndex() + aLastBlock.Size();
136   }
137
138   //    There is no room in the last array or the whole vector
139   //    is not yet initialised. Initialise a new array, but before that
140   //    check whether it is available within myCapacity
141
142   const Standard_Integer nNewBlock =
143     myNBlocks + 1 + (theIndex - myLength) / myIncrement;
144   if (myCapacity < nNewBlock) {
145     // Reallocate the array myData 
146     do myCapacity += GetCapacity(myIncrement); while (myCapacity <= nNewBlock);
147     MemBlock * aNewData = myDataInit (* this, myCapacity, myData, myNBlocks);
148     myDataFree (* this, myData);
149     myData = aNewData;
150   }
151   if (myNBlocks > 0) {
152     // Change length of old last block to myIncrement
153     MemBlock * aLastBlock = (MemBlock *) &myData[myNBlocks-1];
154     aLastBlock -> SetLength (myIncrement);
155   }
156   // Initialise new blocks
157   MemBlock * aNewBlock = (MemBlock *) &myData[myNBlocks++];
158   aNewBlock -> Reinit (myLength, myIncrement);
159   while (myNBlocks < nNewBlock) {
160     aNewBlock -> SetLength (myIncrement);
161     myLength += myIncrement;
162     aNewBlock = (MemBlock *) &myData[myNBlocks++];
163     aNewBlock -> Reinit (myLength, myIncrement);
164   }
165   aNewBlock -> SetLength (aNewLength - myLength);
166   myLength = aNewLength;
167   return aNewBlock -> Find (theIndex - aNewBlock -> FirstIndex(), myItemSize);
168 }
169
170 //=======================================================================
171 //function : Find
172 //purpose  : locate the memory holding the desired value
173 //remark   : This is only useful when the blocks can have holes (i.e., deletion
174 //           is enabled at any location)
175 //         : Currently this method is replaced by a direct one (inline)
176 //=======================================================================
177 #ifdef THIS_IS_NOW_DISABLED
178 void * NCollection_BaseVector::Find (const Standard_Integer theIndex) const
179 {
180 #ifdef DEB
181   if (theIndex < 0 || theIndex >= myLength) Standard_OutOfRange::Raise (NULL);
182 #endif
183   //    Binary search for the last memory block whose 'FirstIndex'
184   //    is not greater than 'theIndex'
185   const MemBlock * ptrArrays = myData;
186   Standard_Integer aLow = 0;
187   Standard_Integer anUp = myNBlocks-1;
188   if (theIndex >= ptrArrays[anUp].FirstIndex()) aLow = anUp;
189   else while (1) {
190     Standard_Integer aMid = (aLow + anUp)/2;
191     if (aMid == aLow) break;
192     if (ptrArrays[aMid].FirstIndex() > theIndex)
193       anUp = aMid;
194     else
195       aLow = aMid;
196   }
197
198   //    Find the item at the proper offset in the found MemBlock-type block
199   const Standard_Integer anOffset = theIndex - ptrArrays[aLow].FirstIndex();
200   return ptrArrays[aLow].Find (anOffset, myItemSize);
201 }
202 #endif