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_popcount(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_clz(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_clz(~ 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_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.
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_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
106ANDROID_BASIC_TYPES_TRAITS(BitSet32)
107
108} // namespace android
109
110#endif // UTILS_BITSET_H
111