1 /* 2 * Copyright (C) 2015 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 ART_LIBARTBASE_BASE_BIT_UTILS_ITERATOR_H_ 18 #define ART_LIBARTBASE_BASE_BIT_UTILS_ITERATOR_H_ 19 20 #include <iterator> 21 #include <limits> 22 #include <type_traits> 23 24 #include <android-base/logging.h> 25 26 #include "base/bit_utils.h" 27 #include "base/iteration_range.h" 28 #include "base/stl_util.h" 29 30 namespace art { 31 32 // Using the Curiously Recurring Template Pattern to implement everything shared 33 // by LowToHighBitIterator and HighToLowBitIterator, i.e. everything but operator*(). 34 template <typename T, typename Iter> 35 class BitIteratorBase 36 : public std::iterator<std::forward_iterator_tag, uint32_t, ptrdiff_t, void, void> { 37 static_assert(std::is_integral<T>::value, "T must be integral"); 38 static_assert(std::is_unsigned<T>::value, "T must be unsigned"); 39 40 static_assert(sizeof(T) == sizeof(uint32_t) || sizeof(T) == sizeof(uint64_t), "Unsupported size"); 41 42 public: 43 BitIteratorBase() : bits_(0u) { } 44 explicit BitIteratorBase(T bits) : bits_(bits) { } 45 46 Iter& operator++() { 47 DCHECK_NE(bits_, 0u); 48 uint32_t bit = *static_cast<Iter&>(*this); 49 bits_ &= ~(static_cast<T>(1u) << bit); 50 return static_cast<Iter&>(*this); 51 } 52 53 Iter& operator++(int) { 54 Iter tmp(static_cast<Iter&>(*this)); 55 ++*this; 56 return tmp; 57 } 58 59 protected: 60 T bits_; 61 62 template <typename U, typename I> 63 friend bool operator==(const BitIteratorBase<U, I>& lhs, const BitIteratorBase<U, I>& rhs); 64 }; 65 66 template <typename T, typename Iter> 67 bool operator==(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 68 return lhs.bits_ == rhs.bits_; 69 } 70 71 template <typename T, typename Iter> 72 bool operator!=(const BitIteratorBase<T, Iter>& lhs, const BitIteratorBase<T, Iter>& rhs) { 73 return !(lhs == rhs); 74 } 75 76 template <typename T> 77 class LowToHighBitIterator : public BitIteratorBase<T, LowToHighBitIterator<T>> { 78 public: 79 using BitIteratorBase<T, LowToHighBitIterator<T>>::BitIteratorBase; 80 81 uint32_t operator*() const { 82 DCHECK_NE(this->bits_, 0u); 83 return CTZ(this->bits_); 84 } 85 }; 86 87 template <typename T> 88 class HighToLowBitIterator : public BitIteratorBase<T, HighToLowBitIterator<T>> { 89 public: 90 using BitIteratorBase<T, HighToLowBitIterator<T>>::BitIteratorBase; 91 92 uint32_t operator*() const { 93 DCHECK_NE(this->bits_, 0u); 94 static_assert(std::numeric_limits<T>::radix == 2, "Unexpected radix!"); 95 return std::numeric_limits<T>::digits - 1u - CLZ(this->bits_); 96 } 97 }; 98 99 template <typename T> 100 IterationRange<LowToHighBitIterator<T>> LowToHighBits(T bits) { 101 return IterationRange<LowToHighBitIterator<T>>( 102 LowToHighBitIterator<T>(bits), LowToHighBitIterator<T>()); 103 } 104 105 template <typename T> 106 IterationRange<HighToLowBitIterator<T>> HighToLowBits(T bits) { 107 return IterationRange<HighToLowBitIterator<T>>( 108 HighToLowBitIterator<T>(bits), HighToLowBitIterator<T>()); 109 } 110 111 } // namespace art 112 113 #endif // ART_LIBARTBASE_BASE_BIT_UTILS_ITERATOR_H_ 114
