src/NCollection/NCollection_SparseArrayBase.hxx

   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 = (Cell)( *abyte & amask );
 104       *abyte = (Cell)( *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 (Cell)( *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 = (Cell)( *abyte & amask );
 123       *abyte = (Cell)( *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