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 specified bit is marked. 48 inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } 49 50 // Marks the specified bit. 51 inline void markBit(uint32_t n) { value |= valueForBit(n); } 52 53 // Clears the specified bit. 54 inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); } 55 56 // Finds the first marked bit in the set. 57 // Result is undefined if all bits are unmarked. 58 inline uint32_t firstMarkedBit() const { return __builtin_clz(value); } 59 60 // Finds the first unmarked bit in the set. 61 // Result is undefined if all bits are marked. 62 inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); } 63 64 inline bool operator== (const BitSet32& other) const { return value == other.value; } 65 inline bool operator!= (const BitSet32& other) const { return value != other.value; } 66 }; 67 68 } // namespace android 69 70 #endif // UTILS_BITSET_H 71