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 "bit_utils.h"
27 #include "iteration_range.h"
28 #include "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