5b86bdb29cf3ac8d98b74928055f85408fb6940a
[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   for (Standard_Integer i = 0; i < myCapacity; i++)
52     myData[i].Reinit (0, 0);
53   myLength = 0;
54   myNBlocks = 0;
55 }
56
57 //=======================================================================
58 //function : NCollection_BaseVector::Iterator::CopyV
59 //purpose  : Copy from another iterator
60 //=======================================================================
61
62 void NCollection_BaseVector::Iterator::CopyV
63                                 (const NCollection_BaseVector::Iterator& theOth)
64 {
65   myVector      = theOth.myVector;
66   myICurBlock   = theOth.myICurBlock;
67   myIEndBlock   = theOth.myIEndBlock;
68   myCurIndex    = theOth.myCurIndex;
69   myEndIndex    = theOth.myEndIndex;
70 }
71
72 //=======================================================================
73 //function : InitV
74 //purpose  : Initialisation of iterator by a vector
75 //=======================================================================
76
77 void NCollection_BaseVector::Iterator::InitV
78                                       (const NCollection_BaseVector& theVector)
79 {
80   myVector      = &theVector;
81   myICurBlock   = 0;
82   myCurIndex    = 0;
83   if (theVector.myNBlocks == 0) {
84     myIEndBlock   = 0;
85     myEndIndex    = 0;
86   } else {
87     myIEndBlock   = theVector.myNBlocks - 1;
88     myEndIndex    = theVector.myData[myIEndBlock].Length();
89   }
90 }
91
92 //=======================================================================
93 //function : operator =
94 //purpose  : assignment
95 //=======================================================================
96
97 NCollection_BaseVector& NCollection_BaseVector::operator =
98                                         (const NCollection_BaseVector& theOther)
99 {
100 //    if (this != &theOther) {
101   myIncrement = theOther.myIncrement;
102   myLength    = theOther.Length();
103   myNBlocks   = (myLength == 0) ? 0 : (1 + (myLength - 1)/myIncrement);
104   for (Standard_Integer i = 0; i < myCapacity; i++)
105     myData[i].Reinit (0, 0);
106   myDataFree (* this, myData);
107   myCapacity  = myIncrement + myLength / myIncrement;
108   myData = myDataInit (* this, myCapacity, NULL, 0);
109 //    }
110   return * this;
111 }
112
113 //=======================================================================
114 //function : ExpandV
115 //purpose  : returns the pointer where the new data item is supposed to be put
116 //=======================================================================
117
118 void * NCollection_BaseVector::ExpandV (const Standard_Integer theIndex)
119 {
120   const Standard_Integer aNewLength = theIndex + 1;
121   if (myNBlocks) {
122     //  Take the last array in the vector of arrays
123     MemBlock& aLastBlock = myData [myNBlocks - 1];
124     Standard_RangeError_Raise_if (theIndex < aLastBlock.FirstIndex(),
125                                   "NColelction_BaseVector::ExpandV");
126     const unsigned int anIndLastBlock = theIndex - aLastBlock.FirstIndex();
127     //  Is there still room for 1 item in the last array?
128     if (anIndLastBlock < aLastBlock.Size()) {
129       myLength = aNewLength;
130       aLastBlock.SetLength (anIndLastBlock + 1);
131       return aLastBlock.Find (anIndLastBlock, myItemSize);
132     }
133     myLength = aLastBlock.FirstIndex() + aLastBlock.Size();
134   }
135
136   //    There is no room in the last array or the whole vector
137   //    is not yet initialised. Initialise a new array, but before that
138   //    check whether it is available within myCapacity
139
140   const Standard_Integer nNewBlock =
141     myNBlocks + 1 + (theIndex - myLength) / myIncrement;
142   if (myCapacity < nNewBlock) {
143     // Reallocate the array myData 
144     do myCapacity += myIncrement; while (myCapacity <= nNewBlock);
145     MemBlock * aNewData = myDataInit (* this, myCapacity, myData, myNBlocks);
146     myDataFree (* this, myData);
147     myData = aNewData;
148   }
149   if (myNBlocks > 0) {
150     // Change length of old last block to myIncrement
151     MemBlock * aLastBlock = (MemBlock *) &myData[myNBlocks-1];
152     aLastBlock -> SetLength (myIncrement);
153   }
154   // Initialise new blocks
155   MemBlock * aNewBlock = (MemBlock *) &myData[myNBlocks++];
156   aNewBlock -> Reinit (myLength, myIncrement);
157   while (myNBlocks < nNewBlock) {
158     aNewBlock -> SetLength (myIncrement);
159     myLength += myIncrement;
160     aNewBlock = (MemBlock *) &myData[myNBlocks++];
161     aNewBlock -> Reinit (myLength, myIncrement);
162   }
163   aNewBlock -> SetLength (aNewLength - myLength);
164   myLength = aNewLength;
165   return aNewBlock -> Find (theIndex - aNewBlock -> FirstIndex(), myItemSize);
166 }
167
168 //=======================================================================
169 //function : Find
170 //purpose  : locate the memory holding the desired value
171 //remark   : This is only useful when the blocks can have holes (i.e., deletion
172 //           is enabled at any location)
173 //         : Currently this method is replaced by a direct one (inline)
174 //=======================================================================
175 #ifdef THIS_IS_NOW_DISABLED
176 void * NCollection_BaseVector::Find (const Standard_Integer theIndex) const
177 {
178 #ifdef DEB
179   if (theIndex < 0 || theIndex >= myLength) Standard_OutOfRange::Raise (NULL);
180 #endif
181   //    Binary search for the last memory block whose 'FirstIndex'
182   //    is not greater than 'theIndex'
183   const MemBlock * ptrArrays = myData;
184   Standard_Integer aLow = 0;
185   Standard_Integer anUp = myNBlocks-1;
186   if (theIndex >= ptrArrays[anUp].FirstIndex()) aLow = anUp;
187   else while (1) {
188     Standard_Integer aMid = (aLow + anUp)/2;
189     if (aMid == aLow) break;
190     if (ptrArrays[aMid].FirstIndex() > theIndex)
191       anUp = aMid;
192     else
193       aLow = aMid;
194   }
195
196   //    Find the item at the proper offset in the found MemBlock-type block
197   const Standard_Integer anOffset = theIndex - ptrArrays[aLow].FirstIndex();
198   return ptrArrays[aLow].Find (anOffset, myItemSize);
199 }
200 #endif