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(0) { } 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 0x80000000 >> n; } 38 39 // Clears the bit set. clearBitSet3240 inline void clear() { value = 0; } 41 42 // Returns the number of marked bits in the set. countBitSet3243 inline uint32_t count() const { return __builtin_popcount(value); } 44 45 // Returns true if the bit set does not contain any marked bits. isEmptyBitSet3246 inline bool isEmpty() const { return ! value; } 47 48 // Returns true if the bit set does not contain any unmarked bits. isFullBitSet3249 inline bool isFull() const { return value == 0xffffffff; } 50 51 // Returns true if the specified bit is marked. hasBitBitSet3252 inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } 53 54 // Marks the specified bit. markBitBitSet3255 inline void markBit(uint32_t n) { value |= valueForBit(n); } 56 57 // Clears the specified bit. clearBitBitSet3258 inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); } 59 60 // Finds the first marked bit in the set. 61 // Result is undefined if all bits are unmarked. firstMarkedBitBitSet3262 inline uint32_t firstMarkedBit() const { return __builtin_clz(value); } 63 64 // Finds the first unmarked bit in the set. 65 // Result is undefined if all bits are marked. firstUnmarkedBitBitSet3266 inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); } 67 68 // Finds the last marked bit in the set. 69 // Result is undefined if all bits are unmarked. lastMarkedBitBitSet3270 inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); } 71 72 // Finds the first marked bit in the set and clears it. Returns the bit index. 73 // Result is undefined if all bits are unmarked. clearFirstMarkedBitBitSet3274 inline uint32_t clearFirstMarkedBit() { 75 uint32_t n = firstMarkedBit(); 76 clearBit(n); 77 return n; 78 } 79 80 // Finds the first unmarked bit in the set and marks it. Returns the bit index. 81 // Result is undefined if all bits are marked. markFirstUnmarkedBitBitSet3282 inline uint32_t markFirstUnmarkedBit() { 83 uint32_t n = firstUnmarkedBit(); 84 markBit(n); 85 return n; 86 } 87 88 // Finds the last marked bit in the set and clears it. Returns the bit index. 89 // Result is undefined if all bits are unmarked. clearLastMarkedBitBitSet3290 inline uint32_t clearLastMarkedBit() { 91 uint32_t n = lastMarkedBit(); 92 clearBit(n); 93 return n; 94 } 95 96 // Gets the index of the specified bit in the set, which is the number of 97 // marked bits that appear before the specified bit. getIndexOfBitBitSet3298 inline uint32_t getIndexOfBit(uint32_t n) const { 99 return __builtin_popcount(value & ~(0xffffffffUL >> n)); 100 } 101 102 inline bool operator== (const BitSet32& other) const { return value == other.value; } 103 inline bool operator!= (const BitSet32& other) const { return value != other.value; } 104 }; 105 106 ANDROID_BASIC_TYPES_TRAITS(BitSet32) 107 108 } // namespace android 109 110 #endif // UTILS_BITSET_H 111