0027794: A danger in the 'NCollection_Vector' initializing constructor
[occt.git] / src / NCollection / NCollection_Vector.hxx
1 // Created on: 2002-04-23
2 // Created by: Alexander GRIGORIEV
3 // Copyright (c) 2002-2013 OPEN CASCADE SAS
4 //
5 // This file is part of Open CASCADE Technology software library.
6 //
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
12 //
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
15
16 #ifndef NCollection_Vector_HeaderFile
17 #define NCollection_Vector_HeaderFile
18
19 #include <NCollection_BaseVector.hxx>
20 #include <NCollection_StlIterator.hxx>
21
22 //! Class NCollection_Vector (dynamic array of objects)
23 //!
24 //! This class is similar to NCollection_Array1  though the indices always start
25 //! at 0 (in Array1 the first index must be specified)
26 //!
27 //! The Vector is always created with 0 length. It can be enlarged by two means:
28 //!  1. Calling the method Append (val) - then "val" is added to the end of the
29 //!     vector (the vector length is incremented)
30 //!  2. Calling the method SetValue (i, val)  - if "i" is greater than or equal
31 //!     to the current length of the vector,  the vector is enlarged to accomo-
32 //!     date this index
33 //!
34 //! The methods Append and SetValue return  a non-const reference  to the copied
35 //! object  inside  the vector.  This reference  is guaranteed to be valid until
36 //! the vector is destroyed. It can be used to access the vector member directly
37 //! or to pass its address to other data structures.
38 //!
39 //! The vector iterator remembers the length of the vector  at the moment of the
40 //! creation or initialisation of the iterator.   Therefore the iteration begins
41 //! at index 0  and stops at the index equal to (remembered_length-1).  It is OK
42 //! to enlarge the vector during the iteration.
43 template <class TheItemType>
44 class NCollection_Vector : public NCollection_BaseVector
45 {
46 public:
47   //! STL-compliant typedef for value type
48   typedef TheItemType value_type;
49
50 public:
51
52   //! Nested class Iterator
53   class Iterator : public NCollection_BaseVector::Iterator
54   {
55   public:
56
57     //! Empty constructor - for later Init
58     Iterator() {}
59
60     //! Constructor with initialisation
61     Iterator (const NCollection_Vector& theVector, Standard_Boolean theToEnd = Standard_False)
62     : NCollection_BaseVector::Iterator (theVector, theToEnd) {}
63
64     //! Copy constructor
65     Iterator (const Iterator& theOther)
66     : NCollection_BaseVector::Iterator (theOther) {}
67
68     //! Initialisation
69     void Init (const NCollection_Vector& theVector)
70     {
71       initV (theVector);
72     }
73
74     //! Assignment
75     Iterator& operator= (const Iterator& theOther)
76     {
77       copyV (theOther);
78       return *this;
79     }
80
81     //! Check end
82     Standard_Boolean More() const
83     {
84       return moreV();
85     }
86
87     //! Increment operator.
88     void Next()
89     {
90       nextV();
91     }
92
93     //! Decrement operator.
94     void Previous()
95     {
96       prevV();
97     }
98
99     //! Offset operator.
100     void Offset (ptrdiff_t theOffset)
101     {
102       offsetV (static_cast<int>(theOffset));
103     }
104
105     //! Difference operator.
106     ptrdiff_t Differ (const Iterator& theOther) const
107     {
108       return differV (theOther);
109     }
110
111     //! Constant value access
112     const TheItemType& Value() const
113     {
114       return ((const TheItemType* )curBlockV()->DataPtr)[myCurIndex];
115     }
116
117     //! Variable value access
118     TheItemType& ChangeValue() const
119     {
120       return ((TheItemType* )curBlockV()->DataPtr)[myCurIndex];
121     }
122
123     //! Performs comparison of two iterators.
124     Standard_Boolean IsEqual (const Iterator& theOther) const
125     {
126       return myVector    == theOther.myVector
127           && myCurIndex  == theOther.myCurIndex
128           && myEndIndex  == theOther.myEndIndex  
129           && myICurBlock == theOther.myICurBlock
130           && myIEndBlock == theOther.myIEndBlock;
131     }
132   };
133
134   //! Shorthand for a regular iterator type.
135   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, false> iterator;
136
137   //! Shorthand for a constant iterator type.
138   typedef NCollection_StlIterator<std::random_access_iterator_tag, Iterator, TheItemType, true> const_iterator;
139
140   //! Returns an iterator pointing to the first element in the vector.
141   iterator begin() const { return Iterator (*this, false); }
142
143   //! Returns an iterator referring to the past-the-end element in the vector.
144   iterator end() const { return Iterator (*this, true); }
145
146   //! Returns a const iterator pointing to the first element in the vector.
147   const_iterator cbegin() const { return Iterator (*this, false); }
148
149   //! Returns a const iterator referring to the past-the-end element in the vector.
150   const_iterator cend() const { return Iterator (*this, true); }
151
152 public: //! @name public methods
153
154   //! Constructor
155   explicit NCollection_Vector (const Standard_Integer theIncrement              = 256,
156                                const Handle(NCollection_BaseAllocator)& theAlloc = NULL) :
157     NCollection_BaseVector (theAlloc, initMemBlocks, sizeof(TheItemType), theIncrement)
158   {}
159
160   //! Copy constructor
161   NCollection_Vector (const NCollection_Vector& theOther) :
162     NCollection_BaseVector (theOther.myAllocator, initMemBlocks, theOther)
163   {
164     copyData (theOther);
165   }
166
167   //! Destructor
168   virtual ~NCollection_Vector()
169   {
170     for (Standard_Integer anItemIter = 0; anItemIter < myCapacity; ++anItemIter)
171     {
172       initMemBlocks (*this, myData[anItemIter], 0, 0);
173     }
174     this->myAllocator->Free (myData);
175   }
176
177   //! Total number of items
178   Standard_Integer Length() const
179   {
180     return myLength;
181   }
182
183   //! Total number of items in the vector
184   Standard_Integer Size() const
185   {
186     return myLength;
187   }
188
189   //! Method for consistency with other collections.
190   //! @return Lower bound (inclusive) for iteration.
191   Standard_Integer Lower() const
192   {
193     return 0;
194   }
195
196   //! Method for consistency with other collections.
197   //! @return Upper bound (inclusive) for iteration.
198   Standard_Integer Upper() const
199   {
200     return myLength - 1;
201   }
202
203   //! Empty query
204   Standard_Boolean IsEmpty() const
205   {
206     return (myLength == 0);
207   }
208
209   //! Assignment to the collection of the same type
210   inline void Assign (const NCollection_Vector& theOther,
211                       const Standard_Boolean theOwnAllocator = Standard_True);
212
213   //! Assignment operator
214   NCollection_Vector& operator= (const NCollection_Vector& theOther)
215   {
216     Assign (theOther, Standard_False);
217     return *this;
218   }
219
220   //! Append
221   TheItemType& Append (const TheItemType& theValue)
222   {
223     TheItemType& anAppended = *(TheItemType* )expandV (myLength);
224     anAppended = theValue;
225     return anAppended;
226   }
227
228   //! Operator() - query the const value
229   const TheItemType& operator() (const Standard_Integer theIndex) const
230   {
231     return Value (theIndex);
232   }
233
234   const TheItemType& Value (const Standard_Integer theIndex) const
235   {
236     return *(const TheItemType* )findV (theIndex);
237   }
238
239   //! @return first element
240   const TheItemType& First() const
241   {
242     return *(const TheItemType* )findV (Lower());
243   }
244
245   //! @return first element
246   TheItemType& ChangeFirst()
247   {
248     return *(TheItemType* )findV (Lower());
249   }
250
251   //! @return last element
252   const TheItemType& Last() const
253   {
254     return *(const TheItemType* )findV (Upper());
255   }
256
257   //! @return last element
258   TheItemType& ChangeLast()
259   {
260     return *(TheItemType* )findV (Upper());
261   }
262
263   //! Operator() - query the value
264   TheItemType& operator() (const Standard_Integer theIndex)
265   {
266     return ChangeValue (theIndex);
267   }
268
269   TheItemType& ChangeValue (const Standard_Integer theIndex)
270   {
271     return *(TheItemType* )findV (theIndex);
272   }
273
274   //! SetValue () - set or append a value
275   TheItemType& SetValue (const Standard_Integer theIndex,
276                          const TheItemType&     theValue)
277   {
278     Standard_OutOfRange_Raise_if (theIndex < 0, "NCollection_Vector::SetValue");
279     TheItemType* const aVecValue = (TheItemType* )(theIndex < myLength ? findV (theIndex) : expandV (theIndex));
280     *aVecValue = theValue;
281     return *aVecValue;
282   }
283
284 private: //! @name private methods
285
286   void copyData (const NCollection_Vector& theOther)
287   {
288     Standard_Integer iBlock = 0;
289     /*NCollection_Vector::*/Iterator anIter (theOther);
290     for (Standard_Integer aLength = 0; aLength < myLength; aLength += myIncrement)
291     {
292       MemBlock& aBlock = myData[iBlock];
293       initMemBlocks (*this, aBlock, aLength, myIncrement);
294       Standard_Integer anItemIter = 0;
295       for (; anItemIter < myIncrement; ++anItemIter)
296       {
297         if (!anIter.More())
298         {
299           break;
300         }
301
302         ((TheItemType* )aBlock.DataPtr)[anItemIter] = anIter.Value();
303         anIter.Next();
304       }
305       aBlock.Length = anItemIter;
306       iBlock++;
307     }
308   }
309
310   //! Method to initialize memory block content
311   static void initMemBlocks (NCollection_BaseVector&           theVector,
312                              NCollection_BaseVector::MemBlock& theBlock,
313                              const Standard_Integer            theFirst,
314                              const Standard_Integer            theSize)
315   {
316     NCollection_Vector& aSelf = static_cast<NCollection_Vector&> (theVector);
317     Handle(NCollection_BaseAllocator)& anAllocator = aSelf.myAllocator;
318
319     // release current content
320     if (theBlock.DataPtr != NULL)
321     {
322       for (Standard_Integer anItemIter = 0; anItemIter < theBlock.Size; ++anItemIter)
323       {
324         ((TheItemType* )theBlock.DataPtr)[anItemIter].~TheItemType();
325       }
326       anAllocator->Free (theBlock.DataPtr);
327       theBlock.DataPtr = NULL;
328     }
329
330     // allocate new content if requested
331     if (theSize > 0)
332     {
333       theBlock.DataPtr = anAllocator->Allocate (theSize * sizeof(TheItemType));
334       for (Standard_Integer anItemIter = 0; anItemIter < theSize; ++anItemIter)
335       {
336         new (&((TheItemType* )theBlock.DataPtr)[anItemIter]) TheItemType;
337       }
338     }
339     theBlock.FirstIndex = theFirst;
340     theBlock.Size       = theSize;
341     theBlock.Length     = 0;
342   }
343
344   friend class Iterator;
345
346 };
347
348 //! Assignment to the collection of the same type
349 template <class TheItemType> inline
350 void NCollection_Vector<TheItemType>::Assign (const NCollection_Vector& theOther,
351                                               const Standard_Boolean    theOwnAllocator)
352 {
353   if (this == &theOther)
354   {
355     return;
356   }
357
358   // destroy current data using current allocator
359   for (Standard_Integer anItemIter = 0; anItemIter < myCapacity; ++anItemIter)
360   {
361     initMemBlocks (*this, myData[anItemIter], 0, 0);
362   }
363   this->myAllocator->Free (myData);
364
365   // allocate memory blocks with new allocator
366   if (!theOwnAllocator)
367   {
368     this->myAllocator = theOther.myAllocator;
369   }
370   myIncrement = theOther.myIncrement;
371   myLength    = theOther.myLength;
372   myNBlocks   = (myLength == 0) ? 0 : (1 + (myLength - 1)/myIncrement);
373   myCapacity  = GetCapacity (myIncrement) + myLength / myIncrement;
374   myData      = allocMemBlocks (myCapacity);
375
376   // copy data
377   copyData (theOther);
378 }
379
380 #endif // NCollection_Vector_HeaderFile