--- /dev/null
+/*
+ This file is a part of libcds - Concurrent Data Structures library
+
+ (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_ALGO_SPLIT_BITSTRING_H
+#define CDSLIB_ALGO_SPLIT_BITSTRING_H
+
+#include <cds/algo/base.h>
+
+namespace cds { namespace algo {
+
+ /// Cuts a bit sequence from fixed-size bit-string
+ /**
+ The splitter can be used as an iterator over bit-string.
+ Each call of \p cut() or \p safe_cut() cuts the bit count specified
+ and keeps the position inside bit-string for the next call.
+
+ The splitter stores a const reference to bit-string, not a copy.
+ The maximum count of bits that can be cut in a single call is <tt> sizeof(UInt) * 8 </tt>
+
+ The splitter keeps byte order.
+
+ Template parameters:
+ - \p BitString - a fixed-sized type that interprets as bit string
+ - \p BitStringSize - the size of \p BitString in bytes, default is <tt>sizeof( BitString )</tt>.
+ You can specify 0 for default.
+ - \p UInt - an unsigned integer, return type for \p cut(), default is \p unsigned
+
+ There are specialized splitters:
+ - a simplified \p byte_splitter algorithm that is suitable when count is multiple of 8.
+ - \p number_splitter algorithm is suitable for a number
+ */
+ template <typename BitString, size_t BitStringSize = sizeof( BitString ), typename UInt = unsigned >
+ class split_bitstring
+ {
+ public:
+ typedef BitString bitstring; ///< Bit-string type
+ typedef UInt uint_type; ///< Result type of \p cut() function
+ static constexpr size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes
+
+ //@cond
+ static constexpr unsigned const c_nBitPerByte = 8;
+ //@endcond
+
+ public:
+ /// Initializises the splitter with reference to \p h and zero start bit offset
+ explicit split_bitstring( bitstring const& h )
+ : cur_( reinterpret_cast<uint8_t const*>( &h ))
+ , offset_( 0 )
+ , first_( cur_ )
+ , last_( cur_ + c_bitstring_size )
+ {}
+
+ /// Initializises the splitter with reference to \p h and start bit offset \p nBitOffset
+ split_bitstring( bitstring const& h, size_t nBitOffset )
+ : cur_( reinterpret_cast<uint8_t const*>( &h ) + nBitOffset / c_nBitPerByte )
+ , offset_( nBitOffset % c_nBitPerByte )
+ , first_( reinterpret_cast<uint8_t const*>( &h ))
+ , last_( first_ + c_bitstring_size )
+ {}
+
+ /// Returns \p true if end-of-string is not reached yet
+ explicit operator bool() const
+ {
+ return !eos();
+ }
+
+ /// Returns \p true if end-of-stream encountered
+ bool eos() const
+ {
+ return cur_ >= last_;
+ }
+
+ /// Cuts next \p count bits from bit-string
+ /**
+ For performance reason, the function does not manage out-of-bound condition.
+ To control that use \p safe_cut().
+ */
+ uint_type cut( unsigned count )
+ {
+ assert( !eos());
+
+ uint_type result = 0;
+# if defined( CDS_ARCH_LITTLE_ENDIAN )
+ for ( unsigned done = 0; done < count; ) {
+ assert( cur_ < last_ );
+ unsigned bits = count - done;
+ if ( bits > c_nBitPerByte - offset_ )
+ bits = c_nBitPerByte - offset_;
+
+ result |= static_cast<uint_type>(( *cur_ >> offset_ ) & (( 1 << bits ) - 1 )) << done;
+
+ offset_ += bits;
+ assert( offset_ <= c_nBitPerByte );
+ if ( offset_ == c_nBitPerByte ) {
+ offset_ = 0;
+ ++cur_;
+ }
+ done += bits;
+ }
+# else
+ while ( count ) {
+ assert( cur_ < last_ );
+
+ unsigned bits = count <= ( c_nBitPerByte - offset_ ) ? count : c_nBitPerByte - offset_;
+
+ result = ( result << bits ) | (( *cur_ >> offset_ ) & ( ( 1 << bits ) - 1 ));
+
+ offset_ += bits;
+ assert( offset_ <= c_nBitPerByte );
+ if ( offset_ == c_nBitPerByte ) {
+ offset_ = 0;
+ ++cur_;
+ }
+ count -= bits;
+ }
+# endif
+
+ return result;
+ }
+
+ /// Cuts up to \p count from the bit-string
+ /**
+ Safe analog of \p cut() but if \p count is more than the rest of bit-string,
+ only the rest is returned.
+ When \p eos() condition is met the function returns 0.
+ */
+ uint_type safe_cut( unsigned count )
+ {
+ if ( eos())
+ return 0;
+
+ unsigned const rest = static_cast<unsigned>( last_ - cur_ - 1 ) * c_nBitPerByte + ( c_nBitPerByte - offset_ );
+ if ( rest < count )
+ count = rest;
+ return count ? cut( count ) : 0;
+ }
+
+ /// Resets the splitter
+ void reset() noexcept
+ {
+ cur_ = first_;
+ offset_ = 0;
+ }
+
+ /// Returns pointer to source bitstring
+ bitstring const * source() const
+ {
+ return reinterpret_cast<bitstring const *>( first_ );
+ }
+
+ /// Returns current bit offset from beginning of bit-string
+ size_t bit_offset() const
+ {
+ return offset_ + (cur_ - first_) * c_nBitPerByte;
+ }
+
+ /// Returns how many bits remain
+ size_t rest_count() const
+ {
+ return c_bitstring_size * c_nBitPerByte - bit_offset();
+ }
+
+ /// Returns \p true for any argument
+ static constexpr bool is_correct( unsigned /*count*/ )
+ {
+ return true;
+ }
+
+ private:
+ //@cond
+ uint8_t const* cur_;
+ unsigned offset_;
+ uint8_t const* const first_;
+ uint8_t const* const last_;
+ //@endcond
+ };
+
+ /// Simplified \p split_bitstring algorithm when \p count is multiple of 8
+ template <typename BitString, size_t BitStringSize = sizeof( BitString ), typename UInt = unsigned >
+ class byte_splitter
+ {
+ public:
+ typedef BitString bitstring; ///< Bit-string type
+ typedef UInt uint_type; ///< Result type of \p cut() function
+ static constexpr size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes
+
+ //@cond
+ static constexpr unsigned const c_nBitPerByte = 8;
+ //@endcond
+
+ public:
+ /// Initializises the splitter with reference to \p h and zero start bit offset
+ explicit byte_splitter( bitstring const& h )
+ : cur_( reinterpret_cast<uint8_t const*>( &h ))
+ , first_( cur_ )
+ , last_( cur_ + c_bitstring_size )
+ {}
+
+ /// Initializises the splitter with reference to \p h and start bit offset \p nBitOffset
+ byte_splitter( bitstring const& h, size_t nBitOffset )
+ : cur_( reinterpret_cast<uint8_t const*>( &h ) + nBitOffset / c_nBitPerByte )
+ , first_( reinterpret_cast<uint8_t const*>( &h ))
+ , last_( first_ + c_bitstring_size )
+ {
+ assert( is_correct( static_cast<unsigned>( nBitOffset )));
+ assert( !eos());
+ }
+
+ /// Returns \p true if end-of-string is not reached yet
+ explicit operator bool() const
+ {
+ return !eos();
+ }
+
+ /// Returns \p true if end-of-stream encountered
+ bool eos() const
+ {
+ return cur_ >= last_;
+ }
+
+ /// Cuts next \p count bits (must be multiplier of 8) from bit-string
+ /**
+ For performance reason, the function does not manage out-of-bound condition.
+ To control that use \p safe_cut().
+ */
+ uint_type cut( unsigned count )
+ {
+ assert( !eos());
+ assert( is_correct( count ));
+
+ uint_type result = 0;
+
+# if defined( CDS_ARCH_LITTLE_ENDIAN )
+ for ( unsigned i = 0; i < count; i += c_nBitPerByte ) {
+ result |= static_cast<uint_type>( *cur_ ) << i;
+ ++cur_;
+ }
+# else
+ for ( ; count; count -= c_nBitPerByte ) {
+ result = ( result << c_nBitPerByte ) | *cur_;
+ ++cur_;
+ }
+# endif
+
+ return result;
+ }
+
+ /// Cuts up to \p count from the bit-string
+ /**
+ Safe analog of \p cut(): if \p count is more than the rest of bit-string,
+ only the rest is returned.
+ When \p eos() condition is met the function returns 0.
+ */
+ uint_type safe_cut( unsigned count )
+ {
+ if ( eos())
+ return 0;
+
+ unsigned const rest = static_cast<unsigned>( last_ - cur_ - 1 ) * c_nBitPerByte;
+ if ( rest < count )
+ count = rest;
+ return count ? cut( count ) : 0;
+ }
+
+ /// Resets the splitter
+ void reset() noexcept
+ {
+ cur_ = first_;
+ }
+
+ /// Returns pointer to source bitstring
+ bitstring const* source() const
+ {
+ return reinterpret_cast<bitstring const *>( first_ );
+ }
+
+ /// Returns current bit offset from beginning of bit-string
+ size_t bit_offset() const
+ {
+ return (cur_ - first_) * c_nBitPerByte;
+ }
+
+ /// Returns how many bits remain
+ size_t rest_count() const
+ {
+ return c_bitstring_size * c_nBitPerByte - bit_offset();
+ }
+
+ /// Checks if \p count is multiple of 8
+ static constexpr bool is_correct( unsigned count )
+ {
+ return count % 8 == 0;
+ }
+
+ private:
+ //@cond
+ uint8_t const* cur_;
+ uint8_t const* const first_;
+ uint8_t const* const last_;
+ //@endcond
+ };
+
+
+ /// Cuts a bit sequence from a number
+ /**
+ The splitter can be used as an iterator over bit representation of the number of type \p Int.
+ Each call of \p cut() or \p safe_cut() cuts the bit count specified
+ and keeps the position inside the number for the next call.
+ */
+ template <typename Int>
+ class number_splitter
+ {
+ public:
+ typedef Int int_type; ///< Number type
+ typedef Int uint_type; ///< Result type of \p cut() function
+
+ //@cond
+ static constexpr unsigned const c_nBitPerByte = 8;
+ //@endcond
+
+ public:
+ /// Initalizes the splitter with nymber \p n and initial bit offset 0
+ explicit number_splitter( int_type n )
+ : number_( n )
+ , shift_( 0 )
+ {}
+
+ /// Initalizes the splitter with nymber \p n and initial bit offset \p initial_offset
+ number_splitter( int_type n, size_t initial_offset )
+ : number_( n )
+ , shift_( static_cast<unsigned>( initial_offset ))
+ {
+ assert( initial_offset < sizeof( int_type ) * c_nBitPerByte );
+ }
+
+ /// Returns \p true if end-of-string is not reached yet
+ explicit operator bool() const
+ {
+ return !eos();
+ }
+
+ /// Returns \p true if end-of-stream encountered
+ bool eos() const
+ {
+ return shift_ >= sizeof( int_type ) * c_nBitPerByte;
+ }
+
+ /// Cuts next \p count bits (must be multiplier of 8) from the number
+ /**
+ For performance reason, the function does not manage out-of-bound condition.
+ To control that use \p safe_cut().
+ */
+ int_type cut( unsigned count )
+ {
+ assert( !eos());
+ assert( is_correct( count ));
+
+ int_type result = ( number_ >> shift_ ) & (( 1 << count ) - 1 );
+ shift_ += count;
+
+ return result;
+ }
+
+ /// Cuts up to \p count from the bit-string
+ /**
+ Safe analog of \p cut(): if \p count is more than the rest of \p int_type,
+ only the rest is returned.
+ When \p eos() condition is met the function returns 0.
+ */
+ int_type safe_cut( unsigned count )
+ {
+ if ( eos())
+ return 0;
+
+ unsigned rest = static_cast<unsigned>( rest_count());
+ if ( rest < count )
+ count = rest;
+ return count ? cut( count ) : 0;
+ }
+
+ /// Resets the splitter
+ void reset() noexcept
+ {
+ shift_ = 0;
+ }
+
+ /// Returns initial number
+ int_type source() const
+ {
+ return number_;
+ }
+
+ /// Returns current bit offset from beginning of the number
+ size_t bit_offset() const
+ {
+ return shift_;
+ }
+
+ /// Returns how many bits remain
+ size_t rest_count() const
+ {
+ return sizeof( int_type ) * c_nBitPerByte - shift_;
+ }
+
+ /// Checks if \p count is multiple of 8
+ static constexpr bool is_correct( unsigned count )
+ {
+ return count < sizeof( int_type ) * c_nBitPerByte;
+ }
+
+ private:
+ //@cond
+ int_type const number_;
+ unsigned shift_;
+ //@endcond
+ };
+
+ /// Metafunctin to select a most suitable splitter for type \p BitString of size \p BitStringSize
+ template <typename BitString, size_t BitStringSize >
+ struct select_splitter
+ {
+ typedef split_bitstring< BitString, BitStringSize > type; ///< metafunction result
+ };
+
+ //@cond
+# define CDS_SELECT_NUMBER_SPLITTER( num_type ) \
+ template <> struct select_splitter<num_type, sizeof(num_type)> { typedef number_splitter<num_type> type; }
+
+ CDS_SELECT_NUMBER_SPLITTER( int );
+ CDS_SELECT_NUMBER_SPLITTER( unsigned );
+ CDS_SELECT_NUMBER_SPLITTER( short );
+ CDS_SELECT_NUMBER_SPLITTER( unsigned short );
+ CDS_SELECT_NUMBER_SPLITTER( long );
+ CDS_SELECT_NUMBER_SPLITTER( unsigned long );
+ CDS_SELECT_NUMBER_SPLITTER( long long );
+ CDS_SELECT_NUMBER_SPLITTER( unsigned long long );
+
+# undef CDS_SELECT_NUMBER_SPLITTER
+ //@endcond
+
+}} // namespace cds::algo
+
+#endif // #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H
projects / c11concurrency-benchmarks.git / blobdiff