//  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).
//
// Copyright (c) 2011 The LevelDB Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file. See the AUTHORS file for names of contributors.

#include "db/file_indexer.h"
#include <string>
#include "db/dbformat.h"
#include "db/version_edit.h"
#include "port/stack_trace.h"
#include "rocksdb/comparator.h"
#include "test_util/testharness.h"
#include "test_util/testutil.h"

namespace rocksdb {

class IntComparator : public Comparator {
 public:
  int Compare(const Slice& a, const Slice& b) const override {
    assert(a.size() == 8);
    assert(b.size() == 8);
    int64_t diff = *reinterpret_cast<const int64_t*>(a.data()) -
                   *reinterpret_cast<const int64_t*>(b.data());
    if (diff < 0) {
      return -1;
    } else if (diff == 0) {
      return 0;
    } else {
      return 1;
    }
  }

  const char* Name() const override { return "IntComparator"; }

  void FindShortestSeparator(std::string* /*start*/,
                             const Slice& /*limit*/) const override {}

  void FindShortSuccessor(std::string* /*key*/) const override {}
};

class FileIndexerTest : public testing::Test {
 public:
  FileIndexerTest()
      : kNumLevels(4), files(new std::vector<FileMetaData*>[kNumLevels]) {}

  ~FileIndexerTest() override {
    ClearFiles();
    delete[] files;
  }

  void AddFile(int level, int64_t smallest, int64_t largest) {
    auto* f = new FileMetaData();
    f->smallest = IntKey(smallest);
    f->largest = IntKey(largest);
    files[level].push_back(f);
  }

  InternalKey IntKey(int64_t v) {
    return InternalKey(Slice(reinterpret_cast<char*>(&v), 8), 0, kTypeValue);
  }

  void ClearFiles() {
    for (uint32_t i = 0; i < kNumLevels; ++i) {
      for (auto* f : files[i]) {
        delete f;
      }
      files[i].clear();
    }
  }

  void GetNextLevelIndex(const uint32_t level, const uint32_t file_index,
      const int cmp_smallest, const int cmp_largest, int32_t* left_index,
      int32_t* right_index) {
    *left_index = 100;
    *right_index = 100;
    indexer->GetNextLevelIndex(level, file_index, cmp_smallest, cmp_largest,
                               left_index, right_index);
  }

  int32_t left = 100;
  int32_t right = 100;
  const uint32_t kNumLevels;
  IntComparator ucmp;
  FileIndexer* indexer;

  std::vector<FileMetaData*>* files;
};

// Case 0: Empty
TEST_F(FileIndexerTest, Empty) {
  Arena arena;
  indexer = new FileIndexer(&ucmp);
  indexer->UpdateIndex(&arena, 0, files);
  delete indexer;
}

// Case 1: no overlap, files are on the left of next level files
TEST_F(FileIndexerTest, no_overlap_left) {
  Arena arena;
  indexer = new FileIndexer(&ucmp);
  // level 1
  AddFile(1, 100, 200);
  AddFile(1, 300, 400);
  AddFile(1, 500, 600);
  // level 2
  AddFile(2, 1500, 1600);
  AddFile(2, 1601, 1699);
  AddFile(2, 1700, 1800);
  // level 3
  AddFile(3, 2500, 2600);
  AddFile(3, 2601, 2699);
  AddFile(3, 2700, 2800);
  indexer->UpdateIndex(&arena, kNumLevels, files);
  for (uint32_t level = 1; level < 3; ++level) {
    for (uint32_t f = 0; f < 3; ++f) {
      GetNextLevelIndex(level, f, -1, -1, &left, &right);
      ASSERT_EQ(0, left);
      ASSERT_EQ(-1, right);
      GetNextLevelIndex(level, f, 0, -1, &left, &right);
      ASSERT_EQ(0, left);
      ASSERT_EQ(-1, right);
      GetNextLevelIndex(level, f, 1, -1, &left, &right);
      ASSERT_EQ(0, left);
      ASSERT_EQ(-1, right);
      GetNextLevelIndex(level, f, 1, 0, &left, &right);
      ASSERT_EQ(0, left);
      ASSERT_EQ(-1, right);
      GetNextLevelIndex(level, f, 1, 1, &left, &right);
      ASSERT_EQ(0, left);
      ASSERT_EQ(2, right);
    }
  }
  delete indexer;
  ClearFiles();
}

// Case 2: no overlap, files are on the right of next level files
TEST_F(FileIndexerTest, no_overlap_right) {
  Arena arena;
  indexer = new FileIndexer(&ucmp);
  // level 1
  AddFile(1, 2100, 2200);
  AddFile(1, 2300, 2400);
  AddFile(1, 2500, 2600);
  // level 2
  AddFile(2, 1500, 1600);
  AddFile(2, 1501, 1699);
  AddFile(2, 1700, 1800);
  // level 3
  AddFile(3, 500, 600);
  AddFile(3, 501, 699);
  AddFile(3, 700, 800);
  indexer->UpdateIndex(&arena, kNumLevels, files);
  for (uint32_t level = 1; level < 3; ++level) {
    for (uint32_t f = 0; f < 3; ++f) {
      GetNextLevelIndex(level, f, -1, -1, &left, &right);
      ASSERT_EQ(f == 0 ? 0 : 3, left);
      ASSERT_EQ(2, right);
      GetNextLevelIndex(level, f, 0, -1, &left, &right);
      ASSERT_EQ(3, left);
      ASSERT_EQ(2, right);
      GetNextLevelIndex(level, f, 1, -1, &left, &right);
      ASSERT_EQ(3, left);
      ASSERT_EQ(2, right);
      GetNextLevelIndex(level, f, 1, -1, &left, &right);
      ASSERT_EQ(3, left);
      ASSERT_EQ(2, right);
      GetNextLevelIndex(level, f, 1, 0, &left, &right);
      ASSERT_EQ(3, left);
      ASSERT_EQ(2, right);
      GetNextLevelIndex(level, f, 1, 1, &left, &right);
      ASSERT_EQ(3, left);
      ASSERT_EQ(2, right);
    }
  }
  delete indexer;
}

// Case 3: empty L2
TEST_F(FileIndexerTest, empty_L2) {
  Arena arena;
  indexer = new FileIndexer(&ucmp);
  for (uint32_t i = 1; i < kNumLevels; ++i) {
    ASSERT_EQ(0U, indexer->LevelIndexSize(i));
  }
  // level 1
  AddFile(1, 2100, 2200);
  AddFile(1, 2300, 2400);
  AddFile(1, 2500, 2600);
  // level 3
  AddFile(3, 500, 600);
  AddFile(3, 501, 699);
  AddFile(3, 700, 800);
  indexer->UpdateIndex(&arena, kNumLevels, files);
  for (uint32_t f = 0; f < 3; ++f) {
    GetNextLevelIndex(1, f, -1, -1, &left, &right);
    ASSERT_EQ(0, left);
    ASSERT_EQ(-1, right);
    GetNextLevelIndex(1, f, 0, -1, &left, &right);
    ASSERT_EQ(0, left);
    ASSERT_EQ(-1, right);
    GetNextLevelIndex(1, f, 1, -1, &left, &right);
    ASSERT_EQ(0, left);
    ASSERT_EQ(-1, right);
    GetNextLevelIndex(1, f, 1, -1, &left, &right);
    ASSERT_EQ(0, left);
    ASSERT_EQ(-1, right);
    GetNextLevelIndex(1, f, 1, 0, &left, &right);
    ASSERT_EQ(0, left);
    ASSERT_EQ(-1, right);
    GetNextLevelIndex(1, f, 1, 1, &left, &right);
    ASSERT_EQ(0, left);
    ASSERT_EQ(-1, right);
  }
  delete indexer;
  ClearFiles();
}

// Case 4: mixed
TEST_F(FileIndexerTest, mixed) {
  Arena arena;
  indexer = new FileIndexer(&ucmp);
  // level 1
  AddFile(1, 100, 200);
  AddFile(1, 250, 400);
  AddFile(1, 450, 500);
  // level 2
  AddFile(2, 100, 150);  // 0
  AddFile(2, 200, 250);  // 1
  AddFile(2, 251, 300);  // 2
  AddFile(2, 301, 350);  // 3
  AddFile(2, 500, 600);  // 4
  // level 3
  AddFile(3, 0, 50);
  AddFile(3, 100, 200);
  AddFile(3, 201, 250);
  indexer->UpdateIndex(&arena, kNumLevels, files);
  // level 1, 0
  GetNextLevelIndex(1, 0, -1, -1, &left, &right);
  ASSERT_EQ(0, left);
  ASSERT_EQ(0, right);
  GetNextLevelIndex(1, 0, 0, -1, &left, &right);
  ASSERT_EQ(0, left);
  ASSERT_EQ(0, right);
  GetNextLevelIndex(1, 0, 1, -1, &left, &right);
  ASSERT_EQ(0, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(1, 0, 1, 0, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(1, 0, 1, 1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(4, right);
  // level 1, 1
  GetNextLevelIndex(1, 1, -1, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(1, 1, 0, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(1, 1, 1, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(3, right);
  GetNextLevelIndex(1, 1, 1, 0, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(3, right);
  GetNextLevelIndex(1, 1, 1, 1, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(4, right);
  // level 1, 2
  GetNextLevelIndex(1, 2, -1, -1, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(3, right);
  GetNextLevelIndex(1, 2, 0, -1, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(3, right);
  GetNextLevelIndex(1, 2, 1, -1, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(4, right);
  GetNextLevelIndex(1, 2, 1, 0, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(4, right);
  GetNextLevelIndex(1, 2, 1, 1, &left, &right);
  ASSERT_EQ(4, left);
  ASSERT_EQ(4, right);
  // level 2, 0
  GetNextLevelIndex(2, 0, -1, -1, &left, &right);
  ASSERT_EQ(0, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(2, 0, 0, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(2, 0, 1, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(2, 0, 1, 0, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(2, 0, 1, 1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(2, right);
  // level 2, 1
  GetNextLevelIndex(2, 1, -1, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(2, 1, 0, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(1, right);
  GetNextLevelIndex(2, 1, 1, -1, &left, &right);
  ASSERT_EQ(1, left);
  ASSERT_EQ(2, right);
  GetNextLevelIndex(2, 1, 1, 0, &left, &right);
  ASSERT_EQ(2, left);
  ASSERT_EQ(2, right);
  GetNextLevelIndex(2, 1, 1, 1, &left, &right);
  ASSERT_EQ(2, left);
  ASSERT_EQ(2, right);
  // level 2, [2 - 4], no overlap
  for (uint32_t f = 2; f <= 4; ++f) {
    GetNextLevelIndex(2, f, -1, -1, &left, &right);
    ASSERT_EQ(f == 2 ? 2 : 3, left);
    ASSERT_EQ(2, right);
    GetNextLevelIndex(2, f, 0, -1, &left, &right);
    ASSERT_EQ(3, left);
    ASSERT_EQ(2, right);
    GetNextLevelIndex(2, f, 1, -1, &left, &right);
    ASSERT_EQ(3, left);
    ASSERT_EQ(2, right);
    GetNextLevelIndex(2, f, 1, 0, &left, &right);
    ASSERT_EQ(3, left);
    ASSERT_EQ(2, right);
    GetNextLevelIndex(2, f, 1, 1, &left, &right);
    ASSERT_EQ(3, left);
    ASSERT_EQ(2, right);
  }
  delete indexer;
  ClearFiles();
}

}  // namespace rocksdb

int main(int argc, char** argv) {
  rocksdb::port::InstallStackTraceHandler();
  ::testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}