1 // File: NCollection_BaseVector.cxx
2 // Created: 24.04.02 10:07:15
3 // Author: Alexander GRIGORIEV
4 // Copyright: Open Cascade 2002
6 #include <NCollection_BaseVector.hxx>
7 #include <Standard_RangeError.hxx>
9 #include <Standard_OutOfRange.hxx>
13 //=======================================================================
14 //function : GetIndexV
16 //=======================================================================
18 Standard_Integer NCollection_BaseVector::MemBlock::GetIndexV
19 (void * theItem, const size_t theItemSize) const
21 const ptrdiff_t anOffset = (char *) theItem - (char *) myData;
22 const Standard_Integer anIndex = anOffset / theItemSize;
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");
29 return anIndex + myFirstInd;
32 //=======================================================================
33 //function : ~NCollection_BaseVector
34 //purpose : Destructor
35 //=======================================================================
37 NCollection_BaseVector::~NCollection_BaseVector()
39 for (Standard_Integer i = 0; i < myCapacity; i++)
40 myData[i].Reinit (0, 0);
41 myDataFree (* this, myData);
44 //=======================================================================
47 //=======================================================================
49 void NCollection_BaseVector::Clear()
52 for (Standard_Integer i = 0; i < myCapacity; i++)
53 myData[i].Reinit (0, 0);
59 //=======================================================================
60 //function : NCollection_BaseVector::Iterator::CopyV
61 //purpose : Copy from another iterator
62 //=======================================================================
64 void NCollection_BaseVector::Iterator::CopyV
65 (const NCollection_BaseVector::Iterator& theOth)
67 myVector = theOth.myVector;
68 myICurBlock = theOth.myICurBlock;
69 myIEndBlock = theOth.myIEndBlock;
70 myCurIndex = theOth.myCurIndex;
71 myEndIndex = theOth.myEndIndex;
74 //=======================================================================
76 //purpose : Initialisation of iterator by a vector
77 //=======================================================================
79 void NCollection_BaseVector::Iterator::InitV
80 (const NCollection_BaseVector& theVector)
82 myVector = &theVector;
85 if (theVector.myNBlocks == 0) {
89 myIEndBlock = theVector.myNBlocks - 1;
90 myEndIndex = theVector.myData[myIEndBlock].Length();
94 //=======================================================================
95 //function : operator =
96 //purpose : assignment
97 //=======================================================================
99 NCollection_BaseVector& NCollection_BaseVector::operator =
100 (const NCollection_BaseVector& theOther)
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);
115 //=======================================================================
117 //purpose : returns the pointer where the new data item is supposed to be put
118 //=======================================================================
120 void * NCollection_BaseVector::ExpandV (const Standard_Integer theIndex)
122 const Standard_Integer aNewLength = theIndex + 1;
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);
135 myLength = aLastBlock.FirstIndex() + aLastBlock.Size();
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
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);
152 // Change length of old last block to myIncrement
153 MemBlock * aLastBlock = (MemBlock *) &myData[myNBlocks-1];
154 aLastBlock -> SetLength (myIncrement);
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);
165 aNewBlock -> SetLength (aNewLength - myLength);
166 myLength = aNewLength;
167 return aNewBlock -> Find (theIndex - aNewBlock -> FirstIndex(), myItemSize);
170 //=======================================================================
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
181 if (theIndex < 0 || theIndex >= myLength) Standard_OutOfRange::Raise (NULL);
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;
190 Standard_Integer aMid = (aLow + anUp)/2;
191 if (aMid == aLow) break;
192 if (ptrArrays[aMid].FirstIndex() > theIndex)
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);