1 /*
2 * Copyright (c) Facebook, Inc. and its affiliates.
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 <algorithm>
20 #include <cassert>
21 #include <cstdint>
22 #include <cstring>
23 #include <functional>
24 #include <iterator>
25 #include <limits>
26 #include <type_traits>
27
28 #include <boost/iterator/iterator_adaptor.hpp>
29
30 #include <folly/Portability.h>
31 #include <folly/Traits.h>
32 #include <folly/functional/Invoke.h>
33
34 /**
35 * Code that aids in storing data aligned on block (possibly cache-line)
36 * boundaries, perhaps with padding.
37 *
38 * Class Node represents one block. Given an iterator to a container of
39 * Node, class Iterator encapsulates an iterator to the underlying elements.
40 * Adaptor converts a sequence of Node into a sequence of underlying elements
41 * (not fully compatible with STL container requirements, see comments
42 * near the Node class declaration).
43 */
44
45 namespace folly {
46 namespace padded {
47
48 /**
49 * A Node is a fixed-size container of as many objects of type T as would
50 * fit in a region of memory of size NS. The last NS % sizeof(T)
51 * bytes are ignored and uninitialized.
52 *
53 * Node only works for trivial types, which is usually not a concern. This
54 * is intentional: Node itself is trivial, which means that it can be
55 * serialized / deserialized using a simple memcpy.
56 */
57 template <class T, size_t NS>
58 class Node {
59 static_assert(
60 std::is_trivial_v<T> && sizeof(T) <= NS && NS % alignof(T) == 0);
61
62 public:
63 typedef T value_type;
64 static constexpr size_t kNodeSize = NS;
65 static constexpr size_t kElementCount = NS / sizeof(T);
66 static constexpr size_t kPaddingBytes = NS % sizeof(T);
67
data()68 T* data() { return storage_.data; }
data()69 const T* data() const { return storage_.data; }
70
71 bool operator==(const Node& other) const {
72 return memcmp(data(), other.data(), sizeof(T) * kElementCount) == 0;
73 }
74 bool operator!=(const Node& other) const { return !(*this == other); }
75
76 /**
77 * Return the number of nodes needed to represent n values. Rounds up.
78 */
nodeCount(size_t n)79 static constexpr size_t nodeCount(size_t n) {
80 return (n + kElementCount - 1) / kElementCount;
81 }
82
83 /**
84 * Return the total byte size needed to represent n values, rounded up
85 * to the nearest full node.
86 */
paddedByteSize(size_t n)87 static constexpr size_t paddedByteSize(size_t n) { return nodeCount(n) * NS; }
88
89 /**
90 * Return the number of bytes used for padding n values.
91 * Note that, even if n is a multiple of kElementCount, this may
92 * return non-zero if kPaddingBytes != 0, as the padding at the end of
93 * the last node is not included in the result.
94 */
paddingBytes(size_t n)95 static constexpr size_t paddingBytes(size_t n) {
96 return (
97 n ? (kPaddingBytes +
98 (kElementCount - 1 - (n - 1) % kElementCount) * sizeof(T))
99 : 0);
100 }
101
102 /**
103 * Return the minimum byte size needed to represent n values.
104 * Does not round up. Even if n is a multiple of kElementCount, this
105 * may be different from paddedByteSize() if kPaddingBytes != 0, as
106 * the padding at the end of the last node is not included in the result.
107 * Note that the calculation below works for n=0 correctly (returns 0).
108 */
unpaddedByteSize(size_t n)109 static constexpr size_t unpaddedByteSize(size_t n) {
110 return paddedByteSize(n) - paddingBytes(n);
111 }
112
113 private:
114 union Storage {
115 unsigned char bytes[NS];
116 T data[kElementCount];
117 } storage_;
118 };
119
120 // We must define kElementCount and kPaddingBytes to work around a bug
121 // in gtest that odr-uses them.
122 template <class T, size_t NS>
123 constexpr size_t Node<T, NS>::kNodeSize;
124 template <class T, size_t NS>
125 constexpr size_t Node<T, NS>::kElementCount;
126 template <class T, size_t NS>
127 constexpr size_t Node<T, NS>::kPaddingBytes;
128
129 template <class Iter>
130 class Iterator;
131
132 namespace detail {
133
134 FOLLY_CREATE_MEMBER_INVOKER(emplace_back, emplace_back);
135
136 // Helper class template to define a base class for Iterator (below) and save
137 // typing.
138 template <
139 template <class>
140 class Class,
141 class Iter,
142 class Traits = std::iterator_traits<Iter>,
143 class Ref = typename Traits::reference,
144 class Val = typename Traits::value_type::value_type>
145 using IteratorBase = boost::iterator_adaptor<
146 Class<Iter>, // CRTC
147 Iter, // Base iterator type
148 Val, // Value type
149 boost::use_default, // Category or traversal
150 like_t<Ref, Val>>; // Reference type
151
152 } // namespace detail
153
154 /**
155 * Wrapper around iterators to Node to return iterators to the underlying
156 * node elements.
157 */
158 template <class Iter>
159 class Iterator : public detail::IteratorBase<Iterator, Iter> {
160 using Super = detail::IteratorBase<Iterator, Iter>;
161
162 public:
163 using Node = typename std::iterator_traits<Iter>::value_type;
164
Iterator()165 Iterator() : pos_(0) {}
166
Iterator(Iter base)167 explicit Iterator(Iter base) : Super(base), pos_(0) {}
168
169 // Return the current node and the position inside the node
node()170 const Node& node() const { return *this->base_reference(); }
pos()171 size_t pos() const { return pos_; }
172
173 private:
dereference()174 typename Super::reference dereference() const {
175 return (*this->base_reference()).data()[pos_];
176 }
177
equal(const Iterator & other)178 bool equal(const Iterator& other) const {
179 return (
180 this->base_reference() == other.base_reference() && pos_ == other.pos_);
181 }
182
advance(typename Super::difference_type n)183 void advance(typename Super::difference_type n) {
184 constexpr ssize_t elementCount = Node::kElementCount; // signed!
185 ssize_t newPos = pos_ + n;
186 if (newPos >= 0 && newPos < elementCount) {
187 pos_ = newPos;
188 return;
189 }
190 ssize_t nblocks = newPos / elementCount;
191 newPos %= elementCount;
192 if (newPos < 0) {
193 --nblocks; // negative
194 newPos += elementCount;
195 }
196 this->base_reference() += nblocks;
197 pos_ = newPos;
198 }
199
increment()200 void increment() {
201 if (++pos_ == Node::kElementCount) {
202 ++this->base_reference();
203 pos_ = 0;
204 }
205 }
206
decrement()207 void decrement() {
208 if (--pos_ == -1) {
209 --this->base_reference();
210 pos_ = Node::kElementCount - 1;
211 }
212 }
213
distance_to(const Iterator & other)214 typename Super::difference_type distance_to(const Iterator& other) const {
215 constexpr ssize_t elementCount = Node::kElementCount; // signed!
216 ssize_t nblocks =
217 std::distance(this->base_reference(), other.base_reference());
218 return nblocks * elementCount + (other.pos_ - pos_);
219 }
220
221 friend class boost::iterator_core_access;
222 ssize_t pos_; // signed for easier advance() implementation
223 };
224
225 /**
226 * Given a container to Node, return iterators to the first element in
227 * the first Node / one past the last element in the last Node.
228 * Note that the last node is assumed to be full; if that's not the case,
229 * subtract from end() as appropriate.
230 */
231
232 template <class Container>
cbegin(const Container & c)233 Iterator<typename Container::const_iterator> cbegin(const Container& c) {
234 return Iterator<typename Container::const_iterator>(std::begin(c));
235 }
236
237 template <class Container>
cend(const Container & c)238 Iterator<typename Container::const_iterator> cend(const Container& c) {
239 return Iterator<typename Container::const_iterator>(std::end(c));
240 }
241
242 template <class Container>
begin(const Container & c)243 Iterator<typename Container::const_iterator> begin(const Container& c) {
244 return cbegin(c);
245 }
246
247 template <class Container>
end(const Container & c)248 Iterator<typename Container::const_iterator> end(const Container& c) {
249 return cend(c);
250 }
251
252 template <class Container>
begin(Container & c)253 Iterator<typename Container::iterator> begin(Container& c) {
254 return Iterator<typename Container::iterator>(std::begin(c));
255 }
256
257 template <class Container>
end(Container & c)258 Iterator<typename Container::iterator> end(Container& c) {
259 return Iterator<typename Container::iterator>(std::end(c));
260 }
261
262 /**
263 * Adaptor around a STL sequence container.
264 *
265 * Converts a sequence of Node into a sequence of its underlying elements
266 * (with enough functionality to make it useful, although it's not fully
267 * compatible with the STL container requirements, see below).
268 *
269 * Provides iterators (of the same category as those of the underlying
270 * container), size(), front(), back(), push_back(), pop_back(), and const /
271 * non-const versions of operator[] (if the underlying container supports
272 * them). Does not provide push_front() / pop_front() or arbitrary insert /
273 * emplace / erase. Also provides reserve() / capacity() if supported by the
274 * underlying container.
275 *
276 * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL
277 * and by boost. Deal with it.
278 *
279 * Internally, we hold a container of Node and the number of elements in
280 * the last block. We don't keep empty blocks, so the number of elements in
281 * the last block is always between 1 and Node::kElementCount (inclusive).
282 * (this is true if the container is empty as well to make push_back() simpler,
283 * see the implementation of the size() method for details).
284 */
285 template <class Container>
286 class Adaptor {
287 public:
288 typedef typename Container::value_type Node;
289 typedef typename Node::value_type value_type;
290 typedef value_type& reference;
291 typedef const value_type& const_reference;
292 typedef Iterator<typename Container::iterator> iterator;
293 typedef Iterator<typename Container::const_iterator> const_iterator;
294 typedef typename const_iterator::difference_type difference_type;
295 typedef typename Container::size_type size_type;
296
297 static constexpr size_t kElementsPerNode = Node::kElementCount;
298 // Constructors
Adaptor()299 Adaptor() : lastCount_(Node::kElementCount) {}
300 explicit Adaptor(Container c, size_t lastCount = Node::kElementCount)
c_(std::move (c))301 : c_(std::move(c)), lastCount_(lastCount) {}
302 explicit Adaptor(size_t n, const value_type& value = value_type())
c_(Node::nodeCount (n),fullNode (value))303 : c_(Node::nodeCount(n), fullNode(value)) {
304 const auto count = n % Node::kElementCount;
305 lastCount_ = count != 0 ? count : Node::kElementCount;
306 }
307
308 Adaptor(const Adaptor&) = default;
309 Adaptor& operator=(const Adaptor&) = default;
Adaptor(Adaptor && other)310 Adaptor(Adaptor&& other) noexcept
311 : c_(std::move(other.c_)), lastCount_(other.lastCount_) {
312 other.lastCount_ = Node::kElementCount;
313 }
314 Adaptor& operator=(Adaptor&& other) {
315 if (this != &other) {
316 c_ = std::move(other.c_);
317 lastCount_ = other.lastCount_;
318 other.lastCount_ = Node::kElementCount;
319 }
320 return *this;
321 }
322
323 // Iterators
cbegin()324 const_iterator cbegin() const { return const_iterator(c_.begin()); }
cend()325 const_iterator cend() const {
326 auto it = const_iterator(c_.end());
327 if (lastCount_ != Node::kElementCount) {
328 it -= (Node::kElementCount - lastCount_);
329 }
330 return it;
331 }
begin()332 const_iterator begin() const { return cbegin(); }
end()333 const_iterator end() const { return cend(); }
begin()334 iterator begin() { return iterator(c_.begin()); }
end()335 iterator end() {
336 auto it = iterator(c_.end());
337 if (lastCount_ != Node::kElementCount) {
338 it -= difference_type(Node::kElementCount - lastCount_);
339 }
340 return it;
341 }
swap(Adaptor & other)342 void swap(Adaptor& other) {
343 using std::swap;
344 swap(c_, other.c_);
345 swap(lastCount_, other.lastCount_);
346 }
empty()347 bool empty() const { return c_.empty(); }
size()348 size_type size() const {
349 return (
350 c_.empty() ? 0 : (c_.size() - 1) * Node::kElementCount + lastCount_);
351 }
max_size()352 size_type max_size() const {
353 return (
354 (c_.max_size() <=
355 std::numeric_limits<size_type>::max() / Node::kElementCount)
356 ? c_.max_size() * Node::kElementCount
357 : std::numeric_limits<size_type>::max());
358 }
359
front()360 const value_type& front() const {
361 assert(!empty());
362 return c_.front().data()[0];
363 }
front()364 value_type& front() {
365 assert(!empty());
366 return c_.front().data()[0];
367 }
368
back()369 const value_type& back() const {
370 assert(!empty());
371 return c_.back().data()[lastCount_ - 1];
372 }
back()373 value_type& back() {
374 assert(!empty());
375 return c_.back().data()[lastCount_ - 1];
376 }
377
378 template <typename... Args>
emplace_back(Args &&...args)379 void emplace_back(Args&&... args) {
380 new (allocate_back()) value_type(std::forward<Args>(args)...);
381 }
382
push_back(value_type x)383 void push_back(value_type x) { emplace_back(std::move(x)); }
384
pop_back()385 void pop_back() {
386 assert(!empty());
387 if (--lastCount_ == 0) {
388 c_.pop_back();
389 lastCount_ = Node::kElementCount;
390 }
391 }
392
clear()393 void clear() {
394 c_.clear();
395 lastCount_ = Node::kElementCount;
396 }
397
reserve(size_type n)398 void reserve(size_type n) {
399 assert(n >= 0);
400 c_.reserve(Node::nodeCount(n));
401 }
402
capacity()403 size_type capacity() const { return c_.capacity() * Node::kElementCount; }
404
405 const value_type& operator[](size_type idx) const {
406 return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
407 }
408 value_type& operator[](size_type idx) {
409 return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
410 }
411
412 /**
413 * Return the underlying container and number of elements in the last block,
414 * and clear *this. Useful when you want to process the data as Nodes
415 * (again) and want to avoid copies.
416 */
move()417 std::pair<Container, size_t> move() {
418 std::pair<Container, size_t> p(std::move(c_), lastCount_);
419 lastCount_ = Node::kElementCount;
420 return p;
421 }
422
423 /**
424 * Return a const reference to the underlying container and the current
425 * number of elements in the last block.
426 */
peek()427 std::pair<const Container&, size_t> peek() const {
428 return std::make_pair(std::cref(c_), lastCount_);
429 }
430
padToFullNode(const value_type & padValue)431 void padToFullNode(const value_type& padValue) {
432 // the if is necessary because c_ may be empty so we can't call c_.back()
433 if (lastCount_ != Node::kElementCount) {
434 auto last = c_.back().data();
435 std::fill(last + lastCount_, last + Node::kElementCount, padValue);
436 lastCount_ = Node::kElementCount;
437 }
438 }
439
440 private:
allocate_back()441 value_type* allocate_back() {
442 if (lastCount_ == Node::kElementCount) {
443 if constexpr (is_invocable_v<detail::emplace_back, Container&>) {
444 c_.emplace_back();
445 } else {
446 c_.push_back(typename Container::value_type());
447 }
448 lastCount_ = 0;
449 }
450 return &c_.back().data()[lastCount_++];
451 }
452
fullNode(const value_type & value)453 static Node fullNode(const value_type& value) {
454 Node n;
455 std::fill(n.data(), n.data() + kElementsPerNode, value);
456 return n;
457 }
458 Container c_; // container of Nodes
459 size_t lastCount_; // number of elements in last Node
460 };
461
462 } // namespace padded
463 } // namespace folly
464