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