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 #include <utils/TypeHelpers.h> 22 23 /* 24 * Contains some bit manipulation helpers. 25 */ 26 27 namespace android { 28 29 // A simple set of 32 bits that can be individually marked or cleared. 30 struct BitSet32 { 31 uint32_t value; 32 BitSet32BitSet3233 inline BitSet32() : value(0UL) { } BitSet32BitSet3234 explicit inline BitSet32(uint32_t value) : value(value) { } 35 36 // Gets the value associated with a particular bit index. valueForBitBitSet3237 static inline uint32_t valueForBit(uint32_t n) { return 0x80000000UL >> n; } 38 39 // Clears the bit set. clearBitSet3240 inline void clear() { clear(value); } 41 clearBitSet3242 static inline void clear(uint32_t& value) { value = 0UL; } 43 44 // Returns the number of marked bits in the set. countBitSet3245 inline uint32_t count() const { return count(value); } 46 countBitSet3247 static inline uint32_t count(uint32_t value) { return __builtin_popcountl(value); } 48 49 // Returns true if the bit set does not contain any marked bits. isEmptyBitSet3250 inline bool isEmpty() const { return isEmpty(value); } 51 isEmptyBitSet3252 static inline bool isEmpty(uint32_t value) { return ! value; } 53 54 // Returns true if the bit set does not contain any unmarked bits. isFullBitSet3255 inline bool isFull() const { return isFull(value); } 56 isFullBitSet3257 static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; } 58 59 // Returns true if the specified bit is marked. hasBitBitSet3260 inline bool hasBit(uint32_t n) const { return hasBit(value, n); } 61 hasBitBitSet3262 static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); } 63 64 // Marks the specified bit. markBitBitSet3265 inline void markBit(uint32_t n) { markBit(value, n); } 66 markBitBitSet3267 static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); } 68 69 // Clears the specified bit. clearBitBitSet3270 inline void clearBit(uint32_t n) { clearBit(value, n); } 71 clearBitBitSet3272 static inline void clearBit(uint32_t& value, uint32_t n) { value &= ~ valueForBit(n); } 73 74 // Finds the first marked bit in the set. 75 // Result is undefined if all bits are unmarked. firstMarkedBitBitSet3276 inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } 77 firstMarkedBitBitSet3278 static uint32_t firstMarkedBit(uint32_t value) { return clz_checked(value); } 79 80 // Finds the first unmarked bit in the set. 81 // Result is undefined if all bits are marked. firstUnmarkedBitBitSet3282 inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } 83 firstUnmarkedBitBitSet3284 static inline uint32_t firstUnmarkedBit(uint32_t value) { return clz_checked(~ value); } 85 86 // Finds the last marked bit in the set. 87 // Result is undefined if all bits are unmarked. lastMarkedBitBitSet3288 inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } 89 lastMarkedBitBitSet3290 static inline uint32_t lastMarkedBit(uint32_t value) { return 31 - ctz_checked(value); } 91 92 // Finds the first marked bit in the set and clears it. Returns the bit index. 93 // Result is undefined if all bits are unmarked. clearFirstMarkedBitBitSet3294 inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } 95 clearFirstMarkedBitBitSet3296 static inline uint32_t clearFirstMarkedBit(uint32_t& value) { 97 uint32_t n = firstMarkedBit(value); 98 clearBit(value, n); 99 return n; 100 } 101 102 // Finds the first unmarked bit in the set and marks it. Returns the bit index. 103 // Result is undefined if all bits are marked. markFirstUnmarkedBitBitSet32104 inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } 105 markFirstUnmarkedBitBitSet32106 static inline uint32_t markFirstUnmarkedBit(uint32_t& value) { 107 uint32_t n = firstUnmarkedBit(value); 108 markBit(value, n); 109 return n; 110 } 111 112 // Finds the last marked bit in the set and clears it. Returns the bit index. 113 // Result is undefined if all bits are unmarked. clearLastMarkedBitBitSet32114 inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } 115 clearLastMarkedBitBitSet32116 static inline uint32_t clearLastMarkedBit(uint32_t& value) { 117 uint32_t n = lastMarkedBit(value); 118 clearBit(value, n); 119 return n; 120 } 121 122 // Gets the index of the specified bit in the set, which is the number of 123 // marked bits that appear before the specified bit. getIndexOfBitBitSet32124 inline uint32_t getIndexOfBit(uint32_t n) const { 125 return getIndexOfBit(value, n); 126 } 127 getIndexOfBitBitSet32128 static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) { 129 return __builtin_popcountl(value & ~(0xffffffffUL >> n)); 130 } 131 132 inline bool operator== (const BitSet32& other) const { return value == other.value; } 133 inline bool operator!= (const BitSet32& other) const { return value != other.value; } 134 inline BitSet32 operator& (const BitSet32& other) const { 135 return BitSet32(value & other.value); 136 } 137 inline BitSet32& operator&= (const BitSet32& other) { 138 value &= other.value; 139 return *this; 140 } 141 inline BitSet32 operator| (const BitSet32& other) const { 142 return BitSet32(value | other.value); 143 } 144 inline BitSet32& operator|= (const BitSet32& other) { 145 value |= other.value; 146 return *this; 147 } 148 149 private: 150 // We use these helpers as the signature of __builtin_c{l,t}z has "unsigned int" for the 151 // input, which is only guaranteed to be 16b, not 32. The compiler should optimize this away. clz_checkedBitSet32152 static inline uint32_t clz_checked(uint32_t value) { 153 if (sizeof(unsigned int) == sizeof(uint32_t)) { 154 return __builtin_clz(value); 155 } else { 156 return __builtin_clzl(value); 157 } 158 } 159 ctz_checkedBitSet32160 static inline uint32_t ctz_checked(uint32_t value) { 161 if (sizeof(unsigned int) == sizeof(uint32_t)) { 162 return __builtin_ctz(value); 163 } else { 164 return __builtin_ctzl(value); 165 } 166 } 167 }; 168 169 ANDROID_BASIC_TYPES_TRAITS(BitSet32) 170 171 // A simple set of 64 bits that can be individually marked or cleared. 172 struct BitSet64 { 173 uint64_t value; 174 BitSet64BitSet64175 inline BitSet64() : value(0ULL) { } BitSet64BitSet64176 explicit inline BitSet64(uint64_t value) : value(value) { } 177 178 // Gets the value associated with a particular bit index. valueForBitBitSet64179 static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; } 180 181 // Clears the bit set. clearBitSet64182 inline void clear() { clear(value); } 183 clearBitSet64184 static inline void clear(uint64_t& value) { value = 0ULL; } 185 186 // Returns the number of marked bits in the set. countBitSet64187 inline uint32_t count() const { return count(value); } 188 countBitSet64189 static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); } 190 191 // Returns true if the bit set does not contain any marked bits. isEmptyBitSet64192 inline bool isEmpty() const { return isEmpty(value); } 193 isEmptyBitSet64194 static inline bool isEmpty(uint64_t value) { return ! value; } 195 196 // Returns true if the bit set does not contain any unmarked bits. isFullBitSet64197 inline bool isFull() const { return isFull(value); } 198 isFullBitSet64199 static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; } 200 201 // Returns true if the specified bit is marked. hasBitBitSet64202 inline bool hasBit(uint32_t n) const { return hasBit(value, n); } 203 hasBitBitSet64204 static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); } 205 206 // Marks the specified bit. markBitBitSet64207 inline void markBit(uint32_t n) { markBit(value, n); } 208 markBitBitSet64209 static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); } 210 211 // Clears the specified bit. clearBitBitSet64212 inline void clearBit(uint32_t n) { clearBit(value, n); } 213 clearBitBitSet64214 static inline void clearBit(uint64_t& value, uint32_t n) { value &= ~ valueForBit(n); } 215 216 // Finds the first marked bit in the set. 217 // Result is undefined if all bits are unmarked. firstMarkedBitBitSet64218 inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } 219 firstMarkedBitBitSet64220 static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); } 221 222 // Finds the first unmarked bit in the set. 223 // Result is undefined if all bits are marked. firstUnmarkedBitBitSet64224 inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } 225 firstUnmarkedBitBitSet64226 static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); } 227 228 // Finds the last marked bit in the set. 229 // Result is undefined if all bits are unmarked. lastMarkedBitBitSet64230 inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } 231 lastMarkedBitBitSet64232 static inline uint32_t lastMarkedBit(uint64_t value) { return 63 - __builtin_ctzll(value); } 233 234 // Finds the first marked bit in the set and clears it. Returns the bit index. 235 // Result is undefined if all bits are unmarked. clearFirstMarkedBitBitSet64236 inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } 237 clearFirstMarkedBitBitSet64238 static inline uint32_t clearFirstMarkedBit(uint64_t& value) { 239 uint64_t n = firstMarkedBit(value); 240 clearBit(value, n); 241 return n; 242 } 243 244 // Finds the first unmarked bit in the set and marks it. Returns the bit index. 245 // Result is undefined if all bits are marked. markFirstUnmarkedBitBitSet64246 inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } 247 markFirstUnmarkedBitBitSet64248 static inline uint32_t markFirstUnmarkedBit(uint64_t& value) { 249 uint64_t n = firstUnmarkedBit(value); 250 markBit(value, n); 251 return n; 252 } 253 254 // Finds the last marked bit in the set and clears it. Returns the bit index. 255 // Result is undefined if all bits are unmarked. clearLastMarkedBitBitSet64256 inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } 257 clearLastMarkedBitBitSet64258 static inline uint32_t clearLastMarkedBit(uint64_t& value) { 259 uint64_t n = lastMarkedBit(value); 260 clearBit(value, n); 261 return n; 262 } 263 264 // Gets the index of the specified bit in the set, which is the number of 265 // marked bits that appear before the specified bit. getIndexOfBitBitSet64266 inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); } 267 getIndexOfBitBitSet64268 static inline uint32_t getIndexOfBit(uint64_t value, uint32_t n) { 269 return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n)); 270 } 271 272 inline bool operator== (const BitSet64& other) const { return value == other.value; } 273 inline bool operator!= (const BitSet64& other) const { return value != other.value; } 274 inline BitSet64 operator& (const BitSet64& other) const { 275 return BitSet64(value & other.value); 276 } 277 inline BitSet64& operator&= (const BitSet64& other) { 278 value &= other.value; 279 return *this; 280 } 281 inline BitSet64 operator| (const BitSet64& other) const { 282 return BitSet64(value | other.value); 283 } 284 inline BitSet64& operator|= (const BitSet64& other) { 285 value |= other.value; 286 return *this; 287 } 288 }; 289 290 ANDROID_BASIC_TYPES_TRAITS(BitSet64) 291 292 } // namespace android 293 294 #endif // UTILS_BITSET_H 295