folly/Padded.h

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