src/NCollection/NCollection_SparseArrayBase.hxx

   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
  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
  45   Standard_Size Size () const { return mySize; }
  46
  47   //! Check whether the value at given index is set
  48   Standard_EXPORT Standard_Boolean HasValue (const Standard_Size theIndex) const;
  49
  50   //! Deletes the item from the array;
  51   //! returns True if that item was defined
  52   Standard_EXPORT Standard_Boolean UnsetValue (const Standard_Size theIndex);
  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() ) );
 118       Cell  anold = (Cell)( *abyte & amask );
 119       *abyte = (Cell)( *abyte | amask );
 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() ) );
 128       return (Cell)( *abyte & amask );
 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() ) );
 137       Cell  anold = (Cell)( *abyte & amask );
 138       *abyte = (Cell)( *abyte & ~amask );
 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
 234   Standard_Address getValue (const Standard_Size theIndex) const
 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
 242   Standard_EXPORT Standard_Address setValue (const Standard_Size theIndex,
 243                                              const Standard_Address theValue);
 244
 245   //! Modification access to the item; allocates necessary space
 246   //! and marks the item as defined
 247   Standard_EXPORT Standard_Address changeValue (const Standard_Size theIndex);
 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