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