cds/algo/split_bitstring.h

   1 //$$CDS-header$$
   2
   3 #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H
   4 #define CDSLIB_ALGO_SPLIT_BITSTRING_H
   5
   6 #include <cds/algo/base.h>
   7
   8 namespace cds { namespace algo {
   9
  10     /// Cuts a bit sequence from fixed-size bit-string
  11     /**
  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.
  15
  16         The splitter stores a const reference to bit-string, not a copy.
  17         The maximum count of bits that can be cut for single call is <tt> sizeof(UInt) * 8 </tt>
  18     */
  19     template <typename BitString, typename UInt = size_t >
  20     class split_bitstring
  21     {
  22     public:
  23         typedef BitString bitstring;    ///< Bit-string type
  24         typedef UInt      uint_type;    ///< Bit-string portion type
  25
  26         //@cond
  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;
  31         //@endcond
  32
  33     public:
  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 ))
  37             , m_pos(0)
  38             , m_first( m_ptr )
  39 #   ifdef _DEBUG
  40             , m_last( m_ptr + c_nHashSize )
  41 #   endif
  42         {}
  43
  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_pos( nBitOffset )
  48             , m_first( reinterpret_cast<uint_type const*>(&h))
  49 #   ifdef _DEBUG
  50             , m_last( m_first + c_nHashSize )
  51 #   endif
  52         {}
  53
  54
  55         /// Returns \p true if end-of-string is not reached yet
  56         explicit operator bool() const
  57         {
  58             return !eos();
  59         }
  60
  61         /// Returns \p true if end-of-stream encountered
  62         bool eos() const
  63         {
  64             return m_pos >= c_nBitPerHash;
  65         }
  66
  67         /// Cuts next \p nBits from bit-string
  68         /**
  69             Precondition: <tt>nBits <= sizeof(uint_type) * 8</tt>
  70
  71             This function does not manage out-of-bound condition.
  72             To control that use \p safe_cut().
  73         */
  74         uint_type cut( size_t nBits )
  75         {
  76             assert( !eos() );
  77             assert( nBits <= c_nBitPerInt );
  78             assert( m_pos + nBits <= c_nBitPerHash );
  79 #   ifdef _DEBUG
  80             assert( m_ptr < m_last );
  81 #   endif
  82             uint_type result;
  83
  84             uint_type const nRest = c_nBitPerInt - m_pos % c_nBitPerInt;
  85             m_pos += nBits;
  86             if ( nBits < nRest ) {
  87                 result = *m_ptr << ( nRest - nBits );
  88                 result = result >> ( c_nBitPerInt - nBits );
  89             }
  90             else if ( nBits == nRest ) {
  91                 result = *m_ptr >> ( c_nBitPerInt - nRest );
  92                 ++m_ptr;
  93                 assert( m_pos % c_nBitPerInt == 0 );
  94             }
  95             else {
  96                 uint_type const lsb = *m_ptr >> ( c_nBitPerInt - nRest );
  97                 nBits -= nRest;
  98                 ++m_ptr;
  99
 100                 result = *m_ptr << ( c_nBitPerInt - nBits );
 101                 result = result >> ( c_nBitPerInt - nBits );
 102                 result = (result << nRest) + lsb;
 103             }
 104
 105             assert( m_pos <= c_nBitPerHash );
 106 #   ifdef _DEBUG
 107             assert( m_ptr <= m_last );
 108 #   endif
 109             return result;
 110         }
 111
 112         /// Cuts up to \p nBits from the bit-string
 113         /**
 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.
 117         */
 118         uint_type safe_cut( size_t nBits )
 119         {
 120             if ( eos() )
 121                 return 0;
 122
 123             assert( nBits <= sizeof(uint_type) * c_nBitPerByte );
 124
 125             if ( m_pos + nBits > c_nBitPerHash )
 126                 nBits = c_nBitPerHash - m_pos;
 127             return nBits ? cut( nBits ) : 0;
 128         }
 129
 130         /// Resets the splitter
 131         void reset() CDS_NOEXCEPT
 132         {
 133             m_ptr = m_first;
 134             m_pos = 0;
 135         }
 136
 137         // Returns pointer to source bitstring
 138         bitstring const * source() const
 139         {
 140             return reinterpret_cast<bitstring const *>( m_first );
 141         }
 142
 143         /// Returns current bit offset from beginning of bit-string
 144         size_t bit_offset() const
 145         {
 146             return m_pos;
 147         }
 148
 149     private:
 150         //@cond
 151         uint_type const* m_ptr;  ///< current position in the hash
 152         size_t           m_pos;  ///< current position in bits
 153         uint_type const* m_first; ///< first position
 154 #   ifdef _DEBUG
 155         uint_type const* m_last;  ///< last position
 156 #   endif
 157         //@endcond
 158     };
 159
 160 }} // namespace cds::algo
 161
 162 #endif // #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H