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()
+ - \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 = typename std::conditional< BitStringSize % sizeof(size_t) == 0, size_t, unsigned >::type >
+ 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; ///< Bit-string portion type
+ typedef UInt uint_type; ///< Result type of \p cut() function
static CDS_CONSTEXPR size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes
- /// Minimum count of bits to be cut
- static CDS_CONSTEXPR size_t const c_nMinBitCut = 1;
-
//@cond
- static CDS_CONSTEXPR size_t const c_nHashSize = (c_bitstring_size + sizeof(uint_type) - 1) / sizeof(uint_type);
- static CDS_CONSTEXPR size_t const c_nBitPerByte = 8;
- static CDS_CONSTEXPR size_t const c_nBitPerHash = c_bitstring_size * c_nBitPerByte;
- static CDS_CONSTEXPR size_t const c_nBitPerInt = sizeof( uint_type ) * c_nBitPerByte;
+ static CDS_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 )
- : m_ptr(reinterpret_cast<uint_type const*>( &h ))
- , m_offset(0)
- , m_first( m_ptr )
-# ifdef _DEBUG
- , m_last( m_ptr + c_nHashSize )
-# endif
+ : 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 )
- : m_ptr( reinterpret_cast<uint_type const*>( &h ) + nBitOffset / c_nBitPerInt )
- , m_offset( nBitOffset )
- , m_first( reinterpret_cast<uint_type const*>(&h))
-# ifdef _DEBUG
- , m_last( m_first + c_nHashSize )
-# endif
+ : 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
{
/// Returns \p true if end-of-stream encountered
bool eos() const
{
- return m_offset >= c_nBitPerHash;
+ return cur_ >= last_;
}
- /// Cuts next \p nBits from bit-string
+ /// Cuts next \p count bits from bit-string
/**
- Precondition: <tt>nBits <= sizeof(uint_type) * 8</tt>
-
- This function does not manage out-of-bound condition.
+ For performance reason, the function does not manage out-of-bound condition.
To control that use \p safe_cut().
*/
- uint_type cut( size_t nBits )
+ uint_type cut( unsigned count )
{
- assert( !eos());
- assert( nBits <= c_nBitPerInt );
- assert( m_offset + nBits <= c_nBitPerHash );
-# ifdef _DEBUG
- assert( m_ptr < m_last );
-# endif
- uint_type result;
-
- size_t const nRest = c_nBitPerInt - m_offset % c_nBitPerInt;
- m_offset += nBits;
- if ( nBits < nRest ) {
- result = static_cast<uint_type>( *m_ptr << ( nRest - nBits ));
- result = static_cast<uint_type>( result >> ( c_nBitPerInt - nBits ));
+ 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 if ( nBits == nRest ) {
- result = static_cast<uint_type>( *m_ptr >> ( c_nBitPerInt - nRest ));
- ++m_ptr;
- assert( m_offset % c_nBitPerInt == 0 );
- }
- else {
- uint_type const lsb = static_cast<uint_type>( *m_ptr >> ( c_nBitPerInt - nRest ));
- nBits -= nRest;
- ++m_ptr;
-
- result = static_cast<uint_type>( *m_ptr << ( c_nBitPerInt - nBits ));
- result = static_cast<uint_type>( result >> ( c_nBitPerInt - nBits ));
- result = static_cast<uint_type>( (result << nRest) + lsb );
+# 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
- assert( m_offset <= c_nBitPerHash );
-# ifdef _DEBUG
- assert( m_ptr <= m_last );
-# endif
return result;
}
- /// Cuts up to \p nBits from the bit-string
+ /// Cuts up to \p count from the bit-string
/**
- Analog of \p cut() but if \p nBits is more than the rest of bit-string,
+ Safe analog of \p cut() but if \p count is more than the rest of bit-string,
only the rest is returned.
- If \p eos() is \p true the function returns 0.
+ When \p eos() condition is met the function returns 0.
*/
- uint_type safe_cut( size_t nBits )
+ uint_type safe_cut( unsigned count )
{
if ( eos())
return 0;
- assert( nBits <= sizeof(uint_type) * c_nBitPerByte );
-
- if ( m_offset + nBits > c_nBitPerHash )
- nBits = c_nBitPerHash - m_offset;
- return nBits ? cut( nBits ) : 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() CDS_NOEXCEPT
{
- m_ptr = m_first;
- m_offset = 0;
+ cur_ = first_;
+ offset_ = 0;
}
/// Returns pointer to source bitstring
bitstring const * source() const
{
- return reinterpret_cast<bitstring const *>( m_first );
+ 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 CDS_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 CDS_CONSTEXPR size_t const c_bitstring_size = BitStringSize ? BitStringSize : sizeof( BitString ); ///< size of \p BitString in bytes
+
+ //@cond
+ static CDS_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() CDS_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 m_offset;
+ 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 CDS_CONSTEXPR bool is_correct( unsigned count )
+ {
+ return count % 8 == 0;
}
private:
//@cond
- uint_type const* m_ptr; ///< current position in the hash
- size_t m_offset; ///< current bit offset in bit-string
- uint_type const* m_first; ///< first position
-# ifdef _DEBUG
- uint_type const* m_last; ///< last position
-# endif
+ 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 CDS_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() CDS_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 CDS_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 / libcds.git / blobdiff