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 | |
44 | namespace folly { |
45 | namespace 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 | */ |
56 | template <class T, size_t NS, class Enable = void> |
57 | class Node; |
58 | |
59 | namespace detail { |
60 | // Shortcut to avoid writing the long enable_if expression every time |
61 | template <class T, size_t NS, class Enable = void> |
62 | struct NodeValid; |
63 | template <class T, size_t NS> |
64 | struct 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 | |
74 | template <class T, size_t NS> |
75 | class 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. |
144 | template <class T, size_t NS> |
145 | constexpr size_t |
146 | Node<T, NS, typename detail::NodeValid<T, NS>::type>::kNodeSize; |
147 | template <class T, size_t NS> |
148 | constexpr size_t |
149 | Node<T, NS, typename detail::NodeValid<T, NS>::type>::kElementCount; |
150 | template <class T, size_t NS> |
151 | constexpr size_t |
152 | Node<T, NS, typename detail::NodeValid<T, NS>::type>::kPaddingBytes; |
153 | |
154 | template <class Iter> |
155 | class Iterator; |
156 | |
157 | namespace detail { |
158 | |
159 | template <typename Void, typename Container, typename... Args> |
160 | struct 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 | |
167 | template <typename Container, typename... Args> |
168 | struct 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 | |
178 | template <typename Container, typename... Args> |
179 | decltype(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& |
192 | template <class From, class To, class Enable = void> |
193 | struct TransferReferenceConstness; |
194 | |
195 | template <class From, class To> |
196 | struct 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 | |
205 | template <class From, class To> |
206 | struct 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. |
216 | template <class Iter> |
217 | struct 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 | */ |
240 | template <class Iter> |
241 | class 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 | |
318 | template <class Container> |
319 | Iterator<typename Container::const_iterator> cbegin(const Container& c) { |
320 | return Iterator<typename Container::const_iterator>(std::begin(c)); |
321 | } |
322 | |
323 | template <class Container> |
324 | Iterator<typename Container::const_iterator> cend(const Container& c) { |
325 | return Iterator<typename Container::const_iterator>(std::end(c)); |
326 | } |
327 | |
328 | template <class Container> |
329 | Iterator<typename Container::const_iterator> begin(const Container& c) { |
330 | return cbegin(c); |
331 | } |
332 | |
333 | template <class Container> |
334 | Iterator<typename Container::const_iterator> end(const Container& c) { |
335 | return cend(c); |
336 | } |
337 | |
338 | template <class Container> |
339 | Iterator<typename Container::iterator> begin(Container& c) { |
340 | return Iterator<typename Container::iterator>(std::begin(c)); |
341 | } |
342 | |
343 | template <class Container> |
344 | Iterator<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 | */ |
371 | template <class Container> |
372 | class 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 | |