cds/opt/buffer.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  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.
  18
  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.
  29 */
  30
  31 #ifndef CDSLIB_OPT_BUFFER_H
  32 #define CDSLIB_OPT_BUFFER_H
  33
  34 #include <memory.h>
  35 #include <cds/details/defs.h>
  36 #include <cds/user_setup/allocator.h>
  37 #include <cds/details/allocator.h>
  38 #include <cds/algo/int_algo.h>
  39
  40 namespace cds { namespace opt {
  41
  42     /// [type-option] Option setter for user-provided plain buffer
  43     /**
  44         This option is used by some container as a random access array for storing
  45         container's item; for example, a bounded queue may use
  46         this option to define underlying buffer implementation.
  47
  48         The template parameter \p Type should be rebindable.
  49
  50         Implementations:
  51             - \p opt::v::initialized_static_buffer
  52             - \p opt::v::uninitialized_static_buffer
  53             - \p opt::v::initialized_dynamic_buffer
  54             - \p opt::v::uninitialized_dynamic_buffer
  55
  56         Uninitialized buffer is just an array of uninitialized elements.
  57         Each element should be manually constructed, for example with a placement new operator.
  58         When the uninitialized buffer is destroyed the destructor of its element is not called.
  59
  60         Initialized buffer contains default-constructed elements. Element destructor is called automatically
  61         when the buffer is destroyed.
  62
  63         @note Usually, initialized and uninitialized buffers are not interchangeable.
  64     */
  65     template <typename Type>
  66     struct buffer {
  67         //@cond
  68         template <typename Base> struct pack: public Base
  69         {
  70             typedef Type buffer;
  71         };
  72         //@endcond
  73     };
  74
  75     namespace v {
  76
  77         /// Static uninitialized buffer
  78         /**
  79             One of available type for \p opt::buffer option.
  80
  81             This buffer maintains static array of uninitialized elements.
  82             You should manually construct each element when needed.
  83             No dynamic memory allocation performed.
  84
  85             \par Template parameters:
  86                 - \p T - item type the buffer stores
  87                 - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true
  88                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
  89                     Otherwise it can be any positive number. Usually, it is required that the buffer has
  90                     size of a power of two.
  91         */
  92         template <typename T, size_t Capacity, bool Exp2 = true>
  93         class uninitialized_static_buffer
  94         {
  95         public:
  96             typedef T   value_type;   ///< value type
  97             static CDS_CONSTEXPR const size_t c_nCapacity = Capacity;    ///< Capacity
  98             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
  99
 100             /// Rebind buffer for other template parameters
 101             template <typename Q, size_t Capacity2 = c_nCapacity, bool Exp22 = c_bExp2>
 102             struct rebind {
 103                 typedef uninitialized_static_buffer<Q, Capacity2, Exp22> other;   ///< Rebind result type
 104             };
 105
 106             // Capacity must be power of 2
 107             static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two");
 108
 109         private:
 110             //@cond
 111             union element {
 112                 value_type v;
 113                 char       c;
 114
 115                 element()
 116                 {}
 117             };
 118
 119             element  m_buffer[c_nCapacity];
 120             //@endcond
 121         public:
 122             /// Construct static buffer
 123             uninitialized_static_buffer() CDS_NOEXCEPT
 124             {}
 125
 126             /// Construct buffer of given capacity
 127             /**
 128                 This ctor ignores \p nCapacity argument. The capacity of static buffer
 129                 is defined by template argument \p Capacity
 130             */
 131             uninitialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT
 132             {
 133                 CDS_UNUSED( nCapacity );
 134             }
 135
 136             uninitialized_static_buffer( const uninitialized_static_buffer& ) = delete;
 137             uninitialized_static_buffer& operator =( const uninitialized_static_buffer& ) = delete;
 138
 139             /// Get item \p i
 140             value_type& operator []( size_t i )
 141             {
 142                 assert( i < capacity());
 143                 return m_buffer[i].v;
 144             }
 145
 146             /// Get item \p i, const version
 147             const value_type& operator []( size_t i ) const
 148             {
 149                 assert( i < capacity());
 150                 return m_buffer[i].v;
 151             }
 152
 153             /// Returns buffer capacity
 154             CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
 155             {
 156                 return c_nCapacity;
 157             }
 158
 159             /// Zeroize the buffer
 160             void zeroize()
 161             {
 162                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 163             }
 164
 165             /// Returns pointer to buffer array
 166             value_type * buffer() CDS_NOEXCEPT
 167             {
 168                 return &( m_buffer[0].v );
 169             }
 170
 171             /// Returns pointer to buffer array
 172             value_type * buffer() const CDS_NOEXCEPT
 173             {
 174                 return &( m_buffer[0].v );
 175             }
 176
 177             /// Returns <tt> idx % capacity() </tt>
 178             /**
 179                 If the buffer size is a power of two, binary arithmethics is used
 180                 instead of modulo arithmetics
 181             */
 182             size_t mod( size_t idx )
 183             {
 184                 static_if( c_bExp2 )
 185                     return idx & ( capacity() - 1 );
 186                 else
 187                     return idx % capacity();
 188             }
 189
 190             //@cond
 191             template <typename I>
 192             typename std::enable_if< sizeof(I) != sizeof(size_t), size_t >::type mod( I idx )
 193             {
 194                 static_if( c_bExp2 )
 195                     return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
 196                 else
 197                     return static_cast<size_t>( idx % capacity());
 198             }
 199             //@endcond
 200         };
 201
 202         /// Static initialized buffer
 203         /**
 204             One of available type for \p opt::buffer option.
 205
 206             This buffer maintains static array of default-constructed elements.
 207             No dynamic memory allocation performed.
 208
 209             \par Template parameters:
 210                 - \p T - item type the buffer stores
 211                 - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true
 212                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 213                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 214                     size of a power of two.
 215         */
 216         template <typename T, size_t Capacity, bool Exp2 = true>
 217         class initialized_static_buffer
 218         {
 219         public:
 220             typedef T   value_type;   ///< value type
 221             static CDS_CONSTEXPR const size_t c_nCapacity = Capacity;    ///< Capacity
 222             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 223
 224             /// Rebind buffer for other template parameters
 225             template <typename Q, size_t Capacity2 = c_nCapacity, bool Exp22 = c_bExp2>
 226             struct rebind {
 227                 typedef initialized_static_buffer<Q, Capacity2, Exp22> other;   ///< Rebind result type
 228             };
 229
 230             // Capacity must be power of 2
 231             static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two");
 232
 233         private:
 234             //@cond
 235             value_type  m_buffer[c_nCapacity];
 236             //@endcond
 237         public:
 238             /// Construct static buffer
 239             initialized_static_buffer() CDS_NOEXCEPT
 240             {}
 241
 242             /// Construct buffer of given capacity
 243             /**
 244                 This ctor ignores \p nCapacity argument. The capacity of static buffer
 245                 is defined by template argument \p Capacity
 246             */
 247             initialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT
 248             {
 249                 CDS_UNUSED( nCapacity );
 250             }
 251
 252             initialized_static_buffer( const initialized_static_buffer& ) = delete;
 253             initialized_static_buffer& operator =( const initialized_static_buffer& ) = delete;
 254
 255             /// Get item \p i
 256             value_type& operator []( size_t i )
 257             {
 258                 assert( i < capacity());
 259                 return m_buffer[i];
 260             }
 261
 262             /// Get item \p i, const version
 263             const value_type& operator []( size_t i ) const
 264             {
 265                 assert( i < capacity());
 266                 return m_buffer[i];
 267             }
 268
 269             /// Returns buffer capacity
 270             CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
 271             {
 272                 return c_nCapacity;
 273             }
 274
 275             /// Zeroize the buffer
 276             void zeroize()
 277             {
 278                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 279             }
 280
 281             /// Returns pointer to buffer array
 282             value_type * buffer() CDS_NOEXCEPT
 283             {
 284                 return m_buffer;
 285             }
 286
 287             /// Returns pointer to buffer array
 288             value_type * buffer() const CDS_NOEXCEPT
 289             {
 290                 return m_buffer;
 291             }
 292
 293             /// Returns <tt> idx % capacity() </tt>
 294             /**
 295             If the buffer size is a power of two, binary arithmethics is used
 296             instead of modulo arithmetics
 297             */
 298             size_t mod( size_t idx )
 299             {
 300                 static_if( c_bExp2 )
 301                     return idx & ( capacity() - 1 );
 302                 else
 303                     return idx % capacity();
 304             }
 305
 306             //@cond
 307             template <typename I>
 308             typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx )
 309             {
 310                 static_if( c_bExp2 )
 311                     return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
 312                 else
 313                     return static_cast<size_t>( idx % capacity());
 314             }
 315             //@endcond
 316         };
 317
 318         /// Dynamically allocated uninitialized buffer
 319         /**
 320             One of available type for \p opt::buffer option.
 321
 322             This buffer maintains dynamically allocated array of uninitialized elements.
 323             You should manually construct each element when needed.
 324             Allocation is performed at construction time.
 325
 326             \par Template parameters:
 327                 - \p T - item type storing in the buffer
 328                 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
 329                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 330                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 331                     size of a power of two.
 332         */
 333         template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
 334         class uninitialized_dynamic_buffer
 335         {
 336         public:
 337             typedef T     value_type;   ///< Value type
 338             typedef Alloc allocator;    ///< Allocator type;
 339             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 340
 341             /// Rebind buffer for other template parameters
 342             template <typename Q, typename Alloc2= allocator, bool Exp22 = c_bExp2>
 343             struct rebind {
 344                 typedef uninitialized_dynamic_buffer<Q, Alloc2, Exp22> other;  ///< Rebinding result type
 345             };
 346
 347             //@cond
 348             typedef typename allocator::template rebind<value_type>::other allocator_type;
 349             //@endcond
 350
 351         private:
 352             //@cond
 353             value_type *    m_buffer;
 354             size_t const    m_nCapacity;
 355             //@endcond
 356         public:
 357             /// Allocates dynamic buffer of given \p nCapacity
 358             /**
 359                 If \p Exp2 class template parameter is \p true then actual capacity
 360                 of allocating buffer is nearest upper to \p nCapacity power of two.
 361             */
 362             uninitialized_dynamic_buffer( size_t nCapacity )
 363                 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
 364             {
 365                 assert( m_nCapacity >= 2 );
 366                 // Capacity must be power of 2
 367                 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
 368
 369                 m_buffer = allocator_type().allocate( m_nCapacity );
 370             }
 371
 372             /// Destroys dynamically allocated buffer
 373             ~uninitialized_dynamic_buffer()
 374             {
 375                 allocator_type().deallocate( m_buffer, m_nCapacity );
 376             }
 377
 378             uninitialized_dynamic_buffer( const uninitialized_dynamic_buffer& ) = delete;
 379             uninitialized_dynamic_buffer& operator =( const uninitialized_dynamic_buffer& ) = delete;
 380
 381             /// Get item \p i
 382             value_type& operator []( size_t i )
 383             {
 384                 assert( i < capacity());
 385                 return m_buffer[i];
 386             }
 387
 388             /// Get item \p i, const version
 389             const value_type& operator []( size_t i ) const
 390             {
 391                 assert( i < capacity());
 392                 return m_buffer[i];
 393             }
 394
 395             /// Returns buffer capacity
 396             size_t capacity() const CDS_NOEXCEPT
 397             {
 398                 return m_nCapacity;
 399             }
 400
 401             /// Zeroize the buffer
 402             void zeroize()
 403             {
 404                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 405             }
 406
 407             /// Returns pointer to buffer array
 408             value_type * buffer() CDS_NOEXCEPT
 409             {
 410                 return m_buffer;
 411             }
 412
 413             /// Returns pointer to buffer array
 414             value_type * buffer() const CDS_NOEXCEPT
 415             {
 416                 return m_buffer;
 417             }
 418
 419             /// Returns <tt> idx % capacity() </tt>
 420             /**
 421                 If the buffer size is a power of two, binary arithmethics is used
 422                 instead of modulo arithmetics
 423             */
 424             size_t mod( size_t idx )
 425             {
 426                 static_if ( c_bExp2 )
 427                     return idx & ( capacity() - 1 );
 428                 else
 429                     return idx % capacity();
 430             }
 431
 432             //@cond
 433             template <typename I>
 434             typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx )
 435             {
 436                 static_if ( c_bExp2 )
 437                     return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
 438                 else
 439                     return static_cast<size_t>( idx % capacity());
 440             }
 441             //@endcond
 442         };
 443
 444
 445         /// Dynamically allocated initialized buffer
 446         /**
 447             One of available type for \p opt::buffer option.
 448
 449             This buffer maintains dynamically allocated array of initialized default-constructed elements.
 450             Allocation is performed at construction time.
 451
 452             \par Template parameters:
 453                 - \p T - item type storing in the buffer
 454                 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
 455                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 456                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 457                     size of a power of two.
 458         */
 459         template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
 460         class initialized_dynamic_buffer
 461         {
 462         public:
 463             typedef T     value_type;   ///< Value type
 464             typedef Alloc allocator;    ///< Allocator type
 465             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 466
 467             /// Rebind buffer for other template parameters
 468             template <typename Q, typename Alloc2= allocator, bool Exp22 = c_bExp2>
 469             struct rebind {
 470                 typedef initialized_dynamic_buffer<Q, Alloc2, Exp22> other;  ///< Rebinding result type
 471             };
 472
 473             //@cond
 474             typedef cds::details::Allocator<value_type, allocator>   allocator_type;
 475             //@endcond
 476
 477         private:
 478             //@cond
 479             value_type *    m_buffer;
 480             size_t const    m_nCapacity;
 481             //@endcond
 482         public:
 483             /// Allocates dynamic buffer of given \p nCapacity
 484             /**
 485                 If \p Exp2 class template parameter is \p true then actual capacity
 486                 of allocating buffer is nearest upper to \p nCapacity power of two.
 487             */
 488             initialized_dynamic_buffer( size_t nCapacity )
 489                 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
 490             {
 491                 assert( m_nCapacity >= 2 );
 492                 // Capacity must be power of 2
 493                 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
 494
 495                 allocator_type a;
 496                 m_buffer = a.NewArray( m_nCapacity );
 497             }
 498
 499             /// Destroys dynamically allocated buffer
 500             ~initialized_dynamic_buffer()
 501             {
 502                 allocator_type a;
 503                 a.Delete( m_buffer, m_nCapacity );
 504             }
 505
 506             initialized_dynamic_buffer( const initialized_dynamic_buffer& ) = delete;
 507             initialized_dynamic_buffer& operator =( const initialized_dynamic_buffer& ) = delete;
 508
 509             /// Get item \p i
 510             value_type& operator []( size_t i )
 511             {
 512                 assert( i < capacity());
 513                 return m_buffer[i];
 514             }
 515
 516             /// Get item \p i, const version
 517             const value_type& operator []( size_t i ) const
 518             {
 519                 assert( i < capacity());
 520                 return m_buffer[i];
 521             }
 522
 523             /// Returns buffer capacity
 524             size_t capacity() const CDS_NOEXCEPT
 525             {
 526                 return m_nCapacity;
 527             }
 528
 529             /// Zeroize the buffer
 530             void zeroize()
 531             {
 532                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 533             }
 534
 535             /// Returns pointer to buffer array
 536             value_type * buffer() CDS_NOEXCEPT
 537             {
 538                 return m_buffer;
 539             }
 540
 541             /// Returns pointer to buffer array
 542             value_type * buffer() const CDS_NOEXCEPT
 543             {
 544                 return m_buffer;
 545             }
 546
 547             /// Returns <tt> idx % capacity() </tt>
 548             /**
 549             If the buffer size is a power of two, binary arithmethics is used
 550             instead of modulo arithmetics
 551             */
 552             size_t mod( size_t idx )
 553             {
 554                 static_if( c_bExp2 )
 555                     return idx & ( capacity() - 1 );
 556                 else
 557                     return idx % capacity();
 558             }
 559
 560             //@cond
 561             template <typename I>
 562             typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx )
 563             {
 564                 static_if( c_bExp2 )
 565                     return static_cast<size_t>( idx & static_cast<I>( capacity() - 1 ));
 566                 else
 567                     return static_cast<size_t>( idx % capacity());
 568             }
 569             //@endcond
 570         };
 571
 572     }   // namespace v
 573
 574 }}  // namespace cds::opt
 575
 576 #endif // #ifndef CDSLIB_OPT_BUFFER_H