2 * Copyright 2012 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.
17 #ifndef FOLLY_PADDED_H_
18 #define FOLLY_PADDED_H_
25 #include <type_traits>
27 #include <boost/iterator/iterator_adaptor.hpp>
29 #include "folly/Portability.h"
32 * Code that aids in storing data aligned on block (possibly cache-line)
33 * boundaries, perhaps with padding.
35 * Class Node represents one block. Given an iterator to a container of
36 * Node, class Iterator encapsulates an iterator to the underlying elements.
37 * Adaptor converts a sequence of Node into a sequence of underlying elements
38 * (not fully compatible with STL container requirements, see comments
39 * near the Node class declaration).
46 * A Node is a fixed-size container of as many objects of type T as would
47 * fit in a region of memory of size NS. The last NS % sizeof(T)
48 * bytes are ignored and uninitialized.
50 * Node only works for trivial types, which is usually not a concern. This
51 * is intentional: Node itself is trivial, which means that it can be
52 * serialized / deserialized using a simple memcpy.
54 template <class T, size_t NS, class Enable=void>
58 // Shortcut to avoid writing the long enable_if expression every time
59 template <class T, size_t NS, class Enable=void> struct NodeValid;
60 template <class T, size_t NS>
61 struct NodeValid<T, NS,
62 typename std::enable_if<(
63 std::is_trivial<T>::value &&
65 NS % alignof(T) == 0)>::type> {
70 template <class T, size_t NS>
71 class Node<T, NS, typename detail::NodeValid<T,NS>::type> {
74 static constexpr size_t kNodeSize = NS;
75 static constexpr size_t kElementCount = NS / sizeof(T);
76 static constexpr size_t kPaddingBytes = NS % sizeof(T);
78 T* data() { return storage_.data; }
79 const T* data() const { return storage_.data; }
81 bool operator==(const Node& other) const {
82 return memcmp(data(), other.data(), sizeof(T) * kElementCount) == 0;
84 bool operator!=(const Node& other) const {
85 return !(*this == other);
89 * Return the number of nodes needed to represent n values. Rounds up.
91 static constexpr size_t nodeCount(size_t n) {
92 return (n + kElementCount - 1) / kElementCount;
96 * Return the total byte size needed to represent n values, rounded up
97 * to the nearest full node.
99 static constexpr size_t paddedByteSize(size_t n) {
100 return nodeCount(n) * NS;
104 * Return the number of bytes used for padding n values.
105 * Note that, even if n is a multiple of kElementCount, this may
106 * return non-zero if kPaddingBytes != 0, as the padding at the end of
107 * the last node is not included in the result.
109 static constexpr size_t paddingBytes(size_t n) {
110 return (n ? (kPaddingBytes +
111 (kElementCount - 1 - (n-1) % kElementCount) * sizeof(T)) :
116 * Return the minimum byte size needed to represent n values.
117 * Does not round up. Even if n is a multiple of kElementCount, this
118 * may be different from paddedByteSize() if kPaddingBytes != 0, as
119 * the padding at the end of the last node is not included in the result.
120 * Note that the calculation below works for n=0 correctly (returns 0).
122 static constexpr size_t unpaddedByteSize(size_t n) {
123 return paddedByteSize(n) - paddingBytes(n);
128 unsigned char bytes[NS];
129 T data[kElementCount];
133 // We must define kElementCount and kPaddingBytes to work around a bug
134 // in gtest that odr-uses them.
135 template <class T, size_t NS> constexpr size_t
136 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kNodeSize;
137 template <class T, size_t NS> constexpr size_t
138 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kElementCount;
139 template <class T, size_t NS> constexpr size_t
140 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kPaddingBytes;
142 template <class Iter> class Iterator;
146 // Helper class to transfer the constness from From (a lvalue reference)
147 // and create a lvalue reference to To.
149 // TransferReferenceConstness<const string&, int> -> const int&
150 // TransferReferenceConstness<string&, int> -> int&
151 // TransferReferenceConstness<string&, const int> -> const int&
152 template <class From, class To, class Enable=void>
153 struct TransferReferenceConstness;
155 template <class From, class To>
156 struct TransferReferenceConstness<
157 From, To, typename std::enable_if<std::is_const<
158 typename std::remove_reference<From>::type>::value>::type> {
159 typedef typename std::add_lvalue_reference<
160 typename std::add_const<To>::type>::type type;
163 template <class From, class To>
164 struct TransferReferenceConstness<
165 From, To, typename std::enable_if<!std::is_const<
166 typename std::remove_reference<From>::type>::value>::type> {
167 typedef typename std::add_lvalue_reference<To>::type type;
170 // Helper class template to define a base class for Iterator (below) and save
172 template <class Iter>
173 struct IteratorBase {
174 typedef boost::iterator_adaptor<
177 // Base iterator type
180 typename std::iterator_traits<Iter>::value_type::value_type,
181 // Category or traversal
184 typename detail::TransferReferenceConstness<
185 typename std::iterator_traits<Iter>::reference,
186 typename std::iterator_traits<Iter>::value_type::value_type
191 } // namespace detail
194 * Wrapper around iterators to Node to return iterators to the underlying
197 template <class Iter>
198 class Iterator : public detail::IteratorBase<Iter>::type {
199 typedef typename detail::IteratorBase<Iter>::type Super;
201 typedef typename std::iterator_traits<Iter>::value_type Node;
203 Iterator() : pos_(0) { }
205 explicit Iterator(Iter base)
210 // Return the current node and the position inside the node
211 const Node& node() const { return *this->base_reference(); }
212 size_t pos() const { return pos_; }
215 typename Super::reference dereference() const {
216 return (*this->base_reference()).data()[pos_];
219 bool equal(const Iterator& other) const {
220 return (this->base_reference() == other.base_reference() &&
224 void advance(typename Super::difference_type n) {
225 constexpr ssize_t elementCount = Node::kElementCount; // signed!
226 ssize_t newPos = pos_ + n;
227 if (newPos >= 0 && newPos < elementCount) {
231 ssize_t nblocks = newPos / elementCount;
232 newPos %= elementCount;
234 --nblocks; // negative
235 newPos += elementCount;
237 this->base_reference() += nblocks;
242 if (++pos_ == Node::kElementCount) {
243 ++this->base_reference();
250 --this->base_reference();
251 pos_ = Node::kElementCount - 1;
255 typename Super::difference_type distance_to(const Iterator& other) const {
256 constexpr ssize_t elementCount = Node::kElementCount; // signed!
258 std::distance(this->base_reference(), other.base_reference());
259 return nblocks * elementCount + (other.pos_ - pos_);
262 friend class boost::iterator_core_access;
263 ssize_t pos_; // signed for easier advance() implementation
267 * Given a container to Node, return iterators to the first element in
268 * the first Node / one past the last element in the last Node.
269 * Note that the last node is assumed to be full; if that's not the case,
270 * subtract from end() as appropriate.
273 template <class Container>
274 Iterator<typename Container::const_iterator> cbegin(const Container& c) {
275 return Iterator<typename Container::const_iterator>(std::begin(c));
278 template <class Container>
279 Iterator<typename Container::const_iterator> cend(const Container& c) {
280 return Iterator<typename Container::const_iterator>(std::end(c));
283 template <class Container>
284 Iterator<typename Container::const_iterator> begin(const Container& c) {
288 template <class Container>
289 Iterator<typename Container::const_iterator> end(const Container& c) {
293 template <class Container>
294 Iterator<typename Container::iterator> begin(Container& c) {
295 return Iterator<typename Container::iterator>(std::begin(c));
298 template <class Container>
299 Iterator<typename Container::iterator> end(Container& c) {
300 return Iterator<typename Container::iterator>(std::end(c));
304 * Adaptor around a STL sequence container.
306 * Converts a sequence of Node into a sequence of its underlying elements
307 * (with enough functionality to make it useful, although it's not fully
308 * compatible with the STL containre requiremenets, see below).
310 * Provides iterators (of the same category as those of the underlying
311 * container), size(), front(), back(), push_back(), pop_back(), and const /
312 * non-const versions of operator[] (if the underlying container supports
313 * them). Does not provide push_front() / pop_front() or arbitrary insert /
314 * emplace / erase. Also provides reserve() / capacity() if supported by the
315 * underlying container.
317 * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL
318 * and by boost. Deal with it.
320 * Internally, we hold a container of Node and the number of elements in
321 * the last block. We don't keep empty blocks, so the number of elements in
322 * the last block is always between 1 and Node::kElementCount (inclusive).
323 * (this is true if the container is empty as well to make push_back() simpler,
324 * see the implementation of the size() method for details).
326 template <class Container>
329 typedef typename Container::value_type Node;
330 typedef typename Node::value_type value_type;
331 typedef value_type& reference;
332 typedef const value_type& const_reference;
333 typedef Iterator<typename Container::iterator> iterator;
334 typedef Iterator<typename Container::const_iterator> const_iterator;
335 typedef typename const_iterator::difference_type difference_type;
336 typedef typename Container::size_type size_type;
338 static constexpr size_t kElementsPerNode = Node::kElementCount;
340 Adaptor() : lastCount_(Node::kElementCount) { }
341 explicit Adaptor(Container c, size_t lastCount=Node::kElementCount)
343 lastCount_(lastCount) {
345 Adaptor(const Adaptor&) = default;
346 Adaptor& operator=(const Adaptor&) = default;
347 Adaptor(Adaptor&& other)
348 : c_(std::move(other.c_)),
349 lastCount_(other.lastCount_) {
350 other.lastCount_ = Node::kElementCount;
352 Adaptor& operator=(Adaptor&& other) {
353 if (this != &other) {
354 c_ = std::move(other.c_);
355 lastCount_ = other.lastCount_;
356 other.lastCount_ = Node::kElementCount;
362 const_iterator cbegin() const {
363 return const_iterator(c_.begin());
365 const_iterator cend() const {
366 auto it = const_iterator(c_.end());
367 if (lastCount_ != Node::kElementCount) {
368 it -= (Node::kElementCount - lastCount_);
372 const_iterator begin() const { return cbegin(); }
373 const_iterator end() const { return cend(); }
375 return iterator(c_.begin());
378 auto it = iterator(c_.end());
379 if (lastCount_ != Node::kElementCount) {
380 it -= (Node::kElementCount - lastCount_);
384 void swap(Adaptor& other) {
387 swap(lastCount_, other.lastCount_);
392 size_type size() const {
393 return (c_.empty() ? 0 :
394 (c_.size() - 1) * Node::kElementCount + lastCount_);
396 size_type max_size() const {
397 return ((c_.max_size() <= std::numeric_limits<size_type>::max() /
398 Node::kElementCount) ?
399 c_.max_size() * Node::kElementCount :
400 std::numeric_limits<size_type>::max());
403 const value_type& front() const {
405 return c_.front().data()[0];
407 value_type& front() {
409 return c_.front().data()[0];
412 const value_type& back() const {
414 return c_.back().data()[lastCount_ - 1];
418 return c_.back().data()[lastCount_ - 1];
421 void push_back(value_type x) {
422 if (lastCount_ == Node::kElementCount) {
423 c_.push_back(Node());
426 c_.back().data()[lastCount_++] = std::move(x);
431 if (--lastCount_ == 0) {
433 lastCount_ = Node::kElementCount;
439 lastCount_ = Node::kElementCount;
442 void reserve(size_type n) {
444 c_.reserve(Node::nodeCount(n));
446 size_type capacity() const {
447 return c_.capacity() * Node::kElementCount;
450 const value_type& operator[](size_type idx) const {
451 return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
453 value_type& operator[](size_type idx) {
454 return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
458 * Return the underlying container and number of elements in the last block,
459 * and clear *this. Useful when you want to process the data as Nodes
460 * (again) and want to avoid copies.
462 std::pair<Container, size_t> move() {
463 std::pair<Container, size_t> p(std::move(c_), lastCount_);
464 lastCount_ = Node::kElementCount;
469 * Return a const reference to the underlying container and the current
470 * number of elements in the last block.
472 std::pair<const Container&, size_t> peek() const {
473 return std::make_pair(std::cref(c_), lastCount_);
476 void padToFullNode(const value_type& padValue) {
477 while (lastCount_ != Node::kElementCount) {
483 Container c_; // container of Nodes
484 size_t lastCount_; // number of elements in last Node
487 } // namespace padded
490 #endif /* FOLLY_PADDED_H_ */