folly/Padded.h

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