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