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/Portability.h>
  31 #include <folly/Traits.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 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)...));
 153   }
 154 };
 155
 156 template <typename Container, typename... Args>
 157 struct padded_emplace_back_or_push_back_<
 158     void_t<decltype(
 159         std::declval<Container&>().emplace_back(std::declval<Args>()...))>,
 160     Container,
 161     Args...> {
 162   static decltype(auto) go(Container& container, Args&&... args) {
 163     return container.emplace_back(std::forward<Args>(args)...);
 164   }
 165 };
 166
 167 template <typename Container, typename... Args>
 168 decltype(auto) padded_emplace_back_or_push_back(
 169     Container& container,
 170     Args&&... args) {
 171   using impl = padded_emplace_back_or_push_back_<void, Container, Args...>;
 172   return impl::go(container, std::forward<Args>(args)...);
 173 }
 174
 175 // Helper class to transfer the constness from From (a lvalue reference)
 176 // and create a lvalue reference to To.
 177 //
 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;
 183
 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;
 190 };
 191
 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;
 197 };
 198
 199 // Helper class template to define a base class for Iterator (below) and save
 200 // typing.
 201 template <class Iter>
 202 struct IteratorBase {
 203   typedef boost::iterator_adaptor<
 204     // CRTC
 205     Iterator<Iter>,
 206     // Base iterator type
 207     Iter,
 208     // Value type
 209     typename std::iterator_traits<Iter>::value_type::value_type,
 210     // Category or traversal
 211     boost::use_default,
 212     // Reference type
 213     typename detail::TransferReferenceConstness<
 214       typename std::iterator_traits<Iter>::reference,
 215       typename std::iterator_traits<Iter>::value_type::value_type
 216     >::type
 217   > type;
 218 };
 219
 220 } // namespace detail
 221
 222 /**
 223  * Wrapper around iterators to Node to return iterators to the underlying
 224  * node elements.
 225  */
 226 template <class Iter>
 227 class Iterator : public detail::IteratorBase<Iter>::type {
 228   typedef typename detail::IteratorBase<Iter>::type Super;
 229  public:
 230   typedef typename std::iterator_traits<Iter>::value_type Node;
 231
 232   Iterator() : pos_(0) { }
 233
 234   explicit Iterator(Iter base)
 235     : Super(base),
 236       pos_(0) {
 237   }
 238
 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_; }
 242
 243  private:
 244   typename Super::reference dereference() const {
 245     return (*this->base_reference()).data()[pos_];
 246   }
 247
 248   bool equal(const Iterator& other) const {
 249     return (this->base_reference() == other.base_reference() &&
 250             pos_ == other.pos_);
 251   }
 252
 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) {
 257       pos_ = newPos;
 258       return;
 259     }
 260     ssize_t nblocks = newPos / elementCount;
 261     newPos %= elementCount;
 262     if (newPos < 0) {
 263       --nblocks;  // negative
 264       newPos += elementCount;
 265     }
 266     this->base_reference() += nblocks;
 267     pos_ = newPos;
 268   }
 269
 270   void increment() {
 271     if (++pos_ == Node::kElementCount) {
 272       ++this->base_reference();
 273       pos_ = 0;
 274     }
 275   }
 276
 277   void decrement() {
 278     if (--pos_ == -1) {
 279       --this->base_reference();
 280       pos_ = Node::kElementCount - 1;
 281     }
 282   }
 283
 284   typename Super::difference_type distance_to(const Iterator& other) const {
 285     constexpr ssize_t elementCount = Node::kElementCount;  // signed!
 286     ssize_t nblocks =
 287       std::distance(this->base_reference(), other.base_reference());
 288     return nblocks * elementCount + (other.pos_ - pos_);
 289   }
 290
 291   friend class boost::iterator_core_access;
 292   ssize_t pos_;  // signed for easier advance() implementation
 293 };
 294
 295 /**
 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.
 300  */
 301
 302 template <class Container>
 303 Iterator<typename Container::const_iterator> cbegin(const Container& c) {
 304   return Iterator<typename Container::const_iterator>(std::begin(c));
 305 }
 306
 307 template <class Container>
 308 Iterator<typename Container::const_iterator> cend(const Container& c) {
 309   return Iterator<typename Container::const_iterator>(std::end(c));
 310 }
 311
 312 template <class Container>
 313 Iterator<typename Container::const_iterator> begin(const Container& c) {
 314   return cbegin(c);
 315 }
 316
 317 template <class Container>
 318 Iterator<typename Container::const_iterator> end(const Container& c) {
 319   return cend(c);
 320 }
 321
 322 template <class Container>
 323 Iterator<typename Container::iterator> begin(Container& c) {
 324   return Iterator<typename Container::iterator>(std::begin(c));
 325 }
 326
 327 template <class Container>
 328 Iterator<typename Container::iterator> end(Container& c) {
 329   return Iterator<typename Container::iterator>(std::end(c));
 330 }
 331
 332 /**
 333  * Adaptor around a STL sequence container.
 334  *
 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).
 338  *
 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.
 345  *
 346  * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL
 347  * and by boost.  Deal with it.
 348  *
 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).
 354  */
 355 template <class Container>
 356 class Adaptor {
 357  public:
 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;
 366
 367   static constexpr size_t kElementsPerNode = Node::kElementCount;
 368   // Constructors
 369   Adaptor() : lastCount_(Node::kElementCount) { }
 370   explicit Adaptor(Container c, size_t lastCount=Node::kElementCount)
 371     : c_(std::move(c)),
 372       lastCount_(lastCount) {
 373   }
 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;
 378   }
 379
 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;
 386   }
 387   Adaptor& operator=(Adaptor&& other) {
 388     if (this != &other) {
 389       c_ = std::move(other.c_);
 390       lastCount_ = other.lastCount_;
 391       other.lastCount_ = Node::kElementCount;
 392     }
 393     return *this;
 394   }
 395
 396   // Iterators
 397   const_iterator cbegin() const {
 398     return const_iterator(c_.begin());
 399   }
 400   const_iterator cend() const {
 401     auto it = const_iterator(c_.end());
 402     if (lastCount_ != Node::kElementCount) {
 403       it -= (Node::kElementCount - lastCount_);
 404     }
 405     return it;
 406   }
 407   const_iterator begin() const { return cbegin(); }
 408   const_iterator end() const { return cend(); }
 409   iterator begin() {
 410     return iterator(c_.begin());
 411   }
 412   iterator end() {
 413     auto it = iterator(c_.end());
 414     if (lastCount_ != Node::kElementCount) {
 415       it -= difference_type(Node::kElementCount - lastCount_);
 416     }
 417     return it;
 418   }
 419   void swap(Adaptor& other) {
 420     using std::swap;
 421     swap(c_, other.c_);
 422     swap(lastCount_, other.lastCount_);
 423   }
 424   bool empty() const {
 425     return c_.empty();
 426   }
 427   size_type size() const {
 428     return (c_.empty() ? 0 :
 429             (c_.size() - 1) * Node::kElementCount + lastCount_);
 430   }
 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());
 436   }
 437
 438   const value_type& front() const {
 439     assert(!empty());
 440     return c_.front().data()[0];
 441   }
 442   value_type& front() {
 443     assert(!empty());
 444     return c_.front().data()[0];
 445   }
 446
 447   const value_type& back() const {
 448     assert(!empty());
 449     return c_.back().data()[lastCount_ - 1];
 450   }
 451   value_type& back() {
 452     assert(!empty());
 453     return c_.back().data()[lastCount_ - 1];
 454   }
 455
 456   template <typename... Args>
 457   void emplace_back(Args&&... args) {
 458     new (allocate_back()) value_type(std::forward<Args>(args)...);
 459   }
 460
 461   void push_back(value_type x) {
 462     emplace_back(std::move(x));
 463   }
 464
 465   void pop_back() {
 466     assert(!empty());
 467     if (--lastCount_ == 0) {
 468       c_.pop_back();
 469       lastCount_ = Node::kElementCount;
 470     }
 471   }
 472
 473   void clear() {
 474     c_.clear();
 475     lastCount_ = Node::kElementCount;
 476   }
 477
 478   void reserve(size_type n) {
 479     assert(n >= 0);
 480     c_.reserve(Node::nodeCount(n));
 481   }
 482
 483   size_type capacity() const {
 484     return c_.capacity() * Node::kElementCount;
 485   }
 486
 487   const value_type& operator[](size_type idx) const {
 488     return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
 489   }
 490   value_type& operator[](size_type idx) {
 491     return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount];
 492   }
 493
 494   /**
 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.
 498    */
 499   std::pair<Container, size_t> move() {
 500     std::pair<Container, size_t> p(std::move(c_), lastCount_);
 501     lastCount_ = Node::kElementCount;
 502     return std::move(p);
 503   }
 504
 505   /**
 506    * Return a const reference to the underlying container and the current
 507    * number of elements in the last block.
 508    */
 509   std::pair<const Container&, size_t> peek() const {
 510     return std::make_pair(std::cref(c_), lastCount_);
 511   }
 512
 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;
 519     }
 520   }
 521
 522  private:
 523   value_type* allocate_back() {
 524     if (lastCount_ == Node::kElementCount) {
 525       detail::padded_emplace_back_or_push_back(c_);
 526       lastCount_ = 0;
 527     }
 528     return &c_.back().data()[lastCount_++];
 529   }
 530
 531   static Node fullNode(const value_type& value) {
 532     Node n;
 533     std::fill(n.data(), n.data() + kElementsPerNode, value);
 534     return n;
 535   }
 536   Container c_;  // container of Nodes
 537   size_t lastCount_;  // number of elements in last Node
 538 };
 539
 540 } // namespace padded
 541 } // namespace folly