From dc8479928c5aee4c6ad6fe4f59006fb604cee701 Mon Sep 17 00:00:00 2001 From: Emmanuel Gil Peyrot Date: Sun, 18 Sep 2016 09:38:01 +0900 Subject: Sources: Run clang-format on everything. --- src/common/bit_set.h | 203 ++++++++++++++++++++++++++++++++------------------- 1 file changed, 129 insertions(+), 74 deletions(-) (limited to 'src/common/bit_set.h') diff --git a/src/common/bit_set.h b/src/common/bit_set.h index 7f5de8df2..b83cbbb36 100644 --- a/src/common/bit_set.h +++ b/src/common/bit_set.h @@ -18,49 +18,60 @@ namespace Common { #ifdef _WIN32 template -static inline int CountSetBits(T v) -{ +static inline int CountSetBits(T v) { // from https://graphics.stanford.edu/~seander/bithacks.html // GCC has this built in, but MSVC's intrinsic will only emit the actual // POPCNT instruction, which we're not depending on - v = v - ((v >> 1) & (T)~(T)0/3); - v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); - v = (v + (v >> 4)) & (T)~(T)0/255*15; - return (T)(v * ((T)~(T)0/255)) >> (sizeof(T) - 1) * 8; + v = v - ((v >> 1) & (T) ~(T)0 / 3); + v = (v & (T) ~(T)0 / 15 * 3) + ((v >> 2) & (T) ~(T)0 / 15 * 3); + v = (v + (v >> 4)) & (T) ~(T)0 / 255 * 15; + return (T)(v * ((T) ~(T)0 / 255)) >> (sizeof(T) - 1) * 8; } -static inline int LeastSignificantSetBit(u8 val) -{ +static inline int LeastSignificantSetBit(u8 val) { unsigned long index; _BitScanForward(&index, val); return (int)index; } -static inline int LeastSignificantSetBit(u16 val) -{ +static inline int LeastSignificantSetBit(u16 val) { unsigned long index; _BitScanForward(&index, val); return (int)index; } -static inline int LeastSignificantSetBit(u32 val) -{ +static inline int LeastSignificantSetBit(u32 val) { unsigned long index; _BitScanForward(&index, val); return (int)index; } -static inline int LeastSignificantSetBit(u64 val) -{ +static inline int LeastSignificantSetBit(u64 val) { unsigned long index; _BitScanForward64(&index, val); return (int)index; } #else -static inline int CountSetBits(u8 val) { return __builtin_popcount(val); } -static inline int CountSetBits(u16 val) { return __builtin_popcount(val); } -static inline int CountSetBits(u32 val) { return __builtin_popcount(val); } -static inline int CountSetBits(u64 val) { return __builtin_popcountll(val); } -static inline int LeastSignificantSetBit(u8 val) { return __builtin_ctz(val); } -static inline int LeastSignificantSetBit(u16 val) { return __builtin_ctz(val); } -static inline int LeastSignificantSetBit(u32 val) { return __builtin_ctz(val); } -static inline int LeastSignificantSetBit(u64 val) { return __builtin_ctzll(val); } +static inline int CountSetBits(u8 val) { + return __builtin_popcount(val); +} +static inline int CountSetBits(u16 val) { + return __builtin_popcount(val); +} +static inline int CountSetBits(u32 val) { + return __builtin_popcount(val); +} +static inline int CountSetBits(u64 val) { + return __builtin_popcountll(val); +} +static inline int LeastSignificantSetBit(u8 val) { + return __builtin_ctz(val); +} +static inline int LeastSignificantSetBit(u16 val) { + return __builtin_ctz(val); +} +static inline int LeastSignificantSetBit(u32 val) { + return __builtin_ctz(val); +} +static inline int LeastSignificantSetBit(u64 val) { + return __builtin_ctzll(val); +} #endif // Similar to std::bitset, this is a class which encapsulates a bitset, i.e. @@ -84,100 +95,144 @@ static inline int LeastSignificantSetBit(u64 val) { return __builtin_ctzll(val); // TODO: use constexpr when MSVC gets out of the Dark Ages template -class BitSet -{ +class BitSet { static_assert(!std::is_signed::value, "BitSet should not be used with signed types"); + public: // A reference to a particular bit, returned from operator[]. - class Ref - { + class Ref { public: - Ref(Ref&& other) : m_bs(other.m_bs), m_mask(other.m_mask) {} - Ref(BitSet* bs, IntTy mask) : m_bs(bs), m_mask(mask) {} - operator bool() const { return (m_bs->m_val & m_mask) != 0; } - bool operator=(bool set) - { + Ref(Ref&& other) : m_bs(other.m_bs), m_mask(other.m_mask) { + } + Ref(BitSet* bs, IntTy mask) : m_bs(bs), m_mask(mask) { + } + operator bool() const { + return (m_bs->m_val & m_mask) != 0; + } + bool operator=(bool set) { m_bs->m_val = (m_bs->m_val & ~m_mask) | (set ? m_mask : 0); return set; } + private: BitSet* m_bs; IntTy m_mask; }; // A STL-like iterator is required to be able to use range-based for loops. - class Iterator - { + class Iterator { public: - Iterator(const Iterator& other) : m_val(other.m_val), m_bit(other.m_bit) {} - Iterator(IntTy val, int bit) : m_val(val), m_bit(bit) {} - Iterator& operator=(Iterator other) { new (this) Iterator(other); return *this; } - int operator*() { return m_bit; } - Iterator& operator++() - { - if (m_val == 0) - { + Iterator(const Iterator& other) : m_val(other.m_val), m_bit(other.m_bit) { + } + Iterator(IntTy val, int bit) : m_val(val), m_bit(bit) { + } + Iterator& operator=(Iterator other) { + new (this) Iterator(other); + return *this; + } + int operator*() { + return m_bit; + } + Iterator& operator++() { + if (m_val == 0) { m_bit = -1; - } - else - { + } else { int bit = LeastSignificantSetBit(m_val); m_val &= ~(1 << bit); m_bit = bit; } return *this; } - Iterator operator++(int _) - { + Iterator operator++(int _) { Iterator other(*this); ++*this; return other; } - bool operator==(Iterator other) const { return m_bit == other.m_bit; } - bool operator!=(Iterator other) const { return m_bit != other.m_bit; } + bool operator==(Iterator other) const { + return m_bit == other.m_bit; + } + bool operator!=(Iterator other) const { + return m_bit != other.m_bit; + } + private: IntTy m_val; int m_bit; }; - BitSet() : m_val(0) {} - explicit BitSet(IntTy val) : m_val(val) {} - BitSet(std::initializer_list init) - { + BitSet() : m_val(0) { + } + explicit BitSet(IntTy val) : m_val(val) { + } + BitSet(std::initializer_list init) { m_val = 0; for (int bit : init) m_val |= (IntTy)1 << bit; } - static BitSet AllTrue(size_t count) - { - return BitSet(count == sizeof(IntTy)*8 ? ~(IntTy)0 : (((IntTy)1 << count) - 1)); - } - - Ref operator[](size_t bit) { return Ref(this, (IntTy)1 << bit); } - const Ref operator[](size_t bit) const { return (*const_cast(this))[bit]; } - bool operator==(BitSet other) const { return m_val == other.m_val; } - bool operator!=(BitSet other) const { return m_val != other.m_val; } - bool operator<(BitSet other) const { return m_val < other.m_val; } - bool operator>(BitSet other) const { return m_val > other.m_val; } - BitSet operator|(BitSet other) const { return BitSet(m_val | other.m_val); } - BitSet operator&(BitSet other) const { return BitSet(m_val & other.m_val); } - BitSet operator^(BitSet other) const { return BitSet(m_val ^ other.m_val); } - BitSet operator~() const { return BitSet(~m_val); } - BitSet& operator|=(BitSet other) { return *this = *this | other; } - BitSet& operator&=(BitSet other) { return *this = *this & other; } - BitSet& operator^=(BitSet other) { return *this = *this ^ other; } + static BitSet AllTrue(size_t count) { + return BitSet(count == sizeof(IntTy) * 8 ? ~(IntTy)0 : (((IntTy)1 << count) - 1)); + } + + Ref operator[](size_t bit) { + return Ref(this, (IntTy)1 << bit); + } + const Ref operator[](size_t bit) const { + return (*const_cast(this))[bit]; + } + bool operator==(BitSet other) const { + return m_val == other.m_val; + } + bool operator!=(BitSet other) const { + return m_val != other.m_val; + } + bool operator<(BitSet other) const { + return m_val < other.m_val; + } + bool operator>(BitSet other) const { + return m_val > other.m_val; + } + BitSet operator|(BitSet other) const { + return BitSet(m_val | other.m_val); + } + BitSet operator&(BitSet other) const { + return BitSet(m_val & other.m_val); + } + BitSet operator^(BitSet other) const { + return BitSet(m_val ^ other.m_val); + } + BitSet operator~() const { + return BitSet(~m_val); + } + BitSet& operator|=(BitSet other) { + return *this = *this | other; + } + BitSet& operator&=(BitSet other) { + return *this = *this & other; + } + BitSet& operator^=(BitSet other) { + return *this = *this ^ other; + } operator u32() = delete; - operator bool() { return m_val != 0; } + operator bool() { + return m_val != 0; + } // Warning: Even though on modern CPUs this is a single fast instruction, // Dolphin's official builds do not currently assume POPCNT support on x86, // so slower explicit bit twiddling is generated. Still should generally // be faster than a loop. - unsigned int Count() const { return CountSetBits(m_val); } + unsigned int Count() const { + return CountSetBits(m_val); + } - Iterator begin() const { Iterator it(m_val, 0); return ++it; } - Iterator end() const { return Iterator(m_val, -1); } + Iterator begin() const { + Iterator it(m_val, 0); + return ++it; + } + Iterator end() const { + return Iterator(m_val, -1); + } IntTy m_val; }; -- cgit v1.2.3