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