3 #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H
4 #define CDSLIB_ALGO_SPLIT_BITSTRING_H
6 #include <cds/algo/base.h>
8 namespace cds { namespace algo {
10 /// Cuts a bit sequence from fixed-size bit-string
12 The splitter can be used as iterator over bit-string.
13 Each call of \p cut() or \p safe_cut() cuts the bit count specified
14 and keeps the position inside bit-string for the next call.
16 The splitter stores a const reference to bit-string, not a copy.
17 The maximum count of bits that can be cut in a single call is <tt> sizeof(UInt) * 8 </tt>
19 template <typename BitString, typename UInt = size_t >
23 typedef BitString bitstring; ///< Bit-string type
24 typedef UInt uint_type; ///< Bit-string portion type
27 static CDS_CONSTEXPR size_t const c_nHashSize = (sizeof(bitstring) + sizeof(uint_type) - 1) / sizeof(uint_type);
28 static CDS_CONSTEXPR size_t const c_nBitPerByte = 8;
29 static CDS_CONSTEXPR size_t const c_nBitPerHash = sizeof(bitstring) * c_nBitPerByte;
30 static CDS_CONSTEXPR size_t const c_nBitPerInt = sizeof(uint_type) * c_nBitPerByte;
34 /// Initializises the splitter with reference to \p h and zero start bit offset
35 explicit split_bitstring( bitstring const& h )
36 : m_ptr(reinterpret_cast<uint_type const*>( &h ))
40 , m_last( m_ptr + c_nHashSize )
44 /// Initializises the splitter with reference to \p h and start bit offset \p nBitOffset
45 split_bitstring( bitstring const& h, size_t nBitOffset )
46 : m_ptr( reinterpret_cast<uint_type const*>( &h ) + nBitOffset / c_nBitPerInt )
47 , m_offset( nBitOffset )
48 , m_first( reinterpret_cast<uint_type const*>(&h))
50 , m_last( m_first + c_nHashSize )
55 /// Returns \p true if end-of-string is not reached yet
56 explicit operator bool() const
61 /// Returns \p true if end-of-stream encountered
64 return m_offset >= c_nBitPerHash;
67 /// Cuts next \p nBits from bit-string
69 Precondition: <tt>nBits <= sizeof(uint_type) * 8</tt>
71 This function does not manage out-of-bound condition.
72 To control that use \p safe_cut().
74 uint_type cut( size_t nBits )
77 assert( nBits <= c_nBitPerInt );
78 assert( m_offset + nBits <= c_nBitPerHash );
80 assert( m_ptr < m_last );
84 uint_type const nRest = c_nBitPerInt - m_offset % c_nBitPerInt;
86 if ( nBits < nRest ) {
87 result = *m_ptr << ( nRest - nBits );
88 result = result >> ( c_nBitPerInt - nBits );
90 else if ( nBits == nRest ) {
91 result = *m_ptr >> ( c_nBitPerInt - nRest );
93 assert( m_offset % c_nBitPerInt == 0 );
96 uint_type const lsb = *m_ptr >> ( c_nBitPerInt - nRest );
100 result = *m_ptr << ( c_nBitPerInt - nBits );
101 result = result >> ( c_nBitPerInt - nBits );
102 result = (result << nRest) + lsb;
105 assert( m_offset <= c_nBitPerHash );
107 assert( m_ptr <= m_last );
112 /// Cuts up to \p nBits from the bit-string
114 Analog of \p cut() but if \p nBits is more than the rest of bit-string,
115 only the rest is returned.
116 If \p eos() is \p true the function returns 0.
118 uint_type safe_cut( size_t nBits )
123 assert( nBits <= sizeof(uint_type) * c_nBitPerByte );
125 if ( m_offset + nBits > c_nBitPerHash )
126 nBits = c_nBitPerHash - m_offset;
127 return nBits ? cut( nBits ) : 0;
130 /// Resets the splitter
131 void reset() CDS_NOEXCEPT
137 /// Returns pointer to source bitstring
138 bitstring const * source() const
140 return reinterpret_cast<bitstring const *>( m_first );
143 /// Returns current bit offset from beginning of bit-string
144 size_t bit_offset() const
151 uint_type const* m_ptr; ///< current position in the hash
152 size_t m_offset; ///< current bit offset in bit-string
153 uint_type const* m_first; ///< first position
155 uint_type const* m_last; ///< last position
160 }} // namespace cds::algo
162 #endif // #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H