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     /// \p vyukov_queue_pool traits
  12     /** @ingroup cds_memory_pool
  13     */
  14     struct vyukov_queue_pool_traits : public cds::intrusive::vyukov_queue::traits
  15     {
  16         /// Allocator type
  17         typedef CDS_DEFAULT_ALLOCATOR allocator;
  18     };
  19     /// Free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
  20     /** @ingroup cds_memory_pool
  21         Template parameters:
  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
  25
  26         \b Internals
  27
  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.
  37
  38         \b Usage
  39
  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:
  43         \code
  44         #include <cds/memory/vyukov_queue_pool.h>
  45         #include <cds/memory/pool_allocator.h>
  46
  47         // Pool of Foo object of size 1024.
  48         struct pool_traits: public cds::memory::vyukov_queue_pool_traits
  49         {
  50             typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
  51         };
  52         typedef cds::memory::vyukov_queue_pool< Foo, pool_traits > pool_type;
  53         static pool_type thePool;
  54
  55         struct pool_accessor {
  56             typedef typename pool_type::value_type  value_type;
  57
  58             pool_type& operator()() const
  59             {
  60                 return thePool;
  61             }
  62         };
  63
  64         // Declare pool allocator
  65         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
  66
  67         // Use pool_allocator
  68         // Allocate an object
  69         Foo * p = pool_allocator().allocate( 1 );
  70
  71         // construct object
  72         new(p) Foo;
  73
  74         //...
  75
  76         // Destruct object
  77         p->~Foo();
  78
  79         // Deallocate object
  80         pool_allocator().deallocate( p , 1 );
  81         \endcode
  82     */
  83     template <typename T, typename Traits = vyukov_queue_pool_traits >
  84     class vyukov_queue_pool
  85     {
  86     public:
  87         typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type  ;   ///< Queue type
  88
  89     public:
  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
  93
  94     protected:
  95         //@cond
  96         queue_type      m_Queue;
  97         value_type *    m_pFirst;
  98         value_type *    m_pLast;
  99         //@endcond
 100
 101     protected:
 102         //@cond
 103         void preallocate_pool()
 104         {
 105             m_pFirst = allocator_type().allocate( m_Queue.capacity() );
 106             m_pLast = m_pFirst + m_Queue.capacity();
 107
 108             for ( value_type * p = m_pFirst; p < m_pLast; ++p )
 109                 CDS_VERIFY( m_Queue.push( *p )) ;   // must be true
 110         }
 111
 112         bool from_pool( value_type * p ) const
 113         {
 114             return m_pFirst <= p && p < m_pLast;
 115         }
 116         //@endcond
 117
 118     public:
 119         /// Preallocates the pool of object
 120         /**
 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.
 124         */
 125         vyukov_queue_pool( size_t nCapacity = 0 )
 126             : m_Queue( nCapacity )
 127         {
 128             preallocate_pool();
 129         }
 130
 131         /// Deallocates the pool.
 132         ~vyukov_queue_pool()
 133         {
 134             m_Queue.clear();
 135             allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
 136         }
 137
 138         /// Allocates an object from pool
 139         /**
 140             The pool supports allocation only single object (\p n = 1).
 141             If \p n > 1 the behaviour is undefined.
 142
 143             If the queue is not empty, the popped value is returned.
 144             Otherwise, a new value allocated.
 145         */
 146         value_type * allocate( size_t n )
 147         {
 148             assert( n == 1 );
 149
 150             value_type * p = m_Queue.pop();
 151             if ( p ) {
 152                 assert( from_pool(p) );
 153                 return p;
 154             }
 155
 156             return allocator_type().allocate( n );
 157         }
 158
 159         /// Deallocated the object \p p
 160         /**
 161             The pool supports allocation only single object (\p n = 1).
 162             If \p n > 1 the behaviour is undefined.
 163
 164             If \p p is from preallocated pool, it pushes into the queue.
 165             Otherwise, \p p is deallocated by allocator provided.
 166         */
 167         void deallocate( value_type * p, size_t n )
 168         {
 169             assert( n == 1 );
 170
 171             if ( p ) {
 172                 if ( from_pool( p ) )
 173                     m_Queue.push( *p );
 174                 else
 175                     allocator_type().deallocate( p, n );
 176             }
 177         }
 178     };
 179
 180
 181     /// Lazy free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
 182     /** @ingroup cds_memory_pool
 183         Template parameters:
 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
 187
 188         \b Internals
 189
 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.
 198
 199         \b Usage
 200
 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:
 204         \code
 205         #include <cds/memory/vyukov_queue_pool.h>
 206         #include <cds/memory/pool_allocator.h>
 207
 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 );
 211
 212         struct pool_accessor {
 213             typedef typename pool_type::value_type  value_type;
 214
 215             pool_type& operator()() const
 216             {
 217                 return thePool;
 218             }
 219         };
 220
 221         // Declare pool allocator
 222         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
 223
 224         // Use pool_allocator
 225         // Allocate an object
 226         Foo * p = pool_allocator().allocate( 1 );
 227
 228         // construct object
 229         new(p) Foo;
 230
 231         //...
 232
 233         // Destruct object
 234         p->~Foo();
 235
 236         // Deallocate object
 237         pool_allocator().deallocate( p , 1 );
 238         \endcode
 239
 240     */
 241     template <typename T, typename Traits = vyukov_queue_pool_traits>
 242     class lazy_vyukov_queue_pool
 243     {
 244     public:
 245         typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type  ;   ///< Queue type
 246
 247     public:
 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
 251
 252     protected:
 253         //@cond
 254         queue_type      m_Queue;
 255         //@endcond
 256
 257     public:
 258         /// Constructs empty pool
 259         lazy_vyukov_queue_pool( size_t nCapacity = 0 )
 260             : m_Queue( nCapacity )
 261         {}
 262
 263         /// Deallocates all objects from the pool
 264         ~lazy_vyukov_queue_pool()
 265         {
 266             allocator_type a;
 267             while ( !m_Queue.empty() ) {
 268                 value_type * p = m_Queue.pop();
 269                 a.deallocate( p, 1 );
 270             }
 271         }
 272
 273         /// Allocates an object from pool
 274         /**
 275             The pool supports allocation only single object (\p n = 1).
 276             If \p n > 1 the behaviour is undefined.
 277
 278             If the queue is not empty, the popped value is returned.
 279             Otherwise, a new value allocated.
 280         */
 281         value_type * allocate( size_t n )
 282         {
 283             assert( n == 1 );
 284
 285             value_type * p = m_Queue.pop();
 286             if ( p )
 287                 return p;
 288
 289             return allocator_type().allocate( n );
 290         }
 291
 292         /// Deallocated the object \p p
 293         /**
 294             The pool supports allocation only single object (\p n = 1).
 295             If \p n > 1 the behaviour is undefined.
 296
 297             If the queue is not full, \p p is pushed into the queue.
 298             Otherwise, \p p is deallocated by allocator provided.
 299         */
 300         void deallocate( value_type * p, size_t n )
 301         {
 302             assert( n == 1 );
 303
 304             if ( p ) {
 305                 if ( !m_Queue.push( *p ))
 306                     allocator_type().deallocate( p, n );
 307             }
 308         }
 309
 310     };
 311
 312     /// Bounded free-list based on bounded lock-free queue cds::intrusive::VyukovMPMCCycleQueue
 313     /** @ingroup cds_memory_pool
 314         Template parameters:
 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
 318
 319         \b Internals
 320
 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.
 330
 331         \b Usage
 332
 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:
 336         \code
 337         #include <cds/memory/vyukov_queue_pool.h>
 338         #include <cds/memory/pool_allocator.h>
 339
 340         // Pool of Foo object of size 1024.
 341         struct pool_traits: public cds::memory::vyukov_queue_pool_traits
 342         {
 343             typedef cds::opt::v::static_buffer< Foo, 1024 > buffer;
 344         };
 345         typedef cds::memory::bounded_vyukov_queue_pool< Foo, pool_traits > pool_type;
 346         static pool_type thePool;
 347
 348         struct pool_accessor {
 349             typedef typename pool_type::value_type  value_type;
 350
 351             pool_type& operator()() const
 352             {
 353                 return thePool;
 354             }
 355         };
 356
 357         // Declare pool allocator
 358         typedef cds::memory::pool_allocator< Foo, pool_accessor >   pool_allocator;
 359
 360         // Use pool_allocator
 361         // Allocate an object
 362         Foo * p = pool_allocator().allocate( 1 );
 363
 364         // construct object
 365         new(p) Foo;
 366
 367         //...
 368
 369         // Destruct object
 370         p->~Foo();
 371
 372         // Deallocate object
 373         pool_allocator().deallocate( p , 1 );
 374         \endcode
 375     */
 376     template <typename T, typename Traits = vyukov_queue_pool_traits >
 377     class bounded_vyukov_queue_pool
 378     {
 379     public:
 380         typedef cds::intrusive::VyukovMPMCCycleQueue< T, Traits > queue_type  ;   ///< Queue type
 381
 382     public:
 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
 386
 387     protected:
 388         //@cond
 389         queue_type      m_Queue;
 390         value_type *    m_pFirst;
 391         value_type *    m_pLast;
 392         //@endcond
 393
 394     protected:
 395         //@cond
 396         void preallocate_pool()
 397         {
 398             m_pFirst = allocator_type().allocate( m_Queue.capacity() );
 399             m_pLast = m_pFirst + m_Queue.capacity();
 400
 401             for ( value_type * p = m_pFirst; p < m_pLast; ++p )
 402                 CDS_VERIFY( m_Queue.push( *p )) ;   // must be true
 403         }
 404
 405         bool from_pool( value_type * p ) const
 406         {
 407             return m_pFirst <= p && p < m_pLast;
 408         }
 409         //@endcond
 410
 411     public:
 412         /// Preallocates the pool of object
 413         /**
 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.
 417         */
 418         bounded_vyukov_queue_pool( size_t nCapacity = 0 )
 419             : m_Queue( nCapacity )
 420         {
 421             preallocate_pool();
 422         }
 423
 424         /// Deallocates the pool.
 425         ~bounded_vyukov_queue_pool()
 426         {
 427             m_Queue.clear();
 428             allocator_type().deallocate( m_pFirst, m_Queue.capacity() );
 429         }
 430
 431         /// Allocates an object from pool
 432         /**
 433             The pool supports allocation only single object (\p n = 1).
 434             If \p n > 1 the behaviour is undefined.
 435
 436             If the queue is not empty, the popped value is returned.
 437             Otherwise, a \p std::bad_alloc exception is raised.
 438         */
 439         value_type * allocate( size_t n )
 440         {
 441             assert( n == 1 );
 442             CDS_UNUSED( n );
 443
 444             value_type * p = m_Queue.pop();
 445             if ( p ) {
 446                 assert( from_pool(p) );
 447                 return p;
 448             }
 449
 450             throw std::bad_alloc();
 451         }
 452
 453         /// Deallocated the object \p p
 454         /**
 455             The pool supports allocation only single object (\p n = 1).
 456             If \p n > 1 the behaviour is undefined.
 457
 458             \p should be from preallocated pool.
 459         */
 460         void deallocate( value_type * p, size_t n )
 461         {
 462             assert( n == 1 );
 463             CDS_UNUSED( n );
 464
 465             if ( p ) {
 466                 assert( from_pool( p ));
 467                 m_Queue.push( *p );
 468             }
 469         }
 470     };
 471
 472
 473 }}  // namespace cds::memory
 474
 475
 476 #endif // #ifndef __CDS_MEMORY_VYUKOV_QUEUE_ALLOCATOR_H