src/NCollection/NCollection_BaseVector.hxx

   1 // Created on: 2002-04-24
   2 // Created by: Alexander GRIGORIEV
   3 // Copyright (c) 2002-2013 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_BaseVector_HeaderFile
  17 #define NCollection_BaseVector_HeaderFile
  18
  19 #include <Standard_TypeDef.hxx>
  20 #include <Standard_OutOfRange.hxx>
  21 #include <NCollection_BaseAllocator.hxx>
  22 #include <NCollection_DefineAlloc.hxx>
  23
  24 #include <stddef.h>
  25
  26 // this value defines the number of blocks that are reserved
  27 // when the capacity of vector is increased
  28 inline Standard_Integer GetCapacity (const Standard_Integer theIncrement)
  29 {
  30   return Max(theIncrement/8, 1);
  31 }
  32
  33 //! Class NCollection_BaseVector - base for NCollection_Vector template
  34 class NCollection_BaseVector
  35 {
  36 public:
  37   //! Memory allocation
  38   DEFINE_STANDARD_ALLOC
  39   DEFINE_NCOLLECTION_ALLOC
  40
  41 protected:
  42
  43   // Auxiliary structure for memory blocks
  44   struct MemBlock
  45   {
  46
  47   public:
  48
  49     //! @param theIndex    Item index in the block
  50     //! @param theItemSize Element size in bytes
  51     //! @return the address of specified item in this memory block
  52     void* findV (const Standard_Integer theIndex,
  53                  const size_t           theItemSize) const
  54     {
  55       return (char* )DataPtr + size_t(theIndex) * theItemSize;
  56     }
  57
  58   public:
  59
  60     void*            DataPtr;    //!< block of elements
  61     Standard_Integer FirstIndex; //!< index of the first element (among all memory blocks in collection)
  62     Standard_Integer Length;
  63     Standard_Integer Size;
  64
  65   };
  66
  67   //! Base class for Iterator implementation
  68   class Iterator
  69   {
  70   protected:
  71     Iterator()
  72     : myVector    (nullptr),
  73       myICurBlock (0),
  74       myIEndBlock (0),
  75       myCurIndex  (0),
  76       myEndIndex  (0) {}
  77
  78     Iterator (const NCollection_BaseVector& theVector, Standard_Boolean theToEnd = Standard_False)
  79     {
  80       initV (theVector, theToEnd);
  81     }
  82
  83     Standard_EXPORT void initV (const NCollection_BaseVector& theVector, Standard_Boolean theToEnd = Standard_False);
  84
  85     Standard_Boolean moreV() const
  86     {
  87       return (myICurBlock < myIEndBlock || myCurIndex < myEndIndex);
  88     }
  89
  90     void nextV()
  91     {
  92       if (++myCurIndex >= myVector->myData[myICurBlock].Length
  93        && myICurBlock < myIEndBlock)
  94       {
  95         ++myICurBlock;
  96         myCurIndex = 0;
  97       }
  98     }
  99
 100     void prevV()
 101     {
 102       if (--myCurIndex < 0 && myICurBlock > 0)
 103       {
 104         --myICurBlock;
 105         myCurIndex = myVector->myData[myICurBlock].Length - 1;
 106       }
 107     }
 108
 109     void offsetV (Standard_Integer theOffset)
 110     {
 111       const Standard_Integer anIndex = myCurIndex + myICurBlock * myVector->myIncrement + theOffset;
 112       myICurBlock = anIndex / myVector->myIncrement;
 113       myCurIndex = anIndex % myVector->myIncrement;
 114       if (myICurBlock > myIEndBlock)
 115       {
 116         // make sure that iterator produced by Offset()
 117         // is equal to the end() iterator
 118         --myICurBlock;
 119         myCurIndex += myVector->myIncrement;
 120       }
 121     }
 122
 123     Standard_Integer differV (const Iterator& theOther) const
 124     {
 125       return (myCurIndex - theOther.myCurIndex) + (myICurBlock - theOther.myICurBlock) * myVector->myIncrement;
 126     }
 127
 128     const MemBlock* curBlockV() const
 129     {
 130       return &myVector->myData[myICurBlock];
 131     }
 132
 133   protected:
 134     const NCollection_BaseVector* myVector;    //!< the Master vector
 135     Standard_Integer              myICurBlock; //!< # of the current block
 136     Standard_Integer              myIEndBlock;
 137     Standard_Integer              myCurIndex;  //!< Index in the current block
 138     Standard_Integer              myEndIndex;
 139   };
 140
 141 protected: //! @name Block initializer
 142
 143   typedef void (*initMemBlocks_t) (NCollection_BaseVector& theVector,
 144                                    MemBlock&               theBlock,
 145                                    const Standard_Integer  theFirst,
 146                                    const Standard_Integer  theSize);
 147
 148   //! Allocate memory for array of memory blocks.
 149   //! @param theCapacity   Number of memory blocks in array
 150   //! @param theSource     Original array of memory blocks, will be automatically deallocated
 151   //! @param theSourceSize Number of memory blocks in original array
 152   Standard_EXPORT MemBlock* allocMemBlocks (const Standard_Integer theCapacity,
 153                                             MemBlock*              theSource     = NULL,
 154                                             const Standard_Integer theSourceSize = 0);
 155
 156 protected: //! @name protected methods
 157
 158   //! Empty constructor
 159   NCollection_BaseVector (const Handle(NCollection_BaseAllocator)& theAllocator,
 160                           initMemBlocks_t                    theInitBlocks,
 161                           const size_t                       theSize,
 162                           const Standard_Integer             theInc)
 163   : myItemSize   (theSize),
 164     myIncrement  (theInc),
 165     myLength     (0),
 166     myCapacity   (GetCapacity (myIncrement)),
 167     myNBlocks    (0),
 168     myInitBlocks (theInitBlocks)
 169   {
 170     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
 171     myData = allocMemBlocks (myCapacity);
 172   }
 173
 174   //! Copy constructor
 175   NCollection_BaseVector (const Handle(NCollection_BaseAllocator)& theAllocator,
 176                           initMemBlocks_t                    theInitBlocks,
 177                           const NCollection_BaseVector&      theOther)
 178   : myItemSize   (theOther.myItemSize),
 179     myIncrement  (theOther.myIncrement),
 180     myLength     (theOther.myLength),
 181     myCapacity   (GetCapacity(myIncrement) + theOther.myLength / theOther.myIncrement),
 182     myNBlocks    (theOther.myLength == 0 ? 0 : 1 + (theOther.myLength - 1)/theOther.myIncrement),
 183     myInitBlocks (theInitBlocks)
 184   {
 185     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
 186     myData = allocMemBlocks (myCapacity);
 187   }
 188
 189   //! Destructor
 190   virtual ~NCollection_BaseVector() {}
 191
 192   //! @return pointer to memory where to put the new item
 193   Standard_EXPORT void* expandV (const Standard_Integer theIndex);
 194
 195   //! Locate the memory holding the desired value
 196   inline void* findV (const Standard_Integer theIndex) const
 197   {
 198     Standard_OutOfRange_Raise_if (theIndex < 0 || theIndex >= myLength,
 199                                   "NCollection_BaseVector::findV");
 200     const Standard_Integer aBlock = theIndex / myIncrement;
 201     return myData[aBlock].findV (theIndex - aBlock * myIncrement, myItemSize);
 202   }
 203
 204 public: //! @name public API
 205
 206   //! Empty the vector of its objects
 207   Standard_EXPORT void Clear();
 208   // to set the size of increment dynamically
 209   void SetIncrement(const Standard_Integer aIncrement) {
 210     if (aIncrement > 0) {
 211       if (!myIncrement) {
 212         myIncrement=aIncrement;
 213       }
 214     }
 215   }
 216
 217   //! Returns attached allocator
 218   const Handle(NCollection_BaseAllocator)& Allocator() const
 219   {
 220     return myAllocator;
 221   }
 222
 223 protected: //! @name Protected fields
 224
 225   Handle(NCollection_BaseAllocator) myAllocator;
 226   size_t           myItemSize;
 227   Standard_Integer myIncrement;
 228   Standard_Integer myLength;
 229   Standard_Integer myCapacity;
 230   Standard_Integer myNBlocks;
 231   MemBlock*        myData;
 232   initMemBlocks_t  myInitBlocks;
 233
 234 protected:
 235
 236   friend class Iterator;
 237 };
 238
 239 #endif // NCollection_BaseVector_HeaderFile