X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Falgo%2Fsplit_bitstring.h;h=ef4909e1e2ef8a0085f411bc1e001923846a7dfb;hb=8abb8f5e76bd8d723aff8078934ee30e59fa117a;hp=7935e8e7f69cd2bd305d154a631d9c4d8de31b87;hpb=01470a158e4c8d196b0b43291b75f68156be34ba;p=libcds.git
diff --git a/cds/algo/split_bitstring.h b/cds/algo/split_bitstring.h
index 7935e8e7..ef4909e1 100644
--- a/cds/algo/split_bitstring.h
+++ b/cds/algo/split_bitstring.h
@@ -44,52 +44,47 @@ namespace cds { namespace algo {
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 sizeof(UInt) * 8
+ 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 sizeof( BitString ).
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 ::type >
+ template
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( &h ))
- , m_offset(0)
- , m_first( m_ptr )
-# ifdef _DEBUG
- , m_last( m_ptr + c_nHashSize )
-# endif
+ : cur_( reinterpret_cast( &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( &h ) + nBitOffset / c_nBitPerInt )
- , m_offset( nBitOffset )
- , m_first( reinterpret_cast(&h))
-# ifdef _DEBUG
- , m_last( m_first + c_nHashSize )
-# endif
+ : cur_( reinterpret_cast( &h ) + nBitOffset / c_nBitPerByte )
+ , offset_( nBitOffset % c_nBitPerByte )
+ , first_( reinterpret_cast( &h ))
+ , last_( first_ + c_bitstring_size )
{}
-
/// Returns \p true if end-of-string is not reached yet
explicit operator bool() const
{
@@ -99,102 +94,377 @@ namespace cds { namespace algo {
/// 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: nBits <= sizeof(uint_type) * 8
-
- 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( *m_ptr << ( nRest - nBits ));
- result = static_cast( result >> ( c_nBitPerInt - nBits ));
- }
- else if ( nBits == nRest ) {
- result = static_cast( *m_ptr >> ( c_nBitPerInt - nRest ));
- ++m_ptr;
- assert( m_offset % c_nBitPerInt == 0 );
+
+ 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(( *cur_ >> offset_ ) & (( 1 << bits ) - 1 )) << done;
+
+ offset_ += bits;
+ assert( offset_ <= c_nBitPerByte );
+ if ( offset_ == c_nBitPerByte ) {
+ offset_ = 0;
+ ++cur_;
+ }
+ done += bits;
}
- else {
- uint_type const lsb = static_cast( *m_ptr >> ( c_nBitPerInt - nRest ));
- nBits -= nRest;
- ++m_ptr;
-
- result = static_cast( *m_ptr << ( c_nBitPerInt - nBits ));
- result = static_cast( result >> ( c_nBitPerInt - nBits ));
- result = static_cast( (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( 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( m_first );
+ return reinterpret_cast( first_ );
}
/// Returns current bit offset from beginning of bit-string
size_t bit_offset() const
{
- return m_offset;
+ 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
- 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_;
+ 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
+ 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( &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( &h ) + nBitOffset / c_nBitPerByte )
+ , first_( reinterpret_cast( &h ))
+ , last_( first_ + c_bitstring_size )
+ {
+ assert( is_correct( static_cast( 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( *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( 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( 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 CDS_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
+ 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( 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( 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
+ struct select_splitter
+ {
+ typedef split_bitstring< BitString, BitStringSize > type; ///< metafunction result
+ };
+
+ //@cond
+# define CDS_SELECT_NUMBER_SPLITTER( num_type ) \
+ template <> struct select_splitter { typedef number_splitter 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