2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
32 #define CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H
34 #include <cds/details/allocator.h>
35 #include <cds/intrusive/vyukov_mpmc_cycle_queue.h>
36 #include <cds/details/throw_exception.h>
38 namespace cds { namespace memory {
40 /// \p vyukov_queue_pool traits
41 /** @ingroup cds_memory_pool
43 struct vyukov_queue_pool_traits : public cds::intrusive::vyukov_queue::traits
46 typedef CDS_DEFAULT_ALLOCATOR allocator;
49 /// Free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
50 /** @ingroup cds_memory_pool
52 - \p T - the type of object maintaining by free-list. \p T must be default constructible.
53 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
54 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
58 This free-list is very simple.
59 At construction time, the free-list allocates the array of N items
60 and stores them into queue, where N is the queue capacity.
61 When allocating the free-list tries to pop an object from
62 internal queue i.e. from preallocated pool. If success the popped object is returned.
63 Otherwise a new one is allocated. When deallocating, the free-list checks whether
64 the object is from preallocated pool. If so, the object is pushed into queue, otherwise
65 it is deallocated by using the allocator provided.
66 The pool can manage more than \p N items but only \p N items is contained in the free-list.
70 \p %vyukov_queue_pool should be used together with \ref pool_allocator.
71 You should declare an static object of type \p %vyukov_queue_pool, provide
72 an accessor to that object and use \p pool_allocator as an allocator:
74 #include <cds/memory/vyukov_queue_pool.h>
75 #include <cds/memory/pool_allocator.h>
77 // Pool of Foo object of size 1024.
78 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
80 typedef cds::opt::v::uninitialized_static_buffer< Foo, 1024 > buffer;
82 typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
83 static pool_type thePool;
85 struct pool_accessor {
86 typedef typename pool_type::value_type value_type;
88 pool_type& operator()() const
94 // Declare pool allocator
95 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
99 Foo * p = pool_allocator().allocate( 1 );
110 pool_allocator().deallocate( p , 1 );
113 template <typename T, typename Traits = vyukov_queue_pool_traits >
114 class vyukov_queue_pool
117 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
120 typedef T value_type ; ///< Value type
121 typedef Traits traits; ///< Traits type
122 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
123 typedef typename traits::back_off back_off; ///< back-off strategy
127 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
128 typedef typename cxx_allocator::allocator_type std_allocator;
131 value_type * m_pFirst;
132 value_type * m_pLast;
137 void preallocate_pool()
139 m_pFirst = std_allocator().allocate( m_Queue.capacity());
140 m_pLast = m_pFirst + m_Queue.capacity();
142 for ( value_type * p = m_pFirst; p < m_pLast; ++p ) {
143 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
147 bool from_pool( value_type * p ) const
149 return m_pFirst <= p && p < m_pLast;
154 /// Preallocates the pool of object
156 \p nCapacity argument is the queue capacity. It should be passed
157 if the queue is based on dynamically-allocated buffer.
158 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
160 vyukov_queue_pool( size_t nCapacity = 0 )
161 : m_Queue( nCapacity )
166 /// Deallocates the pool.
170 std_allocator().deallocate( m_pFirst, m_Queue.capacity());
173 /// Allocates an object from pool
175 The pool supports allocation only single object (\p n = 1).
176 If \p n > 1 the behavior is undefined.
178 If the queue is not empty, the popped value is returned.
179 Otherwise, a new value allocated.
181 value_type * allocate( size_t n )
186 value_type * p = m_Queue.pop();
188 assert( from_pool(p));
189 return new( p ) value_type;
191 // The pool is empty - allocate new from the heap
192 return cxx_allocator().New();
195 /// Deallocated the object \p p
197 The pool supports allocation only single object (\p n = 1).
198 If \p n > 1 the behavior is undefined.
200 If \p p is from preallocated pool, it pushes into the queue.
201 Otherwise, \p p is deallocated by allocator provided.
203 void deallocate( value_type * p, size_t n )
211 // The queue can notify about false fullness state
212 // so we push in loop
214 while ( !m_Queue.push( *p ))
218 cxx_allocator().Delete( p );
224 /// Lazy free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
225 /** @ingroup cds_memory_pool
227 - \p T - the type of object maintaining by free-list. \p T must be default constructible
228 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
229 \p cds::opt::allocator option, default is \p vyukov_queue_pool_traits
233 This free-list is very simple.
234 At construction time the pool is empty.
235 When allocating the free-list tries to pop an object from
236 internal queue. If success the popped object is returned.
237 Otherwise a new one is allocated.
238 When deallocating, the free-list tries to push the object into the pool.
239 If internal queue is full, the object is deallocated by using the allocator provided.
240 The pool can manage more than \p N items but only \p N items is placed in the free-list.
244 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
245 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
246 an accessor functor to this object and use \p pool_allocator as an allocator:
248 #include <cds/memory/vyukov_queue_pool.h>
249 #include <cds/memory/pool_allocator.h>
251 // Pool of Foo object of size 1024.
252 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
253 static pool_type thePool( 1024 );
255 struct pool_accessor {
256 typedef typename pool_type::value_type value_type;
258 pool_type& operator()() const
264 // Declare pool allocator
265 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
267 // Use pool_allocator
268 // Allocate an object
269 Foo * p = pool_allocator().allocate( 1 );
280 pool_allocator().deallocate( p , 1 );
284 template <typename T, typename Traits = vyukov_queue_pool_traits>
285 class lazy_vyukov_queue_pool
288 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
291 typedef T value_type ; ///< Value type
292 typedef Traits traits; ///< Pool traits
293 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
297 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
298 typedef typename cxx_allocator::allocator_type std_allocator;
304 /// Constructs empty pool
305 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
306 : m_Queue( nCapacity )
309 /// Deallocates all objects from the pool
310 ~lazy_vyukov_queue_pool()
313 while ( !m_Queue.empty())
314 a.deallocate( m_Queue.pop(), 1 );
317 /// Allocates an object from pool
319 The pool supports allocation only single object (\p n = 1).
320 If \p n > 1 the behavior is undefined.
322 If the queue is not empty, the popped value is returned.
323 Otherwise, a new value allocated.
325 value_type * allocate( size_t n )
330 value_type * p = m_Queue.pop();
332 return new( p ) value_type;
334 return cxx_allocator().New();
337 /// Deallocates the object \p p
339 The pool supports allocation only single object (\p n = 1).
340 If \p n > 1 the behaviour is undefined.
342 If the queue is not full, \p p is pushed into the queue.
343 Otherwise, \p p is deallocated by allocator provided.
345 void deallocate( value_type * p, size_t n )
352 // Here we ignore false fullness state of the queue
353 if ( !m_Queue.push( *p ))
354 std_allocator().deallocate( p, 1 );
360 /// Bounded free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
361 /** @ingroup cds_memory_pool
363 - \p T - the type of object maintaining by free-list. \p T must be default-constructible
364 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
365 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
369 At construction time, the free-list allocates the array of N items
370 and stores them into the queue, where N is the queue capacity.
371 When allocating the free-list tries to pop an object from
372 internal queue i.e. from preallocated pool. If success the popped object is returned.
373 Otherwise a \p std::bad_alloc exception is raised.
374 So, the pool can contain up to \p N items.
375 When deallocating, the object is pushed into the queue.
376 In debug mode \p deallocate() member function asserts
377 that the pointer is from preallocated pool.
381 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
382 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
383 an accessor functor to this object and use \p pool_allocator as an allocator:
385 #include <cds/memory/vyukov_queue_pool.h>
386 #include <cds/memory/pool_allocator.h>
388 // Pool of Foo object of size 1024.
389 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
391 typedef cds::opt::v::uninitialized_static_buffer< Foo, 1024 > buffer;
393 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
394 static pool_type thePool;
396 struct pool_accessor {
397 typedef typename pool_type::value_type value_type;
399 pool_type& operator()() const
405 // Declare pool allocator
406 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
408 // Use pool_allocator
409 // Allocate an object
410 Foo * p = pool_allocator().allocate( 1 );
421 pool_allocator().deallocate( p , 1 );
424 template <typename T, typename Traits = vyukov_queue_pool_traits >
425 class bounded_vyukov_queue_pool
428 struct internal_traits : public Traits {
429 typedef cds::atomicity::item_counter item_counter;
433 typedef cds::intrusive::VyukovMPMCCycleQueue< T, internal_traits > queue_type ; ///< Queue type
436 typedef T value_type; ///< Value type
437 typedef Traits traits; ///< Pool traits
438 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
439 typedef typename traits::back_off back_off; ///< back-off strategy
443 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
444 typedef typename cxx_allocator::allocator_type std_allocator;
447 value_type * m_pFirst;
448 value_type * m_pLast;
453 void preallocate_pool()
455 size_t const nCount = m_Queue.capacity();
456 m_pFirst = std_allocator().allocate( nCount );
457 m_pLast = m_pFirst + nCount;
459 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
460 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
463 bool from_pool( value_type * p ) const
465 return m_pFirst <= p && p < m_pLast;
470 /// Preallocates the pool of object
472 \p nCapacity argument is the queue capacity. It should be passed
473 if the queue is based on dynamically-allocated buffer.
474 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
476 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
477 : m_Queue( nCapacity )
482 /// Deallocates the pool.
483 ~bounded_vyukov_queue_pool()
486 std_allocator().deallocate( m_pFirst, m_Queue.capacity());
489 /// Allocates an object from pool
491 The pool supports allocation only single object (\p n = 1).
492 If \p n > 1 the behaviour is undefined.
494 If the queue is not empty, the popped value is returned.
495 Otherwise, a \p std::bad_alloc exception is raised.
497 value_type * allocate( size_t n )
502 value_type * p = m_Queue.pop();
506 while ( m_Queue.size()) {
514 CDS_THROW_EXCEPTION( std::bad_alloc() );
518 assert( from_pool(p));
522 /// Deallocates the object \p p
524 The pool supports allocation only single object (\p n = 1).
525 If \p n > 1 the behaviour is undefined.
527 \p p should be from preallocated pool.
529 void deallocate( value_type * p, size_t n )
535 assert( from_pool( p ));
537 // The queue can notify it is full but that is false fullness state
538 // So, we push in loop
539 while ( !m_Queue.push(*p))
546 }} // namespace cds::memory
549 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H