1 // Created on: 2007-01-23
2 // Created by: Andrey BETENEV
3 // Copyright (c) 2007-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
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.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #ifndef NCollection_SparseArrayBase_HeaderFile
17 #define NCollection_SparseArrayBase_HeaderFile
19 #include <Standard.hxx>
20 #include <Standard_OutOfRange.hxx>
22 typedef size_t Standard_Size;
25 * Base class for NCollection_SparseArray;
26 * provides non-template implementation of general mechanics
27 * of block allocation, items creation / deletion etc.
30 class NCollection_SparseArrayBase
33 //!@name Type-independent public interface
36 //! Clears all the data
37 Standard_EXPORT void Clear ();
39 //! Returns number of currently contained items
40 Standard_Size Size () const { return mySize; }
42 //! Check whether the value at given index is set
43 Standard_EXPORT Standard_Boolean HasValue (const Standard_Size theIndex) const;
45 //! Deletes the item from the array;
46 //! returns True if that item was defined
47 Standard_EXPORT Standard_Boolean UnsetValue (const Standard_Size theIndex);
51 #if defined(__SUNPRO_CC) && (__SUNPRO_CC <= 0x530)
52 public: // work-around against obsolete SUN WorkShop 5.3 compiler
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).
62 * The Block structure provides a logical view on the block,
63 * and provides methods to work with bit map.
65 * Note that NCollection_SparseArrayBase class takes responsibility
66 * for correct allocation/deallocation of all the data.
72 typedef unsigned char Cell; //!< type of items used to hold bits
74 //! Number of bits in each cell
75 static Standard_Size BitsPerCell() { return sizeof(Cell) * 8/*BITSPERBYTE*/; }
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))
88 //! Compute required size for block data, in bytes
89 static Standard_Size Size (const Standard_Size theNbItems,
90 const Standard_Size theItemSize)
92 return sizeof(Standard_Size) +
93 sizeof(Cell) * ( (theNbItems + BitsPerCell() - 1) / BitsPerCell() ) +
94 theNbItems * theItemSize;
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*/)
102 return (char*)theAddress + sizeof(Standard_Size);
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)
111 Cell* abyte = Bits + i / BitsPerCell();
112 Cell amask = (Cell)( '\1' << ( i % BitsPerCell() ) );
113 Cell anold = (Cell)( *abyte & amask );
114 *abyte = (Cell)( *abyte | amask );
118 //! Check bit for i-th item; returns non-null if that bit is set
119 Cell IsSet (Standard_Size i)
121 Cell* abyte = Bits + i / BitsPerCell();
122 Cell amask = (Cell)( '\1' << ( i % BitsPerCell() ) );
123 return (Cell)( *abyte & amask );
126 //! Unset bit for i-th item; returns non-null if that bit
127 //! has been set previously
128 Cell Unset (Standard_Size i)
130 Cell* abyte = Bits + i / BitsPerCell();
131 Cell amask = (Cell)( '\1' << ( i % BitsPerCell() ) );
132 Cell anold = (Cell)( *abyte & amask );
133 *abyte = (Cell)( *abyte & ~amask );
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
152 //! Restart iterations on the same array
153 void Restart () { init(myArr); }
155 //! Returns True if current item is available
156 Standard_Boolean More () const { return myHasMore; }
158 //! Advances to the next item
159 Standard_EXPORT void Next ();
161 //! Returns current index
162 Standard_Size Index () const
164 return myIBlock * myArr->myBlockSize + myInd;
168 // Methods for descendant
170 //! Empty constructor
171 Standard_EXPORT Iterator (const NCollection_SparseArrayBase* theArray=0);
173 //! Initialize by the specified array
174 Standard_EXPORT void init (const NCollection_SparseArrayBase* theArray);
176 //! Returns address of the current item
177 Standard_Address value () const
179 return myArr->getItem (myBlock, myInd);
183 const NCollection_SparseArrayBase *myArr;
184 Standard_Boolean myHasMore;
185 Standard_Size myIBlock;
189 friend class Iterator;
192 // Copy constructor and assignment operator are private thus not accessible
193 NCollection_SparseArrayBase (const NCollection_SparseArrayBase&) {}
194 void operator = (const NCollection_SparseArrayBase&) {}
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)
208 virtual ~NCollection_SparseArrayBase ()
214 // Data access interface for descendants
216 //! Creates Block structure for block pointed by theAddr
217 Block getBlock (const Standard_Address theAddr) const
219 return Block (theAddr, myBlockSize, myItemSize);
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
225 return ((char*)theBlock.Array) + myItemSize * theInd;
228 //! Direct const access to the item
229 Standard_Address getValue (const Standard_Size theIndex) const
231 Standard_OutOfRange_Raise_if (!HasValue(theIndex),"NCollection_SparseArray::Value()")
232 return Block::ToArray(myData[theIndex/myBlockSize], myBlockSize, myItemSize) +
233 myItemSize * (theIndex % myBlockSize);
236 //! Set a value to the specified item; returns address of the set item
237 Standard_EXPORT Standard_Address setValue (const Standard_Size theIndex,
238 const Standard_Address theValue);
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);
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);
249 // Methods to be provided by descendant
251 //! Create new item at the specified address with default constructor
252 // virtual void createItem (Standard_Address theAddress) = 0;
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;
258 //! Call destructor to the item
259 virtual void destroyItem (Standard_Address theAddress) = 0;
261 //! Call assignment operator to the item
262 virtual void copyItem (Standard_Address theAddress, Standard_Address theOther) = 0;
265 // Implementation of memory allocation/deallocation and access mechanics
267 //! Allocate space for at least iBlock+1 blocks
268 void allocData (const Standard_Size iBlock);
270 //! Free specified block
271 void freeBlock (const Standard_Size iBlock);
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