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