2 * Copyright 2012-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
26 #include <type_traits>
28 #include <boost/iterator/iterator_adaptor.hpp>
30 #include <folly/Portability.h>
31 #include <folly/Traits.h>
34 * Code that aids in storing data aligned on block (possibly cache-line)
35 * boundaries, perhaps with padding.
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).
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.
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.
56 template <class T, size_t NS, class Enable=void>
60 // Shortcut to avoid writing the long enable_if expression every time
61 template <class T, size_t NS, class Enable=void> struct NodeValid;
62 template <class T, size_t NS>
63 struct NodeValid<T, NS,
64 typename std::enable_if<(
65 std::is_trivial<T>::value &&
67 NS % alignof(T) == 0)>::type> {
72 template <class T, size_t NS>
73 class Node<T, NS, typename detail::NodeValid<T,NS>::type> {
76 static constexpr size_t kNodeSize = NS;
77 static constexpr size_t kElementCount = NS / sizeof(T);
78 static constexpr size_t kPaddingBytes = NS % sizeof(T);
80 T* data() { return storage_.data; }
81 const T* data() const { return storage_.data; }
83 bool operator==(const Node& other) const {
84 return memcmp(data(), other.data(), sizeof(T) * kElementCount) == 0;
86 bool operator!=(const Node& other) const {
87 return !(*this == other);
91 * Return the number of nodes needed to represent n values. Rounds up.
93 static constexpr size_t nodeCount(size_t n) {
94 return (n + kElementCount - 1) / kElementCount;
98 * Return the total byte size needed to represent n values, rounded up
99 * to the nearest full node.
101 static constexpr size_t paddedByteSize(size_t n) {
102 return nodeCount(n) * NS;
106 * Return the number of bytes used for padding n values.
107 * Note that, even if n is a multiple of kElementCount, this may
108 * return non-zero if kPaddingBytes != 0, as the padding at the end of
109 * the last node is not included in the result.
111 static constexpr size_t paddingBytes(size_t n) {
112 return (n ? (kPaddingBytes +
113 (kElementCount - 1 - (n-1) % kElementCount) * sizeof(T)) :
118 * Return the minimum byte size needed to represent n values.
119 * Does not round up. Even if n is a multiple of kElementCount, this
120 * may be different from paddedByteSize() if kPaddingBytes != 0, as
121 * the padding at the end of the last node is not included in the result.
122 * Note that the calculation below works for n=0 correctly (returns 0).
124 static constexpr size_t unpaddedByteSize(size_t n) {
125 return paddedByteSize(n) - paddingBytes(n);
130 unsigned char bytes[NS];
131 T data[kElementCount];
135 // We must define kElementCount and kPaddingBytes to work around a bug
136 // in gtest that odr-uses them.
137 template <class T, size_t NS> constexpr size_t
138 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kNodeSize;
139 template <class T, size_t NS> constexpr size_t
140 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kElementCount;
141 template <class T, size_t NS> constexpr size_t
142 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kPaddingBytes;
144 template <class Iter> class Iterator;
148 template <typename Void, typename Container, typename... Args>
149 struct padded_emplace_back_or_push_back_ {
150 static decltype(auto) go(Container& container, Args&&... args) {
151 using Value = typename Container::value_type;
152 return container.push_back(Value(std::forward<Args>(args)...));
156 template <typename Container, typename... Args>
157 struct padded_emplace_back_or_push_back_<
159 std::declval<Container&>().emplace_back(std::declval<Args>()...))>,
162 static decltype(auto) go(Container& container, Args&&... args) {
163 return container.emplace_back(std::forward<Args>(args)...);
167 template <typename Container, typename... Args>
168 decltype(auto) padded_emplace_back_or_push_back(
169 Container& container,
171 using impl = padded_emplace_back_or_push_back_<void, Container, Args...>;
172 return impl::go(container, std::forward<Args>(args)...);
175 // Helper class to transfer the constness from From (a lvalue reference)
176 // and create a lvalue reference to To.
178 // TransferReferenceConstness<const string&, int> -> const int&
179 // TransferReferenceConstness<string&, int> -> int&
180 // TransferReferenceConstness<string&, const int> -> const int&
181 template <class From, class To, class Enable=void>
182 struct TransferReferenceConstness;
184 template <class From, class To>
185 struct TransferReferenceConstness<
186 From, To, typename std::enable_if<std::is_const<
187 typename std::remove_reference<From>::type>::value>::type> {
188 typedef typename std::add_lvalue_reference<
189 typename std::add_const<To>::type>::type type;
192 template <class From, class To>
193 struct TransferReferenceConstness<
194 From, To, typename std::enable_if<!std::is_const<
195 typename std::remove_reference<From>::type>::value>::type> {
196 typedef typename std::add_lvalue_reference<To>::type type;
199 // Helper class template to define a base class for Iterator (below) and save
201 template <class Iter>
202 struct IteratorBase {
203 typedef boost::iterator_adaptor<
206 // Base iterator type
209 typename std::iterator_traits<Iter>::value_type::value_type,
210 // Category or traversal
213 typename detail::TransferReferenceConstness<
214 typename std::iterator_traits<Iter>::reference,
215 typename std::iterator_traits<Iter>::value_type::value_type
220 } // namespace detail
223 * Wrapper around iterators to Node to return iterators to the underlying
226 template <class Iter>
227 class Iterator : public detail::IteratorBase<Iter>::type {
228 typedef typename detail::IteratorBase<Iter>::type Super;
230 typedef typename std::iterator_traits<Iter>::value_type Node;
232 Iterator() : pos_(0) { }
234 explicit Iterator(Iter base)
239 // Return the current node and the position inside the node
240 const Node& node() const { return *this->base_reference(); }
241 size_t pos() const { return pos_; }
244 typename Super::reference dereference() const {
245 return (*this->base_reference()).data()[pos_];
248 bool equal(const Iterator& other) const {
249 return (this->base_reference() == other.base_reference() &&
253 void advance(typename Super::difference_type n) {
254 constexpr ssize_t elementCount = Node::kElementCount; // signed!
255 ssize_t newPos = pos_ + n;
256 if (newPos >= 0 && newPos < elementCount) {
260 ssize_t nblocks = newPos / elementCount;
261 newPos %= elementCount;
263 --nblocks; // negative
264 newPos += elementCount;
266 this->base_reference() += nblocks;
271 if (++pos_ == Node::kElementCount) {
272 ++this->base_reference();
279 --this->base_reference();
280 pos_ = Node::kElementCount - 1;
284 typename Super::difference_type distance_to(const Iterator& other) const {
285 constexpr ssize_t elementCount = Node::kElementCount; // signed!
287 std::distance(this->base_reference(), other.base_reference());
288 return nblocks * elementCount + (other.pos_ - pos_);
291 friend class boost::iterator_core_access;
292 ssize_t pos_; // signed for easier advance() implementation
296 * Given a container to Node, return iterators to the first element in
297 * the first Node / one past the last element in the last Node.
298 * Note that the last node is assumed to be full; if that's not the case,
299 * subtract from end() as appropriate.
302 template <class Container>
303 Iterator<typename Container::const_iterator> cbegin(const Container& c) {
304 return Iterator<typename Container::const_iterator>(std::begin(c));
307 template <class Container>
308 Iterator<typename Container::const_iterator> cend(const Container& c) {
309 return Iterator<typename Container::const_iterator>(std::end(c));
312 template <class Container>
313 Iterator<typename Container::const_iterator> begin(const Container& c) {
317 template <class Container>
318 Iterator<typename Container::const_iterator> end(const Container& c) {
322 template <class Container>
323 Iterator<typename Container::iterator> begin(Container& c) {
324 return Iterator<typename Container::iterator>(std::begin(c));
327 template <class Container>
328 Iterator<typename Container::iterator> end(Container& c) {
329 return Iterator<typename Container::iterator>(std::end(c));
333 * Adaptor around a STL sequence container.
335 * Converts a sequence of Node into a sequence of its underlying elements
336 * (with enough functionality to make it useful, although it's not fully
337 * compatible with the STL containre requiremenets, see below).
339 * Provides iterators (of the same category as those of the underlying
340 * container), size(), front(), back(), push_back(), pop_back(), and const /
341 * non-const versions of operator[] (if the underlying container supports
342 * them). Does not provide push_front() / pop_front() or arbitrary insert /
343 * emplace / erase. Also provides reserve() / capacity() if supported by the
344 * underlying container.
346 * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL
347 * and by boost. Deal with it.
349 * Internally, we hold a container of Node and the number of elements in
350 * the last block. We don't keep empty blocks, so the number of elements in
351 * the last block is always between 1 and Node::kElementCount (inclusive).
352 * (this is true if the container is empty as well to make push_back() simpler,
353 * see the implementation of the size() method for details).
355 template <class Container>
358 typedef typename Container::value_type Node;
359 typedef typename Node::value_type value_type;
360 typedef value_type& reference;
361 typedef const value_type& const_reference;
362 typedef Iterator<typename Container::iterator> iterator;
363 typedef Iterator<typename Container::const_iterator> const_iterator;
364 typedef typename const_iterator::difference_type difference_type;
365 typedef typename Container::size_type size_type;
367 static constexpr size_t kElementsPerNode = Node::kElementCount;
369 Adaptor() : lastCount_(Node::kElementCount) { }
370 explicit Adaptor(Container c, size_t lastCount=Node::kElementCount)
372 lastCount_(lastCount) {
374 explicit Adaptor(size_t n, const value_type& value = value_type())
375 : c_(Node::nodeCount(n), fullNode(value)) {
376 const auto count = n % Node::kElementCount;
377 lastCount_ = count != 0 ? count : Node::kElementCount;
380 Adaptor(const Adaptor&) = default;
381 Adaptor& operator=(const Adaptor&) = default;
382 Adaptor(Adaptor&& other) noexcept
383 : c_(std::move(other.c_)),
384 lastCount_(other.lastCount_) {
385 other.lastCount_ = Node::kElementCount;
387 Adaptor& operator=(Adaptor&& other) {
388 if (this != &other) {
389 c_ = std::move(other.c_);
390 lastCount_ = other.lastCount_;
391 other.lastCount_ = Node::kElementCount;
397 const_iterator cbegin() const {
398 return const_iterator(c_.begin());
400 const_iterator cend() const {
401 auto it = const_iterator(c_.end());
402 if (lastCount_ != Node::kElementCount) {
403 it -= (Node::kElementCount - lastCount_);
407 const_iterator begin() const { return cbegin(); }
408 const_iterator end() const { return cend(); }
410 return iterator(c_.begin());
413 auto it = iterator(c_.end());
414 if (lastCount_ != Node::kElementCount) {
415 it -= difference_type(Node::kElementCount - lastCount_);
419 void swap(Adaptor& other) {
422 swap(lastCount_, other.lastCount_);
427 size_type size() const {
428 return (c_.empty() ? 0 :
429 (c_.size() - 1) * Node::kElementCount + lastCount_);
431 size_type max_size() const {
432 return ((c_.max_size() <= std::numeric_limits<size_type>::max() /
433 Node::kElementCount) ?
434 c_.max_size() * Node::kElementCount :
435 std::numeric_limits<size_type>::max());
438 const value_type& front() const {
440 return c_.front().data()[0];
442 value_type& front() {
444 return c_.front().data()[0];
447 const value_type& back() const {
449 return c_.back().data()[lastCount_ - 1];
453 return c_.back().data()[lastCount_ - 1];
456 template <typename... Args>
457 void emplace_back(Args&&... args) {
458 new (allocate_back()) value_type(std::forward<Args>(args)...);
461 void push_back(value_type x) {
462 emplace_back(std::move(x));
467 if (--lastCount_ == 0) {
469 lastCount_ = Node::kElementCount;
475 lastCount_ = Node::kElementCount;
478 void reserve(size_type n) {
480 c_.reserve(Node::nodeCount(n));
483 size_type capacity() const {
484 return c_.capacity() * Node::kElementCount;
487 const value_type& operator[](size_type idx) const {
488 return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
490 value_type& operator[](size_type idx) {
491 return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
495 * Return the underlying container and number of elements in the last block,
496 * and clear *this. Useful when you want to process the data as Nodes
497 * (again) and want to avoid copies.
499 std::pair<Container, size_t> move() {
500 std::pair<Container, size_t> p(std::move(c_), lastCount_);
501 lastCount_ = Node::kElementCount;
506 * Return a const reference to the underlying container and the current
507 * number of elements in the last block.
509 std::pair<const Container&, size_t> peek() const {
510 return std::make_pair(std::cref(c_), lastCount_);
513 void padToFullNode(const value_type& padValue) {
514 // the if is necessary because c_ may be empty so we can't call c_.back()
515 if (lastCount_ != Node::kElementCount) {
516 auto last = c_.back().data();
517 std::fill(last + lastCount_, last + Node::kElementCount, padValue);
518 lastCount_ = Node::kElementCount;
523 value_type* allocate_back() {
524 if (lastCount_ == Node::kElementCount) {
525 detail::padded_emplace_back_or_push_back(c_);
528 return &c_.back().data()[lastCount_++];
531 static Node fullNode(const value_type& value) {
533 std::fill(n.data(), n.data() + kElementsPerNode, value);
536 Container c_; // container of Nodes
537 size_t lastCount_; // number of elements in last Node
540 } // namespace padded