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 3366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline BitSet32() : value(0) { } 3466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown explicit inline BitSet32(uint32_t value) : value(value) { } 3566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 3666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Gets the value associated with a particular bit index. 3766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; } 3866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 3966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Clears the bit set. 4066db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline void clear() { value = 0; } 4166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 427d90df8dc30e7b22aea030f7dca01095529cc6b1Jeff Brown // Returns the number of marked bits in the set. 437d90df8dc30e7b22aea030f7dca01095529cc6b1Jeff Brown inline uint32_t count() const { return __builtin_popcount(value); } 447d90df8dc30e7b22aea030f7dca01095529cc6b1Jeff Brown 4566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Returns true if the bit set does not contain any marked bits. 4666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline bool isEmpty() const { return ! value; } 4766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 4882e14f67803d3457b639a8aea772a6490b34165cJeff Brown // Returns true if the bit set does not contain any unmarked bits. 4982e14f67803d3457b639a8aea772a6490b34165cJeff Brown inline bool isFull() const { return value == 0xffffffff; } 5082e14f67803d3457b639a8aea772a6490b34165cJeff Brown 5166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Returns true if the specified bit is marked. 5266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } 5366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 5466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Marks the specified bit. 5566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline void markBit(uint32_t n) { value |= valueForBit(n); } 5666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 5766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Clears the specified bit. 5866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); } 5966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 6066db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Finds the first marked bit in the set. 6166db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Result is undefined if all bits are unmarked. 6266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline uint32_t firstMarkedBit() const { return __builtin_clz(value); } 6366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 6466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Finds the first unmarked bit in the set. 6566db68948c83f1940fa66d76d28208b49bed7815Jeff Brown // Result is undefined if all bits are marked. 6666db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); } 6766db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 685e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown // Finds the last marked bit in the set. 695e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown // Result is undefined if all bits are unmarked. 705e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); } 715e35370a3bd941d8e797b9e9beb1b378e00157d5Jeff Brown 724ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Finds the first marked bit in the set and clears it. Returns the bit index. 734ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Result is undefined if all bits are unmarked. 744ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown inline uint32_t clearFirstMarkedBit() { 754ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown uint32_t n = firstMarkedBit(); 764ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown clearBit(n); 774ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown return n; 784ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown } 794ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown 804ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Finds the first unmarked bit in the set and marks it. Returns the bit index. 814ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Result is undefined if all bits are marked. 824ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown inline uint32_t markFirstUnmarkedBit() { 834ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown uint32_t n = firstUnmarkedBit(); 844ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown markBit(n); 854ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown return n; 864ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown } 874ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown 884ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Finds the last marked bit in the set and clears it. Returns the bit index. 894ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown // Result is undefined if all bits are unmarked. 904ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown inline uint32_t clearLastMarkedBit() { 914ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown uint32_t n = lastMarkedBit(); 924ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown clearBit(n); 934ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown return n; 944ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown } 954ccb2fc8e129236f2832fc18b1ba0f8bbac5abbcJeff Brown 969ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown // Gets the index of the specified bit in the set, which is the number of 979ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown // marked bits that appear before the specified bit. 989ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown inline uint32_t getIndexOfBit(uint32_t n) const { 999ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown return __builtin_popcount(value & ~(0xffffffffUL >> n)); 1009ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown } 1019ae794de4685c080d92d8c2a09d195a0d71ae2a8Jeff Brown 10266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline bool operator== (const BitSet32& other) const { return value == other.value; } 10366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown inline bool operator!= (const BitSet32& other) const { return value != other.value; } 104d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32 operator& (const BitSet32& other) const { 105d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return BitSet32(value & other.value); 106d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 107d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32& operator&= (const BitSet32& other) { 108d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright value &= other.value; 109d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return *this; 110d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 111d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32 operator| (const BitSet32& other) const { 112d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return BitSet32(value | other.value); 113d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 114d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright inline BitSet32& operator|= (const BitSet32& other) { 115d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright value |= other.value; 116d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright return *this; 117d614ee455705047fd27db0ad7f3013e6ea64204dMichael Wright } 11866db68948c83f1940fa66d76d28208b49bed7815Jeff Brown}; 11966db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 1209a0a76df1e961ef4621e81814d8bf891a09bef66Jeff BrownANDROID_BASIC_TYPES_TRAITS(BitSet32) 1219a0a76df1e961ef4621e81814d8bf891a09bef66Jeff Brown 12266db68948c83f1940fa66d76d28208b49bed7815Jeff Brown} // namespace android 12366db68948c83f1940fa66d76d28208b49bed7815Jeff Brown 12466db68948c83f1940fa66d76d28208b49bed7815Jeff Brown#endif // UTILS_BITSET_H 125