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