Home | History | Annotate | Download | only in utils 
      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  * DO NOT USE: std::bitset<32> or std::bitset<64> preferred
     27  */
     28 
     29 namespace android {
     30 
     31 // A simple set of 32 bits that can be individually marked or cleared.
     32 struct BitSet32 {
     33     uint32_t value;
     34 
     35     inline BitSet32() : value(0UL) { }
     36     explicit inline BitSet32(uint32_t value) : value(value) { }
     37 
     38     // Gets the value associated with a particular bit index.
     39     static inline uint32_t valueForBit(uint32_t n) { return 0x80000000UL >> n; }
     40 
     41     // Clears the bit set.
     42     inline void clear() { clear(value); }
     43 
     44     static inline void clear(uint32_t& value) { value = 0UL; }
     45 
     46     // Returns the number of marked bits in the set.
     47     inline uint32_t count() const { return count(value); }
     48 
     49     static inline uint32_t count(uint32_t value) { return __builtin_popcountl(value); }
     50 
     51     // Returns true if the bit set does not contain any marked bits.
     52     inline bool isEmpty() const { return isEmpty(value); }
     53 
     54     static inline bool isEmpty(uint32_t value) { return ! value; }
     55 
     56     // Returns true if the bit set does not contain any unmarked bits.
     57     inline bool isFull() const { return isFull(value); }
     58 
     59     static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; }
     60 
     61     // Returns true if the specified bit is marked.
     62     inline bool hasBit(uint32_t n) const { return hasBit(value, n); }
     63 
     64     static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); }
     65 
     66     // Marks the specified bit.
     67     inline void markBit(uint32_t n) { markBit(value, n); }
     68 
     69     static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); }
     70 
     71     // Clears the specified bit.
     72     inline void clearBit(uint32_t n) { clearBit(value, n); }
     73 
     74     static inline void clearBit(uint32_t& value, uint32_t n) { value &= ~ valueForBit(n); }
     75 
     76     // Finds the first marked bit in the set.
     77     // Result is undefined if all bits are unmarked.
     78     inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); }
     79 
     80     static uint32_t firstMarkedBit(uint32_t value) { return clz_checked(value); }
     81 
     82     // Finds the first unmarked bit in the set.
     83     // Result is undefined if all bits are marked.
     84     inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); }
     85 
     86     static inline uint32_t firstUnmarkedBit(uint32_t value) { return clz_checked(~ value); }
     87 
     88     // Finds the last marked bit in the set.
     89     // Result is undefined if all bits are unmarked.
     90     inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); }
     91 
     92     static inline uint32_t lastMarkedBit(uint32_t value) { return 31 - ctz_checked(value); }
     93 
     94     // Finds the first marked bit in the set and clears it.  Returns the bit index.
     95     // Result is undefined if all bits are unmarked.
     96     inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); }
     97 
     98     static inline uint32_t clearFirstMarkedBit(uint32_t& value) {
     99         uint32_t n = firstMarkedBit(value);
    100         clearBit(value, n);
    101         return n;
    102     }
    103 
    104     // Finds the first unmarked bit in the set and marks it.  Returns the bit index.
    105     // Result is undefined if all bits are marked.
    106     inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); }
    107 
    108     static inline uint32_t markFirstUnmarkedBit(uint32_t& value) {
    109         uint32_t n = firstUnmarkedBit(value);
    110         markBit(value, n);
    111         return n;
    112     }
    113 
    114     // Finds the last marked bit in the set and clears it.  Returns the bit index.
    115     // Result is undefined if all bits are unmarked.
    116     inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); }
    117 
    118     static inline uint32_t clearLastMarkedBit(uint32_t& value) {
    119         uint32_t n = lastMarkedBit(value);
    120         clearBit(value, n);
    121         return n;
    122     }
    123 
    124     // Gets the index of the specified bit in the set, which is the number of
    125     // marked bits that appear before the specified bit.
    126     inline uint32_t getIndexOfBit(uint32_t n) const {
    127         return getIndexOfBit(value, n);
    128     }
    129 
    130     static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) {
    131         return __builtin_popcountl(value & ~(0xffffffffUL >> n));
    132     }
    133 
    134     inline bool operator== (const BitSet32& other) const { return value == other.value; }
    135     inline bool operator!= (const BitSet32& other) const { return value != other.value; }
    136     inline BitSet32 operator& (const BitSet32& other) const {
    137         return BitSet32(value & other.value);
    138     }
    139     inline BitSet32& operator&= (const BitSet32& other) {
    140         value &= other.value;
    141         return *this;
    142     }
    143     inline BitSet32 operator| (const BitSet32& other) const {
    144         return BitSet32(value | other.value);
    145     }
    146     inline BitSet32& operator|= (const BitSet32& other) {
    147         value |= other.value;
    148         return *this;
    149     }
    150 
    151 private:
    152     // We use these helpers as the signature of __builtin_c{l,t}z has "unsigned int" for the
    153     // input, which is only guaranteed to be 16b, not 32. The compiler should optimize this away.
    154     static inline uint32_t clz_checked(uint32_t value) {
    155         if (sizeof(unsigned int) == sizeof(uint32_t)) {
    156             return __builtin_clz(value);
    157         } else {
    158             return __builtin_clzl(value);
    159         }
    160     }
    161 
    162     static inline uint32_t ctz_checked(uint32_t value) {
    163         if (sizeof(unsigned int) == sizeof(uint32_t)) {
    164             return __builtin_ctz(value);
    165         } else {
    166             return __builtin_ctzl(value);
    167         }
    168     }
    169 };
    170 
    171 ANDROID_BASIC_TYPES_TRAITS(BitSet32)
    172 
    173 // A simple set of 64 bits that can be individually marked or cleared.
    174 struct BitSet64 {
    175     uint64_t value;
    176 
    177     inline BitSet64() : value(0ULL) { }
    178     explicit inline BitSet64(uint64_t value) : value(value) { }
    179 
    180     // Gets the value associated with a particular bit index.
    181     static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; }
    182 
    183     // Clears the bit set.
    184     inline void clear() { clear(value); }
    185 
    186     static inline void clear(uint64_t& value) { value = 0ULL; }
    187 
    188     // Returns the number of marked bits in the set.
    189     inline uint32_t count() const { return count(value); }
    190 
    191     static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); }
    192 
    193     // Returns true if the bit set does not contain any marked bits.
    194     inline bool isEmpty() const { return isEmpty(value); }
    195 
    196     static inline bool isEmpty(uint64_t value) { return ! value; }
    197 
    198     // Returns true if the bit set does not contain any unmarked bits.
    199     inline bool isFull() const { return isFull(value); }
    200 
    201     static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; }
    202 
    203     // Returns true if the specified bit is marked.
    204     inline bool hasBit(uint32_t n) const { return hasBit(value, n); }
    205 
    206     static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); }
    207 
    208     // Marks the specified bit.
    209     inline void markBit(uint32_t n) { markBit(value, n); }
    210 
    211     static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); }
    212 
    213     // Clears the specified bit.
    214     inline void clearBit(uint32_t n) { clearBit(value, n); }
    215 
    216     static inline void clearBit(uint64_t& value, uint32_t n) { value &= ~ valueForBit(n); }
    217 
    218     // Finds the first marked bit in the set.
    219     // Result is undefined if all bits are unmarked.
    220     inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); }
    221 
    222     static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); }
    223 
    224     // Finds the first unmarked bit in the set.
    225     // Result is undefined if all bits are marked.
    226     inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); }
    227 
    228     static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); }
    229 
    230     // Finds the last marked bit in the set.
    231     // Result is undefined if all bits are unmarked.
    232     inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); }
    233 
    234     static inline uint32_t lastMarkedBit(uint64_t value) { return 63 - __builtin_ctzll(value); }
    235 
    236     // Finds the first marked bit in the set and clears it.  Returns the bit index.
    237     // Result is undefined if all bits are unmarked.
    238     inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); }
    239 
    240     static inline uint32_t clearFirstMarkedBit(uint64_t& value) {
    241         uint64_t n = firstMarkedBit(value);
    242         clearBit(value, n);
    243         return n;
    244     }
    245 
    246     // Finds the first unmarked bit in the set and marks it.  Returns the bit index.
    247     // Result is undefined if all bits are marked.
    248     inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); }
    249 
    250     static inline uint32_t markFirstUnmarkedBit(uint64_t& value) {
    251         uint64_t n = firstUnmarkedBit(value);
    252         markBit(value, n);
    253         return n;
    254     }
    255 
    256     // Finds the last marked bit in the set and clears it.  Returns the bit index.
    257     // Result is undefined if all bits are unmarked.
    258     inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); }
    259 
    260     static inline uint32_t clearLastMarkedBit(uint64_t& value) {
    261         uint64_t n = lastMarkedBit(value);
    262         clearBit(value, n);
    263         return n;
    264     }
    265 
    266     // Gets the index of the specified bit in the set, which is the number of
    267     // marked bits that appear before the specified bit.
    268     inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); }
    269 
    270     static inline uint32_t getIndexOfBit(uint64_t value, uint32_t n) {
    271         return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n));
    272     }
    273 
    274     inline bool operator== (const BitSet64& other) const { return value == other.value; }
    275     inline bool operator!= (const BitSet64& other) const { return value != other.value; }
    276     inline BitSet64 operator& (const BitSet64& other) const {
    277         return BitSet64(value & other.value);
    278     }
    279     inline BitSet64& operator&= (const BitSet64& other) {
    280         value &= other.value;
    281         return *this;
    282     }
    283     inline BitSet64 operator| (const BitSet64& other) const {
    284         return BitSet64(value | other.value);
    285     }
    286     inline BitSet64& operator|= (const BitSet64& other) {
    287         value |= other.value;
    288         return *this;
    289     }
    290 };
    291 
    292 ANDROID_BASIC_TYPES_TRAITS(BitSet64)
    293 
    294 } // namespace android
    295 
    296 #endif // UTILS_BITSET_H
    297