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
27namespace android {
28
29// A simple set of 32 bits that can be individually marked or cleared.
30struct BitSet32 {
31    uint32_t value;
32
33    inline BitSet32() : value(0UL) { }
34    explicit inline BitSet32(uint32_t value) : value(value) { }
35
36    // Gets the value associated with a particular bit index.
37    static inline uint32_t valueForBit(uint32_t n) { return 0x80000000UL >> n; }
38
39    // Clears the bit set.
40    inline void clear() { clear(value); }
41
42    static inline void clear(uint32_t& value) { value = 0UL; }
43
44    // Returns the number of marked bits in the set.
45    inline uint32_t count() const { return count(value); }
46
47    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.
50    inline bool isEmpty() const { return isEmpty(value); }
51
52    static inline bool isEmpty(uint32_t value) { return ! value; }
53
54    // Returns true if the bit set does not contain any unmarked bits.
55    inline bool isFull() const { return isFull(value); }
56
57    static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; }
58
59    // Returns true if the specified bit is marked.
60    inline bool hasBit(uint32_t n) const { return hasBit(value, n); }
61
62    static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); }
63
64    // Marks the specified bit.
65    inline void markBit(uint32_t n) { markBit(value, n); }
66
67    static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); }
68
69    // Clears the specified bit.
70    inline void clearBit(uint32_t n) { clearBit(value, n); }
71
72    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.
76    inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); }
77
78    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.
82    inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); }
83
84    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.
88    inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); }
89
90    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.
94    inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); }
95
96    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.
104    inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); }
105
106    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.
114    inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); }
115
116    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.
124    inline uint32_t getIndexOfBit(uint32_t n) const {
125        return getIndexOfBit(value, n);
126    }
127
128    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
149private:
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.
152    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
160    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
169ANDROID_BASIC_TYPES_TRAITS(BitSet32)
170
171// A simple set of 64 bits that can be individually marked or cleared.
172struct BitSet64 {
173    uint64_t value;
174
175    inline BitSet64() : value(0ULL) { }
176    explicit inline BitSet64(uint64_t value) : value(value) { }
177
178    // Gets the value associated with a particular bit index.
179    static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; }
180
181    // Clears the bit set.
182    inline void clear() { clear(value); }
183
184    static inline void clear(uint64_t& value) { value = 0ULL; }
185
186    // Returns the number of marked bits in the set.
187    inline uint32_t count() const { return count(value); }
188
189    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.
192    inline bool isEmpty() const { return isEmpty(value); }
193
194    static inline bool isEmpty(uint64_t value) { return ! value; }
195
196    // Returns true if the bit set does not contain any unmarked bits.
197    inline bool isFull() const { return isFull(value); }
198
199    static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; }
200
201    // Returns true if the specified bit is marked.
202    inline bool hasBit(uint32_t n) const { return hasBit(value, n); }
203
204    static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); }
205
206    // Marks the specified bit.
207    inline void markBit(uint32_t n) { markBit(value, n); }
208
209    static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); }
210
211    // Clears the specified bit.
212    inline void clearBit(uint32_t n) { clearBit(value, n); }
213
214    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.
218    inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); }
219
220    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.
224    inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); }
225
226    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.
230    inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); }
231
232    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.
236    inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); }
237
238    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.
246    inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); }
247
248    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.
256    inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); }
257
258    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.
266    inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); }
267
268    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
290ANDROID_BASIC_TYPES_TRAITS(BitSet64)
291
292} // namespace android
293
294#endif // UTILS_BITSET_H
295