folly/Padded.h

   1 /*
   2  * Copyright 2016 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/ContainerTraits.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 -= (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