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     : myICurBlock (0),
  73       myIEndBlock (0),
  74       myCurIndex  (0),
  75       myEndIndex  (0) {}
  76
  77     Iterator (const NCollection_BaseVector& theVector, Standard_Boolean theToEnd = Standard_False)
  78     {
  79       initV (theVector, theToEnd);
  80     }
  81
  82     Iterator (const Iterator& theVector)
  83     {
  84       copyV (theVector);
  85     }
  86
  87     Standard_EXPORT void initV (const NCollection_BaseVector& theVector, Standard_Boolean theToEnd = Standard_False);
  88
  89     Standard_EXPORT void copyV (const Iterator&);
  90
  91     Standard_Boolean moreV() const
  92     {
  93       return (myICurBlock < myIEndBlock || myCurIndex < myEndIndex);
  94     }
  95
  96     void nextV()
  97     {
  98       if (++myCurIndex >= myVector->myData[myICurBlock].Length
  99        && myICurBlock < myIEndBlock)
 100       {
 101         ++myICurBlock;
 102         myCurIndex = 0;
 103       }
 104     }
 105
 106     void prevV()
 107     {
 108       if (--myCurIndex < 0 && myICurBlock > 0)
 109       {
 110         --myICurBlock;
 111         myCurIndex = myVector->myData[myICurBlock].Length - 1;
 112       }
 113     }
 114
 115     void offsetV (Standard_Integer theOffset)
 116     {
 117       const Standard_Integer anIndex = myCurIndex + myICurBlock * myVector->myIncrement + theOffset;
 118       myICurBlock = anIndex / myVector->myIncrement;
 119       myCurIndex = anIndex % myVector->myIncrement;
 120     }
 121
 122     Standard_Integer differV (const Iterator& theOther) const
 123     {
 124       return (myCurIndex - theOther.myCurIndex) + (myICurBlock - theOther.myICurBlock) * myVector->myIncrement;
 125     }
 126
 127     const MemBlock* curBlockV() const
 128     {
 129       return &myVector->myData[myICurBlock];
 130     }
 131
 132     const NCollection_BaseVector* myVector;    //!< the Master vector
 133     Standard_Integer              myICurBlock; //!< # of the current block
 134     Standard_Integer              myIEndBlock;
 135     Standard_Integer              myCurIndex;  //!< Index in the current block
 136     Standard_Integer              myEndIndex;
 137   };
 138
 139 protected: //! @name Block initializer
 140
 141   typedef void (*initMemBlocks_t) (NCollection_BaseVector& theVector,
 142                                    MemBlock&               theBlock,
 143                                    const Standard_Integer  theFirst,
 144                                    const Standard_Integer  theSize);
 145
 146   //! Allocate memory for array of memory blocks.
 147   //! @param theCapacity   Number of memory blocks in array
 148   //! @param theSource     Original array of memory blocks, will be automatically deallocated
 149   //! @param theSourceSize Number of memory blocks in original array
 150   Standard_EXPORT MemBlock* allocMemBlocks (const Standard_Integer theCapacity,
 151                                             MemBlock*              theSource     = NULL,
 152                                             const Standard_Integer theSourceSize = 0);
 153
 154 protected: //! @name protected methods
 155
 156   //! Empty constructor
 157   NCollection_BaseVector (const Handle(NCollection_BaseAllocator)& theAllocator,
 158                           initMemBlocks_t                    theInitBlocks,
 159                           const size_t                       theSize,
 160                           const Standard_Integer             theInc)
 161   : myItemSize   (theSize),
 162     myIncrement  (theInc),
 163     myLength     (0),
 164     myCapacity   (GetCapacity (myIncrement)),
 165     myNBlocks    (0),
 166     myInitBlocks (theInitBlocks)
 167   {
 168     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
 169     myData = allocMemBlocks (myCapacity);
 170   }
 171
 172   //! Copy constructor
 173   NCollection_BaseVector (const Handle(NCollection_BaseAllocator)& theAllocator,
 174                           initMemBlocks_t                    theInitBlocks,
 175                           const NCollection_BaseVector&      theOther)
 176   : myItemSize   (theOther.myItemSize),
 177     myIncrement  (theOther.myIncrement),
 178     myLength     (theOther.myLength),
 179     myCapacity   (GetCapacity(myIncrement) + theOther.myLength / theOther.myIncrement),
 180     myNBlocks    (theOther.myLength == 0 ? 0 : 1 + (theOther.myLength - 1)/theOther.myIncrement),
 181     myInitBlocks (theInitBlocks)
 182   {
 183     myAllocator = (theAllocator.IsNull() ? NCollection_BaseAllocator::CommonBaseAllocator() : theAllocator);
 184     myData = allocMemBlocks (myCapacity);
 185   }
 186
 187   //! Destructor
 188   virtual ~NCollection_BaseVector() {}
 189
 190   //! @return pointer to memory where to put the new item
 191   Standard_EXPORT void* expandV (const Standard_Integer theIndex);
 192
 193   //! Locate the memory holding the desired value
 194   inline void* findV (const Standard_Integer theIndex) const
 195   {
 196     Standard_OutOfRange_Raise_if (theIndex < 0 || theIndex >= myLength,
 197                                   "NCollection_BaseVector::findV");
 198     const Standard_Integer aBlock = theIndex / myIncrement;
 199     return myData[aBlock].findV (theIndex - aBlock * myIncrement, myItemSize);
 200   }
 201
 202 public: //! @name public API
 203
 204   //! Empty the vector of its objects
 205   Standard_EXPORT void Clear();
 206   // to set the size of increment dynamically
 207   void SetIncrement(const Standard_Integer aIncrement) {
 208     if (aIncrement > 0) {
 209       if (!myIncrement) {
 210         myIncrement=aIncrement;
 211       }
 212     }
 213   }
 214
 215   //! Returns attached allocator
 216   const Handle(NCollection_BaseAllocator)& Allocator() const
 217   {
 218     return myAllocator;
 219   }
 220
 221 protected: //! @name Protected fields
 222
 223   Handle(NCollection_BaseAllocator) myAllocator;
 224   size_t           myItemSize;
 225   Standard_Integer myIncrement;
 226   Standard_Integer myLength;
 227   Standard_Integer myCapacity;
 228   Standard_Integer myNBlocks;
 229   MemBlock*        myData;
 230   initMemBlocks_t  myInitBlocks;
 231
 232 protected:
 233
 234   friend class Iterator;
 235 };
 236
 237 #endif // NCollection_BaseVector_HeaderFile