1 | /* |
2 | * Copyright 2011-present Facebook, Inc. |
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 | /** |
18 | * BitIterator |
19 | * Wrapper around an iterator over an integral type that iterates |
20 | * over its underlying bits in MSb to LSb order |
21 | * |
22 | * findFirstSet(BitIterator begin, BitIterator end) |
23 | * return a BitIterator pointing to the first 1 bit in [begin, end), or |
24 | * end if all bits in [begin, end) are 0 |
25 | * |
26 | * @author Tudor Bosman (tudorb@fb.com) |
27 | */ |
28 | |
29 | #pragma once |
30 | |
31 | #include <cassert> |
32 | #include <cinttypes> |
33 | #include <cstdint> |
34 | #include <cstring> |
35 | #include <iterator> |
36 | #include <limits> |
37 | #include <type_traits> |
38 | |
39 | #include <boost/iterator/iterator_adaptor.hpp> |
40 | |
41 | #include <folly/Portability.h> |
42 | #include <folly/container/detail/BitIteratorDetail.h> |
43 | #include <folly/lang/Bits.h> |
44 | |
45 | namespace folly { |
46 | |
47 | /** |
48 | * Fast bit iteration facility. |
49 | */ |
50 | |
51 | template <class BaseIter> |
52 | class BitIterator; |
53 | template <class BaseIter> |
54 | BitIterator<BaseIter> findFirstSet( |
55 | BitIterator<BaseIter>, |
56 | BitIterator<BaseIter>); |
57 | /** |
58 | * Wrapper around an iterator over an integer type that iterates |
59 | * over its underlying bits in LSb to MSb order. |
60 | * |
61 | * BitIterator models the same iterator concepts as the base iterator. |
62 | */ |
63 | template <class BaseIter> |
64 | class BitIterator : public bititerator_detail::BitIteratorBase<BaseIter>::type { |
65 | public: |
66 | /** |
67 | * Return the number of bits in an element of the underlying iterator. |
68 | */ |
69 | static unsigned int bitsPerBlock() { |
70 | return std::numeric_limits<typename std::make_unsigned< |
71 | typename std::iterator_traits<BaseIter>::value_type>::type>::digits; |
72 | } |
73 | |
74 | /** |
75 | * Construct a BitIterator that points at a given bit offset (default 0) |
76 | * in iter. |
77 | */ |
78 | explicit BitIterator(const BaseIter& iter, size_t bitOff = 0) |
79 | : bititerator_detail::BitIteratorBase<BaseIter>::type(iter), |
80 | bitOffset_(bitOff) { |
81 | assert(bitOffset_ < bitsPerBlock()); |
82 | } |
83 | |
84 | size_t bitOffset() const { |
85 | return bitOffset_; |
86 | } |
87 | |
88 | void advanceToNextBlock() { |
89 | bitOffset_ = 0; |
90 | ++this->base_reference(); |
91 | } |
92 | |
93 | BitIterator& operator=(const BaseIter& other) { |
94 | this->~BitIterator(); |
95 | new (this) BitIterator(other); |
96 | return *this; |
97 | } |
98 | |
99 | private: |
100 | friend class boost::iterator_core_access; |
101 | friend BitIterator findFirstSet<>(BitIterator, BitIterator); |
102 | |
103 | typedef bititerator_detail::BitReference< |
104 | typename std::iterator_traits<BaseIter>::reference, |
105 | typename std::iterator_traits<BaseIter>::value_type> |
106 | BitRef; |
107 | |
108 | void advanceInBlock(size_t n) { |
109 | bitOffset_ += n; |
110 | assert(bitOffset_ < bitsPerBlock()); |
111 | } |
112 | |
113 | BitRef dereference() const { |
114 | return BitRef(*this->base_reference(), bitOffset_); |
115 | } |
116 | |
117 | void advance(ssize_t n) { |
118 | size_t bpb = bitsPerBlock(); |
119 | ssize_t blocks = n / ssize_t(bpb); |
120 | bitOffset_ += n % bpb; |
121 | if (bitOffset_ >= bpb) { |
122 | bitOffset_ -= bpb; |
123 | ++blocks; |
124 | } |
125 | this->base_reference() += blocks; |
126 | } |
127 | |
128 | void increment() { |
129 | if (++bitOffset_ == bitsPerBlock()) { |
130 | advanceToNextBlock(); |
131 | } |
132 | } |
133 | |
134 | void decrement() { |
135 | if (bitOffset_-- == 0) { |
136 | bitOffset_ = bitsPerBlock() - 1; |
137 | --this->base_reference(); |
138 | } |
139 | } |
140 | |
141 | bool equal(const BitIterator& other) const { |
142 | return ( |
143 | bitOffset_ == other.bitOffset_ && |
144 | this->base_reference() == other.base_reference()); |
145 | } |
146 | |
147 | ssize_t distance_to(const BitIterator& other) const { |
148 | return ssize_t( |
149 | (other.base_reference() - this->base_reference()) * bitsPerBlock() + |
150 | other.bitOffset_ - bitOffset_); |
151 | } |
152 | |
153 | size_t bitOffset_; |
154 | }; |
155 | |
156 | /** |
157 | * Helper function, so you can write |
158 | * auto bi = makeBitIterator(container.begin()); |
159 | */ |
160 | template <class BaseIter> |
161 | BitIterator<BaseIter> makeBitIterator(const BaseIter& iter) { |
162 | return BitIterator<BaseIter>(iter); |
163 | } |
164 | |
165 | /** |
166 | * Find first bit set in a range of bit iterators. |
167 | * 4.5x faster than the obvious std::find(begin, end, true); |
168 | */ |
169 | template <class BaseIter> |
170 | BitIterator<BaseIter> findFirstSet( |
171 | BitIterator<BaseIter> begin, |
172 | BitIterator<BaseIter> end) { |
173 | // shortcut to avoid ugly static_cast<> |
174 | static const typename std::iterator_traits<BaseIter>::value_type one = 1; |
175 | |
176 | while (begin.base() != end.base()) { |
177 | typename std::iterator_traits<BaseIter>::value_type v = *begin.base(); |
178 | // mask out the bits that don't matter (< begin.bitOffset) |
179 | v &= ~((one << begin.bitOffset()) - 1); |
180 | size_t firstSet = findFirstSet(v); |
181 | if (firstSet) { |
182 | --firstSet; // now it's 0-based |
183 | assert(firstSet >= begin.bitOffset()); |
184 | begin.advanceInBlock(firstSet - begin.bitOffset()); |
185 | return begin; |
186 | } |
187 | begin.advanceToNextBlock(); |
188 | } |
189 | |
190 | // now begin points to the same block as end |
191 | if (end.bitOffset() != 0) { // assume end is dereferenceable |
192 | typename std::iterator_traits<BaseIter>::value_type v = *begin.base(); |
193 | // mask out the bits that don't matter (< begin.bitOffset) |
194 | v &= ~((one << begin.bitOffset()) - 1); |
195 | // mask out the bits that don't matter (>= end.bitOffset) |
196 | v &= (one << end.bitOffset()) - 1; |
197 | size_t firstSet = findFirstSet(v); |
198 | if (firstSet) { |
199 | --firstSet; // now it's 0-based |
200 | assert(firstSet >= begin.bitOffset()); |
201 | begin.advanceInBlock(firstSet - begin.bitOffset()); |
202 | return begin; |
203 | } |
204 | } |
205 | |
206 | return end; |
207 | } |
208 | |
209 | } // namespace folly |
210 | |