1 /* 2 * Copyright (C) 2010 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef UTILS_BITSET_H 18 #define UTILS_BITSET_H 19 20 #include <stdint.h> 21 22 /* 23 * Contains some bit manipulation helpers. 24 */ 25 26 namespace android { 27 28 // A simple set of 32 bits that can be individually marked or cleared. 29 struct BitSet32 { 30 uint32_t value; 31 32 inline BitSet32() : value(0) { } 33 explicit inline BitSet32(uint32_t value) : value(value) { } 34 35 // Gets the value associated with a particular bit index. 36 static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; } 37 38 // Clears the bit set. 39 inline void clear() { value = 0; } 40 41 // Returns the number of marked bits in the set. 42 inline uint32_t count() const { return __builtin_popcount(value); } 43 44 // Returns true if the bit set does not contain any marked bits. 45 inline bool isEmpty() const { return ! value; } 46 47 // Returns true if the bit set does not contain any unmarked bits. 48 inline bool isFull() const { return value == 0xffffffff; } 49 50 // Returns true if the specified bit is marked. 51 inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } 52 53 // Marks the specified bit. 54 inline void markBit(uint32_t n) { value |= valueForBit(n); } 55 56 // Clears the specified bit. 57 inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); } 58 59 // Finds the first marked bit in the set. 60 // Result is undefined if all bits are unmarked. 61 inline uint32_t firstMarkedBit() const { return __builtin_clz(value); } 62 63 // Finds the first unmarked bit in the set. 64 // Result is undefined if all bits are marked. 65 inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); } 66 67 // Finds the last marked bit in the set. 68 // Result is undefined if all bits are unmarked. 69 inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); } 70 71 // Finds the first marked bit in the set and clears it. Returns the bit index. 72 // Result is undefined if all bits are unmarked. 73 inline uint32_t clearFirstMarkedBit() { 74 uint32_t n = firstMarkedBit(); 75 clearBit(n); 76 return n; 77 } 78 79 // Finds the first unmarked bit in the set and marks it. Returns the bit index. 80 // Result is undefined if all bits are marked. 81 inline uint32_t markFirstUnmarkedBit() { 82 uint32_t n = firstUnmarkedBit(); 83 markBit(n); 84 return n; 85 } 86 87 // Finds the last marked bit in the set and clears it. Returns the bit index. 88 // Result is undefined if all bits are unmarked. 89 inline uint32_t clearLastMarkedBit() { 90 uint32_t n = lastMarkedBit(); 91 clearBit(n); 92 return n; 93 } 94 95 // Gets the index of the specified bit in the set, which is the number of 96 // marked bits that appear before the specified bit. 97 inline uint32_t getIndexOfBit(uint32_t n) const { 98 return __builtin_popcount(value & ~(0xffffffffUL >> n)); 99 } 100 101 inline bool operator== (const BitSet32& other) const { return value == other.value; } 102 inline bool operator!= (const BitSet32& other) const { return value != other.value; } 103 }; 104 105 } // namespace android 106 107 #endif // UTILS_BITSET_H 108
