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