diff options
| author | Michael Wright <michaelwr@google.com> | 2014-03-18 17:25:20 -0700 |
|---|---|---|
| committer | Michael Wright <michaelwr@google.com> | 2014-03-18 17:28:22 -0700 |
| commit | bab6ea0bb70dd6d093a0765befc7d6893e2312bf (patch) | |
| tree | 91b5081a3a7ebe6f26a040cd2cd0cc13366b5bb3 /include/utils | |
| parent | 914eec761f53f2b0c7855cd8ffc8a79016b52622 (diff) | |
| download | system_core-bab6ea0bb70dd6d093a0765befc7d6893e2312bf.zip system_core-bab6ea0bb70dd6d093a0765befc7d6893e2312bf.tar.gz system_core-bab6ea0bb70dd6d093a0765befc7d6893e2312bf.tar.bz2 | |
Add BitSet64
Change-Id: Ia0039aae00316f42a8306a9fb8ad37269180b58c
Diffstat (limited to 'include/utils')
| -rw-r--r-- | include/utils/BitSet.h | 103 |
1 files changed, 98 insertions, 5 deletions
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h index 19c03d1..1ca75fe 100644 --- a/include/utils/BitSet.h +++ b/include/utils/BitSet.h @@ -40,7 +40,7 @@ struct BitSet32 { inline void clear() { value = 0; } // Returns the number of marked bits in the set. - inline uint32_t count() const { return __builtin_popcount(value); } + inline uint32_t count() const { return __builtin_popcountl(value); } // Returns true if the bit set does not contain any marked bits. inline bool isEmpty() const { return ! value; } @@ -59,15 +59,15 @@ struct BitSet32 { // 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 __builtin_clzl(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 __builtin_clzl(~ 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 31 - __builtin_ctzl(value); } // Finds the first marked bit in the set and clears it. Returns the bit index. // Result is undefined if all bits are unmarked. @@ -96,7 +96,7 @@ struct BitSet32 { // 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 __builtin_popcountl(value & ~(0xffffffffUL >> n)); } inline bool operator== (const BitSet32& other) const { return value == other.value; } @@ -119,6 +119,99 @@ struct BitSet32 { 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() { value = 0ULL; } + + // Returns the number of marked bits in the set. + inline uint32_t count() const { return __builtin_popcountll(value); } + + // Returns true if the bit set does not contain any marked bits. + inline bool isEmpty() const { return ! value; } + + // Returns true if the bit set does not contain any unmarked bits. + inline bool isFull() const { return value == 0xffffffffffffffffULL; } + + // Returns true if the specified bit is marked. + inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } + + // Marks the specified bit. + inline void markBit(uint32_t n) { value |= valueForBit(n); } + + // Clears the specified bit. + inline void clearBit(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_clzll(value); } + + // Finds the first unmarked bit in the set. + // Result is undefined if all bits are marked. + inline uint32_t firstUnmarkedBit() const { 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 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() { + uint64_t n = firstMarkedBit(); + clearBit(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() { + uint64_t n = firstUnmarkedBit(); + markBit(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() { + uint64_t n = lastMarkedBit(); + clearBit(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_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(BitSet32) + } // namespace android #endif // UTILS_BITSET_H |