diff options
Diffstat (limited to 'include/utils/BitSet.h')
| -rw-r--r-- | include/utils/BitSet.h | 214 |
1 files changed, 192 insertions, 22 deletions
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h index 19c03d1..8c61293 100644 --- a/include/utils/BitSet.h +++ b/include/utils/BitSet.h @@ -30,73 +30,103 @@ namespace android { struct BitSet32 { uint32_t value; - inline BitSet32() : value(0) { } + inline BitSet32() : value(0UL) { } explicit inline BitSet32(uint32_t value) : value(value) { } // Gets the value associated with a particular bit index. - static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; } + static inline uint32_t valueForBit(uint32_t n) { return 0x80000000UL >> n; } // Clears the bit set. - inline void clear() { value = 0; } + inline void clear() { clear(value); } + + static inline void clear(uint32_t& value) { value = 0UL; } // Returns the number of marked bits in the set. - inline uint32_t count() const { return __builtin_popcount(value); } + inline uint32_t count() const { return count(value); } + + static inline uint32_t count(uint32_t value) { return __builtin_popcountl(value); } // Returns true if the bit set does not contain any marked bits. - inline bool isEmpty() const { return ! value; } + inline bool isEmpty() const { return isEmpty(value); } + + static inline bool isEmpty(uint32_t value) { return ! value; } // Returns true if the bit set does not contain any unmarked bits. - inline bool isFull() const { return value == 0xffffffff; } + inline bool isFull() const { return isFull(value); } + + static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; } // Returns true if the specified bit is marked. - inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } + inline bool hasBit(uint32_t n) const { return hasBit(value, n); } + + static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); } // Marks the specified bit. - inline void markBit(uint32_t n) { value |= valueForBit(n); } + inline void markBit(uint32_t n) { markBit(value, n); } + + static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); } // Clears the specified bit. - inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); } + inline void clearBit(uint32_t n) { clearBit(value, n); } + + static inline void clearBit(uint32_t& value, uint32_t n) { value &= ~ valueForBit(n); } // Finds the first marked bit in the set. // Result is undefined if all bits are unmarked. - inline uint32_t firstMarkedBit() const { return __builtin_clz(value); } + inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } + + static uint32_t firstMarkedBit(uint32_t value) { return clz_checked(value); } // Finds the first unmarked bit in the set. // Result is undefined if all bits are marked. - inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); } + inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } + + static inline uint32_t firstUnmarkedBit(uint32_t value) { return clz_checked(~ value); } // Finds the last marked bit in the set. // Result is undefined if all bits are unmarked. - inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); } + inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } + + static inline uint32_t lastMarkedBit(uint32_t value) { return 31 - ctz_checked(value); } // Finds the first marked bit in the set and clears it. Returns the bit index. // Result is undefined if all bits are unmarked. - inline uint32_t clearFirstMarkedBit() { - uint32_t n = firstMarkedBit(); - clearBit(n); + inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } + + static inline uint32_t clearFirstMarkedBit(uint32_t& value) { + uint32_t n = firstMarkedBit(value); + clearBit(value, n); return n; } // Finds the first unmarked bit in the set and marks it. Returns the bit index. // Result is undefined if all bits are marked. - inline uint32_t markFirstUnmarkedBit() { - uint32_t n = firstUnmarkedBit(); - markBit(n); + inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } + + static inline uint32_t markFirstUnmarkedBit(uint32_t& value) { + uint32_t n = firstUnmarkedBit(value); + markBit(value, n); return n; } // Finds the last marked bit in the set and clears it. Returns the bit index. // Result is undefined if all bits are unmarked. - inline uint32_t clearLastMarkedBit() { - uint32_t n = lastMarkedBit(); - clearBit(n); + inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } + + static inline uint32_t clearLastMarkedBit(uint32_t& value) { + uint32_t n = lastMarkedBit(value); + clearBit(value, n); return n; } // Gets the index of the specified bit in the set, which is the number of // marked bits that appear before the specified bit. inline uint32_t getIndexOfBit(uint32_t n) const { - return __builtin_popcount(value & ~(0xffffffffUL >> n)); + return getIndexOfBit(value, n); + } + + static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) { + return __builtin_popcountl(value & ~(0xffffffffUL >> n)); } inline bool operator== (const BitSet32& other) const { return value == other.value; } @@ -115,10 +145,150 @@ struct BitSet32 { value |= other.value; return *this; } + +private: + // We use these helpers as the signature of __builtin_c{l,t}z has "unsigned int" for the + // input, which is only guaranteed to be 16b, not 32. The compiler should optimize this away. + static inline uint32_t clz_checked(uint32_t value) { + if (sizeof(unsigned int) == sizeof(uint32_t)) { + return __builtin_clz(value); + } else { + return __builtin_clzl(value); + } + } + + static inline uint32_t ctz_checked(uint32_t value) { + if (sizeof(unsigned int) == sizeof(uint32_t)) { + return __builtin_ctz(value); + } else { + return __builtin_ctzl(value); + } + } }; ANDROID_BASIC_TYPES_TRAITS(BitSet32) +// A simple set of 64 bits that can be individually marked or cleared. +struct BitSet64 { + uint64_t value; + + inline BitSet64() : value(0ULL) { } + explicit inline BitSet64(uint64_t value) : value(value) { } + + // Gets the value associated with a particular bit index. + static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; } + + // Clears the bit set. + inline void clear() { clear(value); } + + static inline void clear(uint64_t& value) { value = 0ULL; } + + // Returns the number of marked bits in the set. + inline uint32_t count() const { return count(value); } + + static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); } + + // Returns true if the bit set does not contain any marked bits. + inline bool isEmpty() const { return isEmpty(value); } + + static inline bool isEmpty(uint64_t value) { return ! value; } + + // Returns true if the bit set does not contain any unmarked bits. + inline bool isFull() const { return isFull(value); } + + static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; } + + // Returns true if the specified bit is marked. + inline bool hasBit(uint32_t n) const { return hasBit(value, n); } + + static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); } + + // Marks the specified bit. + inline void markBit(uint32_t n) { markBit(value, n); } + + static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); } + + // Clears the specified bit. + inline void clearBit(uint32_t n) { clearBit(value, n); } + + static inline void clearBit(uint64_t& value, uint32_t n) { value &= ~ valueForBit(n); } + + // Finds the first marked bit in the set. + // Result is undefined if all bits are unmarked. + inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } + + static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); } + + // Finds the first unmarked bit in the set. + // Result is undefined if all bits are marked. + inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } + + static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); } + + // Finds the last marked bit in the set. + // Result is undefined if all bits are unmarked. + inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } + + static inline uint32_t lastMarkedBit(uint64_t value) { return 63 - __builtin_ctzll(value); } + + // Finds the first marked bit in the set and clears it. Returns the bit index. + // Result is undefined if all bits are unmarked. + inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } + + static inline uint32_t clearFirstMarkedBit(uint64_t& value) { + uint64_t n = firstMarkedBit(value); + clearBit(value, n); + return n; + } + + // Finds the first unmarked bit in the set and marks it. Returns the bit index. + // Result is undefined if all bits are marked. + inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } + + static inline uint32_t markFirstUnmarkedBit(uint64_t& value) { + uint64_t n = firstUnmarkedBit(value); + markBit(value, n); + return n; + } + + // Finds the last marked bit in the set and clears it. Returns the bit index. + // Result is undefined if all bits are unmarked. + inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } + + static inline uint32_t clearLastMarkedBit(uint64_t& value) { + uint64_t n = lastMarkedBit(value); + clearBit(value, n); + return n; + } + + // Gets the index of the specified bit in the set, which is the number of + // marked bits that appear before the specified bit. + inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); } + + static inline uint32_t getIndexOfBit(uint64_t value, uint32_t n) { + return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n)); + } + + inline bool operator== (const BitSet64& other) const { return value == other.value; } + inline bool operator!= (const BitSet64& other) const { return value != other.value; } + inline BitSet64 operator& (const BitSet64& other) const { + return BitSet64(value & other.value); + } + inline BitSet64& operator&= (const BitSet64& other) { + value &= other.value; + return *this; + } + inline BitSet64 operator| (const BitSet64& other) const { + return BitSet64(value | other.value); + } + inline BitSet64& operator|= (const BitSet64& other) { + value |= other.value; + return *this; + } +}; + +ANDROID_BASIC_TYPES_TRAITS(BitSet64) + } // namespace android #endif // UTILS_BITSET_H |