folly/test/PaddedTest.cpp

   1 /*
   2  * Copyright 2012-present 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 #include <folly/Padded.h>
  18
  19 #include <glog/logging.h>
  20
  21 #include <folly/portability/GTest.h>
  22
  23 using namespace folly;
  24
  25 TEST(NodeTest, Padding) {
  26   typedef padded::Node<int32_t, 64> IntNode;
  27   EXPECT_EQ(16, IntNode::kElementCount);
  28   EXPECT_EQ(0, IntNode::kPaddingBytes);
  29   EXPECT_EQ(alignof(int32_t), alignof(IntNode));
  30   EXPECT_EQ(64, sizeof(IntNode));
  31   EXPECT_EQ(0, IntNode::nodeCount(0));
  32   EXPECT_EQ(0, IntNode::paddedByteSize(0));
  33   EXPECT_EQ(0, IntNode::unpaddedByteSize(0));
  34   EXPECT_EQ(1, IntNode::nodeCount(1));
  35   EXPECT_EQ(64, IntNode::paddedByteSize(1));
  36   EXPECT_EQ(4, IntNode::unpaddedByteSize(1));
  37   EXPECT_EQ(1, IntNode::nodeCount(16));
  38   EXPECT_EQ(64, IntNode::paddedByteSize(16));
  39   EXPECT_EQ(64, IntNode::unpaddedByteSize(16));
  40   EXPECT_EQ(2, IntNode::nodeCount(17));
  41   EXPECT_EQ(128, IntNode::paddedByteSize(17));
  42   EXPECT_EQ(68, IntNode::unpaddedByteSize(17));
  43   EXPECT_EQ(128, IntNode::paddedByteSize(32));
  44   EXPECT_EQ(128, IntNode::unpaddedByteSize(32));
  45   EXPECT_EQ(3, IntNode::nodeCount(33));
  46   EXPECT_EQ(192, IntNode::paddedByteSize(33));
  47   EXPECT_EQ(132, IntNode::unpaddedByteSize(33));
  48
  49   struct SevenBytes {
  50     char c[7];
  51   };
  52   EXPECT_EQ(1, alignof(SevenBytes));
  53   typedef padded::Node<SevenBytes, 64> SevenByteNode;
  54   EXPECT_EQ(9, SevenByteNode::kElementCount);  // 64 / 7
  55   EXPECT_EQ(1, SevenByteNode::kPaddingBytes);  // 64 % 7
  56   EXPECT_EQ(1, alignof(SevenByteNode));
  57   EXPECT_EQ(64, sizeof(SevenByteNode));
  58   EXPECT_EQ(0, SevenByteNode::nodeCount(0));
  59   EXPECT_EQ(0, SevenByteNode::paddedByteSize(0));
  60   EXPECT_EQ(0, SevenByteNode::unpaddedByteSize(0));
  61   EXPECT_EQ(1, SevenByteNode::nodeCount(1));
  62   EXPECT_EQ(64, SevenByteNode::paddedByteSize(1));
  63   EXPECT_EQ(7, SevenByteNode::unpaddedByteSize(1));
  64   EXPECT_EQ(1, SevenByteNode::nodeCount(9));
  65   EXPECT_EQ(64, SevenByteNode::paddedByteSize(9));
  66   EXPECT_EQ(63, SevenByteNode::unpaddedByteSize(9));
  67   EXPECT_EQ(2, SevenByteNode::nodeCount(10));
  68   EXPECT_EQ(128, SevenByteNode::paddedByteSize(10));
  69   EXPECT_EQ(71, SevenByteNode::unpaddedByteSize(10));
  70   EXPECT_EQ(2, SevenByteNode::nodeCount(18));
  71   EXPECT_EQ(128, SevenByteNode::paddedByteSize(18));
  72   EXPECT_EQ(127, SevenByteNode::unpaddedByteSize(18));
  73   EXPECT_EQ(3, SevenByteNode::nodeCount(19));
  74   EXPECT_EQ(192, SevenByteNode::paddedByteSize(19));
  75   EXPECT_EQ(135, SevenByteNode::unpaddedByteSize(19));
  76 }
  77
  78 class IntPaddedTestBase : public ::testing::Test {
  79  protected:
  80   typedef padded::Node<uint32_t, 64> IntNode;
  81   typedef std::vector<IntNode> IntNodeVec;
  82   IntNodeVec v_;
  83   int n_;
  84 };
  85
  86 class IntPaddedConstTest : public IntPaddedTestBase {
  87  protected:
  88   void SetUp() override {
  89     v_.resize(4);
  90     n_ = 0;
  91     for (int i = 0; i < 4; i++) {
  92       for (size_t j = 0; j < IntNode::kElementCount; ++j, ++n_) {
  93         v_[i].data()[j] = n_;
  94       }
  95     }
  96   }
  97 };
  98
  99 TEST_F(IntPaddedConstTest, Iteration) {
 100   int k = 0;
 101   for (auto it = padded::cbegin(v_); it != padded::cend(v_); ++it, ++k) {
 102     EXPECT_EQ(k, *it);
 103   }
 104   EXPECT_EQ(n_, k);
 105 }
 106
 107 TEST_F(IntPaddedConstTest, Arithmetic) {
 108   EXPECT_EQ(64, padded::cend(v_) - padded::cbegin(v_));
 109   // Play around block boundaries
 110   auto it = padded::cbegin(v_);
 111   EXPECT_EQ(0, *it);
 112   {
 113     auto i2 = it;
 114     EXPECT_EQ(0, i2 - it);
 115     i2 += 1;
 116     EXPECT_EQ(1, *i2);
 117     EXPECT_EQ(1, i2 - it);
 118     EXPECT_EQ(-1, it - i2);
 119   }
 120   it += 15;
 121   EXPECT_EQ(15, *it);
 122   {
 123     auto i2 = it;
 124     i2 += 1;
 125     EXPECT_EQ(16, *i2);
 126     EXPECT_EQ(1, i2 - it);
 127     EXPECT_EQ(-1, it - i2);
 128   }
 129   ++it;
 130   EXPECT_EQ(16, *it);
 131   {
 132     auto i2 = it;
 133     i2 -= 1;
 134     EXPECT_EQ(15, *i2);
 135     EXPECT_EQ(-1, i2 - it);
 136     EXPECT_EQ(1, it - i2);
 137   }
 138   --it;
 139   EXPECT_EQ(15, *it);
 140   {
 141     auto i2 = it;
 142     i2 -= 1;
 143     EXPECT_EQ(14, *i2);
 144     EXPECT_EQ(-1, i2 - it);
 145     EXPECT_EQ(1, it - i2);
 146   }
 147 }
 148
 149 class IntPaddedNonConstTest : public IntPaddedTestBase {
 150 };
 151
 152 TEST_F(IntPaddedNonConstTest, Iteration) {
 153   v_.resize(4);
 154   n_ = 64;
 155
 156   int k = 0;
 157   for (auto it = padded::begin(v_); it != padded::end(v_); ++it, ++k) {
 158     *it = k;
 159   }
 160   EXPECT_EQ(n_, k);
 161
 162   k = 0;
 163   for (int i = 0; i < 4; i++) {
 164     for (size_t j = 0; j < IntNode::kElementCount; ++j, ++k) {
 165       EXPECT_EQ(k, v_[i].data()[j]);
 166     }
 167   }
 168 }
 169
 170 class StructPaddedTestBase : public ::testing::Test {
 171  protected:
 172   struct Point {
 173     uint8_t x;
 174     uint8_t y;
 175     uint8_t z;
 176   };
 177   typedef padded::Node<Point, 64> PointNode;
 178   typedef std::vector<PointNode> PointNodeVec;
 179   PointNodeVec v_;
 180   int n_;
 181 };
 182
 183 class StructPaddedConstTest : public StructPaddedTestBase {
 184  protected:
 185   void SetUp() override {
 186     v_.resize(4);
 187     n_ = 0;
 188     for (int i = 0; i < 4; i++) {
 189       for (size_t j = 0; j < PointNode::kElementCount; ++j, ++n_) {
 190         auto& point = v_[i].data()[j];
 191         point.x = n_;
 192         point.y = n_ + 1;
 193         point.z = n_ + 2;
 194       }
 195     }
 196   }
 197 };
 198
 199 TEST_F(StructPaddedConstTest, Iteration) {
 200   int k = 0;
 201   for (auto it = padded::cbegin(v_); it != padded::cend(v_); ++it, ++k) {
 202     EXPECT_EQ(k, it->x);
 203     EXPECT_EQ(k + 1, it->y);
 204     EXPECT_EQ(k + 2, it->z);
 205   }
 206   EXPECT_EQ(n_, k);
 207 }
 208
 209 class IntAdaptorTest : public IntPaddedConstTest {
 210  protected:
 211   typedef padded::Adaptor<IntNodeVec> IntAdaptor;
 212   IntAdaptor a_;
 213 };
 214
 215 TEST_F(IntAdaptorTest, Simple) {
 216   for (int i = 0; i < n_; ++i) {
 217     EXPECT_EQ((i == 0), a_.empty());
 218     EXPECT_EQ(i, a_.size());
 219     a_.push_back(i);
 220   }
 221   EXPECT_EQ(n_, a_.size());
 222
 223   int k = 0;
 224   for (auto it = a_.begin(); it != a_.end(); ++it, ++k) {
 225     EXPECT_EQ(k, a_[k]);
 226     EXPECT_EQ(k, *it);
 227   }
 228   EXPECT_EQ(n_, k);
 229
 230   auto p = a_.move();
 231   EXPECT_TRUE(a_.empty());
 232   EXPECT_EQ(16, p.second);
 233   EXPECT_TRUE(v_ == p.first);
 234 }
 235
 236 TEST_F(IntAdaptorTest, ResizeConstructor) {
 237   IntAdaptor a(n_, 42);
 238   EXPECT_EQ(n_, a.size());
 239   for (int i = 0; i < n_; ++i) {
 240     EXPECT_EQ(42, a[i]);
 241   }
 242 }
 243
 244 TEST_F(IntAdaptorTest, SimpleEmplaceBack) {
 245   for (int i = 0; i < n_; ++i) {
 246     EXPECT_EQ((i == 0), a_.empty());
 247     EXPECT_EQ(i, a_.size());
 248     a_.emplace_back(i);
 249   }
 250   EXPECT_EQ(n_, a_.size());
 251
 252   int k = 0;
 253   for (auto it = a_.begin(); it != a_.end(); ++it, ++k) {
 254     EXPECT_EQ(k, a_[k]);
 255     EXPECT_EQ(k, *it);
 256   }
 257   EXPECT_EQ(n_, k);
 258
 259   auto p = a_.move();
 260   EXPECT_TRUE(a_.empty());
 261   EXPECT_EQ(16, p.second);
 262   EXPECT_TRUE(v_ == p.first);
 263 }