1 // This file is part of the ustl library, an STL implementation. 2 // 3 // Copyright (C) 2005 by Mike Sharov <msharov@users.sourceforge.net> 4 // This file is free software, distributed under the MIT License. 5 // 6 // ubitset.h 7 // 8 #ifndef UBITSET_H_7B6450EC1400CBA45DCE0127739F82EE 9 #define UBITSET_H_7B6450EC1400CBA45DCE0127739F82EE 10 11 #include "uassert.h" 12 #include "ustring.h" 13 #include "ufunction.h" 14 15 namespace ustl { 16 17 typedef uint32_t bitset_value_type; 18 19 void convert_to_bitstring (const bitset_value_type* v, size_t n, string& buf); 20 void convert_from_bitstring (const string& buf, bitset_value_type* v, size_t n); 21 22 /// \class bitset ubitset.h ustl.h 23 /// \ingroup Sequences 24 /// 25 /// \brief bitset is a fixed-size block of memory with addressable bits. 26 /// 27 /// Normally used for state flags; allows setting and unsetting of individual 28 /// bits as well as bitwise operations on the entire set. The interface is 29 /// most like that of unsigned integers, and is intended to be used as such. 30 /// If you were using begin() and end() functions in STL's bitset, you would 31 /// not be able to do the same thing here, because those functions return 32 /// host type iterators, not bits. 33 /// 34 template <size_t Size> 35 class bitset { 36 public: 37 typedef bitset_value_type value_type; 38 typedef value_type* pointer; 39 typedef const value_type* const_pointer; 40 typedef pointer iterator; 41 typedef const_pointer const_iterator; 42 typedef size_t difference_type; 43 typedef size_t size_type; 44 private: 45 static const size_t s_WordBits = BitsInType (value_type); 46 static const size_t s_nWords = Size / s_WordBits + ((Size % s_WordBits) != 0); 47 static const size_t s_nBits = s_nWords * s_WordBits; 48 private: BitRef(uoff_t n)49 inline value_type& BitRef (uoff_t n) { assert (n < Size); return (m_Bits [n / s_WordBits]); } BitRef(uoff_t n)50 inline const value_type BitRef (uoff_t n) const { assert (n < Size); return (m_Bits [n / s_WordBits]); } Mask(uoff_t n)51 inline const value_type Mask (uoff_t n) const { assert (n < Size); return (1 << (n % s_WordBits)); } 52 public: 53 inline bitset (value_type v = 0) { fill_n (m_Bits, s_nWords, 0); m_Bits[0] = v; } bitset(const string & buf)54 inline bitset (const string& buf) { convert_from_bitstring (buf, m_Bits, s_nWords); } flip(uoff_t n)55 inline void flip (uoff_t n) { BitRef(n) ^= Mask(n); } reset(void)56 inline void reset (void) { fill_n (m_Bits, s_nWords, 0); } clear(void)57 inline void clear (void) { fill_n (m_Bits, s_nWords, 0); } set(void)58 inline void set (void) { fill_n (m_Bits, s_nWords, -1); } 59 inline bitset operator~ (void) const { bitset rv (*this); rv.flip(); return (rv); } size(void)60 inline size_type size (void) const { return (Size); } capacity(void)61 inline size_type capacity (void) const { return (s_nBits); } test(uoff_t n)62 inline const bool test (uoff_t n) const { return (BitRef(n) & Mask(n)); } 63 inline const bool operator[] (uoff_t n) const { return (test(n)); } begin(void)64 inline const_iterator begin (void) const { return (m_Bits); } begin(void)65 inline iterator begin (void) { return (m_Bits); } end(void)66 inline const_iterator end (void) const { return (m_Bits + s_nWords); } end(void)67 inline iterator end (void) { return (m_Bits + s_nWords); } 68 /// Returns the value_type with the equivalent bits. If size() > 1, you'll get only the first BitsInType(value_type) bits. to_value(void)69 inline const value_type to_value (void) const { return (m_Bits[0]); } 70 /// Flips all the bits in the set. flip(void)71 inline void flip (void) { transform (begin(), end(), begin(), bitwise_not<value_type>()); } 72 /// Sets or clears bit \p n. 73 inline void set (uoff_t n, bool val = true) 74 { 75 value_type& br (BitRef (n)); 76 const value_type mask (Mask (n)); 77 const value_type bOn (br | mask), bOff (br & ~mask); 78 br = val ? bOn : bOff; 79 } 80 // Sets the value of the bitrange \p first through \p last to the equivalent number of bits from \p v. set(uoff_t first,uoff_t DebugArg (last),value_type v)81 inline void set (uoff_t first, uoff_t DebugArg(last), value_type v) 82 { 83 #if !PLATFORM_ANDROID 84 assert (size_t (distance (first, last)) <= s_WordBits && "Bit ranges must be 32 bits or smaller"); 85 assert (first / s_WordBits == last / s_WordBits && "Bit ranges can not cross dword (4 byte) boundary"); 86 assert ((v & BitMask(value_type,distance(first,last))) == v && "The value is too large to fit in the given bit range"); 87 #endif 88 BitRef(first) |= v << (first % s_WordBits); 89 } 90 /// Clears the bit \p n. reset(uoff_t n)91 inline void reset (uoff_t n) { set (n, false); } 92 /// Returns a string with bits MSB "001101001..." LSB. to_string(void)93 inline string to_string (void) const 94 { 95 string rv (Size, '0'); 96 convert_to_bitstring (m_Bits, s_nWords, rv); 97 return (rv); 98 } at(uoff_t n)99 inline value_type at (uoff_t n) const { return (test(n)); } 100 /// Returns the value in bits \p first through \p last. at(uoff_t first,uoff_t last)101 inline value_type at (uoff_t first, uoff_t last) const 102 { 103 assert (size_t (distance (first, last)) <= s_WordBits && "Bit ranges must be 32 bits or smaller"); 104 assert (first / s_WordBits == last / s_WordBits && "Bit ranges can not cross dword (4 byte) boundary"); 105 return ((BitRef(first) >> (first % s_WordBits)) & BitMask(value_type,distance(first, last))); 106 } any(void)107 inline bool any (void) const { value_type sum = 0; foreach (const_iterator, i, *this) sum |= *i; return (sum); } none(void)108 inline bool none (void) const { return (!any()); } count(void)109 inline size_t count (void) const { size_t sum = 0; foreach (const_iterator, i, *this) sum += popcount(*i); return (sum); } 110 inline bool operator== (const bitset<Size>& v) const 111 { return (s_nWords == 1 ? (m_Bits[0] == v.m_Bits[0]) : equal (begin(), end(), v.begin())); } 112 inline const bitset operator& (const bitset<Size>& v) 113 { bitset<Size> result; transform (begin(), end(), v.begin(), result.begin(), bitwise_and<value_type>()); return (result); } 114 inline const bitset operator| (const bitset<Size>& v) 115 { bitset<Size> result; transform (begin(), end(), v.begin(), result.begin(), bitwise_or<value_type>()); return (result); } 116 inline const bitset operator^ (const bitset<Size>& v) 117 { bitset<Size> result; transform (begin(), end(), v.begin(), result.begin(), bitwise_xor<value_type>()); return (result); } 118 inline const bitset& operator&= (const bitset<Size>& v) 119 { transform (begin(), end(), v.begin(), begin(), bitwise_and<value_type>()); return (*this); } 120 inline const bitset& operator|= (const bitset<Size>& v) 121 { transform (begin(), end(), v.begin(), begin(), bitwise_or<value_type>()); return (*this); } 122 inline const bitset& operator^= (const bitset<Size>& v) 123 { transform (begin(), end(), v.begin(), begin(), bitwise_xor<value_type>()); return (*this); } 124 private: 125 value_type m_Bits [s_nWords]; 126 }; 127 128 } // namespace ustl 129 130 #endif 131 132