• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
BitSet32BitSet3232     inline BitSet32() : value(0) { }
BitSet32BitSet3233     explicit inline BitSet32(uint32_t value) : value(value) { }
34 
35     // Gets the value associated with a particular bit index.
valueForBitBitSet3236     static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; }
37 
38     // Clears the bit set.
clearBitSet3239     inline void clear() { value = 0; }
40 
41     // Returns the number of marked bits in the set.
countBitSet3242     inline uint32_t count() const { return __builtin_popcount(value); }
43 
44     // Returns true if the bit set does not contain any marked bits.
isEmptyBitSet3245     inline bool isEmpty() const { return ! value; }
46 
47     // Returns true if the bit set does not contain any unmarked bits.
isFullBitSet3248     inline bool isFull() const { return value == 0xffffffff; }
49 
50     // Returns true if the specified bit is marked.
hasBitBitSet3251     inline bool hasBit(uint32_t n) const { return value & valueForBit(n); }
52 
53     // Marks the specified bit.
markBitBitSet3254     inline void markBit(uint32_t n) { value |= valueForBit(n); }
55 
56     // Clears the specified bit.
clearBitBitSet3257     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.
firstMarkedBitBitSet3261     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.
firstUnmarkedBitBitSet3265     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.
lastMarkedBitBitSet3269     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.
clearFirstMarkedBitBitSet3273     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.
markFirstUnmarkedBitBitSet3281     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.
clearLastMarkedBitBitSet3289     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.
getIndexOfBitBitSet3297     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