cds/memory/vyukov_queue_pool.h

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