1 | /* |
2 | * Copyright 2014-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 <cstddef> |
20 | #include <iterator> |
21 | #include <type_traits> |
22 | |
23 | /* |
24 | * This contains stripped-down workalikes of some Boost classes: |
25 | * |
26 | * iterator_adaptor |
27 | * iterator_facade |
28 | * |
29 | * Rationale: the boost headers providing those classes are surprisingly large. |
30 | * The bloat comes from the headers themselves, but more so, their transitive |
31 | * includes. |
32 | * |
33 | * These implementations are simple and minimal. They may be missing features |
34 | * provided by the Boost classes mentioned above. Also at this time they only |
35 | * support forward-iterators. They provide just enough for the few uses within |
36 | * Folly libs; more features will be slapped in here if and when they're needed. |
37 | * |
38 | * These classes may possibly add features as well. Care is taken not to |
39 | * change functionality where it's expected to be the same (e.g. `dereference` |
40 | * will do the same thing). |
41 | * |
42 | * These are currently only intended for use within Folly, hence their living |
43 | * under detail. Use outside Folly is not recommended. |
44 | * |
45 | * To see how to use these classes, find the instances where this is used within |
46 | * Folly libs. Common use cases can also be found in `IteratorsTest.cpp`. |
47 | */ |
48 | |
49 | namespace folly { |
50 | namespace detail { |
51 | |
52 | /** |
53 | * Currently this only supports forward and bidirectional iteration. The |
54 | * derived class must must have definitions for these methods: |
55 | * |
56 | * void increment(); |
57 | * void decrement(); // optional, to be used with bidirectional |
58 | * reference dereference() const; |
59 | * bool equal([appropriate iterator type] const& rhs) const; |
60 | * |
61 | * These names are consistent with those used by the Boost iterator |
62 | * facade / adaptor classes to ease migration classes in this file. |
63 | * |
64 | * Template parameters: |
65 | * D: the deriving class (CRTP) |
66 | * V: value type |
67 | * Tag: the iterator category, one of: |
68 | * std::forward_iterator_tag |
69 | * std::bidirectional_iterator_tag |
70 | */ |
71 | template <class D, class V, class Tag> |
72 | class IteratorFacade { |
73 | public: |
74 | using value_type = V; |
75 | using reference = value_type&; |
76 | using pointer = value_type*; |
77 | using difference_type = ssize_t; |
78 | using iterator_category = Tag; |
79 | |
80 | bool operator==(D const& rhs) const { |
81 | return asDerivedConst().equal(rhs); |
82 | } |
83 | |
84 | bool operator!=(D const& rhs) const { |
85 | return !operator==(rhs); |
86 | } |
87 | |
88 | /* |
89 | * Allow for comparisons between this and an iterator of some other class. |
90 | * (e.g. a const_iterator version of this, the probable use case). |
91 | * Does a conversion of D (or D reference) to D2, if one exists (otherwise |
92 | * this is disabled). Disabled if D and D2 are the same, to disambiguate |
93 | * this and the `operator==(D const&) const` method above. |
94 | */ |
95 | |
96 | template <class D2> |
97 | typename std::enable_if<std::is_convertible<D, D2>::value, bool>::type |
98 | operator==(D2 const& rhs) const { |
99 | return D2(asDerivedConst()) == rhs; |
100 | } |
101 | |
102 | template <class D2> |
103 | bool operator!=(D2 const& rhs) const { |
104 | return !operator==(rhs); |
105 | } |
106 | |
107 | V& operator*() const { |
108 | return asDerivedConst().dereference(); |
109 | } |
110 | |
111 | V* operator->() const { |
112 | return std::addressof(operator*()); |
113 | } |
114 | |
115 | D& operator++() { |
116 | asDerived().increment(); |
117 | return asDerived(); |
118 | } |
119 | |
120 | D operator++(int) { |
121 | auto ret = asDerived(); // copy |
122 | asDerived().increment(); |
123 | return ret; |
124 | } |
125 | |
126 | D& operator--() { |
127 | asDerived().decrement(); |
128 | return asDerived(); |
129 | } |
130 | |
131 | D operator--(int) { |
132 | auto ret = asDerived(); // copy |
133 | asDerived().decrement(); |
134 | return ret; |
135 | } |
136 | |
137 | private: |
138 | D& asDerived() { |
139 | return static_cast<D&>(*this); |
140 | } |
141 | |
142 | D const& asDerivedConst() const { |
143 | return static_cast<D const&>(*this); |
144 | } |
145 | }; |
146 | |
147 | /** |
148 | * Wrap one iterator while providing an interator interface with e.g. a |
149 | * different value_type. |
150 | * |
151 | * Template parameters: |
152 | * D: the deriving class (CRTP) |
153 | * I: the wrapper iterator type |
154 | * V: value type |
155 | */ |
156 | template <class D, class I, class V, class Tag> |
157 | class IteratorAdaptor : public IteratorFacade<D, V, Tag> { |
158 | public: |
159 | using Super = IteratorFacade<D, V, Tag>; |
160 | using value_type = typename Super::value_type; |
161 | using iterator_category = typename Super::iterator_category; |
162 | using reference = typename Super::reference; |
163 | using pointer = typename Super::pointer; |
164 | using difference_type = typename Super::difference_type; |
165 | |
166 | explicit IteratorAdaptor(I base) : base_(base) {} |
167 | |
168 | void increment() { |
169 | ++base_; |
170 | } |
171 | |
172 | void decrement() { |
173 | --base_; |
174 | } |
175 | |
176 | V& dereference() const { |
177 | return *base_; |
178 | } |
179 | |
180 | bool equal(D const& rhs) const { |
181 | return base_ == rhs.base_; |
182 | } |
183 | |
184 | I const& base() const { |
185 | return base_; |
186 | } |
187 | I& base() { |
188 | return base_; |
189 | } |
190 | |
191 | private: |
192 | I base_; |
193 | }; |
194 | |
195 | } // namespace detail |
196 | } // namespace folly |
197 | |