From af8b3ec14ab348b696875f9056b6d9e35f4bc17d Mon Sep 17 00:00:00 2001 From: Tudor Bosman Date: Wed, 5 Dec 2012 15:51:36 -0800 Subject: [PATCH] folly::padded_sequence -> folly::padded Summary: Mechanical. Test Plan: fbconfig unicorn/test unicorn/diskindex3 unicorn/diskindex4/test common/datastruct:css_tree_test folly/test:padded_test dragon/test:posting_list_test && fbmake opt Reviewed By: soren@fb.com FB internal diff: D649539 --- folly/Padded.h | 491 ++++++++++++++++++++++++++++++++++++++ folly/test/PaddedTest.cpp | 234 ++++++++++++++++++ 2 files changed, 725 insertions(+) create mode 100644 folly/Padded.h create mode 100644 folly/test/PaddedTest.cpp diff --git a/folly/Padded.h b/folly/Padded.h new file mode 100644 index 00000000..4c0af2af --- /dev/null +++ b/folly/Padded.h @@ -0,0 +1,491 @@ +/* + * Copyright 2012 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FOLLY_PADDED_H_ +#define FOLLY_PADDED_H_ + +#include +#include +#include +#include +#include +#include + +#include + +#include "folly/Portability.h" + +/** + * Code that aids in storing data aligned on block (possibly cache-line) + * boundaries, perhaps with padding. + * + * Class Node represents one block. Given an iterator to a container of + * Node, class Iterator encapsulates an iterator to the underlying elements. + * Adaptor converts a sequence of Node into a sequence of underlying elements + * (not fully compatible with STL container requirements, see comments + * near the Node class declaration). + */ + +namespace folly { +namespace padded { + +/** + * A Node is a fixed-size container of as many objects of type T as would + * fit in a region of memory of size NS. The last NS % sizeof(T) + * bytes are ignored and uninitialized. + * + * Node only works for trivial types, which is usually not a concern. This + * is intentional: Node itself is trivial, which means that it can be + * serialized / deserialized using a simple memcpy. + */ +template +class Node; + +namespace detail { +// Shortcut to avoid writing the long enable_if expression every time +template struct NodeValid; +template +struct NodeValid::value && + sizeof(T) <= NS && + NS % alignof(T) == 0)>::type> { + typedef void type; +}; +} // namespace detail + +template +class Node::type> { + public: + typedef T value_type; + static constexpr size_t kNodeSize = NS; + static constexpr size_t kElementCount = NS / sizeof(T); + static constexpr size_t kPaddingBytes = NS % sizeof(T); + + T* data() { return storage_.data; } + const T* data() const { return storage_.data; } + + bool operator==(const Node& other) const { + return memcmp(data(), other.data(), sizeof(T) * kElementCount) == 0; + } + bool operator!=(const Node& other) const { + return !(*this == other); + } + + /** + * Return the number of nodes needed to represent n values. Rounds up. + */ + static constexpr size_t nodeCount(size_t n) { + return (n + kElementCount - 1) / kElementCount; + } + + /** + * Return the total byte size needed to represent n values, rounded up + * to the nearest full node. + */ + static constexpr size_t paddedByteSize(size_t n) { + return nodeCount(n) * NS; + } + + /** + * Return the number of bytes used for padding n values. + * Note that, even if n is a multiple of kElementCount, this may + * return non-zero if kPaddingBytes != 0, as the padding at the end of + * the last node is not included in the result. + */ + static constexpr size_t paddingBytes(size_t n) { + return (n ? (kPaddingBytes + + (kElementCount - 1 - (n-1) % kElementCount) * sizeof(T)) : + 0); + } + + /** + * Return the minimum byte size needed to represent n values. + * Does not round up. Even if n is a multiple of kElementCount, this + * may be different from paddedByteSize() if kPaddingBytes != 0, as + * the padding at the end of the last node is not included in the result. + * Note that the calculation below works for n=0 correctly (returns 0). + */ + static constexpr size_t unpaddedByteSize(size_t n) { + return paddedByteSize(n) - paddingBytes(n); + } + + private: + union Storage { + unsigned char bytes[NS]; + T data[kElementCount]; + } storage_; +}; + +// We must define kElementCount and kPaddingBytes to work around a bug +// in gtest that odr-uses them. +template constexpr size_t +Node::type>::kNodeSize; +template constexpr size_t +Node::type>::kElementCount; +template constexpr size_t +Node::type>::kPaddingBytes; + +template class Iterator; + +namespace detail { + +// Helper class to transfer the constness from From (a lvalue reference) +// and create a lvalue reference to To. +// +// TransferReferenceConstness -> const int& +// TransferReferenceConstness -> int& +// TransferReferenceConstness -> const int& +template +struct TransferReferenceConstness; + +template +struct TransferReferenceConstness< + From, To, typename std::enable_if::type>::value>::type> { + typedef typename std::add_lvalue_reference< + typename std::add_const::type>::type type; +}; + +template +struct TransferReferenceConstness< + From, To, typename std::enable_if::type>::value>::type> { + typedef typename std::add_lvalue_reference::type type; +}; + +// Helper class template to define a base class for Iterator (below) and save +// typing. +template +struct IteratorBase { + typedef boost::iterator_adaptor< + // CRTC + Iterator, + // Base iterator type + Iter, + // Value type + typename std::iterator_traits::value_type::value_type, + // Category or traversal + boost::use_default, + // Reference type + typename detail::TransferReferenceConstness< + typename std::iterator_traits::reference, + typename std::iterator_traits::value_type::value_type + >::type + > type; +}; + +} // namespace detail + +/** + * Wrapper around iterators to Node to return iterators to the underlying + * node elements. + */ +template +class Iterator : public detail::IteratorBase::type { + typedef typename detail::IteratorBase::type Super; + public: + typedef typename std::iterator_traits::value_type Node; + + Iterator() : pos_(0) { } + + explicit Iterator(Iter base) + : Super(base), + pos_(0) { + } + + // Return the current node and the position inside the node + const Node& node() const { return *this->base_reference(); } + size_t pos() const { return pos_; } + + private: + typename Super::reference dereference() const { + return (*this->base_reference()).data()[pos_]; + } + + bool equal(const Iterator& other) const { + return (this->base_reference() == other.base_reference() && + pos_ == other.pos_); + } + + void advance(typename Super::difference_type n) { + constexpr ssize_t elementCount = Node::kElementCount; // signed! + ssize_t newPos = pos_ + n; + if (newPos >= 0 && newPos < elementCount) { + pos_ = newPos; + return; + } + ssize_t nblocks = newPos / elementCount; + newPos %= elementCount; + if (newPos < 0) { + --nblocks; // negative + newPos += elementCount; + } + this->base_reference() += nblocks; + pos_ = newPos; + } + + void increment() { + if (++pos_ == Node::kElementCount) { + ++this->base_reference(); + pos_ = 0; + } + } + + void decrement() { + if (--pos_ == -1) { + --this->base_reference(); + pos_ = Node::kElementCount - 1; + } + } + + typename Super::difference_type distance_to(const Iterator& other) const { + constexpr ssize_t elementCount = Node::kElementCount; // signed! + ssize_t nblocks = + std::distance(this->base_reference(), other.base_reference()); + return nblocks * elementCount + (other.pos_ - pos_); + } + + friend class boost::iterator_core_access; + ssize_t pos_; // signed for easier advance() implementation +}; + +/** + * Given a container to Node, return iterators to the first element in + * the first Node / one past the last element in the last Node. + * Note that the last node is assumed to be full; if that's not the case, + * subtract from end() as appropriate. + */ + +template +Iterator cbegin(const Container& c) { + return Iterator(std::begin(c)); +} + +template +Iterator cend(const Container& c) { + return Iterator(std::end(c)); +} + +template +Iterator begin(const Container& c) { + return cbegin(c); +} + +template +Iterator end(const Container& c) { + return cend(c); +} + +template +Iterator begin(Container& c) { + return Iterator(std::begin(c)); +} + +template +Iterator end(Container& c) { + return Iterator(std::end(c)); +} + +/** + * Adaptor around a STL sequence container. + * + * Converts a sequence of Node into a sequence of its underlying elements + * (with enough functionality to make it useful, although it's not fully + * compatible with the STL containre requiremenets, see below). + * + * Provides iterators (of the same category as those of the underlying + * container), size(), front(), back(), push_back(), pop_back(), and const / + * non-const versions of operator[] (if the underlying container supports + * them). Does not provide push_front() / pop_front() or arbitrary insert / + * emplace / erase. Also provides reserve() / capacity() if supported by the + * underlying container. + * + * Yes, it's called Adaptor, not Adapter, as that's the name used by the STL + * and by boost. Deal with it. + * + * Internally, we hold a container of Node and the number of elements in + * the last block. We don't keep empty blocks, so the number of elements in + * the last block is always between 1 and Node::kElementCount (inclusive). + * (this is true if the container is empty as well to make push_back() simpler, + * see the implementation of the size() method for details). + */ +template +class Adaptor { + public: + typedef typename Container::value_type Node; + typedef typename Node::value_type value_type; + typedef value_type& reference; + typedef const value_type& const_reference; + typedef Iterator iterator; + typedef Iterator const_iterator; + typedef typename const_iterator::difference_type difference_type; + typedef typename Container::size_type size_type; + + static constexpr size_t kElementsPerNode = Node::kElementCount; + // Constructors + Adaptor() : lastCount_(Node::kElementCount) { } + explicit Adaptor(Container c, size_t lastCount=Node::kElementCount) + : c_(std::move(c)), + lastCount_(lastCount) { + } + Adaptor(const Adaptor&) = default; + Adaptor& operator=(const Adaptor&) = default; + Adaptor(Adaptor&& other) + : c_(std::move(other.c_)), + lastCount_(other.lastCount_) { + other.lastCount_ = Node::kElementCount; + } + Adaptor& operator=(Adaptor&& other) { + if (this != &other) { + c_ = std::move(other.c_); + lastCount_ = other.lastCount_; + other.lastCount_ = Node::kElementCount; + } + return *this; + } + + // Iterators + const_iterator cbegin() const { + return const_iterator(c_.begin()); + } + const_iterator cend() const { + auto it = const_iterator(c_.end()); + if (lastCount_ != Node::kElementCount) { + it -= (Node::kElementCount - lastCount_); + } + return it; + } + const_iterator begin() const { return cbegin(); } + const_iterator end() const { return cend(); } + iterator begin() { + return iterator(c_.begin()); + } + iterator end() { + auto it = iterator(c_.end()); + if (lastCount_ != Node::kElementCount) { + it -= (Node::kElementCount - lastCount_); + } + return it; + } + void swap(Adaptor& other) { + using std::swap; + swap(c_, other.c_); + swap(lastCount_, other.lastCount_); + } + bool empty() const { + return c_.empty(); + } + size_type size() const { + return (c_.empty() ? 0 : + (c_.size() - 1) * Node::kElementCount + lastCount_); + } + size_type max_size() const { + return ((c_.max_size() <= std::numeric_limits::max() / + Node::kElementCount) ? + c_.max_size() * Node::kElementCount : + std::numeric_limits::max()); + } + + const value_type& front() const { + assert(!empty()); + return c_.front().data()[0]; + } + value_type& front() { + assert(!empty()); + return c_.front().data()[0]; + } + + const value_type& back() const { + assert(!empty()); + return c_.back().data()[lastCount_ - 1]; + } + value_type& back() { + assert(!empty()); + return c_.back().data()[lastCount_ - 1]; + } + + void push_back(value_type x) { + if (lastCount_ == Node::kElementCount) { + c_.push_back(Node()); + lastCount_ = 0; + } + c_.back().data()[lastCount_++] = std::move(x); + } + + void pop_back() { + assert(!empty()); + if (--lastCount_ == 0) { + c_.pop_back(); + lastCount_ = Node::kElementCount; + } + } + + void clear() { + c_.clear(); + lastCount_ = Node::kElementCount; + } + + void reserve(size_type n) { + assert(n >= 0); + c_.reserve(Node::nodeCount(n)); + } + size_type capacity() const { + return c_.capacity() * Node::kElementCount; + } + + const value_type& operator[](size_type idx) const { + return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount]; + } + value_type& operator[](size_type idx) { + return c_[idx / Node::kElementCount].data()[idx % Node::kElementCount]; + } + + /** + * Return the underlying container and number of elements in the last block, + * and clear *this. Useful when you want to process the data as Nodes + * (again) and want to avoid copies. + */ + std::pair move() { + std::pair p(std::move(c_), lastCount_); + lastCount_ = Node::kElementCount; + return std::move(p); + } + + /** + * Return a const reference to the underlying container and the current + * number of elements in the last block. + */ + std::pair peek() const { + return std::make_pair(std::cref(c_), lastCount_); + } + + void padToFullNode(const value_type& padValue) { + while (lastCount_ != Node::kElementCount) { + push_back(padValue); + } + } + + private: + Container c_; // container of Nodes + size_t lastCount_; // number of elements in last Node +}; + +} // namespace padded +} // namespace folly + +#endif /* FOLLY_PADDED_H_ */ + diff --git a/folly/test/PaddedTest.cpp b/folly/test/PaddedTest.cpp new file mode 100644 index 00000000..f5fde484 --- /dev/null +++ b/folly/test/PaddedTest.cpp @@ -0,0 +1,234 @@ +/* + * Copyright 2012 Facebook, Inc. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "folly/Padded.h" + +#include +#include + +using namespace folly; +namespace ps = ::folly::padded; + +TEST(NodeTest, Padding) { + typedef ps::Node IntNode; + EXPECT_EQ(16, IntNode::kElementCount); + EXPECT_EQ(0, IntNode::kPaddingBytes); + EXPECT_EQ(alignof(int32_t), alignof(IntNode)); + EXPECT_EQ(64, sizeof(IntNode)); + EXPECT_EQ(0, IntNode::nodeCount(0)); + EXPECT_EQ(0, IntNode::paddedByteSize(0)); + EXPECT_EQ(0, IntNode::unpaddedByteSize(0)); + EXPECT_EQ(1, IntNode::nodeCount(1)); + EXPECT_EQ(64, IntNode::paddedByteSize(1)); + EXPECT_EQ(4, IntNode::unpaddedByteSize(1)); + EXPECT_EQ(1, IntNode::nodeCount(16)); + EXPECT_EQ(64, IntNode::paddedByteSize(16)); + EXPECT_EQ(64, IntNode::unpaddedByteSize(16)); + EXPECT_EQ(2, IntNode::nodeCount(17)); + EXPECT_EQ(128, IntNode::paddedByteSize(17)); + EXPECT_EQ(68, IntNode::unpaddedByteSize(17)); + EXPECT_EQ(128, IntNode::paddedByteSize(32)); + EXPECT_EQ(128, IntNode::unpaddedByteSize(32)); + EXPECT_EQ(3, IntNode::nodeCount(33)); + EXPECT_EQ(192, IntNode::paddedByteSize(33)); + EXPECT_EQ(132, IntNode::unpaddedByteSize(33)); + + struct SevenBytes { + char c[7]; + }; + EXPECT_EQ(1, alignof(SevenBytes)); + typedef ps::Node SevenByteNode; + EXPECT_EQ(9, SevenByteNode::kElementCount); // 64 / 7 + EXPECT_EQ(1, SevenByteNode::kPaddingBytes); // 64 % 7 + EXPECT_EQ(1, alignof(SevenByteNode)); + EXPECT_EQ(64, sizeof(SevenByteNode)); + EXPECT_EQ(0, SevenByteNode::nodeCount(0)); + EXPECT_EQ(0, SevenByteNode::paddedByteSize(0)); + EXPECT_EQ(0, SevenByteNode::unpaddedByteSize(0)); + EXPECT_EQ(1, SevenByteNode::nodeCount(1)); + EXPECT_EQ(64, SevenByteNode::paddedByteSize(1)); + EXPECT_EQ(7, SevenByteNode::unpaddedByteSize(1)); + EXPECT_EQ(1, SevenByteNode::nodeCount(9)); + EXPECT_EQ(64, SevenByteNode::paddedByteSize(9)); + EXPECT_EQ(63, SevenByteNode::unpaddedByteSize(9)); + EXPECT_EQ(2, SevenByteNode::nodeCount(10)); + EXPECT_EQ(128, SevenByteNode::paddedByteSize(10)); + EXPECT_EQ(71, SevenByteNode::unpaddedByteSize(10)); + EXPECT_EQ(2, SevenByteNode::nodeCount(18)); + EXPECT_EQ(128, SevenByteNode::paddedByteSize(18)); + EXPECT_EQ(127, SevenByteNode::unpaddedByteSize(18)); + EXPECT_EQ(3, SevenByteNode::nodeCount(19)); + EXPECT_EQ(192, SevenByteNode::paddedByteSize(19)); + EXPECT_EQ(135, SevenByteNode::unpaddedByteSize(19)); +} + +class IntPaddedTestBase : public ::testing::Test { + protected: + typedef ps::Node IntNode; + typedef std::vector IntNodeVec; + IntNodeVec v_; + int n_; +}; + +class IntPaddedConstTest : public IntPaddedTestBase { + protected: + void SetUp() { + v_.resize(4); + n_ = 0; + for (int i = 0; i < 4; i++) { + for (int j = 0; j < IntNode::kElementCount; ++j, ++n_) { + v_[i].data()[j] = n_; + } + } + } +}; + +TEST_F(IntPaddedConstTest, Iteration) { + int k = 0; + for (auto it = ps::cbegin(v_); it != ps::cend(v_); ++it, ++k) { + EXPECT_EQ(k, *it); + } + EXPECT_EQ(n_, k); +} + +TEST_F(IntPaddedConstTest, Arithmetic) { + EXPECT_EQ(64, ps::cend(v_) - ps::cbegin(v_)); + // Play around block boundaries + auto it = ps::cbegin(v_); + EXPECT_EQ(0, *it); + { + auto i2 = it; + EXPECT_EQ(0, i2 - it); + i2 += 1; + EXPECT_EQ(1, *i2); + EXPECT_EQ(1, i2 - it); + EXPECT_EQ(-1, it - i2); + } + it += 15; + EXPECT_EQ(15, *it); + { + auto i2 = it; + i2 += 1; + EXPECT_EQ(16, *i2); + EXPECT_EQ(1, i2 - it); + EXPECT_EQ(-1, it - i2); + } + ++it; + EXPECT_EQ(16, *it); + { + auto i2 = it; + i2 -= 1; + EXPECT_EQ(15, *i2); + EXPECT_EQ(-1, i2 - it); + EXPECT_EQ(1, it - i2); + } + --it; + EXPECT_EQ(15, *it); + { + auto i2 = it; + i2 -= 1; + EXPECT_EQ(14, *i2); + EXPECT_EQ(-1, i2 - it); + EXPECT_EQ(1, it - i2); + } +} + +class IntPaddedNonConstTest : public IntPaddedTestBase { +}; + +TEST_F(IntPaddedNonConstTest, Iteration) { + v_.resize(4); + n_ = 64; + + int k = 0; + for (auto it = ps::begin(v_); it != ps::end(v_); ++it, ++k) { + *it = k; + } + EXPECT_EQ(n_, k); + + k = 0; + for (int i = 0; i < 4; i++) { + for (int j = 0; j < IntNode::kElementCount; ++j, ++k) { + EXPECT_EQ(k, v_[i].data()[j]); + } + } +} + +class StructPaddedTestBase : public ::testing::Test { + protected: + struct Point { + uint8_t x; + uint8_t y; + uint8_t z; + }; + typedef ps::Node PointNode; + typedef std::vector PointNodeVec; + PointNodeVec v_; + int n_; +}; + +class StructPaddedConstTest : public StructPaddedTestBase { + protected: + void SetUp() { + v_.resize(4); + n_ = 0; + for (int i = 0; i < 4; i++) { + for (int j = 0; j < PointNode::kElementCount; ++j, ++n_) { + auto& point = v_[i].data()[j]; + point.x = n_; + point.y = n_ + 1; + point.z = n_ + 2; + } + } + } +}; + +TEST_F(StructPaddedConstTest, Iteration) { + int k = 0; + for (auto it = ps::cbegin(v_); it != ps::cend(v_); ++it, ++k) { + EXPECT_EQ(k, it->x); + EXPECT_EQ(k + 1, it->y); + EXPECT_EQ(k + 2, it->z); + } + EXPECT_EQ(n_, k); +} + +class IntAdaptorTest : public IntPaddedConstTest { + protected: + typedef ps::Adaptor IntAdaptor; + IntAdaptor a_; +}; + +TEST_F(IntAdaptorTest, Simple) { + for (int i = 0; i < n_; ++i) { + EXPECT_EQ((i == 0), a_.empty()); + EXPECT_EQ(i, a_.size()); + a_.push_back(i); + } + EXPECT_EQ(n_, a_.size()); + + int k = 0; + for (auto it = a_.begin(); it != a_.end(); ++it, ++k) { + EXPECT_EQ(k, a_[k]); + EXPECT_EQ(k, *it); + } + EXPECT_EQ(n_, k); + + auto p = a_.move(); + EXPECT_TRUE(a_.empty()); + EXPECT_EQ(16, p.second); + EXPECT_TRUE(v_ == p.first); +} -- 2.34.1