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
 191         /// Static initialized buffer
 192         /**
 193             One of available type for \p opt::buffer option.
 194
 195             This buffer maintains static array of default-constructed elements.
 196             No dynamic memory allocation performed.
 197
 198             \par Template parameters:
 199                 - \p T - item type the buffer stores
 200                 - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true
 201                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 202                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 203                     size of a power of two.
 204         */
 205         template <typename T, size_t Capacity, bool Exp2 = true>
 206         class initialized_static_buffer
 207         {
 208         public:
 209             typedef T   value_type;   ///< value type
 210             static CDS_CONSTEXPR const size_t c_nCapacity = Capacity;    ///< Capacity
 211             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 212
 213             /// Rebind buffer for other template parameters
 214             template <typename Q, size_t Capacity2 = c_nCapacity, bool Exp22 = c_bExp2>
 215             struct rebind {
 216                 typedef initialized_static_buffer<Q, Capacity2, Exp22> other;   ///< Rebind result type
 217             };
 218
 219             // Capacity must be power of 2
 220             static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two");
 221
 222         private:
 223             //@cond
 224             value_type  m_buffer[c_nCapacity];
 225             //@endcond
 226         public:
 227             /// Construct static buffer
 228             initialized_static_buffer() CDS_NOEXCEPT
 229             {}
 230
 231             /// Construct buffer of given capacity
 232             /**
 233                 This ctor ignores \p nCapacity argument. The capacity of static buffer
 234                 is defined by template argument \p Capacity
 235             */
 236             initialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT
 237             {
 238                 CDS_UNUSED( nCapacity );
 239             }
 240
 241             initialized_static_buffer( const initialized_static_buffer& ) = delete;
 242             initialized_static_buffer& operator =( const initialized_static_buffer& ) = delete;
 243
 244             /// Get item \p i
 245             value_type& operator []( size_t i )
 246             {
 247                 assert( i < capacity());
 248                 return m_buffer[i];
 249             }
 250
 251             /// Get item \p i, const version
 252             const value_type& operator []( size_t i ) const
 253             {
 254                 assert( i < capacity());
 255                 return m_buffer[i];
 256             }
 257
 258             /// Returns buffer capacity
 259             CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT
 260             {
 261                 return c_nCapacity;
 262             }
 263
 264             /// Zeroize the buffer
 265             void zeroize()
 266             {
 267                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 268             }
 269
 270             /// Returns pointer to buffer array
 271             value_type * buffer() CDS_NOEXCEPT
 272             {
 273                 return m_buffer;
 274             }
 275
 276             /// Returns pointer to buffer array
 277             value_type * buffer() const CDS_NOEXCEPT
 278             {
 279                 return m_buffer;
 280             }
 281
 282             /// Returns <tt> idx % capacity() </tt>
 283             /**
 284             If the buffer size is a power of two, binary arithmethics is used
 285             instead of modulo arithmetics
 286             */
 287             size_t mod( size_t idx )
 288             {
 289                 static_if( c_bExp2 )
 290                     return idx & ( capacity() - 1 );
 291                 else
 292                     return idx % capacity();
 293             }
 294         };
 295
 296         /// Dynamically allocated uninitialized buffer
 297         /**
 298             One of available type for \p opt::buffer option.
 299
 300             This buffer maintains dynamically allocated array of uninitialized elements.
 301             You should manually construct each element when needed.
 302             Allocation is performed at construction time.
 303
 304             \par Template parameters:
 305                 - \p T - item type storing in the buffer
 306                 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
 307                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 308                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 309                     size of a power of two.
 310         */
 311         template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
 312         class uninitialized_dynamic_buffer
 313         {
 314         public:
 315             typedef T     value_type;   ///< Value type
 316             typedef Alloc allocator;    ///< Allocator type;
 317             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 318
 319             /// Rebind buffer for other template parameters
 320             template <typename Q, typename Alloc2= allocator, bool Exp22 = c_bExp2>
 321             struct rebind {
 322                 typedef uninitialized_dynamic_buffer<Q, Alloc2, Exp22> other;  ///< Rebinding result type
 323             };
 324
 325             //@cond
 326             typedef typename allocator::template rebind<value_type>::other allocator_type;
 327             //@endcond
 328
 329         private:
 330             //@cond
 331             value_type *    m_buffer;
 332             size_t const    m_nCapacity;
 333             //@endcond
 334         public:
 335             /// Allocates dynamic buffer of given \p nCapacity
 336             /**
 337                 If \p Exp2 class template parameter is \p true then actual capacity
 338                 of allocating buffer is nearest upper to \p nCapacity power of two.
 339             */
 340             uninitialized_dynamic_buffer( size_t nCapacity )
 341                 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
 342             {
 343                 assert( m_nCapacity >= 2 );
 344                 // Capacity must be power of 2
 345                 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
 346
 347                 m_buffer = allocator_type().allocate( m_nCapacity );
 348             }
 349
 350             /// Destroys dynamically allocated buffer
 351             ~uninitialized_dynamic_buffer()
 352             {
 353                 allocator_type().deallocate( m_buffer, m_nCapacity );
 354             }
 355
 356             uninitialized_dynamic_buffer( const uninitialized_dynamic_buffer& ) = delete;
 357             uninitialized_dynamic_buffer& operator =( const uninitialized_dynamic_buffer& ) = delete;
 358
 359             /// Get item \p i
 360             value_type& operator []( size_t i )
 361             {
 362                 assert( i < capacity());
 363                 return m_buffer[i];
 364             }
 365
 366             /// Get item \p i, const version
 367             const value_type& operator []( size_t i ) const
 368             {
 369                 assert( i < capacity());
 370                 return m_buffer[i];
 371             }
 372
 373             /// Returns buffer capacity
 374             size_t capacity() const CDS_NOEXCEPT
 375             {
 376                 return m_nCapacity;
 377             }
 378
 379             /// Zeroize the buffer
 380             void zeroize()
 381             {
 382                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 383             }
 384
 385             /// Returns pointer to buffer array
 386             value_type * buffer() CDS_NOEXCEPT
 387             {
 388                 return m_buffer;
 389             }
 390
 391             /// Returns pointer to buffer array
 392             value_type * buffer() const CDS_NOEXCEPT
 393             {
 394                 return m_buffer;
 395             }
 396
 397             /// Returns <tt> idx % capacity() </tt>
 398             /**
 399                 If the buffer size is a power of two, binary arithmethics is used
 400                 instead of modulo arithmetics
 401             */
 402             size_t mod( size_t idx )
 403             {
 404                 static_if ( c_bExp2 )
 405                     return idx & ( capacity() - 1 );
 406                 else
 407                     return idx % capacity();
 408             }
 409         };
 410
 411
 412         /// Dynamically allocated initialized buffer
 413         /**
 414             One of available type for \p opt::buffer option.
 415
 416             This buffer maintains dynamically allocated array of initialized default-constructed elements.
 417             Allocation is performed at construction time.
 418
 419             \par Template parameters:
 420                 - \p T - item type storing in the buffer
 421                 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
 422                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 423                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 424                     size of a power of two.
 425         */
 426         template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
 427         class initialized_dynamic_buffer
 428         {
 429         public:
 430             typedef T     value_type;   ///< Value type
 431             typedef Alloc allocator;    ///< Allocator type
 432             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 433
 434             /// Rebind buffer for other template parameters
 435             template <typename Q, typename Alloc2= allocator, bool Exp22 = c_bExp2>
 436             struct rebind {
 437                 typedef initialized_dynamic_buffer<Q, Alloc2, Exp22> other;  ///< Rebinding result type
 438             };
 439
 440             //@cond
 441             typedef cds::details::Allocator<value_type, allocator>   allocator_type;
 442             //@endcond
 443
 444         private:
 445             //@cond
 446             value_type *    m_buffer;
 447             size_t const    m_nCapacity;
 448             //@endcond
 449         public:
 450             /// Allocates dynamic buffer of given \p nCapacity
 451             /**
 452                 If \p Exp2 class template parameter is \p true then actual capacity
 453                 of allocating buffer is nearest upper to \p nCapacity power of two.
 454             */
 455             initialized_dynamic_buffer( size_t nCapacity )
 456                 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
 457             {
 458                 assert( m_nCapacity >= 2 );
 459                 // Capacity must be power of 2
 460                 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
 461
 462                 allocator_type a;
 463                 m_buffer = a.NewArray( m_nCapacity );
 464             }
 465
 466             /// Destroys dynamically allocated buffer
 467             ~initialized_dynamic_buffer()
 468             {
 469                 allocator_type a;
 470                 a.Delete( m_buffer, m_nCapacity );
 471             }
 472
 473             initialized_dynamic_buffer( const initialized_dynamic_buffer& ) = delete;
 474             initialized_dynamic_buffer& operator =( const initialized_dynamic_buffer& ) = delete;
 475
 476             /// Get item \p i
 477             value_type& operator []( size_t i )
 478             {
 479                 assert( i < capacity());
 480                 return m_buffer[i];
 481             }
 482
 483             /// Get item \p i, const version
 484             const value_type& operator []( size_t i ) const
 485             {
 486                 assert( i < capacity());
 487                 return m_buffer[i];
 488             }
 489
 490             /// Returns buffer capacity
 491             size_t capacity() const CDS_NOEXCEPT
 492             {
 493                 return m_nCapacity;
 494             }
 495
 496             /// Zeroize the buffer
 497             void zeroize()
 498             {
 499                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]));
 500             }
 501
 502             /// Returns pointer to buffer array
 503             value_type * buffer() CDS_NOEXCEPT
 504             {
 505                 return m_buffer;
 506             }
 507
 508             /// Returns pointer to buffer array
 509             value_type * buffer() const CDS_NOEXCEPT
 510             {
 511                 return m_buffer;
 512             }
 513
 514             /// Returns <tt> idx % capacity() </tt>
 515             /**
 516             If the buffer size is a power of two, binary arithmethics is used
 517             instead of modulo arithmetics
 518             */
 519             size_t mod( size_t idx )
 520             {
 521                 static_if( c_bExp2 )
 522                     return idx & ( capacity() - 1 );
 523                 else
 524                     return idx % capacity();
 525             }
 526         };
 527
 528     }   // namespace v
 529
 530 }}  // namespace cds::opt
 531
 532 #endif // #ifndef CDSLIB_OPT_BUFFER_H