src/SMDS/ObjectPool.hxx

   1 // Copyright (C) 2010-2016  CEA/DEN, EDF R&D, OPEN CASCADE
   2 //
   3 // This library is free software; you can redistribute it and/or
   4 // modify it under the terms of the GNU Lesser General Public
   5 // License as published by the Free Software Foundation; either
   6 // version 2.1 of the License, or (at your option) any later version.
   7 //
   8 // This library is distributed in the hope that it will be useful,
   9 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 // Lesser General Public License for more details.
  12 //
  13 // You should have received a copy of the GNU Lesser General Public
  14 // License along with this library; if not, write to the Free Software
  15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
  16 //
  17 // See http://www.salome-platform.org/ or email : webmaster.salome@opencascade.com
  18 //
  19
  20 #ifndef _OBJECTPOOL_HXX_
  21 #define _OBJECTPOOL_HXX_
  22
  23 #include <vector>
  24 #include <iostream>
  25
  26 #include "SMDS_Iterator.hxx"
  27
  28 namespace
  29 {
  30   // assure deallocation of memory of a vector
  31   template<class Y> void clearVector(Y & v )
  32   {
  33     Y emptyVec; v.swap( emptyVec );
  34   }
  35 }
  36
  37 template<class X> class ObjectPoolIterator;
  38
  39 template<class X> class ObjectPool
  40 {
  41
  42 private:
  43   std::vector<X*>   _chunkList;
  44   std::vector<bool> _freeList;
  45   int               _nextFree;    // either the 1st hole or last added
  46   int               _maxAvail;    // nb allocated elements
  47   int               _chunkSize;
  48   int               _maxOccupied; // max used ID
  49   int               _nbHoles;
  50   int               _lastDelChunk;
  51
  52   friend class ObjectPoolIterator<X>;
  53
  54   int getNextFree()
  55   {
  56     // Don't iterate on the _freeList if all the "holes"
  57     // are filled. Go straight to the last occupied ID + 1
  58     if ( _nbHoles == 0 )
  59       return std::min(_maxOccupied + 1, _maxAvail);
  60
  61     for (int i = _nextFree; i < _maxAvail; i++)
  62       if (_freeList[i] == true)
  63         {
  64           return i;
  65           break;
  66         }
  67     return _maxAvail;
  68   }
  69
  70   void checkDelete(int chunkId)
  71   {
  72     int i0 = _chunkSize * chunkId;
  73     int i1 = _chunkSize * (chunkId + 1);
  74     for (int i = i0; i < i1; i++)
  75       if (_freeList[i] == false)
  76         return;
  77     std::cerr << "a chunk to delete" << std::endl;
  78     // compactage des vecteurs un peu lourd, pas necessaire
  79     //X* chunk = _chunkList[chunkId];
  80     //delete [] chunk;
  81   }
  82
  83 public:
  84   ObjectPool(int nblk = 1024)
  85   {
  86     _chunkSize    = nblk;
  87     _nextFree     = 0;
  88     _maxAvail     = 0;
  89     _maxOccupied  = -1;
  90     _nbHoles      = 0;
  91     _lastDelChunk = 0;
  92     _chunkList.clear();
  93     _freeList.clear();
  94   }
  95
  96   virtual ~ObjectPool()
  97   {
  98     for (size_t i = 0; i < _chunkList.size(); i++)
  99       delete[] _chunkList[i];
 100   }
 101
 102   X* getNew()
 103   {
 104     X *obj = 0;
 105     _nextFree = getNextFree();
 106     if (_nextFree == _maxAvail)
 107       {
 108         X* newChunk = new X[_chunkSize];
 109         _chunkList.push_back(newChunk);
 110         _freeList.insert(_freeList.end(), _chunkSize, true);
 111         _maxAvail += _chunkSize;
 112         _freeList[_nextFree] = false;
 113         obj = newChunk;
 114       }
 115     else
 116       {
 117         int chunkId = _nextFree / _chunkSize;
 118         int rank = _nextFree - chunkId * _chunkSize;
 119         _freeList[_nextFree] = false;
 120         obj = _chunkList[chunkId] + rank;
 121       }
 122     if (_nextFree <= _maxOccupied)
 123       {
 124         _nbHoles-=1;
 125       }
 126     else
 127       {
 128         _maxOccupied = _nextFree;
 129       }
 130     return obj;
 131   }
 132
 133   void destroy(X* obj)
 134   {
 135     size_t i = 0;
 136     if ( obj >= _chunkList[ _lastDelChunk ] &&
 137          obj <  _chunkList[ _lastDelChunk ] + _chunkSize )
 138       i = _lastDelChunk;
 139     else
 140       for ( ; i < _chunkList.size(); i++ )
 141       {
 142         if ( obj >= _chunkList[ i ] &&
 143              obj <  _chunkList[ i ] + _chunkSize )
 144           break;
 145       }
 146     X*    chunk = _chunkList[i];
 147     long adrobj = (long) (obj);
 148     long adrmin = (long) (chunk);
 149     int  rank   = (adrobj - adrmin) / sizeof(X);
 150     int  toFree = i * _chunkSize + rank;
 151     _freeList[toFree] = true;
 152     if (toFree < _nextFree)
 153       _nextFree = toFree;
 154     if (toFree < _maxOccupied)
 155       ++_nbHoles;
 156     else
 157       --_maxOccupied;
 158     _lastDelChunk = i;
 159   }
 160
 161   void clear()
 162   {
 163     _nextFree = 0;
 164     _maxAvail = 0;
 165     _maxOccupied = 0;
 166     _nbHoles = 0;
 167     _lastDelChunk = 0;
 168     for (size_t i = 0; i < _chunkList.size(); i++)
 169       delete[] _chunkList[i];
 170     clearVector( _chunkList );
 171     clearVector( _freeList );
 172   }
 173
 174   // nb allocated elements
 175   size_t size() const
 176   {
 177     return _freeList.size();
 178   }
 179
 180   // nb used elements
 181   size_t nbElements() const
 182   {
 183     return _maxOccupied + 1 - _nbHoles;
 184   }
 185
 186   // return an element w/o any check
 187   const X* operator[]( size_t i ) const // i < size()
 188   {
 189     int chunkId = i / _chunkSize;
 190     int    rank = i - chunkId * _chunkSize;
 191     return _chunkList[ chunkId ] + rank;
 192   }
 193
 194   // return only being used element
 195   const X* at( size_t i ) const // i < size()
 196   {
 197     if ( i >= size() || _freeList[ i ] )
 198       return 0;
 199
 200     int chunkId = i / _chunkSize;
 201     int    rank = i - chunkId * _chunkSize;
 202     return _chunkList[ chunkId ] + rank;
 203   }
 204
 205   //  void destroy(int toFree)
 206   //  {
 207   //    // no control 0<= toFree < _freeList.size()
 208   //    _freeList[toFree] = true;
 209   //    if (toFree < _nextFree)
 210   //      _nextFree = toFree;
 211   //  }
 212
 213 };
 214
 215 template<class X> class ObjectPoolIterator : public SMDS_Iterator<const X*>
 216 {
 217   const ObjectPool<X>& _pool;
 218   int                  _i, _nbFound;
 219 public:
 220
 221   ObjectPoolIterator( const ObjectPool<X>& pool ) : _pool( pool ), _i( 0 ), _nbFound( 0 )
 222   {
 223     if ( more() && _pool._freeList[ _i ] == true )
 224     {
 225       next();
 226       --_nbFound;
 227     }
 228   }
 229
 230   virtual bool more()
 231   {
 232     return ( _i <= _pool._maxOccupied && _nbFound < (int)_pool.nbElements() );
 233   }
 234
 235   virtual const X* next()
 236   {
 237     const X* x = 0;
 238     if ( more() )
 239     {
 240       x = _pool[ _i ];
 241
 242       ++_nbFound;
 243
 244       for ( ++_i; _i <= _pool._maxOccupied; ++_i )
 245         if ( _pool._freeList[ _i ] == false )
 246           break;
 247     }
 248     return x;
 249   }
 250 };
 251
 252 #endif