166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown/* 266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * Copyright (C) 2010 The Android Open Source Project 366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * 466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * Licensed under the Apache License, Version 2.0 (the "License"); 566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * you may not use this file except in compliance with the License. 666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * You may obtain a copy of the License at 766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * 866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * http://www.apache.org/licenses/LICENSE-2.0 966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * 1066db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * Unless required by applicable law or agreed to in writing, software 1166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * distributed under the License is distributed on an "AS IS" BASIS, 1266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 1366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * See the License for the specific language governing permissions and 1466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * limitations under the License. 1566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown */ 1666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 1766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown#ifndef UTILS_BITSET_H 1866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown#define UTILS_BITSET_H 1966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 2066db68948c83f1940fa66d76d28208b49bed7815Jeff Brown#include <stdint.h> 219a0a76df1e961ef4621e81814d8bf891a09bef66Jeff Brown#include <utils/TypeHelpers.h> 2266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 2366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown/* 2466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown * Contains some bit manipulation helpers. 2566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown */ 2666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 2766db68948c83f1940fa66d76d28208b49bed7815Jeff Brownnamespace android { 2866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 2966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown// A simple set of 32 bits that can be individually marked or cleared. 3066db68948c83f1940fa66d76d28208b49bed7815Jeff Brownstruct BitSet32 { 3166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown uint32_t value; 3266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 332ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline BitSet32() : value(0UL) { } 3466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown explicit inline BitSet32(uint32_t value) : value(value) { } 3566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 3666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Gets the value associated with a particular bit index. 372ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t valueForBit(uint32_t n) { return 0x80000000UL >> n; } 3866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 3966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Clears the bit set. 402ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline void clear() { clear(value); } 412ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 422ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline void clear(uint32_t& value) { value = 0UL; } 4366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 447d90df8dc30e7b22aea030f7dca01095529cc6b1Jeff Brown // Returns the number of marked bits in the set. 452ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t count() const { return count(value); } 462ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 472ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t count(uint32_t value) { return __builtin_popcountl(value); } 487d90df8dc30e7b22aea030f7dca01095529cc6b1Jeff Brown 4966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Returns true if the bit set does not contain any marked bits. 502ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline bool isEmpty() const { return isEmpty(value); } 512ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 522ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline bool isEmpty(uint32_t value) { return ! value; } 5366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 5482e14f67803d3457b639a8aea772a6490b34165cJeff Brown // Returns true if the bit set does not contain any unmarked bits. 552ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline bool isFull() const { return isFull(value); } 562ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 572ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline bool isFull(uint32_t value) { return value == 0xffffffffUL; } 5882e14f67803d3457b639a8aea772a6490b34165cJeff Brown 5966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Returns true if the specified bit is marked. 602ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline bool hasBit(uint32_t n) const { return hasBit(value, n); } 612ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 622ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline bool hasBit(uint32_t value, uint32_t n) { return value & valueForBit(n); } 6366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 6466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Marks the specified bit. 652ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline void markBit(uint32_t n) { markBit(value, n); } 662ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 672ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline void markBit (uint32_t& value, uint32_t n) { value |= valueForBit(n); } 6866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 6966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Clears the specified bit. 702ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline void clearBit(uint32_t n) { clearBit(value, n); } 712ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 722ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline void clearBit(uint32_t& value, uint32_t n) { value &= ~ valueForBit(n); } 7366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 7466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Finds the first marked bit in the set. 7566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Result is undefined if all bits are unmarked. 762ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } 772ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 7802c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe static uint32_t firstMarkedBit(uint32_t value) { return clz_checked(value); } 7966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 8066db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Finds the first unmarked bit in the set. 8166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Result is undefined if all bits are marked. 822ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } 832ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 8402c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe static inline uint32_t firstUnmarkedBit(uint32_t value) { return clz_checked(~ value); } 8566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 865e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown // Finds the last marked bit in the set. 875e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown // Result is undefined if all bits are unmarked. 882ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } 892ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 9002c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe static inline uint32_t lastMarkedBit(uint32_t value) { return 31 - ctz_checked(value); } 915e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown 924ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Finds the first marked bit in the set and clears it. Returns the bit index. 934ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Result is undefined if all bits are unmarked. 942ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } 952ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 962ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t clearFirstMarkedBit(uint32_t& value) { 972ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright uint32_t n = firstMarkedBit(value); 982ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright clearBit(value, n); 994ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown return n; 1004ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown } 1014ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown 1024ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Finds the first unmarked bit in the set and marks it. Returns the bit index. 1034ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Result is undefined if all bits are marked. 1042ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } 1052ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1062ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t markFirstUnmarkedBit(uint32_t& value) { 1072ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright uint32_t n = firstUnmarkedBit(value); 1082ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright markBit(value, n); 1094ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown return n; 1104ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown } 1114ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown 1124ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Finds the last marked bit in the set and clears it. Returns the bit index. 1134ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Result is undefined if all bits are unmarked. 1142ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } 1152ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1162ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t clearLastMarkedBit(uint32_t& value) { 1172ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright uint32_t n = lastMarkedBit(value); 1182ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright clearBit(value, n); 1194ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown return n; 1204ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown } 1214ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown 1229ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown // Gets the index of the specified bit in the set, which is the number of 1239ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown // marked bits that appear before the specified bit. 1249ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown inline uint32_t getIndexOfBit(uint32_t n) const { 1252ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright return getIndexOfBit(value, n); 1262ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright } 1272ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1282ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t getIndexOfBit(uint32_t value, uint32_t n) { 129bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return __builtin_popcountl(value & ~(0xffffffffUL >> n)); 1309ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown } 1319ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown 13266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline bool operator== (const BitSet32& other) const { return value == other.value; } 13366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline bool operator!= (const BitSet32& other) const { return value != other.value; } 134d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32 operator& (const BitSet32& other) const { 135d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return BitSet32(value & other.value); 136d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 137d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32& operator&= (const BitSet32& other) { 138d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright value &= other.value; 139d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return *this; 140d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 141d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32 operator| (const BitSet32& other) const { 142d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return BitSet32(value | other.value); 143d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 144d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32& operator|= (const BitSet32& other) { 145d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright value |= other.value; 146d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return *this; 147d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 14802c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe 14902c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampeprivate: 15002c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe // We use these helpers as the signature of __builtin_c{l,t}z has "unsigned int" for the 15102c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe // input, which is only guaranteed to be 16b, not 32. The compiler should optimize this away. 15202c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe static inline uint32_t clz_checked(uint32_t value) { 15302c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe if (sizeof(unsigned int) == sizeof(uint32_t)) { 15402c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe return __builtin_clz(value); 15502c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe } else { 15602c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe return __builtin_clzl(value); 15702c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe } 15802c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe } 15902c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe 16002c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe static inline uint32_t ctz_checked(uint32_t value) { 16102c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe if (sizeof(unsigned int) == sizeof(uint32_t)) { 16202c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe return __builtin_ctz(value); 16302c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe } else { 16402c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe return __builtin_ctzl(value); 16502c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe } 16602c9460a0a05f27e0501f9e64cdf24091e7d3579Andreas Gampe } 16766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown}; 16866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 1699a0a76df1e961ef4621e81814d8bf891a09bef66Jeff BrownANDROID_BASIC_TYPES_TRAITS(BitSet32) 1709a0a76df1e961ef4621e81814d8bf891a09bef66Jeff Brown 171bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright// A simple set of 64 bits that can be individually marked or cleared. 172bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wrightstruct BitSet64 { 173bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright uint64_t value; 174bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 175bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline BitSet64() : value(0ULL) { } 176bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright explicit inline BitSet64(uint64_t value) : value(value) { } 177bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 178bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Gets the value associated with a particular bit index. 179bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright static inline uint64_t valueForBit(uint32_t n) { return 0x8000000000000000ULL >> n; } 180bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 181bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Clears the bit set. 1822ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline void clear() { clear(value); } 1832ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1842ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline void clear(uint64_t& value) { value = 0ULL; } 185bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 186bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Returns the number of marked bits in the set. 1872ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t count() const { return count(value); } 1882ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1892ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t count(uint64_t value) { return __builtin_popcountll(value); } 190bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 191bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Returns true if the bit set does not contain any marked bits. 1922ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline bool isEmpty() const { return isEmpty(value); } 1932ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1942ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline bool isEmpty(uint64_t value) { return ! value; } 195bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 196bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Returns true if the bit set does not contain any unmarked bits. 1972ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline bool isFull() const { return isFull(value); } 1982ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 1992ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline bool isFull(uint64_t value) { return value == 0xffffffffffffffffULL; } 200bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 201bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Returns true if the specified bit is marked. 2022ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline bool hasBit(uint32_t n) const { return hasBit(value, n); } 2032ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2042ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline bool hasBit(uint64_t value, uint32_t n) { return value & valueForBit(n); } 205bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 206bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Marks the specified bit. 2072ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline void markBit(uint32_t n) { markBit(value, n); } 2082ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2092ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline void markBit(uint64_t& value, uint32_t n) { value |= valueForBit(n); } 210bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 211bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Clears the specified bit. 2122ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline void clearBit(uint32_t n) { clearBit(value, n); } 2132ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2142ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline void clearBit(uint64_t& value, uint32_t n) { value &= ~ valueForBit(n); } 215bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 216bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Finds the first marked bit in the set. 217bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Result is undefined if all bits are unmarked. 2182ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t firstMarkedBit() const { return firstMarkedBit(value); } 2192ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2202ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t firstMarkedBit(uint64_t value) { return __builtin_clzll(value); } 221bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 222bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Finds the first unmarked bit in the set. 223bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Result is undefined if all bits are marked. 2242ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t firstUnmarkedBit() const { return firstUnmarkedBit(value); } 2252ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2262ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t firstUnmarkedBit(uint64_t value) { return __builtin_clzll(~ value); } 227bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 228bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Finds the last marked bit in the set. 229bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Result is undefined if all bits are unmarked. 2302ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t lastMarkedBit() const { return lastMarkedBit(value); } 2312ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2322ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t lastMarkedBit(uint64_t value) { return 63 - __builtin_ctzll(value); } 233bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 234bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Finds the first marked bit in the set and clears it. Returns the bit index. 235bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Result is undefined if all bits are unmarked. 2362ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t clearFirstMarkedBit() { return clearFirstMarkedBit(value); } 2372ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2382ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t clearFirstMarkedBit(uint64_t& value) { 2392ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright uint64_t n = firstMarkedBit(value); 2402ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright clearBit(value, n); 241bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return n; 242bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 243bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 244bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Finds the first unmarked bit in the set and marks it. Returns the bit index. 245bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Result is undefined if all bits are marked. 2462ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t markFirstUnmarkedBit() { return markFirstUnmarkedBit(value); } 2472ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2482ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t markFirstUnmarkedBit(uint64_t& value) { 2492ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright uint64_t n = firstUnmarkedBit(value); 2502ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright markBit(value, n); 251bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return n; 252bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 253bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 254bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Finds the last marked bit in the set and clears it. Returns the bit index. 255bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Result is undefined if all bits are unmarked. 2562ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t clearLastMarkedBit() { return clearLastMarkedBit(value); } 2572ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2582ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t clearLastMarkedBit(uint64_t& value) { 2592ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright uint64_t n = lastMarkedBit(value); 2602ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright clearBit(value, n); 261bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return n; 262bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 263bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 264bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // Gets the index of the specified bit in the set, which is the number of 265bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright // marked bits that appear before the specified bit. 2662ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright inline uint32_t getIndexOfBit(uint32_t n) const { return getIndexOfBit(value, n); } 2672ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright 2682ec064597ce1cfa5f8bf5f480c90644d57d8d2c5Michael Wright static inline uint32_t getIndexOfBit(uint64_t value, uint32_t n) { 269bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return __builtin_popcountll(value & ~(0xffffffffffffffffULL >> n)); 270bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 271bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 272bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline bool operator== (const BitSet64& other) const { return value == other.value; } 273bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline bool operator!= (const BitSet64& other) const { return value != other.value; } 274bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline BitSet64 operator& (const BitSet64& other) const { 275bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return BitSet64(value & other.value); 276bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 277bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline BitSet64& operator&= (const BitSet64& other) { 278bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright value &= other.value; 279bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return *this; 280bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 281bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline BitSet64 operator| (const BitSet64& other) const { 282bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return BitSet64(value | other.value); 283bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 284bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright inline BitSet64& operator|= (const BitSet64& other) { 285bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright value |= other.value; 286bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright return *this; 287bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright } 288bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright}; 289bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 29074e2538b48658d0912fc8566c381fbb8be095c8aMichael WrightANDROID_BASIC_TYPES_TRAITS(BitSet64) 291bab6ea0bb70dd6d093a0765befc7d6893e2312bfMichael Wright 29266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown} // namespace android 29366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 29466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown#endif // UTILS_BITSET_H 295