Commit | Line | Data |
---|---|---|
b311480e | 1 | // Created on: 2007-01-23 |
2 | // Created by: Andrey BETENEV | |
3 | // Copyright (c) 2007-2012 OPEN CASCADE SAS | |
4 | // | |
5 | // The content of this file is subject to the Open CASCADE Technology Public | |
6 | // License Version 6.5 (the "License"). You may not use the content of this file | |
7 | // except in compliance with the License. Please obtain a copy of the License | |
8 | // at http://www.opencascade.org and read it completely before using this file. | |
9 | // | |
10 | // The Initial Developer of the Original Code is Open CASCADE S.A.S., having its | |
11 | // main offices at: 1, place des Freres Montgolfier, 78280 Guyancourt, France. | |
12 | // | |
13 | // The Original Code and all software distributed under the License is | |
14 | // distributed on an "AS IS" basis, without warranty of any kind, and the | |
15 | // Initial Developer hereby disclaims all such warranties, including without | |
16 | // limitation, any warranties of merchantability, fitness for a particular | |
17 | // purpose or non-infringement. Please see the License for the specific terms | |
18 | // and conditions governing the rights and limitations under the License. | |
19 | ||
7fd59977 | 20 | |
21 | #ifndef NCollection_SparseArrayBase_HeaderFile | |
22 | #define NCollection_SparseArrayBase_HeaderFile | |
23 | ||
24 | #include <Standard.hxx> | |
25 | #include <Standard_OutOfRange.hxx> | |
26 | ||
27 | typedef size_t Standard_Size; | |
28 | ||
29 | /** | |
30 | * Base class for NCollection_SparseArray; | |
31 | * provides non-template implementation of general mechanics | |
32 | * of block allocation, items creation / deletion etc. | |
33 | */ | |
34 | ||
35 | class NCollection_SparseArrayBase | |
36 | { | |
37 | public: | |
38 | //!@name Type-independent public interface | |
39 | //!@{ | |
40 | ||
41 | //! Clears all the data | |
42 | Standard_EXPORT void Clear (); | |
43 | ||
44 | //! Returns number of currently contained items | |
fb8a7358 | 45 | Standard_Size Size () const { return mySize; } |
7fd59977 | 46 | |
47 | //! Check whether the value at given index is set | |
d93f7683 | 48 | Standard_EXPORT Standard_Boolean HasValue (const Standard_Size theIndex) const; |
7fd59977 | 49 | |
50 | //! Deletes the item from the array; | |
51 | //! returns True if that item was defined | |
d93f7683 | 52 | Standard_EXPORT Standard_Boolean UnsetValue (const Standard_Size theIndex); |
7fd59977 | 53 | |
54 | //!@} | |
55 | ||
56 | #if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530) | |
57 | public: // work-around against obsolete SUN WorkShop 5.3 compiler | |
58 | #else | |
59 | private: | |
60 | #endif | |
61 | ||
62 | /** | |
63 | * The block of data contains array of items, counter | |
64 | * and bit field, allocated as single piece of memory addressed | |
65 | * from the blocks array (myData). | |
66 | * | |
67 | * The Block structure provides a logical view on the block, | |
68 | * and provides methods to work with bit map. | |
69 | * | |
70 | * Note that NCollection_SparseArrayBase class takes responsibility | |
71 | * for correct allocation/deallocation of all the data. | |
72 | */ | |
73 | ||
74 | class Block { | |
75 | public: | |
76 | ||
77 | typedef unsigned char Cell; //!< type of items used to hold bits | |
78 | ||
79 | //! Number of bits in each cell | |
80 | static Standard_Size BitsPerCell() { return sizeof(Cell) * 8/*BITSPERBYTE*/; } | |
81 | ||
82 | public: | |
83 | ||
84 | //! Initializes the block by pointer to block data | |
85 | Block (const Standard_Address theAddr, const Standard_Size theNbItems, | |
86 | const Standard_Size theItemSize) | |
87 | : Count((Standard_Size*)theAddr), | |
88 | Array((char*)theAddr + sizeof(Standard_Size)), | |
89 | Bits ((Cell*)((char*)theAddr + sizeof(Standard_Size) + theNbItems * theItemSize)) | |
90 | { | |
91 | } | |
92 | ||
93 | //! Compute required size for block data, in bytes | |
94 | static Standard_Size Size (const Standard_Size theNbItems, | |
95 | const Standard_Size theItemSize) | |
96 | { | |
97 | return sizeof(Standard_Size) + | |
98 | sizeof(Cell) * ( (theNbItems + BitsPerCell() - 1) / BitsPerCell() ) + | |
99 | theNbItems * theItemSize; | |
100 | } | |
101 | ||
102 | //! Returns address of array from address of block | |
103 | static char* ToArray (const Standard_Address theAddress, | |
104 | const Standard_Size /*theNbItems*/, | |
105 | const Standard_Size /*theItemSize*/) | |
106 | { | |
107 | return (char*)theAddress + sizeof(Standard_Size); | |
108 | } | |
109 | ||
110 | public: | |
111 | ||
112 | //! Set bit for i-th item; returns non-null if that bit has | |
113 | //! not been set previously | |
114 | Cell Set (Standard_Size i) | |
115 | { | |
116 | Cell* abyte = Bits + i / BitsPerCell(); | |
117 | Cell amask = (Cell)( '\1' << ( i % BitsPerCell() ) ); | |
fb9d45d0 A |
118 | Cell anold = (Cell)( *abyte & amask ); |
119 | *abyte = (Cell)( *abyte | amask ); | |
7fd59977 | 120 | return ! anold; |
121 | } | |
122 | ||
123 | //! Check bit for i-th item; returns non-null if that bit is set | |
124 | Cell IsSet (Standard_Size i) | |
125 | { | |
126 | Cell* abyte = Bits + i / BitsPerCell(); | |
127 | Cell amask = (Cell)( '\1' << ( i % BitsPerCell() ) ); | |
fb9d45d0 | 128 | return (Cell)( *abyte & amask ); |
7fd59977 | 129 | } |
130 | ||
131 | //! Unset bit for i-th item; returns non-null if that bit | |
132 | //! has been set previously | |
133 | Cell Unset (Standard_Size i) | |
134 | { | |
135 | Cell* abyte = Bits + i / BitsPerCell(); | |
136 | Cell amask = (Cell)( '\1' << ( i % BitsPerCell() ) ); | |
fb9d45d0 A |
137 | Cell anold = (Cell)( *abyte & amask ); |
138 | *abyte = (Cell)( *abyte & ~amask ); | |
7fd59977 | 139 | return anold; |
140 | } | |
141 | ||
142 | public: | |
143 | Standard_Size* Count; //!< items counter | |
144 | Standard_Address Array; //!< pointer to the data items array | |
145 | Cell* Bits; //!< bit map for defined/undefined flags | |
146 | }; | |
147 | ||
148 | public: | |
149 | /** | |
150 | * Iterator | |
151 | */ | |
152 | ||
153 | class Iterator { | |
154 | public: | |
155 | // Public interface | |
156 | ||
157 | //! Restart iterations on the same array | |
158 | void Restart () { init(myArr); } | |
159 | ||
160 | //! Returns True if current item is available | |
161 | Standard_Boolean More () const { return myHasMore; } | |
162 | ||
163 | //! Advances to the next item | |
164 | Standard_EXPORT void Next (); | |
165 | ||
166 | //! Returns current index | |
167 | Standard_EXPORT Standard_Size Index () const | |
168 | { | |
169 | return myIBlock * myArr->myBlockSize + myInd; | |
170 | } | |
171 | ||
172 | protected: | |
173 | // Methods for descendant | |
174 | ||
175 | //! Empty constructor | |
176 | Standard_EXPORT Iterator (const NCollection_SparseArrayBase* theArray=0); | |
177 | ||
178 | //! Initialize by the specified array | |
179 | Standard_EXPORT void init (const NCollection_SparseArrayBase* theArray); | |
180 | ||
181 | //! Returns address of the current item | |
182 | Standard_Address value () const | |
183 | { | |
184 | return myArr->getItem (myBlock, myInd); | |
185 | } | |
186 | ||
187 | private: | |
188 | const NCollection_SparseArrayBase *myArr; | |
189 | Standard_Boolean myHasMore; | |
190 | Standard_Size myIBlock; | |
191 | Standard_Size myInd; | |
192 | Block myBlock; | |
193 | }; | |
194 | friend class Iterator; | |
195 | ||
196 | private: | |
197 | // Copy constructor and assignment operator are private thus not accessible | |
198 | NCollection_SparseArrayBase (const NCollection_SparseArrayBase&) {} | |
199 | void operator = (const NCollection_SparseArrayBase&) {} | |
200 | ||
201 | protected: | |
202 | // Object life | |
203 | ||
204 | //! Constructor; initialized by size of item and of block (in items) | |
205 | NCollection_SparseArrayBase (Standard_Size theItemSize, | |
206 | Standard_Size theBlockSize) | |
207 | : myItemSize(theItemSize), myBlockSize(theBlockSize), | |
208 | myNbBlocks(0), mySize(0), myData(0) | |
209 | { | |
210 | } | |
211 | ||
212 | //! Destructor | |
213 | virtual ~NCollection_SparseArrayBase () | |
214 | { | |
215 | Clear(); | |
216 | } | |
217 | ||
218 | protected: | |
219 | // Data access interface for descendants | |
220 | ||
221 | //! Creates Block structure for block pointed by theAddr | |
222 | Block getBlock (const Standard_Address theAddr) const | |
223 | { | |
224 | return Block (theAddr, myBlockSize, myItemSize); | |
225 | } | |
226 | ||
227 | //! Find address of the item in the block by index (in the block) | |
228 | Standard_Address getItem (const Block &theBlock, Standard_Size theInd) const | |
229 | { | |
230 | return ((char*)theBlock.Array) + myItemSize * theInd; | |
231 | } | |
232 | ||
233 | //! Direct const access to the item | |
d93f7683 | 234 | Standard_Address getValue (const Standard_Size theIndex) const |
7fd59977 | 235 | { |
236 | Standard_OutOfRange_Raise_if (!HasValue(theIndex),"NCollection_SparseArray::Value()") | |
237 | return Block::ToArray(myData[theIndex/myBlockSize], myBlockSize, myItemSize) + | |
238 | myItemSize * (theIndex % myBlockSize); | |
239 | } | |
240 | ||
241 | //! Set a value to the specified item; returns address of the set item | |
d93f7683 | 242 | Standard_EXPORT Standard_Address setValue (const Standard_Size theIndex, |
7fd59977 | 243 | const Standard_Address theValue); |
244 | ||
245 | //! Modification access to the item; allocates necessary space | |
246 | //! and marks the item as defined | |
d93f7683 | 247 | Standard_EXPORT Standard_Address changeValue (const Standard_Size theIndex); |
7fd59977 | 248 | |
249 | //! Copy contents of theOther to this; | |
250 | //! assumes that this and theOther have exactly the same type of arguments | |
251 | Standard_EXPORT void assign (const NCollection_SparseArrayBase& theOther); | |
252 | ||
253 | //! Exchange contents of theOther and this; | |
254 | //! assumes that this and theOther have exactly the same type of arguments | |
255 | Standard_EXPORT void exchange (NCollection_SparseArrayBase& theOther); | |
256 | ||
257 | protected: | |
258 | // Methods to be provided by descendant | |
259 | ||
260 | //! Create new item at the specified address with default constructor | |
261 | // virtual void createItem (Standard_Address theAddress) = 0; | |
262 | ||
263 | //! Create new item at the specified address with copy constructor | |
264 | //! from existing item | |
265 | virtual void createItem (Standard_Address theAddress, Standard_Address theOther) = 0; | |
266 | ||
267 | //! Call destructor to the item | |
268 | virtual void destroyItem (Standard_Address theAddress) = 0; | |
269 | ||
270 | //! Call assignment operator to the item | |
271 | virtual void copyItem (Standard_Address theAddress, Standard_Address theOther) = 0; | |
272 | ||
273 | private: | |
274 | // Implementation of memory allocation/deallocation and access mechanics | |
275 | ||
276 | //! Allocate space for at least iBlock+1 blocks | |
277 | void allocData (const Standard_Size iBlock); | |
278 | ||
279 | //! Free specified block | |
280 | void freeBlock (const Standard_Size iBlock); | |
281 | ||
282 | protected: | |
283 | Standard_Size myItemSize; //!< size of item | |
284 | Standard_Size myBlockSize; //!< block size (in items) | |
285 | Standard_Size myNbBlocks; //!< allocated size of blocks table | |
286 | Standard_Size mySize; //!< number of currently defined items | |
287 | Standard_Address *myData; //!< array of pointers to data blocks | |
288 | }; | |
289 | ||
290 | #endif | |
291 |