BitSet.h revision bab6ea0bb70dd6d093a0765befc7d6893e2312bf 
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(0) { }
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 0x80000000 >> n; }
38
39    // Clears the bit set.
40    inline void clear() { value = 0; }
41
42    // Returns the number of marked bits in the set.
43    inline uint32_t count() const { return __builtin_popcountl(value); }
44
45    // Returns true if the bit set does not contain any marked bits.
46    inline bool isEmpty() const { return ! value; }
47
48    // Returns true if the bit set does not contain any unmarked bits.
49    inline bool isFull() const { return value == 0xffffffff; }
50
51    // Returns true if the specified bit is marked.
52    inline bool hasBit(uint32_t n) const { return value & valueForBit(n); }
53
54    // Marks the specified bit.
55    inline void markBit(uint32_t n) { value |= valueForBit(n); }
56
57    // Clears the specified bit.
58    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.
62    inline uint32_t firstMarkedBit() const { return __builtin_clzl(value); }
63
64    // Finds the first unmarked bit in the set.
65    // Result is undefined if all bits are marked.
66    inline uint32_t firstUnmarkedBit() const { return __builtin_clzl(~ value); }
67
68    // Finds the last marked bit in the set.
69    // Result is undefined if all bits are unmarked.
70    inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctzl(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.
74    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.
82    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.
90    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.
98    inline uint32_t getIndexOfBit(uint32_t n) const {
99        return __builtin_popcountl(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    inline BitSet32 operator& (const BitSet32& other) const {
105        return BitSet32(value & other.value);
106    }
107    inline BitSet32& operator&= (const BitSet32& other) {
108        value &= other.value;
109        return *this;
110    }
111    inline BitSet32 operator| (const BitSet32& other) const {
112        return BitSet32(value | other.value);
113    }
114    inline BitSet32& operator|= (const BitSet32& other) {
115        value |= other.value;
116        return *this;
117    }
118};
119
120ANDROID_BASIC_TYPES_TRAITS(BitSet32)
121
122// A simple set of 64 bits that can be individually marked or cleared.
123struct BitSet64 {
124    uint64_t value;
125
126    inline BitSet64() : value(0ULL) { }
127    explicit inline BitSet64(uint64_t value) : value(value) { }
128
129    // Gets the value associated with a particular bit index.
130    static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; }
131
132    // Clears the bit set.
133    inline void clear() { value = 0ULL; }
134
135    // Returns the number of marked bits in the set.
136    inline uint32_t count() const { return __builtin_popcountll(value); }
137
138    // Returns true if the bit set does not contain any marked bits.
139    inline bool isEmpty() const { return ! value; }
140
141    // Returns true if the bit set does not contain any unmarked bits.
142    inline bool isFull() const { return value == 0xffffffffffffffffULL; }
143
144    // Returns true if the specified bit is marked.
145    inline bool hasBit(uint32_t n) const { return value & valueForBit(n); }
146
147    // Marks the specified bit.
148    inline void markBit(uint32_t n) { value |= valueForBit(n); }
149
150    // Clears the specified bit.
151    inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); }
152
153    // Finds the first marked bit in the set.
154    // Result is undefined if all bits are unmarked.
155    inline uint32_t firstMarkedBit() const { return __builtin_clzll(value); }
156
157    // Finds the first unmarked bit in the set.
158    // Result is undefined if all bits are marked.
159    inline uint32_t firstUnmarkedBit() const { return __builtin_clzll(~ value); }
160
161    // Finds the last marked bit in the set.
162    // Result is undefined if all bits are unmarked.
163    inline uint32_t lastMarkedBit() const { return 63 - __builtin_ctzll(value); }
164
165    // Finds the first marked bit in the set and clears it.  Returns the bit index.
166    // Result is undefined if all bits are unmarked.
167    inline uint32_t clearFirstMarkedBit() {
168        uint64_t n = firstMarkedBit();
169        clearBit(n);
170        return n;
171    }
172
173    // Finds the first unmarked bit in the set and marks it.  Returns the bit index.
174    // Result is undefined if all bits are marked.
175    inline uint32_t markFirstUnmarkedBit() {
176        uint64_t n = firstUnmarkedBit();
177        markBit(n);
178        return n;
179    }
180
181    // Finds the last marked bit in the set and clears it.  Returns the bit index.
182    // Result is undefined if all bits are unmarked.
183    inline uint32_t clearLastMarkedBit() {
184        uint64_t n = lastMarkedBit();
185        clearBit(n);
186        return n;
187    }
188
189    // Gets the index of the specified bit in the set, which is the number of
190    // marked bits that appear before the specified bit.
191    inline uint32_t getIndexOfBit(uint32_t n) const {
192        return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n));
193    }
194
195    inline bool operator== (const BitSet64& other) const { return value == other.value; }
196    inline bool operator!= (const BitSet64& other) const { return value != other.value; }
197    inline BitSet64 operator& (const BitSet64& other) const {
198        return BitSet64(value & other.value);
199    }
200    inline BitSet64& operator&= (const BitSet64& other) {
201        value &= other.value;
202        return *this;
203    }
204    inline BitSet64 operator| (const BitSet64& other) const {
205        return BitSet64(value | other.value);
206    }
207    inline BitSet64& operator|= (const BitSet64& other) {
208        value |= other.value;
209        return *this;
210    }
211};
212
213ANDROID_BASIC_TYPES_TRAITS(BitSet32)
214
215} // namespace android
216
217#endif // UTILS_BITSET_H
218