0024911: Avoid using virtual functions in NCollection classes
[occt.git] / src / NCollection / NCollection_BaseVector.hxx
1 // Created on: 2002-04-24
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_BaseVector_HeaderFile
17 #define NCollection_BaseVector_HeaderFile
18
19 #include <Standard_TypeDef.hxx>
20 #include <Standard_OutOfRange.hxx>
21 #include <NCollection_BaseAllocator.hxx>
22 #include <NCollection_DefineAlloc.hxx>
23
24 #include <stddef.h>
25
26 // this value defines the number of blocks that are reserved
27 // when the capacity of vector is increased
28 inline Standard_Integer GetCapacity (const Standard_Integer theIncrement)
29 {
30   return Max(theIncrement/8, 1);
31 }
32
33 //! Class NCollection_BaseVector - base for NCollection_Vector template
34 class NCollection_BaseVector
35 {
36 public:
37   //! Memory allocation
38   DEFINE_STANDARD_ALLOC
39   DEFINE_NCOLLECTION_ALLOC
40
41 protected:
42
43   // Auxiliary structure for memory blocks
44   struct MemBlock
45   {
46
47   public:
48
49     //! @param theIndex    Item index in the block
50     //! @param theItemSize Element size in bytes
51     //! @return the address of specified item in this memory block
52     void* findV (const Standard_Integer theIndex,
53                  const size_t           theItemSize) const
54     {
55       return (char* )DataPtr + size_t(theIndex) * theItemSize;
56     }
57
58   public:
59
60     void*            DataPtr;    //!< block of elements
61     Standard_Integer FirstIndex; //!< index of the first element (among all memory blocks in collection)
62     Standard_Integer Length;
63     Standard_Integer Size;
64
65   };
66
67   //! Base class for Iterator implementation
68   class Iterator
69   {
70   protected:
71     Iterator()
72     : myICurBlock (0),
73       myIEndBlock (0),
74       myCurIndex  (0),
75       myEndIndex  (0) {}
76
77     Iterator (const NCollection_BaseVector& theVector, Standard_Boolean theToEnd = Standard_False)
78     {
79       initV (theVector, theToEnd);
80     }
81
82     Iterator (const Iterator& theVector)
83     {
84       copyV (theVector);
85     }
86
87     Standard_EXPORT void initV (const NCollection_BaseVector& theVector, Standard_Boolean theToEnd = Standard_False);
88
89     Standard_EXPORT void copyV (const Iterator&);
90
91     Standard_Boolean moreV() const
92     {
93       return (myICurBlock < myIEndBlock || myCurIndex < myEndIndex);
94     }
95
96     void nextV()
97     {
98       if (++myCurIndex >= myVector->myData[myICurBlock].Length
99        && myICurBlock < myIEndBlock)
100       {
101         ++myICurBlock;
102         myCurIndex = 0;
103       }
104     }
105
106     void prevV()
107     {
108       if (--myCurIndex < 0 && myICurBlock > 0)
109       {
110         --myICurBlock;
111         myCurIndex = myVector->myData[myICurBlock].Length - 1;
112       }
113     }
114
115     void offsetV (Standard_Integer theOffset)
116     {
117       const Standard_Integer anIndex = myCurIndex + myICurBlock * myVector->myIncrement + theOffset;
118       myICurBlock = anIndex / myVector->myIncrement;
119       myCurIndex = anIndex % myVector->myIncrement;
120     }
121
122     Standard_Integer differV (const Iterator& theOther) const
123     {
124       return (myCurIndex - theOther.myCurIndex) + (myICurBlock - theOther.myICurBlock) * myVector->myIncrement;
125     }
126
127     const MemBlock* curBlockV() const
128     {
129       return &myVector->myData[myICurBlock];
130     }
131
132     const NCollection_BaseVector* myVector;    //!< the Master vector
133     Standard_Integer              myICurBlock; //!< # of the current block
134     Standard_Integer              myIEndBlock;
135     Standard_Integer              myCurIndex;  //!< Index in the current block
136     Standard_Integer              myEndIndex;
137   };
138
139 protected: //! @name Block initializer
140
141   typedef void (*initMemBlocks_t) (NCollection_BaseVector& theVector,
142                                    MemBlock&               theBlock,
143                                    const Standard_Integer  theFirst,
144                                    const Standard_Integer  theSize);
145
146   //! Allocate memory for array of memory blocks.
147   //! @param theCapacity   Number of memory blocks in array
148   //! @param theSource     Original array of memory blocks, will be automatically deallocated
149   //! @param theSourceSize Number of memory blocks in original array
150   Standard_EXPORT MemBlock* allocMemBlocks (const Standard_Integer theCapacity,
151                                             MemBlock*              theSource     = NULL,
152                                             const Standard_Integer theSourceSize = 0);
153
154 protected: //! @name protected methods
155
156   //! Empty constructor
157   NCollection_BaseVector (const Handle(NCollection_BaseAllocator)& theAllocator,
158                           initMemBlocks_t                    theInitBlocks,
159                           const size_t                       theSize,
160                           const Standard_Integer             theInc)
161   : myItemSize   (theSize),
162     myIncrement  (theInc),
163     myLength     (0),
164     myCapacity   (GetCapacity (myIncrement)),
165     myNBlocks    (0),
166     myInitBlocks (theInitBlocks)
167   {
168     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
169     myData = allocMemBlocks (myCapacity);
170   }
171
172   //! Copy constructor
173   NCollection_BaseVector (const Handle(NCollection_BaseAllocator)& theAllocator,
174                           initMemBlocks_t                    theInitBlocks,
175                           const NCollection_BaseVector&      theOther)
176   : myItemSize   (theOther.myItemSize),
177     myIncrement  (theOther.myIncrement),
178     myLength     (theOther.myLength),
179     myCapacity   (GetCapacity(myIncrement) + theOther.myLength / theOther.myIncrement),
180     myNBlocks    (1 + (theOther.myLength - 1)/theOther.myIncrement),
181     myInitBlocks (theInitBlocks)
182   {
183     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
184     myData = allocMemBlocks (myCapacity);
185   }
186
187   //! @return pointer to memory where to put the new item
188   Standard_EXPORT void* expandV (const Standard_Integer theIndex);
189
190   //! Locate the memory holding the desired value
191   inline void* findV (const Standard_Integer theIndex) const
192   {
193     Standard_OutOfRange_Raise_if (theIndex < 0 || theIndex >= myLength,
194                                   "NCollection_BaseVector::findV");
195     const Standard_Integer aBlock = theIndex / myIncrement;
196     return myData[aBlock].findV (theIndex - aBlock * myIncrement, myItemSize);
197   }
198
199 public: //! @name public API
200
201   //! Empty the vector of its objects
202   Standard_EXPORT void Clear();
203
204 protected: //! @name Protected fields
205
206   Handle(NCollection_BaseAllocator) myAllocator;
207   size_t           myItemSize;
208   Standard_Integer myIncrement;
209   Standard_Integer myLength;
210   Standard_Integer myCapacity;
211   Standard_Integer myNBlocks;
212   MemBlock*        myData;
213   initMemBlocks_t  myInitBlocks;
214
215 protected:
216
217   friend class Iterator;
218 };
219
220 #endif // NCollection_BaseVector_HeaderFile