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