Move libcds 1.6.0 from SVN
[libcds.git] / cds / memory / vyukov_queue_pool.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
4 #define __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
5
6 #include <cds/details/allocator.h>
7 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
8
9 namespace cds { namespace memory {
10
11     /// Free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
12     /** @ingroup cds_memory_pool
13         Template parameters:
14         - \p T - the type of object maintaining by free-list
15         - \p Options - the options of cds::intrusive::VyukovMPMCCycleQueue class plus
16             cds::opt::allocator option.
17
18         \b Internals
19
20         This free-list is very simple.
21         At construction time, the free-list allocates the array of N items
22         and stores them into queue, where N is the queue capacity.
23         When allocating the free-list tries to pop an object from
24         internal queue i.e. from preallocated pool. If success the popped object is returned.
25         Otherwise a new one is allocated. When deallocating, the free-list checks whether
26         the object is from preallocated pool. If so, the object is pushed into queue, otherwise
27         it is deallocated by using the allocator provided.
28         The pool can manage more than \p N items but only \p N items is contained in the free-list.
29
30         \b Usage
31
32         \p %vyukov_queue_pool should be used together with \ref pool_allocator.
33         You should declare an static object of type \p %vyukov_queue_pool, provide
34         an accessor to that object and use \p pool_allocator as an allocator:
35         \code
36         #include <cds/memory/vyukov_queue_pool.h>
37         #include <cds/memory/pool_allocator.h>
38
39         // Pool of Foo object of size 1024.
40         typedef cds::memory::vyukov_queue_pool< Foo, cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > > pool_type;
41         static pool_type thePool;
42
43         struct pool_accessor {
44             typedef typename pool_type::value_type  value_type;
45
46             pool_type& operator()() const
47             {
48                 return thePool;
49             }
50         };
51
52         // Declare pool allocator
53         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
54
55         // Use pool_allocator
56         // Allocate an object
57         Foo * p = pool_allocator().allocate( 1 );
58
59         // construct object
60         new(p) Foo;
61
62         //...
63
64         // Destruct object
65         p->~Foo();
66
67         // Deallocate object
68         pool_allocator().deallocate( p , 1 );
69         \endcode
70     */
71     template <typename T, CDS_DECL_OPTIONS6>
72     class vyukov_queue_pool
73     {
74     public:
75         typedef cds::intrusive::VyukovMPMCCycleQueue< T, CDS_OPTIONS6 > queue_type  ;   ///< Queue type
76
77     protected:
78         //@cond
79         struct default_options: public queue_type::options
80         {
81             typedef CDS_DEFAULT_ALLOCATOR   allocator;
82         };
83         typedef typename opt::make_options< default_options, CDS_OPTIONS6 >::type   options;
84         //@endcond
85
86     public:
87         typedef T  value_type ; ///< Value type
88         typedef typename options::allocator::template rebind<value_type>::other allocator_type  ;   ///< allocator type
89
90     protected:
91         //@cond
92         queue_type      m_Queue;
93         value_type *    m_pFirst;
94         value_type *    m_pLast;
95         //@endcond
96
97     protected:
98         //@cond
99         void preallocate_pool()
100         {
101             m_pFirst = allocator_type().allocate( m_Queue.capacity() );
102             m_pLast = m_pFirst + m_Queue.capacity();
103
104             for ( value_type * p = m_pFirst; p < m_pLast; ++p )
105                 CDS_VERIFY( m_Queue.push( *p )) ;   // must be true
106         }
107
108         bool from_pool( value_type * p ) const
109         {
110             return m_pFirst <= p && p < m_pLast;
111         }
112         //@endcond
113
114     public:
115         /// Preallocates the pool of object
116         /**
117             \p nCapacity argument is the queue capacity. It should be passed
118             if the queue is based on dynamically-allocated buffer.
119             See cds::intrusive::VyukovMPMCCycleQueue for explanation.
120         */
121         vyukov_queue_pool( size_t nCapacity = 0 )
122             : m_Queue( nCapacity )
123         {
124             preallocate_pool();
125         }
126
127         /// Deallocates the pool.
128         ~vyukov_queue_pool()
129         {
130             m_Queue.clear();
131             allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
132         }
133
134         /// Allocates an object from pool
135         /**
136             The pool supports allocation only single object (\p n = 1).
137             If \p n > 1 the behaviour is undefined.
138
139             If the queue is not empty, the popped value is returned.
140             Otherwise, a new value allocated.
141         */
142         value_type * allocate( size_t n )
143         {
144             assert( n == 1 );
145
146             value_type * p = m_Queue.pop();
147             if ( p ) {
148                 assert( from_pool(p) );
149                 return p;
150             }
151
152             return allocator_type().allocate( n );
153         }
154
155         /// Deallocated the object \p p
156         /**
157             The pool supports allocation only single object (\p n = 1).
158             If \p n > 1 the behaviour is undefined.
159
160             If \p p is from preallocated pool, it pushes into the queue.
161             Otherwise, \p p is deallocated by allocator provided.
162         */
163         void deallocate( value_type * p, size_t n )
164         {
165             assert( n == 1 );
166
167             if ( p ) {
168                 if ( from_pool( p ) )
169                     m_Queue.push( *p );
170                 else
171                     allocator_type().deallocate( p, n );
172             }
173         }
174     };
175
176     /// Lazy free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
177     /** @ingroup cds_memory_pool
178         Template parameters:
179         - \p T - the type of object maintaining by free-list
180         - \p Options - the options of cds::intrusive::VyukovMPMCCycleQueue class plus
181             cds::opt::allocator option.
182
183         \b Internals
184
185         This free-list is very simple.
186         At construction time the pool is empty.
187         When allocating the free-list tries to pop an object from
188         internal queue. If success the popped object is returned.
189         Otherwise a new one is allocated.
190         When deallocating, the free-list tries to push the object into the pool.
191         If internal queue is full, the object is deallocated by using the allocator provided.
192         The pool can manage more than \p N items but only \p N items is placed in the free-list.
193
194         \b Usage
195
196         \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
197         You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
198         an accessor functor to this object and use \p pool_allocator as an allocator:
199         \code
200         #include <cds/memory/vyukov_queue_pool.h>
201         #include <cds/memory/pool_allocator.h>
202
203         // Pool of Foo object of size 1024.
204         typedef cds::memory::lazy_vyukov_queue_pool< Foo, cds::opt::buffer< cds::opt::v::dynamic_buffer< Foo > > pool_type;
205         static pool_type thePool( 1024 );
206
207         struct pool_accessor {
208             typedef typename pool_type::value_type  value_type;
209
210             pool_type& operator()() const
211             {
212                 return thePool;
213             }
214         };
215
216         // Declare pool allocator
217         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
218
219         // Use pool_allocator
220         // Allocate an object
221         Foo * p = pool_allocator().allocate( 1 );
222
223         // construct object
224         new(p) Foo;
225
226         //...
227
228         // Destruct object
229         p->~Foo();
230
231         // Deallocate object
232         pool_allocator().deallocate( p , 1 );
233         \endcode
234
235     */
236     template <typename T, CDS_DECL_OPTIONS6>
237     class lazy_vyukov_queue_pool
238     {
239     public:
240         typedef cds::intrusive::VyukovMPMCCycleQueue< T, CDS_OPTIONS6 > queue_type  ;   ///< Queue type
241
242     protected:
243         //@cond
244         struct default_options: public queue_type::options
245         {
246             typedef CDS_DEFAULT_ALLOCATOR   allocator;
247         };
248         typedef typename opt::make_options< default_options, CDS_OPTIONS6 >::type   options;
249         //@endcond
250
251     public:
252         typedef T  value_type ; ///< Value type
253         typedef typename options::allocator::template rebind<value_type>::other allocator_type  ;   ///< allocator type
254
255     protected:
256         //@cond
257         queue_type      m_Queue;
258         //@endcond
259
260     public:
261         /// Constructs empty pool
262         lazy_vyukov_queue_pool( size_t nCapacity = 0 )
263             : m_Queue( nCapacity )
264         {}
265
266         /// Deallocates all objects from the pool
267         ~lazy_vyukov_queue_pool()
268         {
269             allocator_type a;
270             while ( !m_Queue.empty() ) {
271                 value_type * p = m_Queue.pop();
272                 a.deallocate( p, 1 );
273             }
274         }
275
276         /// Allocates an object from pool
277         /**
278             The pool supports allocation only single object (\p n = 1).
279             If \p n > 1 the behaviour is undefined.
280
281             If the queue is not empty, the popped value is returned.
282             Otherwise, a new value allocated.
283         */
284         value_type * allocate( size_t n )
285         {
286             assert( n == 1 );
287
288             value_type * p = m_Queue.pop();
289             if ( p )
290                 return p;
291
292             return allocator_type().allocate( n );
293         }
294
295         /// Deallocated the object \p p
296         /**
297             The pool supports allocation only single object (\p n = 1).
298             If \p n > 1 the behaviour is undefined.
299
300             If the queue is not full, \p p is pushed into the queue.
301             Otherwise, \p p is deallocated by allocator provided.
302         */
303         void deallocate( value_type * p, size_t n )
304         {
305             assert( n == 1 );
306
307             if ( p ) {
308                 if ( !m_Queue.push( *p ))
309                     allocator_type().deallocate( p, n );
310             }
311         }
312
313     };
314
315     /// Bounded free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
316     /** @ingroup cds_memory_pool
317         Template parameters:
318         - \p T - the type of object maintaining by free-list
319         - \p Options - the options of cds::intrusive::VyukovMPMCCycleQueue class plus
320             cds::opt::allocator option.
321
322         \b Internals
323
324         At construction time, the free-list allocates the array of N items
325         and stores them into queue, where N is the queue capacity.
326         When allocating the free-list tries to pop an object from
327         internal queue i.e. from preallocated pool. If success the popped object is returned.
328         Otherwise a \p std::bad_alloc exception is raised.
329         So, the pool can contain up to \p N items.
330         When deallocating, the object is pushed into queue.
331         In debug mode the \ref deallocate member function asserts
332         that the pointer is from preallocated pool.
333
334         \b Usage
335
336         \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
337         You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
338         an accessor functor to this object and use \p pool_allocator as an allocator:
339         \code
340         #include <cds/memory/vyukov_queue_pool.h>
341         #include <cds/memory/pool_allocator.h>
342
343         // Pool of Foo object of size 1024.
344         typedef cds::memory::bounded_vyukov_queue_pool< Foo, cds::opt::buffer< cds::opt::v::static_buffer< Foo, 1024 > > pool_type;
345         static pool_type thePool;
346
347         struct pool_accessor {
348             typedef typename pool_type::value_type  value_type;
349
350             pool_type& operator()() const
351             {
352                 return thePool;
353             }
354         };
355
356         // Declare pool allocator
357         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
358
359         // Use pool_allocator
360         // Allocate an object
361         Foo * p = pool_allocator().allocate( 1 );
362
363         // construct object
364         new(p) Foo;
365
366         //...
367
368         // Destruct object
369         p->~Foo();
370
371         // Deallocate object
372         pool_allocator().deallocate( p , 1 );
373         \endcode
374     */
375     template <typename T, CDS_DECL_OPTIONS6>
376     class bounded_vyukov_queue_pool
377     {
378     public:
379         typedef cds::intrusive::VyukovMPMCCycleQueue< T, CDS_OPTIONS6 > queue_type  ;   ///< Queue type
380
381     protected:
382         //@cond
383         struct default_options: public queue_type::options
384         {
385             typedef CDS_DEFAULT_ALLOCATOR   allocator;
386         };
387         typedef typename opt::make_options< default_options, CDS_OPTIONS6 >::type   options;
388         //@endcond
389
390     public:
391         typedef T  value_type ; ///< Value type
392         typedef typename options::allocator::template rebind<value_type>::other allocator_type  ;   ///< allocator type
393
394     protected:
395         //@cond
396         queue_type      m_Queue;
397         value_type *    m_pFirst;
398         value_type *    m_pLast;
399         //@endcond
400
401     protected:
402         //@cond
403         void preallocate_pool()
404         {
405             m_pFirst = allocator_type().allocate( m_Queue.capacity() );
406             m_pLast = m_pFirst + m_Queue.capacity();
407
408             for ( value_type * p = m_pFirst; p < m_pLast; ++p )
409                 CDS_VERIFY( m_Queue.push( *p )) ;   // must be true
410         }
411
412         bool from_pool( value_type * p ) const
413         {
414             return m_pFirst <= p && p < m_pLast;
415         }
416         //@endcond
417
418     public:
419         /// Preallocates the pool of object
420         /**
421             \p nCapacity argument is the queue capacity. It should be passed
422             if the queue is based on dynamically-allocated buffer.
423             See cds::intrusive::VyukovMPMCCycleQueue for explanation.
424         */
425         bounded_vyukov_queue_pool( size_t nCapacity = 0 )
426             : m_Queue( nCapacity )
427         {
428             preallocate_pool();
429         }
430
431         /// Deallocates the pool.
432         ~bounded_vyukov_queue_pool()
433         {
434             m_Queue.clear();
435             allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
436         }
437
438         /// Allocates an object from pool
439         /**
440             The pool supports allocation only single object (\p n = 1).
441             If \p n > 1 the behaviour is undefined.
442
443             If the queue is not empty, the popped value is returned.
444             Otherwise, a \p std::bad_alloc exception is raised.
445         */
446         value_type * allocate( size_t n )
447         {
448             assert( n == 1 );
449
450             value_type * p = m_Queue.pop();
451             if ( p ) {
452                 assert( from_pool(p) );
453                 return p;
454             }
455
456             throw std::bad_alloc();
457         }
458
459         /// Deallocated the object \p p
460         /**
461             The pool supports allocation only single object (\p n = 1).
462             If \p n > 1 the behaviour is undefined.
463
464             \p should be from preallocated pool.
465         */
466         void deallocate( value_type * p, size_t n )
467         {
468             assert( n == 1 );
469
470             if ( p ) {
471                 assert( from_pool( p ));
472                 m_Queue.push( *p );
473             }
474         }
475     };
476
477
478 }}  // namespace cds::memory
479
480
481 #endif // #ifndef __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H