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 an 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
  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         /// Returns \p true if end-of-string is not reached yet
  45         explicit operator bool() const
  46         {
  47             return !eos();
  48         }
  49
  50         /// Returns \p true if end-of-stream encountered
  51         bool eos() const
  52         {
  53             return m_pos >= c_nBitPerHash;
  54         }
  55
  56         /// Cuts next \p nBits from bit-string
  57         /**
  58             Precondition: <tt>nBits <= sizeof(uint_type) * 8</tt>
  59
  60             This function does not manage out-of-bound condition.
  61             To control that use \p safe_cut().
  62         */
  63         uint_type cut( size_t nBits )
  64         {
  65             assert( !eos() );
  66             assert( nBits <= c_nBitPerInt );
  67             assert( m_pos + nBits <= c_nBitPerHash );
  68 #   ifdef _DEBUG
  69             assert( m_ptr < m_last );
  70 #   endif
  71             uint_type result;
  72
  73             uint_type const nRest = c_nBitPerInt - m_pos % c_nBitPerInt;
  74             m_pos += nBits;
  75             if ( nBits < nRest ) {
  76                 result = *m_ptr << ( nRest - nBits );
  77                 result = result >> ( c_nBitPerInt - nBits );
  78             }
  79             else if ( nBits == nRest ) {
  80                 result = *m_ptr >> ( c_nBitPerInt - nRest );
  81                 ++m_ptr;
  82             }
  83             else {
  84                 uint_type const lsb = *m_ptr >> ( c_nBitPerInt - nRest );
  85                 nBits -= nRest;
  86                 ++m_ptr;
  87
  88                 result = *m_ptr << ( c_nBitPerInt - nBits );
  89                 result = result >> ( c_nBitPerInt - nBits );
  90                 result = (result << nRest) + lsb;
  91             }
  92
  93             assert( m_pos <= c_nBitPerHash );
  94 #   ifdef _DEBUG
  95             assert( m_ptr <= m_last );
  96 #   endif
  97             return result;
  98         }
  99
 100         /// Cuts up to \p nBits from the bit-string
 101         /**
 102             Analog of \p cut() but if \p nBits is more than the rest of bit-string,
 103             only the rest is returned.
 104             If \p eos() is \p true the function returns 0.
 105         */
 106         uint_type safe_cut( size_t nBits )
 107         {
 108             if ( eos() )
 109                 return 0;
 110
 111             assert( nBits <= sizeof(uint_type) * c_nBitPerByte );
 112
 113             if ( m_pos + nBits > c_nBitPerHash )
 114                 nBits = c_nBitPerHash - m_pos;
 115             return nBits ? cut( nBits ) : 0;
 116         }
 117
 118         /// Resets the splitter
 119         void reset()
 120         {
 121             m_ptr = m_first;
 122             m_pos = 0;
 123         }
 124
 125     private:
 126         //@cond
 127         uint_type const* m_ptr;  ///< current position in the hash
 128         size_t           m_pos;  ///< current position in bits
 129         uint_type const* m_first; ///< first position
 130 #   ifdef _DEBUG
 131         uint_type const* m_last;  ///< last position
 132 #   endif
 133         //@endcond
 134     };
 135
 136 }} // namespace cds::algo
 137
 138 #endif // #ifndef CDSLIB_ALGO_SPLIT_BITSTRING_H