]> SALOME platform Git repositories - modules/smesh.git/blob - src/SMDS/ObjectPool.hxx
Salome HOME
Merge branch 'master' into gni/adaptation
[modules/smesh.git] / src / SMDS / ObjectPool.hxx
1 // Copyright (C) 2010-2020  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