1f1b30cc6ac1582a9762dcdb69fddd0cb4483b49
[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 <NCollection_BaseAllocator.hxx>
21 #include <stddef.h>
22
23 #include <Standard_OutOfRange.hxx>
24
25 #if defined(_MSC_VER)
26   #pragma warning(push, 1)
27   #pragma warning(disable:4355)
28 #endif
29
30 // this value defines the number of blocks that are reserved
31 // when the capacity of vector is increased
32 inline Standard_Integer GetCapacity (const Standard_Integer theIncrement)
33 {
34   return Max(theIncrement/8, 1);
35 }
36
37 //! Class NCollection_BaseVector - base for NCollection_Vector template
38 class NCollection_BaseVector
39 {
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     virtual 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     virtual 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 theAllocator  Memory allocator to use
148   //! @param theCapacity   Number of memory blocks in array
149   //! @param theSource     Original array of memory blocks, will be automatically deallocated
150   //! @param theSourceSize Number of memory blocks in original array
151   Standard_EXPORT static MemBlock* allocMemBlocks (Handle(NCollection_BaseAllocator)& theAllocator,
152                                                    const Standard_Integer             theCapacity,
153                                                    MemBlock*                          theSource     = NULL,
154                                                    const Standard_Integer             theSourceSize = 0);
155
156 protected: //! @name protected methods
157
158   //! Empty constructor
159   NCollection_BaseVector (Handle(NCollection_BaseAllocator)& theAllocator,
160                           initMemBlocks_t                    theInitBlocks,
161                           const size_t                       theSize,
162                           const Standard_Integer             theInc)
163   : myItemSize   (theSize),
164     myIncrement  (theInc),
165     myLength     (0),
166     myCapacity   (GetCapacity (myIncrement)),
167     myNBlocks    (0),
168     myData       (allocMemBlocks (theAllocator, myCapacity)),
169     myInitBlocks (theInitBlocks) {}
170
171   //! Copy constructor
172   NCollection_BaseVector (Handle(NCollection_BaseAllocator)& theAllocator,
173                           initMemBlocks_t                    theInitBlocks,
174                           const NCollection_BaseVector&      theOther)
175   : myItemSize   (theOther.myItemSize),
176     myIncrement  (theOther.myIncrement),
177     myLength     (theOther.myLength),
178     myCapacity   (GetCapacity(myIncrement) + theOther.myLength / theOther.myIncrement),
179     myNBlocks    (1 + (theOther.myLength - 1)/theOther.myIncrement),
180     myData       (allocMemBlocks (theAllocator, myCapacity)),
181     myInitBlocks (theInitBlocks) {}
182
183   //! @return pointer to memory where to put the new item
184   Standard_EXPORT void* expandV (Handle(NCollection_BaseAllocator)& theAllocator,
185                                  const Standard_Integer             theIndex);
186
187   //! Locate the memory holding the desired value
188   inline void* findV (const Standard_Integer theIndex) const
189   {
190     Standard_OutOfRange_Raise_if (theIndex < 0 || theIndex >= myLength,
191                                   "NCollection_BaseVector::findV");
192     const Standard_Integer aBlock = theIndex / myIncrement;
193     return myData[aBlock].findV (theIndex - aBlock * myIncrement, myItemSize);
194   }
195
196 public: //! @name public API
197
198   //! Empty the vector of its objects
199   Standard_EXPORT void Clear();
200
201 protected: //! @name Private fields
202
203   size_t           myItemSize;
204   Standard_Integer myIncrement;
205   Standard_Integer myLength;
206   Standard_Integer myCapacity;
207   Standard_Integer myNBlocks;
208   MemBlock*        myData;
209   initMemBlocks_t  myInitBlocks;
210
211 protected:
212
213   friend class Iterator;
214
215 };
216
217 #if defined(_MSC_VER)
218   #pragma warning(pop)
219 #endif
220
221 #endif // NCollection_BaseVector_HeaderFile