ca499aad0f70ad0626f620c06aca676caa400ce9
[folly.git] / folly / Padded.h
1 /*
2  * Copyright 2017 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/ContainerTraits.h>
31 #include <folly/Portability.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> 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 &&
66                      sizeof(T) <= NS &&
67                      NS % alignof(T) == 0)>::type> {
68   typedef void type;
69 };
70 }  // namespace detail
71
72 template <class T, size_t NS>
73 class Node<T, NS, typename detail::NodeValid<T,NS>::type> {
74  public:
75   typedef T value_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);
79
80   T* data() { return storage_.data; }
81   const T* data() const { return storage_.data; }
82
83   bool operator==(const Node& other) const {
84     return memcmp(data(), other.data(), sizeof(T) * kElementCount) == 0;
85   }
86   bool operator!=(const Node& other) const {
87     return !(*this == other);
88   }
89
90   /**
91    * Return the number of nodes needed to represent n values.  Rounds up.
92    */
93   static constexpr size_t nodeCount(size_t n) {
94     return (n + kElementCount - 1) / kElementCount;
95   }
96
97   /**
98    * Return the total byte size needed to represent n values, rounded up
99    * to the nearest full node.
100    */
101   static constexpr size_t paddedByteSize(size_t n) {
102     return nodeCount(n) * NS;
103   }
104
105   /**
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.
110    */
111   static constexpr size_t paddingBytes(size_t n) {
112     return (n ? (kPaddingBytes +
113                  (kElementCount - 1 - (n-1) % kElementCount) * sizeof(T)) :
114             0);
115   }
116
117   /**
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).
123    */
124   static constexpr size_t unpaddedByteSize(size_t n) {
125     return paddedByteSize(n) - paddingBytes(n);
126   }
127
128  private:
129   union Storage {
130     unsigned char bytes[NS];
131     T data[kElementCount];
132   } storage_;
133 };
134
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;
143
144 template <class Iter> class Iterator;
145
146 namespace detail {
147
148 // Helper class to transfer the constness from From (a lvalue reference)
149 // and create a lvalue reference to To.
150 //
151 // TransferReferenceConstness<const string&, int> -> const int&
152 // TransferReferenceConstness<string&, int> -> int&
153 // TransferReferenceConstness<string&, const int> -> const int&
154 template <class From, class To, class Enable=void>
155 struct TransferReferenceConstness;
156
157 template <class From, class To>
158 struct TransferReferenceConstness<
159   From, To, typename std::enable_if<std::is_const<
160     typename std::remove_reference<From>::type>::value>::type> {
161   typedef typename std::add_lvalue_reference<
162     typename std::add_const<To>::type>::type type;
163 };
164
165 template <class From, class To>
166 struct TransferReferenceConstness<
167   From, To, typename std::enable_if<!std::is_const<
168     typename std::remove_reference<From>::type>::value>::type> {
169   typedef typename std::add_lvalue_reference<To>::type type;
170 };
171
172 // Helper class template to define a base class for Iterator (below) and save
173 // typing.
174 template <class Iter>
175 struct IteratorBase {
176   typedef boost::iterator_adaptor<
177     // CRTC
178     Iterator<Iter>,
179     // Base iterator type
180     Iter,
181     // Value type
182     typename std::iterator_traits<Iter>::value_type::value_type,
183     // Category or traversal
184     boost::use_default,
185     // Reference type
186     typename detail::TransferReferenceConstness<
187       typename std::iterator_traits<Iter>::reference,
188       typename std::iterator_traits<Iter>::value_type::value_type
189     >::type
190   > type;
191 };
192
193 }  // namespace detail
194
195 /**
196  * Wrapper around iterators to Node to return iterators to the underlying
197  * node elements.
198  */
199 template <class Iter>
200 class Iterator : public detail::IteratorBase<Iter>::type {
201   typedef typename detail::IteratorBase<Iter>::type Super;
202  public:
203   typedef typename std::iterator_traits<Iter>::value_type Node;
204
205   Iterator() : pos_(0) { }
206
207   explicit Iterator(Iter base)
208     : Super(base),
209       pos_(0) {
210   }
211
212   // Return the current node and the position inside the node
213   const Node& node() const { return *this->base_reference(); }
214   size_t pos() const { return pos_; }
215
216  private:
217   typename Super::reference dereference() const {
218     return (*this->base_reference()).data()[pos_];
219   }
220
221   bool equal(const Iterator& other) const {
222     return (this->base_reference() == other.base_reference() &&
223             pos_ == other.pos_);
224   }
225
226   void advance(typename Super::difference_type n) {
227     constexpr ssize_t elementCount = Node::kElementCount;  // signed!
228     ssize_t newPos = pos_ + n;
229     if (newPos >= 0 && newPos < elementCount) {
230       pos_ = newPos;
231       return;
232     }
233     ssize_t nblocks = newPos / elementCount;
234     newPos %= elementCount;
235     if (newPos < 0) {
236       --nblocks;  // negative
237       newPos += elementCount;
238     }
239     this->base_reference() += nblocks;
240     pos_ = newPos;
241   }
242
243   void increment() {
244     if (++pos_ == Node::kElementCount) {
245       ++this->base_reference();
246       pos_ = 0;
247     }
248   }
249
250   void decrement() {
251     if (--pos_ == -1) {
252       --this->base_reference();
253       pos_ = Node::kElementCount - 1;
254     }
255   }
256
257   typename Super::difference_type distance_to(const Iterator& other) const {
258     constexpr ssize_t elementCount = Node::kElementCount;  // signed!
259     ssize_t nblocks =
260       std::distance(this->base_reference(), other.base_reference());
261     return nblocks * elementCount + (other.pos_ - pos_);
262   }
263
264   friend class boost::iterator_core_access;
265   ssize_t pos_;  // signed for easier advance() implementation
266 };
267
268 /**
269  * Given a container to Node, return iterators to the first element in
270  * the first Node / one past the last element in the last Node.
271  * Note that the last node is assumed to be full; if that's not the case,
272  * subtract from end() as appropriate.
273  */
274
275 template <class Container>
276 Iterator<typename Container::const_iterator> cbegin(const Container& c) {
277   return Iterator<typename Container::const_iterator>(std::begin(c));
278 }
279
280 template <class Container>
281 Iterator<typename Container::const_iterator> cend(const Container& c) {
282   return Iterator<typename Container::const_iterator>(std::end(c));
283 }
284
285 template <class Container>
286 Iterator<typename Container::const_iterator> begin(const Container& c) {
287   return cbegin(c);
288 }
289
290 template <class Container>
291 Iterator<typename Container::const_iterator> end(const Container& c) {
292   return cend(c);
293 }
294
295 template <class Container>
296 Iterator<typename Container::iterator> begin(Container& c) {
297   return Iterator<typename Container::iterator>(std::begin(c));
298 }
299
300 template <class Container>
301 Iterator<typename Container::iterator> end(Container& c) {
302   return Iterator<typename Container::iterator>(std::end(c));
303 }
304
305 /**
306  * Adaptor around a STL sequence container.
307  *
308  * Converts a sequence of Node into a sequence of its underlying elements
309  * (with enough functionality to make it useful, although it's not fully
310  * compatible with the STL containre requiremenets, see below).
311  *
312  * Provides iterators (of the same category as those of the underlying
313  * container), size(), front(), back(), push_back(), pop_back(), and const /
314  * non-const versions of operator[] (if the underlying container supports
315  * them).  Does not provide push_front() / pop_front() or arbitrary insert /
316  * emplace / erase.  Also provides reserve() / capacity() if supported by the
317  * underlying container.
318  *
319  * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL
320  * and by boost.  Deal with it.
321  *
322  * Internally, we hold a container of Node and the number of elements in
323  * the last block.  We don't keep empty blocks, so the number of elements in
324  * the last block is always between 1 and Node::kElementCount (inclusive).
325  * (this is true if the container is empty as well to make push_back() simpler,
326  * see the implementation of the size() method for details).
327  */
328 template <class Container>
329 class Adaptor {
330  public:
331   typedef typename Container::value_type Node;
332   typedef typename Node::value_type value_type;
333   typedef value_type& reference;
334   typedef const value_type& const_reference;
335   typedef Iterator<typename Container::iterator> iterator;
336   typedef Iterator<typename Container::const_iterator> const_iterator;
337   typedef typename const_iterator::difference_type difference_type;
338   typedef typename Container::size_type size_type;
339
340   static constexpr size_t kElementsPerNode = Node::kElementCount;
341   // Constructors
342   Adaptor() : lastCount_(Node::kElementCount) { }
343   explicit Adaptor(Container c, size_t lastCount=Node::kElementCount)
344     : c_(std::move(c)),
345       lastCount_(lastCount) {
346   }
347   explicit Adaptor(size_t n, const value_type& value = value_type())
348     : c_(Node::nodeCount(n), fullNode(value)) {
349     const auto count = n % Node::kElementCount;
350     lastCount_ = count != 0 ? count : Node::kElementCount;
351   }
352
353   Adaptor(const Adaptor&) = default;
354   Adaptor& operator=(const Adaptor&) = default;
355   Adaptor(Adaptor&& other) noexcept
356     : c_(std::move(other.c_)),
357       lastCount_(other.lastCount_) {
358     other.lastCount_ = Node::kElementCount;
359   }
360   Adaptor& operator=(Adaptor&& other) {
361     if (this != &other) {
362       c_ = std::move(other.c_);
363       lastCount_ = other.lastCount_;
364       other.lastCount_ = Node::kElementCount;
365     }
366     return *this;
367   }
368
369   // Iterators
370   const_iterator cbegin() const {
371     return const_iterator(c_.begin());
372   }
373   const_iterator cend() const {
374     auto it = const_iterator(c_.end());
375     if (lastCount_ != Node::kElementCount) {
376       it -= (Node::kElementCount - lastCount_);
377     }
378     return it;
379   }
380   const_iterator begin() const { return cbegin(); }
381   const_iterator end() const { return cend(); }
382   iterator begin() {
383     return iterator(c_.begin());
384   }
385   iterator end() {
386     auto it = iterator(c_.end());
387     if (lastCount_ != Node::kElementCount) {
388       it -= difference_type(Node::kElementCount - lastCount_);
389     }
390     return it;
391   }
392   void swap(Adaptor& other) {
393     using std::swap;
394     swap(c_, other.c_);
395     swap(lastCount_, other.lastCount_);
396   }
397   bool empty() const {
398     return c_.empty();
399   }
400   size_type size() const {
401     return (c_.empty() ? 0 :
402             (c_.size() - 1) * Node::kElementCount + lastCount_);
403   }
404   size_type max_size() const {
405     return ((c_.max_size() <= std::numeric_limits<size_type>::max() /
406              Node::kElementCount) ?
407             c_.max_size() * Node::kElementCount :
408             std::numeric_limits<size_type>::max());
409   }
410
411   const value_type& front() const {
412     assert(!empty());
413     return c_.front().data()[0];
414   }
415   value_type& front() {
416     assert(!empty());
417     return c_.front().data()[0];
418   }
419
420   const value_type& back() const {
421     assert(!empty());
422     return c_.back().data()[lastCount_ - 1];
423   }
424   value_type& back() {
425     assert(!empty());
426     return c_.back().data()[lastCount_ - 1];
427   }
428
429   template <typename... Args>
430   void emplace_back(Args&&... args) {
431     new (allocate_back()) value_type(std::forward<Args>(args)...);
432   }
433
434   void push_back(value_type x) {
435     emplace_back(std::move(x));
436   }
437
438   void pop_back() {
439     assert(!empty());
440     if (--lastCount_ == 0) {
441       c_.pop_back();
442       lastCount_ = Node::kElementCount;
443     }
444   }
445
446   void clear() {
447     c_.clear();
448     lastCount_ = Node::kElementCount;
449   }
450
451   void reserve(size_type n) {
452     assert(n >= 0);
453     c_.reserve(Node::nodeCount(n));
454   }
455
456   size_type capacity() const {
457     return c_.capacity() * Node::kElementCount;
458   }
459
460   const value_type& operator[](size_type idx) const {
461     return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
462   }
463   value_type& operator[](size_type idx) {
464     return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
465   }
466
467   /**
468    * Return the underlying container and number of elements in the last block,
469    * and clear *this.  Useful when you want to process the data as Nodes
470    * (again) and want to avoid copies.
471    */
472   std::pair<Container, size_t> move() {
473     std::pair<Container, size_t> p(std::move(c_), lastCount_);
474     lastCount_ = Node::kElementCount;
475     return std::move(p);
476   }
477
478   /**
479    * Return a const reference to the underlying container and the current
480    * number of elements in the last block.
481    */
482   std::pair<const Container&, size_t> peek() const {
483     return std::make_pair(std::cref(c_), lastCount_);
484   }
485
486   void padToFullNode(const value_type& padValue) {
487     // the if is necessary because c_ may be empty so we can't call c_.back()
488     if (lastCount_ != Node::kElementCount) {
489       auto last = c_.back().data();
490       std::fill(last + lastCount_, last + Node::kElementCount, padValue);
491       lastCount_ = Node::kElementCount;
492     }
493   }
494
495  private:
496   value_type* allocate_back() {
497     if (lastCount_ == Node::kElementCount) {
498       container_emplace_back_or_push_back(c_);
499       lastCount_ = 0;
500     }
501     return &c_.back().data()[lastCount_++];
502   }
503
504   static Node fullNode(const value_type& value) {
505     Node n;
506     std::fill(n.data(), n.data() + kElementsPerNode, value);
507     return n;
508   }
509   Container c_;  // container of Nodes
510   size_t lastCount_;  // number of elements in last Node
511 };
512
513 }  // namespace padded
514 }  // namespace folly