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         Initialized and uninitialized buffers are not
  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             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 291
 292             /// Rebind buffer for other template parameters
 293             template <typename Q, typename Alloc2=Alloc, bool Exp22 = c_bExp2>
 294             struct rebind {
 295                 typedef uninitialized_dynamic_buffer<Q, Alloc2, Exp22> other;  ///< Rebinding result type
 296             };
 297
 298             //@cond
 299             typedef typename Alloc::template rebind<value_type>::other allocator_type;
 300             //@endcond
 301
 302         private:
 303             //@cond
 304             value_type *    m_buffer;
 305             size_t const    m_nCapacity;
 306             //@endcond
 307         public:
 308             /// Allocates dynamic buffer of given \p nCapacity
 309             /**
 310                 If \p Exp2 class template parameter is \p true then actual capacity
 311                 of allocating buffer is nearest upper to \p nCapacity power of two.
 312             */
 313             uninitialized_dynamic_buffer( size_t nCapacity )
 314                 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
 315             {
 316                 assert( m_nCapacity >= 2 );
 317                 // Capacity must be power of 2
 318                 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
 319
 320                 m_buffer = allocator_type().allocate( m_nCapacity );
 321             }
 322
 323             /// Destroys dynamically allocated buffer
 324             ~uninitialized_dynamic_buffer()
 325             {
 326                 allocator_type().deallocate( m_buffer, m_nCapacity );
 327             }
 328
 329             uninitialized_dynamic_buffer( const uninitialized_dynamic_buffer& ) = delete;
 330             uninitialized_dynamic_buffer& operator =( const uninitialized_dynamic_buffer& ) = delete;
 331
 332             /// Get item \p i
 333             value_type& operator []( size_t i )
 334             {
 335                 assert( i < capacity() );
 336                 return m_buffer[i];
 337             }
 338
 339             /// Get item \p i, const version
 340             const value_type& operator []( size_t i ) const
 341             {
 342                 assert( i < capacity() );
 343                 return m_buffer[i];
 344             }
 345
 346             /// Returns buffer capacity
 347             size_t capacity() const CDS_NOEXCEPT
 348             {
 349                 return m_nCapacity;
 350             }
 351
 352             /// Zeroize the buffer
 353             void zeroize()
 354             {
 355                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]) );
 356             }
 357
 358             /// Returns pointer to buffer array
 359             value_type * buffer() CDS_NOEXCEPT
 360             {
 361                 return m_buffer;
 362             }
 363
 364             /// Returns pointer to buffer array
 365             value_type * buffer() const CDS_NOEXCEPT
 366             {
 367                 return m_buffer;
 368             }
 369         };
 370
 371
 372         /// Dynamically allocated initialized buffer
 373         /**
 374             One of available type for \p opt::buffer option.
 375
 376             This buffer maintains dynamically allocated array of initialized default-constructed elements.
 377             Allocation is performed at construction time.
 378
 379             \par Template parameters:
 380                 - \p T - item type storing in the buffer
 381                 - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface)
 382                 - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two.
 383                     Otherwise it can be any positive number. Usually, it is required that the buffer has
 384                     size of a power of two.
 385         */
 386         template <typename T, class Alloc = CDS_DEFAULT_ALLOCATOR, bool Exp2 = true>
 387         class initialized_dynamic_buffer
 388         {
 389         public:
 390             typedef T   value_type;   ///< Value type
 391             static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag
 392
 393             /// Rebind buffer for other template parameters
 394             template <typename Q, typename Alloc2=Alloc, bool Exp22 = c_bExp2>
 395             struct rebind {
 396                 typedef initialized_dynamic_buffer<Q, Alloc2, Exp22> other;  ///< Rebinding result type
 397             };
 398
 399             //@cond
 400             typedef cds::details::Allocator<value_type, Alloc>   allocator_type;
 401             //@endcond
 402
 403         private:
 404             //@cond
 405             value_type *    m_buffer;
 406             size_t const    m_nCapacity;
 407             //@endcond
 408         public:
 409             /// Allocates dynamic buffer of given \p nCapacity
 410             /**
 411                 If \p Exp2 class template parameter is \p true then actual capacity
 412                 of allocating buffer is nearest upper to \p nCapacity power of two.
 413             */
 414             initialized_dynamic_buffer( size_t nCapacity )
 415                 : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity )
 416             {
 417                 assert( m_nCapacity >= 2 );
 418                 // Capacity must be power of 2
 419                 assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 );
 420
 421                 allocator_type a;
 422                 m_buffer = a.NewArray( m_nCapacity );
 423             }
 424
 425             /// Destroys dynamically allocated buffer
 426             ~initialized_dynamic_buffer()
 427             {
 428                 allocator_type a;
 429                 a.Delete( m_buffer, m_nCapacity );
 430             }
 431
 432             initialized_dynamic_buffer( const initialized_dynamic_buffer& ) = delete;
 433             initialized_dynamic_buffer& operator =( const initialized_dynamic_buffer& ) = delete;
 434
 435             /// Get item \p i
 436             value_type& operator []( size_t i )
 437             {
 438                 assert( i < capacity() );
 439                 return m_buffer[i];
 440             }
 441
 442             /// Get item \p i, const version
 443             const value_type& operator []( size_t i ) const
 444             {
 445                 assert( i < capacity() );
 446                 return m_buffer[i];
 447             }
 448
 449             /// Returns buffer capacity
 450             size_t capacity() const CDS_NOEXCEPT
 451             {
 452                 return m_nCapacity;
 453             }
 454
 455             /// Zeroize the buffer
 456             void zeroize()
 457             {
 458                 memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]) );
 459             }
 460
 461             /// Returns pointer to buffer array
 462             value_type * buffer() CDS_NOEXCEPT
 463             {
 464                 return m_buffer;
 465             }
 466
 467             /// Returns pointer to buffer array
 468             value_type * buffer() const CDS_NOEXCEPT
 469             {
 470                 return m_buffer;
 471             }
 472         };
 473
 474     }   // namespace v
 475
 476 }}  // namespace cds::opt
 477
 478 #endif // #ifndef CDSLIB_OPT_BUFFER_H