text: //  Copyright (c) 2011-present, Facebook, Inc.  All rights reserved.
  //  This source code is licensed under both the GPLv2 (found in the
  //  COPYING file in the root directory) and Apache 2.0 License
  //  (found in the LICENSE.Apache file in the root directory).
  
  #include <atomic>
  #include <iostream>
  #include <string>
  #include <utility>
  
  #include "rocksdb/env.h"
  #include "util/autovector.h"
  #include "util/string_util.h"
  #include "util/testharness.h"
  #include "util/testutil.h"
  
  using std::cout;
  using std::endl;
  
  namespace rocksdb {
  
  class AutoVectorTest : public testing::Test {};
  const unsigned long kSize = 8;
  
  namespace {
  template <class T>
  void AssertAutoVectorOnlyInStack(autovector<T, kSize>* vec, bool result) {
  #ifndef ROCKSDB_LITE
    ASSERT_EQ(vec->only_in_stack(), result);
  #endif  // !ROCKSDB_LITE
  }
  }  // namespace
  
  TEST_F(AutoVectorTest, PushBackAndPopBack) {
    autovector<size_t, kSize> vec;
    ASSERT_TRUE(vec.empty());
    ASSERT_EQ(0ul, vec.size());
  
    for (size_t i = 0; i < 1000 * kSize; ++i) {
      vec.push_back(i);
      ASSERT_TRUE(!vec.empty());
      if (i < kSize) {
        AssertAutoVectorOnlyInStack(&vec, true);
      } else {
        AssertAutoVectorOnlyInStack(&vec, false);
      }
      ASSERT_EQ(i + 1, vec.size());
      ASSERT_EQ(i, vec[i]);
      ASSERT_EQ(i, vec.at(i));
    }
  
    size_t size = vec.size();
    while (size != 0) {
      vec.pop_back();
      // will always be in heap
      AssertAutoVectorOnlyInStack(&vec, false);
      ASSERT_EQ(--size, vec.size());
    }
  
    ASSERT_TRUE(vec.empty());
  }
  
  TEST_F(AutoVectorTest, EmplaceBack) {
    typedef std::pair<size_t, std::string> ValType;
    autovector<ValType, kSize> vec;
  
    for (size_t i = 0; i < 1000 * kSize; ++i) {
      vec.emplace_back(i, ToString(i + 123));
      ASSERT_TRUE(!vec.empty());
      if (i < kSize) {
        AssertAutoVectorOnlyInStack(&vec, true);
      } else {
        AssertAutoVectorOnlyInStack(&vec, false);
      }
  
      ASSERT_EQ(i + 1, vec.size());
      ASSERT_EQ(i, vec[i].first);
      ASSERT_EQ(ToString(i + 123), vec[i].second);
    }
  
    vec.clear();
    ASSERT_TRUE(vec.empty());
    AssertAutoVectorOnlyInStack(&vec, false);
  }
  
  TEST_F(AutoVectorTest, Resize) {
    autovector<size_t, kSize> vec;
  
    vec.resize(kSize);
    AssertAutoVectorOnlyInStack(&vec, true);
    for (size_t i = 0; i < kSize; ++i) {
      vec[i] = i;
    }
  
    vec.resize(kSize * 2);
    AssertAutoVectorOnlyInStack(&vec, false);
    for (size_t i = 0; i < kSize; ++i) {
      ASSERT_EQ(vec[i], i);
    }
    for (size_t i = 0; i < kSize; ++i) {
      vec[i + kSize] = i;
    }
  
    vec.resize(1);
    ASSERT_EQ(1U, vec.size());
  }
  
  namespace {
  void AssertEqual(
      const autovector<size_t, kSize>& a, const autovector<size_t, kSize>& b) {
    ASSERT_EQ(a.size(), b.size());
    ASSERT_EQ(a.empty(), b.empty());
  #ifndef ROCKSDB_LITE
    ASSERT_EQ(a.only_in_stack(), b.only_in_stack());
  #endif  // !ROCKSDB_LITE
    for (size_t i = 0; i < a.size(); ++i) {
      ASSERT_EQ(a[i], b[i]);
    }
  }
  }  // namespace
  
  TEST_F(AutoVectorTest, CopyAndAssignment) {
    // Test both heap-allocated and stack-allocated cases.
    for (auto size : { kSize / 2, kSize * 1000 }) {
      autovector<size_t, kSize> vec;
      for (size_t i = 0; i < size; ++i) {
        vec.push_back(i);
      }
  
      {
        autovector<size_t, kSize> other;
        other = vec;
        AssertEqual(other, vec);
      }
  
      {
        autovector<size_t, kSize> other(vec);
        AssertEqual(other, vec);
      }
    }
  }
  
  TEST_F(AutoVectorTest, Iterators) {
    autovector<std::string, kSize> vec;
    for (size_t i = 0; i < kSize * 1000; ++i) {
      vec.push_back(ToString(i));
    }
  
    // basic operator test
    ASSERT_EQ(vec.front(), *vec.begin());
    ASSERT_EQ(vec.back(), *(vec.end() - 1));
    ASSERT_TRUE(vec.begin() < vec.end());
  
    // non-const iterator
    size_t index = 0;
    for (const auto& item : vec) {
      ASSERT_EQ(vec[index++], item);
    }
  
    index = vec.size() - 1;
    for (auto pos = vec.rbegin(); pos != vec.rend(); ++pos) {
      ASSERT_EQ(vec[index--], *pos);
    }
  
    // const iterator
    const auto& cvec = vec;
    index = 0;
    for (const auto& item : cvec) {
      ASSERT_EQ(cvec[index++], item);
    }
  
    index = vec.size() - 1;
    for (auto pos = cvec.rbegin(); pos != cvec.rend(); ++pos) {
      ASSERT_EQ(cvec[index--], *pos);
    }
  
    // forward and backward
    auto pos = vec.begin();
    while (pos != vec.end()) {
      auto old_val = *pos;
      auto old = pos++;
      // HACK: make sure -> works
      ASSERT_TRUE(!old->empty());
      ASSERT_EQ(old_val, *old);
      ASSERT_TRUE(pos == vec.end() || old_val != *pos);
    }
  
    pos = vec.begin();
    for (size_t i = 0; i < vec.size(); i += 2) {
      // Cannot use ASSERT_EQ since that macro depends on iostream serialization
      ASSERT_TRUE(pos + 2 - 2 == pos);
      pos += 2;
      ASSERT_TRUE(pos >= vec.begin());
      ASSERT_TRUE(pos <= vec.end());
  
      size_t diff = static_cast<size_t>(pos - vec.begin());
      ASSERT_EQ(i + 2, diff);
    }
  }
  
  namespace {
  std::vector<std::string> GetTestKeys(size_t size) {
    std::vector<std::string> keys;
    keys.resize(size);
  
    int index = 0;
    for (auto& key : keys) {
      key = "item-" + rocksdb::ToString(index++);
    }
    return keys;
  }
  }  // namespace
  
  template <class TVector>
  void BenchmarkVectorCreationAndInsertion(
      std::string name, size_t ops, size_t item_size,
      const std::vector<typename TVector::value_type>& items) {
    auto env = Env::Default();
  
    int index = 0;
    auto start_time = env->NowNanos();
    auto ops_remaining = ops;
    while(ops_remaining--) {
      TVector v;
      for (size_t i = 0; i < item_size; ++i) {
        v.push_back(items[index++]);
      }
    }
    auto elapsed = env->NowNanos() - start_time;
    cout << "created " << ops << " " << name << " instances:\n\t"
         << "each was inserted with " << item_size << " elements\n\t"
         << "total time elapsed: " << elapsed << " (ns)" << endl;
  }
  
  template <class TVector>
  size_t BenchmarkSequenceAccess(std::string name, size_t ops, size_t elem_size) {
    TVector v;
    for (const auto& item : GetTestKeys(elem_size)) {
      v.push_back(item);
    }
    auto env = Env::Default();
  
    auto ops_remaining = ops;
    auto start_time = env->NowNanos();
    size_t total = 0;
    while (ops_remaining--) {
      auto end = v.end();
      for (auto pos = v.begin(); pos != end; ++pos) {
        total += pos->size();
      }
    }
    auto elapsed = env->NowNanos() - start_time;
    cout << "performed " << ops << " sequence access against " << name << "\n\t"
         << "size: " << elem_size << "\n\t"
         << "total time elapsed: " << elapsed << " (ns)" << endl;
    // HACK avoid compiler's optimization to ignore total
    return total;
  }
  
  // This test case only reports the performance between std::vector<std::string>
  // and autovector<std::string>. We chose string for comparison because in most
  // of our use cases we used std::vector<std::string>.
  TEST_F(AutoVectorTest, PerfBench) {
    // We run same operations for kOps times in order to get a more fair result.
    size_t kOps = 100000;
  
    // Creation and insertion test
    // Test the case when there is:
    //  * no element inserted: internal array of std::vector may not really get
    //    initialize.
    //  * one element inserted: internal array of std::vector must have
    //    initialized.
    //  * kSize elements inserted. This shows the most time we'll spend if we
    //    keep everything in stack.
    //  * 2 * kSize elements inserted. The internal vector of
    //    autovector must have been initialized.
    cout << "=====================================================" << endl;
    cout << "Creation and Insertion Test (value type: std::string)" << endl;
    cout << "=====================================================" << endl;
  
    // pre-generated unique keys
    auto string_keys = GetTestKeys(kOps * 2 * kSize);
    for (auto insertions : { 0ul, 1ul, kSize / 2, kSize, 2 * kSize }) {
      BenchmarkVectorCreationAndInsertion<std::vector<std::string>>(
          "std::vector<std::string>", kOps, insertions, string_keys);
      BenchmarkVectorCreationAndInsertion<autovector<std::string, kSize>>(
          "autovector<std::string>", kOps, insertions, string_keys);
      cout << "-----------------------------------" << endl;
    }
  
    cout << "=====================================================" << endl;
    cout << "Creation and Insertion Test (value type: uint64_t)" << endl;
    cout << "=====================================================" << endl;
  
    // pre-generated unique keys
    std::vector<uint64_t> int_keys(kOps * 2 * kSize);
    for (size_t i = 0; i < kOps * 2 * kSize; ++i) {
      int_keys[i] = i;
    }
    for (auto insertions : { 0ul, 1ul, kSize / 2, kSize, 2 * kSize }) {
      BenchmarkVectorCreationAndInsertion<std::vector<uint64_t>>(
          "std::vector<uint64_t>", kOps, insertions, int_keys);
      BenchmarkVectorCreationAndInsertion<autovector<uint64_t, kSize>>(
        "autovector<uint64_t>", kOps, insertions, int_keys
      );
      cout << "-----------------------------------" << endl;
    }
  
    // Sequence Access Test
    cout << "=====================================================" << endl;
    cout << "Sequence Access Test" << endl;
    cout << "=====================================================" << endl;
    for (auto elem_size : { kSize / 2, kSize, 2 * kSize }) {
      BenchmarkSequenceAccess<std::vector<std::string>>("std::vector", kOps,
                                                        elem_size);
      BenchmarkSequenceAccess<autovector<std::string, kSize>>("autovector", kOps,
                                                              elem_size);
      cout << "-----------------------------------" << endl;
    }
  }
  
  }  // namespace rocksdb
  
  int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
  }
  