2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
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>
37 namespace cds { namespace memory {
39 /// \p vyukov_queue_pool traits
40 /** @ingroup cds_memory_pool
42 struct vyukov_queue_pool_traits : public cds::intrusive::vyukov_queue::traits
45 typedef CDS_DEFAULT_ALLOCATOR allocator;
48 /// Free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
49 /** @ingroup cds_memory_pool
51 - \p T - the type of object maintaining by free-list
52 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
53 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
57 This free-list is very simple.
58 At construction time, the free-list allocates the array of N items
59 and stores them into queue, where N is the queue capacity.
60 When allocating the free-list tries to pop an object from
61 internal queue i.e. from preallocated pool. If success the popped object is returned.
62 Otherwise a new one is allocated. When deallocating, the free-list checks whether
63 the object is from preallocated pool. If so, the object is pushed into queue, otherwise
64 it is deallocated by using the allocator provided.
65 The pool can manage more than \p N items but only \p N items is contained in the free-list.
69 \p %vyukov_queue_pool should be used together with \ref pool_allocator.
70 You should declare an static object of type \p %vyukov_queue_pool, provide
71 an accessor to that object and use \p pool_allocator as an allocator:
73 #include <cds/memory/vyukov_queue_pool.h>
74 #include <cds/memory/pool_allocator.h>
76 // Pool of Foo object of size 1024.
77 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
79 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
81 typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
82 static pool_type thePool;
84 struct pool_accessor {
85 typedef typename pool_type::value_type value_type;
87 pool_type& operator()() const
93 // Declare pool allocator
94 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
98 Foo * p = pool_allocator().allocate( 1 );
109 pool_allocator().deallocate( p , 1 );
112 template <typename T, typename Traits = vyukov_queue_pool_traits >
113 class vyukov_queue_pool
116 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
119 typedef T value_type ; ///< Value type
120 typedef Traits traits; ///< Traits type
121 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
122 typedef typename traits::back_off back_off; ///< back-off strategy
126 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
129 value_type * m_pFirst;
130 value_type * m_pLast;
135 void preallocate_pool()
137 m_pFirst = cxx_allocator().NewArray( m_Queue.capacity() );
138 m_pLast = m_pFirst + m_Queue.capacity();
140 for ( value_type * p = m_pFirst; p < m_pLast; ++p ) {
141 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
145 bool from_pool( value_type * p ) const
147 return m_pFirst <= p && p < m_pLast;
152 /// Preallocates the pool of object
154 \p nCapacity argument is the queue capacity. It should be passed
155 if the queue is based on dynamically-allocated buffer.
156 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
158 vyukov_queue_pool( size_t nCapacity = 0 )
159 : m_Queue( nCapacity )
164 /// Deallocates the pool.
168 cxx_allocator().Delete( m_pFirst, m_Queue.capacity());
171 /// Allocates an object from pool
173 The pool supports allocation only single object (\p n = 1).
174 If \p n > 1 the behaviour is undefined.
176 If the queue is not empty, the popped value is returned.
177 Otherwise, a new value allocated.
179 value_type * allocate( size_t n )
184 value_type * p = m_Queue.pop();
186 assert( from_pool(p) );
189 // The pool is empty - allocate new from the heap
190 return cxx_allocator().New();
193 /// Deallocated the object \p p
195 The pool supports allocation only single object (\p n = 1).
196 If \p n > 1 the behaviour is undefined.
198 If \p p is from preallocated pool, it pushes into the queue.
199 Otherwise, \p p is deallocated by allocator provided.
201 void deallocate( value_type * p, size_t n )
207 if ( from_pool(p) ) {
208 // The queue can notify about false fullness state
209 // so we push in loop
211 while ( !m_Queue.push( *p ))
215 cxx_allocator().Delete( p );
221 /// Lazy free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
222 /** @ingroup cds_memory_pool
224 - \p T - the type of object maintaining by free-list
225 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
226 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
230 This free-list is very simple.
231 At construction time the pool is empty.
232 When allocating the free-list tries to pop an object from
233 internal queue. If success the popped object is returned.
234 Otherwise a new one is allocated.
235 When deallocating, the free-list tries to push the object into the pool.
236 If internal queue is full, the object is deallocated by using the allocator provided.
237 The pool can manage more than \p N items but only \p N items is placed in the free-list.
241 \p %lazy_vyukov_queue_pool should be used together with \ref pool_allocator.
242 You should declare an static object of type \p %lazy_vyukov_queue_pool, provide
243 an accessor functor to this object and use \p pool_allocator as an allocator:
245 #include <cds/memory/vyukov_queue_pool.h>
246 #include <cds/memory/pool_allocator.h>
248 // Pool of Foo object of size 1024.
249 typedef cds::memory::lazy_vyukov_queue_pool< Foo > pool_type;
250 static pool_type thePool( 1024 );
252 struct pool_accessor {
253 typedef typename pool_type::value_type value_type;
255 pool_type& operator()() const
261 // Declare pool allocator
262 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
264 // Use pool_allocator
265 // Allocate an object
266 Foo * p = pool_allocator().allocate( 1 );
277 pool_allocator().deallocate( p , 1 );
281 template <typename T, typename Traits = vyukov_queue_pool_traits>
282 class lazy_vyukov_queue_pool
285 typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type ; ///< Queue type
288 typedef T value_type ; ///< Value type
289 typedef Traits traits; ///< Pool traits
290 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
294 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
300 /// Constructs empty pool
301 lazy_vyukov_queue_pool( size_t nCapacity = 0 )
302 : m_Queue( nCapacity )
305 /// Deallocates all objects from the pool
306 ~lazy_vyukov_queue_pool()
309 while ( !m_Queue.empty() )
310 a.Delete( m_Queue.pop());
313 /// Allocates an object from pool
315 The pool supports allocation only single object (\p n = 1).
316 If \p n > 1 the behaviour is undefined.
318 If the queue is not empty, the popped value is returned.
319 Otherwise, a new value allocated.
321 value_type * allocate( size_t n )
326 value_type * p = m_Queue.pop();
330 return cxx_allocator().New();
333 /// Deallocates the object \p p
335 The pool supports allocation only single object (\p n = 1).
336 If \p n > 1 the behaviour is undefined.
338 If the queue is not full, \p p is pushed into the queue.
339 Otherwise, \p p is deallocated by allocator provided.
341 void deallocate( value_type * p, size_t n )
347 // Here we ignore false fullness state of the queue
348 if ( !m_Queue.push( *p ))
349 cxx_allocator().Delete( p );
355 /// Bounded free-list based on bounded lock-free queue \p cds::intrusive::VyukovMPMCCycleQueue
356 /** @ingroup cds_memory_pool
358 - \p T - the type of object maintaining by free-list
359 - \p Traits - traits for \p cds::intrusive::VyukovMPMCCycleQueue class plus
360 \p cds::opt::allocator option, defaul is \p vyukov_queue_pool_traits
364 At construction time, the free-list allocates the array of N items
365 and stores them into the queue, where N is the queue capacity.
366 When allocating the free-list tries to pop an object from
367 internal queue i.e. from preallocated pool. If success the popped object is returned.
368 Otherwise a \p std::bad_alloc exception is raised.
369 So, the pool can contain up to \p N items.
370 When deallocating, the object is pushed into the queue.
371 In debug mode \p deallocate() member function asserts
372 that the pointer is from preallocated pool.
376 \p %bounded_vyukov_queue_pool should be used together with \ref pool_allocator.
377 You should declare an static object of type \p %bounded_vyukov_queue_pool, provide
378 an accessor functor to this object and use \p pool_allocator as an allocator:
380 #include <cds/memory/vyukov_queue_pool.h>
381 #include <cds/memory/pool_allocator.h>
383 // Pool of Foo object of size 1024.
384 struct pool_traits: public cds::memory::vyukov_queue_pool_traits
386 typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
388 typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
389 static pool_type thePool;
391 struct pool_accessor {
392 typedef typename pool_type::value_type value_type;
394 pool_type& operator()() const
400 // Declare pool allocator
401 typedef cds::memory::pool_allocator< Foo, pool_accessor > pool_allocator;
403 // Use pool_allocator
404 // Allocate an object
405 Foo * p = pool_allocator().allocate( 1 );
416 pool_allocator().deallocate( p , 1 );
419 template <typename T, typename Traits = vyukov_queue_pool_traits >
420 class bounded_vyukov_queue_pool
423 struct internal_traits : public Traits {
424 typedef cds::atomicity::item_counter item_counter;
428 typedef cds::intrusive::VyukovMPMCCycleQueue< T, internal_traits > queue_type ; ///< Queue type
431 typedef T value_type; ///< Value type
432 typedef Traits traits; ///< Pool traits
433 typedef typename traits::allocator::template rebind<value_type>::other allocator_type ; ///< allocator type
434 typedef typename traits::back_off back_off; ///< back-off strategy
438 typedef cds::details::Allocator< value_type, allocator_type > cxx_allocator;
441 value_type * m_pFirst;
442 value_type * m_pLast;
447 void preallocate_pool()
449 size_t const nCount = m_Queue.capacity();
450 m_pFirst = cxx_allocator().NewArray( nCount );
451 m_pLast = m_pFirst + nCount;
453 for ( value_type * p = m_pFirst; p < m_pLast; ++p )
454 CDS_VERIFY( m_Queue.push( *p )) ; // must be true
457 bool from_pool( value_type * p ) const
459 return m_pFirst <= p && p < m_pLast;
464 /// Preallocates the pool of object
466 \p nCapacity argument is the queue capacity. It should be passed
467 if the queue is based on dynamically-allocated buffer.
468 See \p cds::intrusive::VyukovMPMCCycleQueue for explanation.
470 bounded_vyukov_queue_pool( size_t nCapacity = 0 )
471 : m_Queue( nCapacity )
476 /// Deallocates the pool.
477 ~bounded_vyukov_queue_pool()
480 cxx_allocator().Delete( m_pFirst, m_Queue.capacity() );
483 /// Allocates an object from pool
485 The pool supports allocation only single object (\p n = 1).
486 If \p n > 1 the behaviour is undefined.
488 If the queue is not empty, the popped value is returned.
489 Otherwise, a \p std::bad_alloc exception is raised.
491 value_type * allocate( size_t n )
496 value_type * p = m_Queue.pop();
500 while ( m_Queue.size() ) {
508 throw std::bad_alloc();
512 assert( from_pool(p) );
516 /// Deallocates the object \p p
518 The pool supports allocation only single object (\p n = 1).
519 If \p n > 1 the behaviour is undefined.
521 \p p should be from preallocated pool.
523 void deallocate( value_type * p, size_t n )
529 assert( from_pool( p ));
531 // The queue can notify it is full but that is false fullness state
532 // So, we push in loop
533 while ( !m_Queue.push(*p) )
540 }} // namespace cds::memory
543 #endif // #ifndef CDSLIB_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H