src/NCollection/NCollection_SparseArrayBase.hxx

   1 // Created on: 2007-01-23
   2 // Created by: Andrey BETENEV
   3 // Copyright (c) 2007-2014 OPEN CASCADE SAS
   4 //
   5 // This file is part of Open CASCADE Technology software library.
   6 //
   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.
  12 //
  13 // Alternatively, this file may be used under the terms of Open CASCADE
  14 // commercial license or contractual agreement.
  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
  40   Standard_Size Size () const { return mySize; }
  41
  42   //! Check whether the value at given index is set
  43   Standard_EXPORT Standard_Boolean HasValue (const Standard_Size theIndex) const;
  44
  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);
  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() ) );
 113       Cell  anold = (Cell)( *abyte & amask );
 114       *abyte = (Cell)( *abyte | amask );
 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() ) );
 123       return (Cell)( *abyte & amask );
 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() ) );
 132       Cell  anold = (Cell)( *abyte & amask );
 133       *abyte = (Cell)( *abyte & ~amask );
 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
 162     Standard_EXPORT Standard_Size Index () const
 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
 193   NCollection_SparseArrayBase (const NCollection_SparseArrayBase&) {}
 194   void operator = (const NCollection_SparseArrayBase&) {}
 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
 229   Standard_Address getValue (const Standard_Size theIndex) const
 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
 237   Standard_EXPORT Standard_Address setValue (const Standard_Size theIndex,
 238                                              const Standard_Address theValue);
 239
 240   //! Modification access to the item; allocates necessary space
 241   //! and marks the item as defined
 242   Standard_EXPORT Standard_Address changeValue (const Standard_Size theIndex);
 243
 244   //! Copy contents of theOther to this;
 245   //! assumes that this and theOther have exactly the same type of arguments
 246   Standard_EXPORT void assign (const NCollection_SparseArrayBase& theOther);
 247
 248   //! Exchange contents of theOther and this;
 249   //! assumes that this and theOther have exactly the same type of arguments
 250   Standard_EXPORT void exchange (NCollection_SparseArrayBase& theOther);
 251
 252 protected:
 253   // Methods to be provided by descendant
 254
 255   //! Create new item at the specified address with default constructor
 256 //  virtual void createItem (Standard_Address theAddress) = 0;
 257
 258   //! Create new item at the specified address with copy constructor
 259   //! from existing item
 260   virtual void createItem (Standard_Address theAddress, Standard_Address theOther) = 0;
 261
 262   //! Call destructor to the item
 263   virtual void destroyItem (Standard_Address theAddress) = 0;
 264
 265   //! Call assignment operator to the item
 266   virtual void copyItem (Standard_Address theAddress, Standard_Address theOther) = 0;
 267
 268 private:
 269   // Implementation of memory allocation/deallocation and access mechanics
 270
 271   //! Allocate space for at least iBlock+1 blocks
 272   void allocData (const Standard_Size iBlock);
 273
 274   //! Free specified block
 275   void freeBlock (const Standard_Size iBlock);
 276
 277 protected:
 278   Standard_Size     myItemSize;  //!< size of item
 279   Standard_Size     myBlockSize; //!< block size (in items)
 280   Standard_Size     myNbBlocks;  //!< allocated size of blocks table
 281   Standard_Size     mySize;      //!< number of currently defined items
 282   Standard_Address *myData;      //!< array of pointers to data blocks
 283 };
 284
 285 #endif
 286