3 #ifndef __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
4 #define __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
6 #include <cds/details/allocator.h>
7 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
9 namespace cds { namespace memory {
11 /// \p vyukov_queue_pool traits
12 /** @ingroup cds_memory_pool
14 struct vyukov_queue_pool_traits : public cds::intrusive::vyukov_queue::traits
17 typedef CDS_DEFAULT_ALLOCATOR allocator;
19 /// Free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
20 /** @ingroup cds_memory_pool
22 - \p T - the type of object maintaining by free-list
23 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
24 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
28 This free-list is very simple.
29 At construction time, the free-list allocates the array of N items
30 and stores them into queue, where N is the queue capacity.
31 When allocating the free-list tries to pop an object from
32 internal queue i.e. from preallocated pool. If success the popped object is returned.
33 Otherwise a new one is allocated. When deallocating, the free-list checks whether
34 the object is from preallocated pool. If so, the object is pushed into queue, otherwise
35 it is deallocated by using the allocator provided.
36 The pool can manage more than \p N items but only \p N items is contained in the free-list.
40 \p %vyukov_queue_pool should be used together with \ref pool_allocator.
41 You should declare an static object of type \p %vyukov_queue_pool, provide
42 an accessor to that object and use \p pool_allocator as an allocator:
44 #include <cds/memory/vyukov_queue_pool.h>
45 #include <cds/memory/pool_allocator.h>
47 // Pool of Foo object of size 1024.
48 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
50 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
52 typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
53 static pool_type thePool;
55 struct pool_accessor {
56 typedef typename pool_type::value_type value_type;
58 pool_type& operator()() const
64 // Declare pool allocator
65 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
69 Foo * p = pool_allocator().allocate( 1 );
80 pool_allocator().deallocate( p , 1 );
83 template <typename T, typename Traits = vyukov_queue_pool_traits >
84 class vyukov_queue_pool
87 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
90 typedef T value_type ; ///< Value type
91 typedef Traits traits; ///< Traits type
92 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
97 value_type * m_pFirst;
103 void preallocate_pool()
105 m_pFirst = allocator_type().allocate( m_Queue.capacity() );
106 m_pLast = m_pFirst + m_Queue.capacity();
108 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
109 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
112 bool from_pool( value_type * p ) const
114 return m_pFirst <= p && p < m_pLast;
119 /// Preallocates the pool of object
121 \p nCapacity argument is the queue capacity. It should be passed
122 if the queue is based on dynamically-allocated buffer.
123 See cds::intrusive::VyukovMPMCCycleQueue for explanation.
125 vyukov_queue_pool( size_t nCapacity = 0 )
126 : m_Queue( nCapacity )
131 /// Deallocates the pool.
135 allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
138 /// Allocates an object from pool
140 The pool supports allocation only single object (\p n = 1).
141 If \p n > 1 the behaviour is undefined.
143 If the queue is not empty, the popped value is returned.
144 Otherwise, a new value allocated.
146 value_type * allocate( size_t n )
150 value_type * p = m_Queue.pop();
152 assert( from_pool(p) );
156 return allocator_type().allocate( n );
159 /// Deallocated the object \p p
161 The pool supports allocation only single object (\p n = 1).
162 If \p n > 1 the behaviour is undefined.
164 If \p p is from preallocated pool, it pushes into the queue.
165 Otherwise, \p p is deallocated by allocator provided.
167 void deallocate( value_type * p, size_t n )
172 if ( from_pool( p ) )
175 allocator_type().deallocate( p, n );
181 /// Lazy free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
182 /** @ingroup cds_memory_pool
184 - \p T - the type of object maintaining by free-list
185 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
186 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
190 This free-list is very simple.
191 At construction time the pool is empty.
192 When allocating the free-list tries to pop an object from
193 internal queue. If success the popped object is returned.
194 Otherwise a new one is allocated.
195 When deallocating, the free-list tries to push the object into the pool.
196 If internal queue is full, the object is deallocated by using the allocator provided.
197 The pool can manage more than \p N items but only \p N items is placed in the free-list.
201 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
202 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
203 an accessor functor to this object and use \p pool_allocator as an allocator:
205 #include <cds/memory/vyukov_queue_pool.h>
206 #include <cds/memory/pool_allocator.h>
208 // Pool of Foo object of size 1024.
209 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
210 static pool_type thePool( 1024 );
212 struct pool_accessor {
213 typedef typename pool_type::value_type value_type;
215 pool_type& operator()() const
221 // Declare pool allocator
222 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
224 // Use pool_allocator
225 // Allocate an object
226 Foo * p = pool_allocator().allocate( 1 );
237 pool_allocator().deallocate( p , 1 );
241 template <typename T, typename Traits = vyukov_queue_pool_traits>
242 class lazy_vyukov_queue_pool
245 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
248 typedef T value_type ; ///< Value type
249 typedef Traits traits; ///< Pool traits
250 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
258 /// Constructs empty pool
259 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
260 : m_Queue( nCapacity )
263 /// Deallocates all objects from the pool
264 ~lazy_vyukov_queue_pool()
267 while ( !m_Queue.empty() ) {
268 value_type * p = m_Queue.pop();
269 a.deallocate( p, 1 );
273 /// Allocates an object from pool
275 The pool supports allocation only single object (\p n = 1).
276 If \p n > 1 the behaviour is undefined.
278 If the queue is not empty, the popped value is returned.
279 Otherwise, a new value allocated.
281 value_type * allocate( size_t n )
285 value_type * p = m_Queue.pop();
289 return allocator_type().allocate( n );
292 /// Deallocated the object \p p
294 The pool supports allocation only single object (\p n = 1).
295 If \p n > 1 the behaviour is undefined.
297 If the queue is not full, \p p is pushed into the queue.
298 Otherwise, \p p is deallocated by allocator provided.
300 void deallocate( value_type * p, size_t n )
305 if ( !m_Queue.push( *p ))
306 allocator_type().deallocate( p, n );
312 /// Bounded free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
313 /** @ingroup cds_memory_pool
315 - \p T - the type of object maintaining by free-list
316 - \p Traits - traits for cds::intrusive::VyukovMPMCCycleQueue class plus
317 cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
321 At construction time, the free-list allocates the array of N items
322 and stores them into the queue, where N is the queue capacity.
323 When allocating the free-list tries to pop an object from
324 internal queue i.e. from preallocated pool. If success the popped object is returned.
325 Otherwise a \p std::bad_alloc exception is raised.
326 So, the pool can contain up to \p N items.
327 When deallocating, the object is pushed into the queue.
328 In debug mode \p deallocate() member function asserts
329 that the pointer is from preallocated pool.
333 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
334 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
335 an accessor functor to this object and use \p pool_allocator as an allocator:
337 #include <cds/memory/vyukov_queue_pool.h>
338 #include <cds/memory/pool_allocator.h>
340 // Pool of Foo object of size 1024.
341 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
343 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
345 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
346 static pool_type thePool;
348 struct pool_accessor {
349 typedef typename pool_type::value_type value_type;
351 pool_type& operator()() const
357 // Declare pool allocator
358 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
360 // Use pool_allocator
361 // Allocate an object
362 Foo * p = pool_allocator().allocate( 1 );
373 pool_allocator().deallocate( p , 1 );
376 template <typename T, typename Traits = vyukov_queue_pool_traits >
377 class bounded_vyukov_queue_pool
380 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
383 typedef T value_type; ///< Value type
384 typedef Traits traits; ///< Pool traits
385 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
390 value_type * m_pFirst;
391 value_type * m_pLast;
396 void preallocate_pool()
398 m_pFirst = allocator_type().allocate( m_Queue.capacity() );
399 m_pLast = m_pFirst + m_Queue.capacity();
401 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
402 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
405 bool from_pool( value_type * p ) const
407 return m_pFirst <= p && p < m_pLast;
412 /// Preallocates the pool of object
414 \p nCapacity argument is the queue capacity. It should be passed
415 if the queue is based on dynamically-allocated buffer.
416 See cds::intrusive::VyukovMPMCCycleQueue for explanation.
418 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
419 : m_Queue( nCapacity )
424 /// Deallocates the pool.
425 ~bounded_vyukov_queue_pool()
428 allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
431 /// Allocates an object from pool
433 The pool supports allocation only single object (\p n = 1).
434 If \p n > 1 the behaviour is undefined.
436 If the queue is not empty, the popped value is returned.
437 Otherwise, a \p std::bad_alloc exception is raised.
439 value_type * allocate( size_t n )
443 value_type * p = m_Queue.pop();
445 assert( from_pool(p) );
449 throw std::bad_alloc();
452 /// Deallocated the object \p p
454 The pool supports allocation only single object (\p n = 1).
455 If \p n > 1 the behaviour is undefined.
457 \p should be from preallocated pool.
459 void deallocate( value_type * p, size_t n )
464 assert( from_pool( p ));
471 }} // namespace cds::memory
474 #endif // #ifndef __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H