X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fopt%2Fbuffer.h;h=2623069eca3d967a69a33e0fcbd82422e8d22f4e;hb=e360657e258514a73ab99af0bd726c21d05156fc;hp=d80efc918843f34936ef4c960922f4fef7f983c9;hpb=68c4bb6ce67fc8fccf8d850868e1e95b91f334a4;p=libcds.git diff --git a/cds/opt/buffer.h b/cds/opt/buffer.h index d80efc91..2623069e 100644 --- a/cds/opt/buffer.h +++ b/cds/opt/buffer.h @@ -1,8 +1,37 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library -#ifndef __CDS_OPT_BUFFER_H -#define __CDS_OPT_BUFFER_H + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSLIB_OPT_BUFFER_H +#define CDSLIB_OPT_BUFFER_H + +#include #include #include #include @@ -19,8 +48,19 @@ namespace cds { namespace opt { The template parameter \p Type should be rebindable. Implementations: - - opt::v::static_buffer - - opt::v::dynamic_buffer + - \p opt::v::initialized_static_buffer + - \p opt::v::uninitialized_static_buffer + - \p opt::v::initialized_dynamic_buffer + - \p opt::v::uninitialized_dynamic_buffer + + Uninitialized buffer is just an array of uninitialized elements. + Each element should be manually constructed, for example with a placement new operator. + When the uninitialized buffer is destroyed the destructor of its element is not called. + + Initialized buffer contains default-constructed elements. Element destructor is called automatically + when the buffer is destroyed. + + @note Usually, initialized and uninitialized buffers are not interchangeable. */ template struct buffer { @@ -34,11 +74,13 @@ namespace cds { namespace opt { namespace v { - /// Static buffer (see \p cds::opt::buffer option) + /// Static uninitialized buffer /** - One of available type for opt::buffer type-option. + One of available type for \p opt::buffer option. - This buffer maintains static array. No dynamic memory allocation performed. + This buffer maintains static array of uninitialized elements. + You should manually construct each element when needed. + No dynamic memory allocation performed. \par Template parameters: - \p T - item type the buffer stores @@ -48,53 +90,179 @@ namespace cds { namespace opt { size of a power of two. */ template - class static_buffer + class uninitialized_static_buffer { public: - typedef T value_type ; ///< value type - static const size_t c_nCapacity = Capacity ; ///< Capacity - static const bool c_bExp2 = Exp2; ///< \p Exp2 flag + typedef T value_type; ///< value type + static CDS_CONSTEXPR const size_t c_nCapacity = Capacity; ///< Capacity + static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag /// Rebind buffer for other template parameters template struct rebind { - typedef static_buffer other ; ///< Rebind result type + typedef uninitialized_static_buffer other; ///< Rebind result type }; + + // Capacity must be power of 2 + static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two"); + private: //@cond - value_type m_buffer[c_nCapacity]; + union element { + value_type v; + char c; + + element() + {} + }; + + element m_buffer[c_nCapacity]; //@endcond public: /// Construct static buffer - static_buffer() + uninitialized_static_buffer() CDS_NOEXCEPT + {} + + /// Construct buffer of given capacity + /** + This ctor ignores \p nCapacity argument. The capacity of static buffer + is defined by template argument \p Capacity + */ + uninitialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT { - // Capacity must be power of 2 - static_assert( !c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two" ); + CDS_UNUSED( nCapacity ); + } + + uninitialized_static_buffer( const uninitialized_static_buffer& ) = delete; + uninitialized_static_buffer& operator =( const uninitialized_static_buffer& ) = delete; + + /// Get item \p i + value_type& operator []( size_t i ) + { + assert( i < capacity()); + return m_buffer[i].v; + } + + /// Get item \p i, const version + const value_type& operator []( size_t i ) const + { + assert( i < capacity()); + return m_buffer[i].v; + } + + /// Returns buffer capacity + CDS_CONSTEXPR size_t capacity() const CDS_NOEXCEPT + { + return c_nCapacity; + } + + /// Zeroize the buffer + void zeroize() + { + memset( m_buffer, 0, capacity() * sizeof(m_buffer[0])); + } + + /// Returns pointer to buffer array + value_type * buffer() CDS_NOEXCEPT + { + return &( m_buffer[0].v ); + } + + /// Returns pointer to buffer array + value_type * buffer() const CDS_NOEXCEPT + { + return &( m_buffer[0].v ); } + + /// Returns idx % capacity() + /** + If the buffer size is a power of two, binary arithmethics is used + instead of modulo arithmetics + */ + size_t mod( size_t idx ) + { + static_if( c_bExp2 ) + return idx & ( capacity() - 1 ); + else + return idx % capacity(); + } + + //@cond + template + typename std::enable_if< sizeof(I) != sizeof(size_t), size_t >::type mod( I idx ) + { + static_if( c_bExp2 ) + return static_cast( idx & static_cast( capacity() - 1 )); + else + return static_cast( idx % capacity()); + } + //@endcond + }; + + /// Static initialized buffer + /** + One of available type for \p opt::buffer option. + + This buffer maintains static array of default-constructed elements. + No dynamic memory allocation performed. + + \par Template parameters: + - \p T - item type the buffer stores + - \p Capacity - the capacity of buffer. The value must be power of two if \p Exp2 is \p true + - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two. + Otherwise it can be any positive number. Usually, it is required that the buffer has + size of a power of two. + */ + template + class initialized_static_buffer + { + public: + typedef T value_type; ///< value type + static CDS_CONSTEXPR const size_t c_nCapacity = Capacity; ///< Capacity + static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag + + /// Rebind buffer for other template parameters + template + struct rebind { + typedef initialized_static_buffer other; ///< Rebind result type + }; + + // Capacity must be power of 2 + static_assert(!c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two"); + + private: + //@cond + value_type m_buffer[c_nCapacity]; + //@endcond + public: + /// Construct static buffer + initialized_static_buffer() CDS_NOEXCEPT + {} + /// Construct buffer of given capacity /** This ctor ignores \p nCapacity argument. The capacity of static buffer is defined by template argument \p Capacity */ - static_buffer( size_t nCapacity ) + initialized_static_buffer( size_t nCapacity ) CDS_NOEXCEPT { CDS_UNUSED( nCapacity ); - // Capacity must be power of 2 - static_assert( !c_bExp2 || (c_nCapacity & (c_nCapacity - 1)) == 0, "Capacity must be power of two"); - //assert( c_nCapacity == nCapacity ); } + initialized_static_buffer( const initialized_static_buffer& ) = delete; + initialized_static_buffer& operator =( const initialized_static_buffer& ) = delete; + /// Get item \p i value_type& operator []( size_t i ) { - assert( i < capacity() ); + assert( i < capacity()); return m_buffer[i]; } /// Get item \p i, const version const value_type& operator []( size_t i ) const { - assert( i < capacity() ); + assert( i < capacity()); return m_buffer[i]; } @@ -107,35 +275,178 @@ namespace cds { namespace opt { /// Zeroize the buffer void zeroize() { - memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]) ); + memset( m_buffer, 0, capacity() * sizeof(m_buffer[0])); } /// Returns pointer to buffer array - value_type * buffer() + value_type * buffer() CDS_NOEXCEPT { return m_buffer; } - /// Returns pointer to buffer array (const version) - value_type * buffer() const + /// Returns pointer to buffer array + value_type * buffer() const CDS_NOEXCEPT { return m_buffer; } + /// Returns idx % capacity() + /** + If the buffer size is a power of two, binary arithmethics is used + instead of modulo arithmetics + */ + size_t mod( size_t idx ) + { + static_if( c_bExp2 ) + return idx & ( capacity() - 1 ); + else + return idx % capacity(); + } + + //@cond + template + typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx ) + { + static_if( c_bExp2 ) + return static_cast( idx & static_cast( capacity() - 1 )); + else + return static_cast( idx % capacity()); + } + //@endcond + }; + + /// Dynamically allocated uninitialized buffer + /** + One of available type for \p opt::buffer option. + + This buffer maintains dynamically allocated array of uninitialized elements. + You should manually construct each element when needed. + Allocation is performed at construction time. + + \par Template parameters: + - \p T - item type storing in the buffer + - \p Alloc - an allocator used for allocating internal buffer (\p std::allocator interface) + - \p Exp2 - a boolean flag. If it is \p true the buffer capacity must be power of two. + Otherwise it can be any positive number. Usually, it is required that the buffer has + size of a power of two. + */ + template + class uninitialized_dynamic_buffer + { + public: + typedef T value_type; ///< Value type + typedef Alloc allocator; ///< Allocator type; + static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag + + /// Rebind buffer for other template parameters + template + struct rebind { + typedef uninitialized_dynamic_buffer other; ///< Rebinding result type + }; + + //@cond + typedef typename allocator::template rebind::other allocator_type; + //@endcond + private: //@cond - // non-copyable - static_buffer(const static_buffer&); - void operator =(const static_buffer&); + value_type * m_buffer; + size_t const m_nCapacity; + //@endcond + public: + /// Allocates dynamic buffer of given \p nCapacity + /** + If \p Exp2 class template parameter is \p true then actual capacity + of allocating buffer is nearest upper to \p nCapacity power of two. + */ + uninitialized_dynamic_buffer( size_t nCapacity ) + : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity ) + { + assert( m_nCapacity >= 2 ); + // Capacity must be power of 2 + assert( !c_bExp2 || (m_nCapacity & (m_nCapacity - 1)) == 0 ); + + m_buffer = allocator_type().allocate( m_nCapacity ); + } + + /// Destroys dynamically allocated buffer + ~uninitialized_dynamic_buffer() + { + allocator_type().deallocate( m_buffer, m_nCapacity ); + } + + uninitialized_dynamic_buffer( const uninitialized_dynamic_buffer& ) = delete; + uninitialized_dynamic_buffer& operator =( const uninitialized_dynamic_buffer& ) = delete; + + /// Get item \p i + value_type& operator []( size_t i ) + { + assert( i < capacity()); + return m_buffer[i]; + } + + /// Get item \p i, const version + const value_type& operator []( size_t i ) const + { + assert( i < capacity()); + return m_buffer[i]; + } + + /// Returns buffer capacity + size_t capacity() const CDS_NOEXCEPT + { + return m_nCapacity; + } + + /// Zeroize the buffer + void zeroize() + { + memset( m_buffer, 0, capacity() * sizeof(m_buffer[0])); + } + + /// Returns pointer to buffer array + value_type * buffer() CDS_NOEXCEPT + { + return m_buffer; + } + + /// Returns pointer to buffer array + value_type * buffer() const CDS_NOEXCEPT + { + return m_buffer; + } + + /// Returns idx % capacity() + /** + If the buffer size is a power of two, binary arithmethics is used + instead of modulo arithmetics + */ + size_t mod( size_t idx ) + { + static_if ( c_bExp2 ) + return idx & ( capacity() - 1 ); + else + return idx % capacity(); + } + + //@cond + template + typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx ) + { + static_if ( c_bExp2 ) + return static_cast( idx & static_cast( capacity() - 1 )); + else + return static_cast( idx % capacity()); + } //@endcond }; - /// Dynamically allocated buffer + /// Dynamically allocated initialized buffer /** - One of available \p cds::opt::buffer type-option. + One of available type for \p opt::buffer option. - This buffer maintains dynamically allocated array. + This buffer maintains dynamically allocated array of initialized default-constructed elements. Allocation is performed at construction time. \par Template parameters: @@ -146,20 +457,21 @@ namespace cds { namespace opt { size of a power of two. */ template - class dynamic_buffer + class initialized_dynamic_buffer { public: - typedef T value_type ; ///< Value type + typedef T value_type; ///< Value type + typedef Alloc allocator; ///< Allocator type static CDS_CONSTEXPR const bool c_bExp2 = Exp2; ///< \p Exp2 flag /// Rebind buffer for other template parameters - template + template struct rebind { - typedef dynamic_buffer other ; ///< Rebinding result type + typedef initialized_dynamic_buffer other; ///< Rebinding result type }; //@cond - typedef cds::details::Allocator allocator_type; + typedef cds::details::Allocator allocator_type; //@endcond private: @@ -173,7 +485,7 @@ namespace cds { namespace opt { If \p Exp2 class template parameter is \p true then actual capacity of allocating buffer is nearest upper to \p nCapacity power of two. */ - dynamic_buffer( size_t nCapacity ) + initialized_dynamic_buffer( size_t nCapacity ) : m_nCapacity( c_bExp2 ? beans::ceil2(nCapacity) : nCapacity ) { assert( m_nCapacity >= 2 ); @@ -185,23 +497,26 @@ namespace cds { namespace opt { } /// Destroys dynamically allocated buffer - ~dynamic_buffer() + ~initialized_dynamic_buffer() { allocator_type a; a.Delete( m_buffer, m_nCapacity ); } + initialized_dynamic_buffer( const initialized_dynamic_buffer& ) = delete; + initialized_dynamic_buffer& operator =( const initialized_dynamic_buffer& ) = delete; + /// Get item \p i value_type& operator []( size_t i ) { - assert( i < capacity() ); + assert( i < capacity()); return m_buffer[i]; } /// Get item \p i, const version const value_type& operator []( size_t i ) const { - assert( i < capacity() ); + assert( i < capacity()); return m_buffer[i]; } @@ -214,26 +529,43 @@ namespace cds { namespace opt { /// Zeroize the buffer void zeroize() { - memset( m_buffer, 0, capacity() * sizeof(m_buffer[0]) ); + memset( m_buffer, 0, capacity() * sizeof(m_buffer[0])); } /// Returns pointer to buffer array - value_type * buffer() + value_type * buffer() CDS_NOEXCEPT { return m_buffer; } - /// Returns pointer to buffer array (const version) - value_type * buffer() const + /// Returns pointer to buffer array + value_type * buffer() const CDS_NOEXCEPT { return m_buffer; } - private: + /// Returns idx % capacity() + /** + If the buffer size is a power of two, binary arithmethics is used + instead of modulo arithmetics + */ + size_t mod( size_t idx ) + { + static_if( c_bExp2 ) + return idx & ( capacity() - 1 ); + else + return idx % capacity(); + } + //@cond - // non-copyable - dynamic_buffer(const dynamic_buffer&); - void operator =(const dynamic_buffer&); + template + typename std::enable_if< sizeof( I ) != sizeof( size_t ), size_t >::type mod( I idx ) + { + static_if( c_bExp2 ) + return static_cast( idx & static_cast( capacity() - 1 )); + else + return static_cast( idx % capacity()); + } //@endcond }; @@ -241,4 +573,4 @@ namespace cds { namespace opt { }} // namespace cds::opt -#endif // #ifndef __CDS_OPT_BUFFER_H +#endif // #ifndef CDSLIB_OPT_BUFFER_H