folly/Padded.h

   1 /*
   2  * Copyright 2015 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 #ifndef FOLLY_PADDED_H_
  18 #define FOLLY_PADDED_H_
  19
  20 #include <algorithm>
  21 #include <cassert>
  22 #include <cstdint>
  23 #include <cstring>
  24 #include <functional>
  25 #include <iterator>
  26 #include <limits>
  27 #include <type_traits>
  28
  29 #include <boost/iterator/iterator_adaptor.hpp>
  30
  31 #include <folly/Portability.h>
  32 #include <folly/ContainerTraits.h>
  33
  34 /**
  35  * Code that aids in storing data aligned on block (possibly cache-line)
  36  * boundaries, perhaps with padding.
  37  *
  38  * Class Node represents one block.  Given an iterator to a container of
  39  * Node, class Iterator encapsulates an iterator to the underlying elements.
  40  * Adaptor converts a sequence of Node into a sequence of underlying elements
  41  * (not fully compatible with STL container requirements, see comments
  42  * near the Node class declaration).
  43  */
  44
  45 namespace folly {
  46 namespace padded {
  47
  48 /**
  49  * A Node is a fixed-size container of as many objects of type T as would
  50  * fit in a region of memory of size NS.  The last NS % sizeof(T)
  51  * bytes are ignored and uninitialized.
  52  *
  53  * Node only works for trivial types, which is usually not a concern.  This
  54  * is intentional: Node itself is trivial, which means that it can be
  55  * serialized / deserialized using a simple memcpy.
  56  */
  57 template <class T, size_t NS, class Enable=void>
  58 class Node;
  59
  60 namespace detail {
  61 // Shortcut to avoid writing the long enable_if expression every time
  62 template <class T, size_t NS, class Enable=void> struct NodeValid;
  63 template <class T, size_t NS>
  64 struct NodeValid<T, NS,
  65                  typename std::enable_if<(
  66                      std::is_trivial<T>::value &&
  67                      sizeof(T) <= NS &&
  68                      NS % alignof(T) == 0)>::type> {
  69   typedef void type;
  70 };
  71 }  // namespace detail
  72
  73 template <class T, size_t NS>
  74 class Node<T, NS, typename detail::NodeValid<T,NS>::type> {
  75  public:
  76   typedef T value_type;
  77   static constexpr size_t kNodeSize = NS;
  78   static constexpr size_t kElementCount = NS / sizeof(T);
  79   static constexpr size_t kPaddingBytes = NS % sizeof(T);
  80
  81   T* data() { return storage_.data; }
  82   const T* data() const { return storage_.data; }
  83
  84   bool operator==(const Node& other) const {
  85     return memcmp(data(), other.data(), sizeof(T) * kElementCount) == 0;
  86   }
  87   bool operator!=(const Node& other) const {
  88     return !(*this == other);
  89   }
  90
  91   /**
  92    * Return the number of nodes needed to represent n values.  Rounds up.
  93    */
  94   static constexpr size_t nodeCount(size_t n) {
  95     return (n + kElementCount - 1) / kElementCount;
  96   }
  97
  98   /**
  99    * Return the total byte size needed to represent n values, rounded up
 100    * to the nearest full node.
 101    */
 102   static constexpr size_t paddedByteSize(size_t n) {
 103     return nodeCount(n) * NS;
 104   }
 105
 106   /**
 107    * Return the number of bytes used for padding n values.
 108    * Note that, even if n is a multiple of kElementCount, this may
 109    * return non-zero if kPaddingBytes != 0, as the padding at the end of
 110    * the last node is not included in the result.
 111    */
 112   static constexpr size_t paddingBytes(size_t n) {
 113     return (n ? (kPaddingBytes +
 114                  (kElementCount - 1 - (n-1) % kElementCount) * sizeof(T)) :
 115             0);
 116   }
 117
 118   /**
 119    * Return the minimum byte size needed to represent n values.
 120    * Does not round up.  Even if n is a multiple of kElementCount, this
 121    * may be different from paddedByteSize() if kPaddingBytes != 0, as
 122    * the padding at the end of the last node is not included in the result.
 123    * Note that the calculation below works for n=0 correctly (returns 0).
 124    */
 125   static constexpr size_t unpaddedByteSize(size_t n) {
 126     return paddedByteSize(n) - paddingBytes(n);
 127   }
 128
 129  private:
 130   union Storage {
 131     unsigned char bytes[NS];
 132     T data[kElementCount];
 133   } storage_;
 134 };
 135
 136 // We must define kElementCount and kPaddingBytes to work around a bug
 137 // in gtest that odr-uses them.
 138 template <class T, size_t NS> constexpr size_t
 139 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kNodeSize;
 140 template <class T, size_t NS> constexpr size_t
 141 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kElementCount;
 142 template <class T, size_t NS> constexpr size_t
 143 Node<T, NS, typename detail::NodeValid<T,NS>::type>::kPaddingBytes;
 144
 145 template <class Iter> class Iterator;
 146
 147 namespace detail {
 148
 149 // Helper class to transfer the constness from From (a lvalue reference)
 150 // and create a lvalue reference to To.
 151 //
 152 // TransferReferenceConstness<const string&, int> -> const int&
 153 // TransferReferenceConstness<string&, int> -> int&
 154 // TransferReferenceConstness<string&, const int> -> const int&
 155 template <class From, class To, class Enable=void>
 156 struct TransferReferenceConstness;
 157
 158 template <class From, class To>
 159 struct TransferReferenceConstness<
 160   From, To, typename std::enable_if<std::is_const<
 161     typename std::remove_reference<From>::type>::value>::type> {
 162   typedef typename std::add_lvalue_reference<
 163     typename std::add_const<To>::type>::type type;
 164 };
 165
 166 template <class From, class To>
 167 struct TransferReferenceConstness<
 168   From, To, typename std::enable_if<!std::is_const<
 169     typename std::remove_reference<From>::type>::value>::type> {
 170   typedef typename std::add_lvalue_reference<To>::type type;
 171 };
 172
 173 // Helper class template to define a base class for Iterator (below) and save
 174 // typing.
 175 template <class Iter>
 176 struct IteratorBase {
 177   typedef boost::iterator_adaptor<
 178     // CRTC
 179     Iterator<Iter>,
 180     // Base iterator type
 181     Iter,
 182     // Value type
 183     typename std::iterator_traits<Iter>::value_type::value_type,
 184     // Category or traversal
 185     boost::use_default,
 186     // Reference type
 187     typename detail::TransferReferenceConstness<
 188       typename std::iterator_traits<Iter>::reference,
 189       typename std::iterator_traits<Iter>::value_type::value_type
 190     >::type
 191   > type;
 192 };
 193
 194 }  // namespace detail
 195
 196 /**
 197  * Wrapper around iterators to Node to return iterators to the underlying
 198  * node elements.
 199  */
 200 template <class Iter>
 201 class Iterator : public detail::IteratorBase<Iter>::type {
 202   typedef typename detail::IteratorBase<Iter>::type Super;
 203  public:
 204   typedef typename std::iterator_traits<Iter>::value_type Node;
 205
 206   Iterator() : pos_(0) { }
 207
 208   explicit Iterator(Iter base)
 209     : Super(base),
 210       pos_(0) {
 211   }
 212
 213   // Return the current node and the position inside the node
 214   const Node& node() const { return *this->base_reference(); }
 215   size_t pos() const { return pos_; }
 216
 217  private:
 218   typename Super::reference dereference() const {
 219     return (*this->base_reference()).data()[pos_];
 220   }
 221
 222   bool equal(const Iterator& other) const {
 223     return (this->base_reference() == other.base_reference() &&
 224             pos_ == other.pos_);
 225   }
 226
 227   void advance(typename Super::difference_type n) {
 228     constexpr ssize_t elementCount = Node::kElementCount;  // signed!
 229     ssize_t newPos = pos_ + n;
 230     if (newPos >= 0 && newPos < elementCount) {
 231       pos_ = newPos;
 232       return;
 233     }
 234     ssize_t nblocks = newPos / elementCount;
 235     newPos %= elementCount;
 236     if (newPos < 0) {
 237       --nblocks;  // negative
 238       newPos += elementCount;
 239     }
 240     this->base_reference() += nblocks;
 241     pos_ = newPos;
 242   }
 243
 244   void increment() {
 245     if (++pos_ == Node::kElementCount) {
 246       ++this->base_reference();
 247       pos_ = 0;
 248     }
 249   }
 250
 251   void decrement() {
 252     if (--pos_ == -1) {
 253       --this->base_reference();
 254       pos_ = Node::kElementCount - 1;
 255     }
 256   }
 257
 258   typename Super::difference_type distance_to(const Iterator& other) const {
 259     constexpr ssize_t elementCount = Node::kElementCount;  // signed!
 260     ssize_t nblocks =
 261       std::distance(this->base_reference(), other.base_reference());
 262     return nblocks * elementCount + (other.pos_ - pos_);
 263   }
 264
 265   friend class boost::iterator_core_access;
 266   ssize_t pos_;  // signed for easier advance() implementation
 267 };
 268
 269 /**
 270  * Given a container to Node, return iterators to the first element in
 271  * the first Node / one past the last element in the last Node.
 272  * Note that the last node is assumed to be full; if that's not the case,
 273  * subtract from end() as appropriate.
 274  */
 275
 276 template <class Container>
 277 Iterator<typename Container::const_iterator> cbegin(const Container& c) {
 278   return Iterator<typename Container::const_iterator>(std::begin(c));
 279 }
 280
 281 template <class Container>
 282 Iterator<typename Container::const_iterator> cend(const Container& c) {
 283   return Iterator<typename Container::const_iterator>(std::end(c));
 284 }
 285
 286 template <class Container>
 287 Iterator<typename Container::const_iterator> begin(const Container& c) {
 288   return cbegin(c);
 289 }
 290
 291 template <class Container>
 292 Iterator<typename Container::const_iterator> end(const Container& c) {
 293   return cend(c);
 294 }
 295
 296 template <class Container>
 297 Iterator<typename Container::iterator> begin(Container& c) {
 298   return Iterator<typename Container::iterator>(std::begin(c));
 299 }
 300
 301 template <class Container>
 302 Iterator<typename Container::iterator> end(Container& c) {
 303   return Iterator<typename Container::iterator>(std::end(c));
 304 }
 305
 306 /**
 307  * Adaptor around a STL sequence container.
 308  *
 309  * Converts a sequence of Node into a sequence of its underlying elements
 310  * (with enough functionality to make it useful, although it's not fully
 311  * compatible with the STL containre requiremenets, see below).
 312  *
 313  * Provides iterators (of the same category as those of the underlying
 314  * container), size(), front(), back(), push_back(), pop_back(), and const /
 315  * non-const versions of operator[] (if the underlying container supports
 316  * them).  Does not provide push_front() / pop_front() or arbitrary insert /
 317  * emplace / erase.  Also provides reserve() / capacity() if supported by the
 318  * underlying container.
 319  *
 320  * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL
 321  * and by boost.  Deal with it.
 322  *
 323  * Internally, we hold a container of Node and the number of elements in
 324  * the last block.  We don't keep empty blocks, so the number of elements in
 325  * the last block is always between 1 and Node::kElementCount (inclusive).
 326  * (this is true if the container is empty as well to make push_back() simpler,
 327  * see the implementation of the size() method for details).
 328  */
 329 template <class Container>
 330 class Adaptor {
 331  public:
 332   typedef typename Container::value_type Node;
 333   typedef typename Node::value_type value_type;
 334   typedef value_type& reference;
 335   typedef const value_type& const_reference;
 336   typedef Iterator<typename Container::iterator> iterator;
 337   typedef Iterator<typename Container::const_iterator> const_iterator;
 338   typedef typename const_iterator::difference_type difference_type;
 339   typedef typename Container::size_type size_type;
 340
 341   static constexpr size_t kElementsPerNode = Node::kElementCount;
 342   // Constructors
 343   Adaptor() : lastCount_(Node::kElementCount) { }
 344   explicit Adaptor(Container c, size_t lastCount=Node::kElementCount)
 345     : c_(std::move(c)),
 346       lastCount_(lastCount) {
 347   }
 348   explicit Adaptor(size_t n, const value_type& value = value_type())
 349     : c_(Node::nodeCount(n), fullNode(value)),
 350       lastCount_(n % Node::kElementCount ?: 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 -= (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
 515
 516 #endif /* FOLLY_PADDED_H_ */