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