diff options
author | The Android Open Source Project <initial-contribution@android.com> | 2013-11-22 11:28:10 -0800 |
---|---|---|
committer | Conley Owens <cco3@android.com> | 2013-11-22 13:44:43 -0800 |
commit | 66ed50af6870210ce013a5588a688434a5d48ee9 (patch) | |
tree | a879f3ea31083496d0efe491bc187b6e0ebada39 /include/utils/BitSet.h | |
parent | dd2ac3de625e6c0328a0f70530d8ade0d2151bfc (diff) | |
parent | 536dea9d61a032e64bbe584a97463c6638ead009 (diff) | |
download | system_core-66ed50af6870210ce013a5588a688434a5d48ee9.zip system_core-66ed50af6870210ce013a5588a688434a5d48ee9.tar.gz system_core-66ed50af6870210ce013a5588a688434a5d48ee9.tar.bz2 |
Merge commit '536dea9d61a032e64bbe584a97463c6638ead009' into HEAD
Change-Id: I5c469a4b738629d99d721cad7ded02d6c35f56d5
Diffstat (limited to 'include/utils/BitSet.h')
-rw-r--r-- | include/utils/BitSet.h | 124 |
1 files changed, 124 insertions, 0 deletions
diff --git a/include/utils/BitSet.h b/include/utils/BitSet.h new file mode 100644 index 0000000..19c03d1 --- /dev/null +++ b/include/utils/BitSet.h @@ -0,0 +1,124 @@ +/* + * Copyright (C) 2010 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef UTILS_BITSET_H +#define UTILS_BITSET_H + +#include <stdint.h> +#include <utils/TypeHelpers.h> + +/* + * Contains some bit manipulation helpers. + */ + +namespace android { + +// A simple set of 32 bits that can be individually marked or cleared. +struct BitSet32 { + uint32_t value; + + inline BitSet32() : value(0) { } + explicit inline BitSet32(uint32_t value) : value(value) { } + + // Gets the value associated with a particular bit index. + static inline uint32_t valueForBit(uint32_t n) { return 0x80000000 >> n; } + + // Clears the bit set. + inline void clear() { value = 0; } + + // Returns the number of marked bits in the set. + inline uint32_t count() const { return __builtin_popcount(value); } + + // Returns true if the bit set does not contain any marked bits. + inline bool isEmpty() const { return ! value; } + + // Returns true if the bit set does not contain any unmarked bits. + inline bool isFull() const { return value == 0xffffffff; } + + // Returns true if the specified bit is marked. + inline bool hasBit(uint32_t n) const { return value & valueForBit(n); } + + // Marks the specified bit. + inline void markBit(uint32_t n) { value |= valueForBit(n); } + + // Clears the specified bit. + inline void clearBit(uint32_t n) { value &= ~ valueForBit(n); } + + // Finds the first marked bit in the set. + // Result is undefined if all bits are unmarked. + inline uint32_t firstMarkedBit() const { return __builtin_clz(value); } + + // Finds the first unmarked bit in the set. + // Result is undefined if all bits are marked. + inline uint32_t firstUnmarkedBit() const { return __builtin_clz(~ value); } + + // Finds the last marked bit in the set. + // Result is undefined if all bits are unmarked. + inline uint32_t lastMarkedBit() const { return 31 - __builtin_ctz(value); } + + // Finds the first marked bit in the set and clears it. Returns the bit index. + // Result is undefined if all bits are unmarked. + inline uint32_t clearFirstMarkedBit() { + uint32_t n = firstMarkedBit(); + clearBit(n); + return n; + } + + // Finds the first unmarked bit in the set and marks it. Returns the bit index. + // Result is undefined if all bits are marked. + inline uint32_t markFirstUnmarkedBit() { + uint32_t n = firstUnmarkedBit(); + markBit(n); + return n; + } + + // Finds the last marked bit in the set and clears it. Returns the bit index. + // Result is undefined if all bits are unmarked. + inline uint32_t clearLastMarkedBit() { + uint32_t n = lastMarkedBit(); + clearBit(n); + return n; + } + + // Gets the index of the specified bit in the set, which is the number of + // marked bits that appear before the specified bit. + inline uint32_t getIndexOfBit(uint32_t n) const { + return __builtin_popcount(value & ~(0xffffffffUL >> n)); + } + + inline bool operator== (const BitSet32& other) const { return value == other.value; } + inline bool operator!= (const BitSet32& other) const { return value != other.value; } + inline BitSet32 operator& (const BitSet32& other) const { + return BitSet32(value & other.value); + } + inline BitSet32& operator&= (const BitSet32& other) { + value &= other.value; + return *this; + } + inline BitSet32 operator| (const BitSet32& other) const { + return BitSet32(value | other.value); + } + inline BitSet32& operator|= (const BitSet32& other) { + value |= other.value; + return *this; + } +}; + +ANDROID_BASIC_TYPES_TRAITS(BitSet32) + +} // namespace android + +#endif // UTILS_BITSET_H |