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 | #pragma once |
18 | |
19 | #include <iterator> |
20 | #include <type_traits> |
21 | |
22 | #include <boost/iterator/iterator_adaptor.hpp> |
23 | |
24 | namespace folly { |
25 | |
26 | template <class BaseIter> |
27 | class BitIterator; |
28 | |
29 | namespace bititerator_detail { |
30 | |
31 | // Reference to a bit. |
32 | // Templatize on both parent reference and value types to capture |
33 | // const-ness correctly and to work with the case where Ref is a |
34 | // reference-like type (not T&), just like our BitReference here. |
35 | template <class Ref, class Value> |
36 | class BitReference { |
37 | public: |
38 | BitReference(Ref r, size_t bit) : ref_(r), bit_(bit) {} |
39 | |
40 | /* implicit */ operator bool() const { |
41 | return ref_ & (one_ << bit_); |
42 | } |
43 | |
44 | BitReference& operator=(bool b) { |
45 | if (b) { |
46 | set(); |
47 | } else { |
48 | clear(); |
49 | } |
50 | return *this; |
51 | } |
52 | |
53 | void set() { |
54 | ref_ |= (one_ << bit_); |
55 | } |
56 | |
57 | void clear() { |
58 | ref_ &= ~(one_ << bit_); |
59 | } |
60 | |
61 | void flip() { |
62 | ref_ ^= (one_ << bit_); |
63 | } |
64 | |
65 | private: |
66 | // shortcut to avoid writing static_cast everywhere |
67 | const static Value one_ = 1; |
68 | |
69 | Ref ref_; |
70 | size_t bit_; |
71 | }; |
72 | |
73 | template <class BaseIter> |
74 | struct BitIteratorBase { |
75 | static_assert( |
76 | std::is_integral< |
77 | typename std::iterator_traits<BaseIter>::value_type>::value, |
78 | "BitIterator may only be used with integral types" ); |
79 | typedef boost::iterator_adaptor< |
80 | BitIterator<BaseIter>, // Derived |
81 | BaseIter, // Base |
82 | bool, // Value |
83 | boost::use_default, // CategoryOrTraversal |
84 | bititerator_detail::BitReference< |
85 | typename std::iterator_traits<BaseIter>::reference, |
86 | typename std::iterator_traits<BaseIter>::value_type>, // Reference |
87 | ssize_t> |
88 | type; |
89 | }; |
90 | |
91 | } // namespace bititerator_detail |
92 | } // namespace folly |
93 | |