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
49namespace folly {
50namespace 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 */
71template <class D, class V, class Tag>
72class 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 */
156template <class D, class I, class V, class Tag>
157class 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