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