diff options
author | Michael Wright <michaelwr@google.com> | 2014-03-19 11:23:01 -0700 |
---|---|---|
committer | Michael Wright <michaelwr@google.com> | 2014-03-19 11:23:01 -0700 |
commit | 2ec064597ce1cfa5f8bf5f480c90644d57d8d2c5 (patch) | |
tree | 7494cea359dc6a3617659b35bee9559498e5772e | |
parent | 74e2538b48658d0912fc8566c381fbb8be095c8a (diff) | |
download | system_core-2ec064597ce1cfa5f8bf5f480c90644d57d8d2c5.zip system_core-2ec064597ce1cfa5f8bf5f480c90644d57d8d2c5.tar.gz system_core-2ec064597ce1cfa5f8bf5f480c90644d57d8d2c5.tar.bz2 |
Add static methods to BitSet.
Also, moar testing.
Change-Id: I512b337a1a85a0794445fc6249af7ca39ba7c381
-rw-r--r-- | include/utils/BitSet.h | 140 | ||||
-rw-r--r-- | libutils/tests/BitSet_test.cpp | 121 |
2 files changed, 220 insertions, 41 deletions
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h index 75abe6c..f1d68a0 100644 --- a/include/utils/BitSet.h +++ b/include/utils/BitSet.h @@ -30,72 +30,102 @@ 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_popcountl(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_clzl(value); } + inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } + + static uint32_t firstMarkedBit(uint32_t value) { 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_clzl(~ value); } + inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } + + static inline uint32_t firstUnmarkedBit(uint32_t value) { 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_ctzl(value); } + inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } + + static inline uint32_t lastMarkedBit(uint32_t value) { 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. - 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 getIndexOfBit(value, n); + } + + static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) { return __builtin_popcountl(value & ~(0xffffffffUL >> n)); } @@ -130,65 +160,93 @@ struct BitSet64 { static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; } // Clears the bit set. - inline void clear() { value = 0ULL; } + 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 __builtin_popcountll(value); } + 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 ! value; } + 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 value == 0xffffffffffffffffULL; } + 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 value & valueForBit(n); } + 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) { value |= valueForBit(n); } + 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) { value &= ~ valueForBit(n); } + 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 __builtin_clzll(value); } + 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 __builtin_clzll(~ value); } + 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 63 - __builtin_ctzll(value); } + 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() { - uint64_t n = firstMarkedBit(); - clearBit(n); + 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() { - uint64_t n = firstUnmarkedBit(); - markBit(n); + 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() { - uint64_t n = lastMarkedBit(); - clearBit(n); + 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 { + 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)); } diff --git a/libutils/tests/BitSet_test.cpp b/libutils/tests/BitSet_test.cpp index 1f4917a..38b668a 100644 --- a/libutils/tests/BitSet_test.cpp +++ b/libutils/tests/BitSet_test.cpp @@ -85,6 +85,66 @@ TEST_F(BitSet32Test, BitWiseAnd_NonDisjoint) { EXPECT_TRUE(b2.hasBit(3) && b2.hasBit(6) && b2.hasBit(9)); } +TEST_F(BitSet32Test, MarkFirstUnmarkedBit) { + b1.markBit(1); + + b1.markFirstUnmarkedBit(); + EXPECT_EQ(b1.count(), 2u); + EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1)); + + b1.markFirstUnmarkedBit(); + EXPECT_EQ(b1.count(), 3u); + EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1) && b1.hasBit(2)); +} + +TEST_F(BitSet32Test, ClearFirstMarkedBit) { + b1.markBit(0); + b1.markBit(10); + + b1.clearFirstMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(10)); + + b1.markBit(30); + b1.clearFirstMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(30)); +} + +TEST_F(BitSet32Test, ClearLastMarkedBit) { + b1.markBit(10); + b1.markBit(31); + + b1.clearLastMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(10)); + + b1.markBit(5); + b1.clearLastMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(5)); +} + +TEST_F(BitSet32Test, FillAndClear) { + EXPECT_TRUE(b1.isEmpty()); + for (size_t i = 0; i < 32; i++) { + b1.markFirstUnmarkedBit(); + } + EXPECT_TRUE(b1.isFull()); + b1.clear(); + EXPECT_TRUE(b1.isEmpty()); +} + +TEST_F(BitSet32Test, GetIndexOfBit) { + b1.markBit(1); + b1.markBit(4); + EXPECT_EQ(b1.getIndexOfBit(1), 0); + EXPECT_EQ(b1.getIndexOfBit(4), 1); + b1.markFirstUnmarkedBit(); + EXPECT_EQ(b1.getIndexOfBit(1), 1); + EXPECT_EQ(b1.getIndexOfBit(4), 2); +} + class BitSet64Test : public testing::Test { protected: BitSet64 b1; @@ -146,4 +206,65 @@ TEST_F(BitSet64Test, BitWiseAnd_NonDisjoint) { EXPECT_EQ(b2.count(), 3u); EXPECT_TRUE(b2.hasBit(30) && b2.hasBit(60) && b2.hasBit(63)); } + +TEST_F(BitSet64Test, MarkFirstUnmarkedBit) { + b1.markBit(1); + + b1.markFirstUnmarkedBit(); + EXPECT_EQ(b1.count(), 2u); + EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1)); + + b1.markFirstUnmarkedBit(); + EXPECT_EQ(b1.count(), 3u); + EXPECT_TRUE(b1.hasBit(0) && b1.hasBit(1) && b1.hasBit(2)); +} + +TEST_F(BitSet64Test, ClearFirstMarkedBit) { + b1.markBit(0); + b1.markBit(10); + + b1.clearFirstMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(10)); + + b1.markBit(50); + b1.clearFirstMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(50)); +} + +TEST_F(BitSet64Test, ClearLastMarkedBit) { + b1.markBit(10); + b1.markBit(63); + + b1.clearLastMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(10)); + + b1.markBit(5); + b1.clearLastMarkedBit(); + EXPECT_EQ(b1.count(), 1u); + EXPECT_TRUE(b1.hasBit(5)); +} + +TEST_F(BitSet64Test, FillAndClear) { + EXPECT_TRUE(b1.isEmpty()); + for (size_t i = 0; i < 64; i++) { + b1.markFirstUnmarkedBit(); + } + EXPECT_TRUE(b1.isFull()); + b1.clear(); + EXPECT_TRUE(b1.isEmpty()); +} + +TEST_F(BitSet64Test, GetIndexOfBit) { + b1.markBit(10); + b1.markBit(40); + EXPECT_EQ(b1.getIndexOfBit(10), 0); + EXPECT_EQ(b1.getIndexOfBit(40), 1); + b1.markFirstUnmarkedBit(); + EXPECT_EQ(b1.getIndexOfBit(10), 1); + EXPECT_EQ(b1.getIndexOfBit(40), 2); +} + } // namespace android |