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 * DO NOT USE: std::bitset<32> or std::bitset<64> preferred 27 */ 28 29 namespace android { 30 31 // A simple set of 32 bits that can be individually marked or cleared. 32 struct BitSet32 { 33 uint32_t value; 34 BitSet32BitSet3235 inline BitSet32() : value(0UL) { } BitSet32BitSet3236 explicit inline BitSet32(uint32_t value) : value(value) { } 37 38 // Gets the value associated with a particular bit index. valueForBitBitSet3239 static inline uint32_t valueForBit(uint32_t n) { return 0x80000000UL >> n; } 40 41 // Clears the bit set. clearBitSet3242 inline void clear() { clear(value); } 43 clearBitSet3244 static inline void clear(uint32_t& value) { value = 0UL; } 45 46 // Returns the number of marked bits in the set. countBitSet3247 inline uint32_t count() const { return count(value); } 48 countBitSet3249 static inline uint32_t count(uint32_t value) { return __builtin_popcountl(value); } 50 51 // Returns true if the bit set does not contain any marked bits. isEmptyBitSet3252 inline bool isEmpty() const { return isEmpty(value); } 53 isEmptyBitSet3254 static inline bool isEmpty(uint32_t value) { return ! value; } 55 56 // Returns true if the bit set does not contain any unmarked bits. isFullBitSet3257 inline bool isFull() const { return isFull(value); } 58 isFullBitSet3259 static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; } 60 61 // Returns true if the specified bit is marked. hasBitBitSet3262 inline bool hasBit(uint32_t n) const { return hasBit(value, n); } 63 hasBitBitSet3264 static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); } 65 66 // Marks the specified bit. markBitBitSet3267 inline void markBit(uint32_t n) { markBit(value, n); } 68 markBitBitSet3269 static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); } 70 71 // Clears the specified bit. clearBitBitSet3272 inline void clearBit(uint32_t n) { clearBit(value, n); } 73 clearBitBitSet3274 static inline void clearBit(uint32_t& value, uint32_t n) { value &= ~ valueForBit(n); } 75 76 // Finds the first marked bit in the set. 77 // Result is undefined if all bits are unmarked. firstMarkedBitBitSet3278 inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } 79 firstMarkedBitBitSet3280 static uint32_t firstMarkedBit(uint32_t value) { return clz_checked(value); } 81 82 // Finds the first unmarked bit in the set. 83 // Result is undefined if all bits are marked. firstUnmarkedBitBitSet3284 inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } 85 firstUnmarkedBitBitSet3286 static inline uint32_t firstUnmarkedBit(uint32_t value) { return clz_checked(~ value); } 87 88 // Finds the last marked bit in the set. 89 // Result is undefined if all bits are unmarked. lastMarkedBitBitSet3290 inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } 91 lastMarkedBitBitSet3292 static inline uint32_t lastMarkedBit(uint32_t value) { return 31 - ctz_checked(value); } 93 94 // Finds the first marked bit in the set and clears it. Returns the bit index. 95 // Result is undefined if all bits are unmarked. clearFirstMarkedBitBitSet3296 inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } 97 clearFirstMarkedBitBitSet3298 static inline uint32_t clearFirstMarkedBit(uint32_t& value) { 99 uint32_t n = firstMarkedBit(value); 100 clearBit(value, n); 101 return n; 102 } 103 104 // Finds the first unmarked bit in the set and marks it. Returns the bit index. 105 // Result is undefined if all bits are marked. markFirstUnmarkedBitBitSet32106 inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } 107 markFirstUnmarkedBitBitSet32108 static inline uint32_t markFirstUnmarkedBit(uint32_t& value) { 109 uint32_t n = firstUnmarkedBit(value); 110 markBit(value, n); 111 return n; 112 } 113 114 // Finds the last marked bit in the set and clears it. Returns the bit index. 115 // Result is undefined if all bits are unmarked. clearLastMarkedBitBitSet32116 inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } 117 clearLastMarkedBitBitSet32118 static inline uint32_t clearLastMarkedBit(uint32_t& value) { 119 uint32_t n = lastMarkedBit(value); 120 clearBit(value, n); 121 return n; 122 } 123 124 // Gets the index of the specified bit in the set, which is the number of 125 // marked bits that appear before the specified bit. getIndexOfBitBitSet32126 inline uint32_t getIndexOfBit(uint32_t n) const { 127 return getIndexOfBit(value, n); 128 } 129 getIndexOfBitBitSet32130 static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) { 131 return __builtin_popcountl(value & ~(0xffffffffUL >> n)); 132 } 133 134 inline bool operator== (const BitSet32& other) const { return value == other.value; } 135 inline bool operator!= (const BitSet32& other) const { return value != other.value; } 136 inline BitSet32 operator& (const BitSet32& other) const { 137 return BitSet32(value & other.value); 138 } 139 inline BitSet32& operator&= (const BitSet32& other) { 140 value &= other.value; 141 return *this; 142 } 143 inline BitSet32 operator| (const BitSet32& other) const { 144 return BitSet32(value | other.value); 145 } 146 inline BitSet32& operator|= (const BitSet32& other) { 147 value |= other.value; 148 return *this; 149 } 150 151 private: 152 // We use these helpers as the signature of __builtin_c{l,t}z has "unsigned int" for the 153 // input, which is only guaranteed to be 16b, not 32. The compiler should optimize this away. clz_checkedBitSet32154 static inline uint32_t clz_checked(uint32_t value) { 155 if (sizeof(unsigned int) == sizeof(uint32_t)) { 156 return __builtin_clz(value); 157 } else { 158 return __builtin_clzl(value); 159 } 160 } 161 ctz_checkedBitSet32162 static inline uint32_t ctz_checked(uint32_t value) { 163 if (sizeof(unsigned int) == sizeof(uint32_t)) { 164 return __builtin_ctz(value); 165 } else { 166 return __builtin_ctzl(value); 167 } 168 } 169 }; 170 171 ANDROID_BASIC_TYPES_TRAITS(BitSet32) 172 173 // A simple set of 64 bits that can be individually marked or cleared. 174 struct BitSet64 { 175 uint64_t value; 176 BitSet64BitSet64177 inline BitSet64() : value(0ULL) { } BitSet64BitSet64178 explicit inline BitSet64(uint64_t value) : value(value) { } 179 180 // Gets the value associated with a particular bit index. valueForBitBitSet64181 static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; } 182 183 // Clears the bit set. clearBitSet64184 inline void clear() { clear(value); } 185 clearBitSet64186 static inline void clear(uint64_t& value) { value = 0ULL; } 187 188 // Returns the number of marked bits in the set. countBitSet64189 inline uint32_t count() const { return count(value); } 190 countBitSet64191 static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); } 192 193 // Returns true if the bit set does not contain any marked bits. isEmptyBitSet64194 inline bool isEmpty() const { return isEmpty(value); } 195 isEmptyBitSet64196 static inline bool isEmpty(uint64_t value) { return ! value; } 197 198 // Returns true if the bit set does not contain any unmarked bits. isFullBitSet64199 inline bool isFull() const { return isFull(value); } 200 isFullBitSet64201 static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; } 202 203 // Returns true if the specified bit is marked. hasBitBitSet64204 inline bool hasBit(uint32_t n) const { return hasBit(value, n); } 205 hasBitBitSet64206 static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); } 207 208 // Marks the specified bit. markBitBitSet64209 inline void markBit(uint32_t n) { markBit(value, n); } 210 markBitBitSet64211 static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); } 212 213 // Clears the specified bit. clearBitBitSet64214 inline void clearBit(uint32_t n) { clearBit(value, n); } 215 clearBitBitSet64216 static inline void clearBit(uint64_t& value, uint32_t n) { value &= ~ valueForBit(n); } 217 218 // Finds the first marked bit in the set. 219 // Result is undefined if all bits are unmarked. firstMarkedBitBitSet64220 inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } 221 firstMarkedBitBitSet64222 static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); } 223 224 // Finds the first unmarked bit in the set. 225 // Result is undefined if all bits are marked. firstUnmarkedBitBitSet64226 inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } 227 firstUnmarkedBitBitSet64228 static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); } 229 230 // Finds the last marked bit in the set. 231 // Result is undefined if all bits are unmarked. lastMarkedBitBitSet64232 inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } 233 lastMarkedBitBitSet64234 static inline uint32_t lastMarkedBit(uint64_t value) { return 63 - __builtin_ctzll(value); } 235 236 // Finds the first marked bit in the set and clears it. Returns the bit index. 237 // Result is undefined if all bits are unmarked. clearFirstMarkedBitBitSet64238 inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } 239 clearFirstMarkedBitBitSet64240 static inline uint32_t clearFirstMarkedBit(uint64_t& value) { 241 uint64_t n = firstMarkedBit(value); 242 clearBit(value, n); 243 return n; 244 } 245 246 // Finds the first unmarked bit in the set and marks it. Returns the bit index. 247 // Result is undefined if all bits are marked. markFirstUnmarkedBitBitSet64248 inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } 249 markFirstUnmarkedBitBitSet64250 static inline uint32_t markFirstUnmarkedBit(uint64_t& value) { 251 uint64_t n = firstUnmarkedBit(value); 252 markBit(value, n); 253 return n; 254 } 255 256 // Finds the last marked bit in the set and clears it. Returns the bit index. 257 // Result is undefined if all bits are unmarked. clearLastMarkedBitBitSet64258 inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } 259 clearLastMarkedBitBitSet64260 static inline uint32_t clearLastMarkedBit(uint64_t& value) { 261 uint64_t n = lastMarkedBit(value); 262 clearBit(value, n); 263 return n; 264 } 265 266 // Gets the index of the specified bit in the set, which is the number of 267 // marked bits that appear before the specified bit. getIndexOfBitBitSet64268 inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); } 269 getIndexOfBitBitSet64270 static inline uint32_t getIndexOfBit(uint64_t value, uint32_t n) { 271 return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n)); 272 } 273 274 inline bool operator== (const BitSet64& other) const { return value == other.value; } 275 inline bool operator!= (const BitSet64& other) const { return value != other.value; } 276 inline BitSet64 operator& (const BitSet64& other) const { 277 return BitSet64(value & other.value); 278 } 279 inline BitSet64& operator&= (const BitSet64& other) { 280 value &= other.value; 281 return *this; 282 } 283 inline BitSet64 operator| (const BitSet64& other) const { 284 return BitSet64(value | other.value); 285 } 286 inline BitSet64& operator|= (const BitSet64& other) { 287 value |= other.value; 288 return *this; 289 } 290 }; 291 292 ANDROID_BASIC_TYPES_TRAITS(BitSet64) 293 294 } // namespace android 295 296 #endif // UTILS_BITSET_H 297