/**
 * Copyright (c) 2021 OceanBase
 * OceanBase CE is licensed under Mulan PubL v2.
 * You can use this software according to the terms and conditions of the Mulan PubL v2.
 * You may obtain a copy of Mulan PubL v2 at:
 *          http://license.coscl.org.cn/MulanPubL-2.0
 * THIS SOFTWARE IS PROVIDED ON AN "AS IS" BASIS, WITHOUT WARRANTIES OF ANY KIND,
 * EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO NON-INFRINGEMENT,
 * MERCHANTABILITY OR FIT FOR A PARTICULAR PURPOSE.
 * See the Mulan PubL v2 for more details.
 */

#include "gtest/gtest.h"
#include "lib/hash/ob_cuckoo_hashmap.h"
#include "lib/hash/ob_hashmap.h"

using namespace oceanbase;
using namespace oceanbase::common;

struct Key {
public:
  Key() : key_(0)
  {}
  explicit Key(int64_t k) : key_(k)
  {}
  uint64_t hash() const
  {
    return murmurhash(&key_, sizeof(key_), 0);
  }
  bool operator==(const Key& other) const
  {
    return key_ == other.key_;
  }
  TO_STRING_KV(K_(key));
  int64_t key_;
};

struct MacroKey {
public:
  static const uint64_t HASH_MAGIC_NUM = 2654435761;
  MacroKey() : key_(0)
  {}
  explicit MacroKey(int64_t k) : key_(k)
  {}
  uint64_t hash() const
  {
    return key_ * HASH_MAGIC_NUM;
  }
  bool operator==(const MacroKey& other) const
  {
    return key_ == other.key_;
  }
  TO_STRING_KV(K_(key));
  int64_t key_;
};

struct BadKey {
public:
  BadKey() : key_(0)
  {}
  explicit BadKey(int64_t k) : key_(k)
  {}
  uint64_t hash() const
  {
    return 1;
  }
  bool operator==(const BadKey& other) const
  {
    return key_ == other.key_;
  }
  TO_STRING_KV(K_(key));
  int64_t key_;
};

struct ModKey {
public:
  ModKey() : key_(0)
  {}
  explicit ModKey(int64_t k) : key_(k)
  {}
  uint64_t hash() const
  {
    return key_ % 7;
  }
  bool operator==(const ModKey& other) const
  {
    return key_ == other.key_;
  }
  TO_STRING_KV(K_(key));
  int64_t key_;
};

struct Value {
public:
  Value() : value_(0)
  {}
  explicit Value(int64_t v) : value_(v)
  {}
  bool operator==(const Value& other) const
  {
    return value_ == other.value_;
  }
  bool operator!=(const Value& other) const
  {
    return !operator==(other);
  }
  TO_STRING_KV(K_(value));
  int64_t value_;
};

class TestCuckooHashMap : public ::testing::Test {
public:
  TestCuckooHashMap();
  virtual ~TestCuckooHashMap();
};

TestCuckooHashMap::TestCuckooHashMap()
{}

TestCuckooHashMap::~TestCuckooHashMap()
{}

TEST_F(TestCuckooHashMap, basic_test)
{
  const int64_t bucket_num = 100;
  hash::ObCuckooHashMap<Key, Value> map;
  ObMalloc allocator;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(value.value_, i);
  }

  // test overwrite
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i + 50);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value, true));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i + 100);
    ASSERT_EQ(OB_HASH_EXIST, map.set(key, value, false));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(value.value_, i + 50);
  }

  for (int64_t i = 50; i < 100; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i + 50, value.value_);
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
  // erase not exist item
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.erase(key, &value));
  }
}

TEST_F(TestCuckooHashMap, test_rehash)
{
  const int64_t bucket_num = 40;
  hash::ObCuckooHashMap<Key, Value> map;
  ObMalloc allocator;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(value.value_, i);
  }

  // test overwrite
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i + 50);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value, true));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(value.value_, i + 50);
  }

  for (int64_t i = 50; i < 100; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i + 50, value.value_);
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
  // erase not exist item
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.erase(key, &value));
  }
}

TEST_F(TestCuckooHashMap, test_bad_hash)
{
  const int64_t bucket_num = 40;
  hash::ObCuckooHashMap<BadKey, Value> map;
  ObMalloc allocator;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i + 50);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(value.value_, i);
  }
  // test overwrite
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value(i);
    ASSERT_EQ(OB_HASH_EXIST, map.set(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value(i + 50);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value, true));
  }
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(i + 50, value.value_);
  }
  // test erase
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i + 50);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.erase(key));
  }
  // test erase success
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i + 50, value.value_);
  }
  for (int64_t i = 0; i < 50; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
}

TEST_F(TestCuckooHashMap, test_bad_hash_big_data)
{
  const int64_t bucket_num = 50;
  const int64_t insert_count = 10000;
  hash::ObCuckooHashMap<BadKey, Value> map;
  ObMalloc allocator(ObModIds::TEST);
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  for (int64_t i = 0; i < insert_count; ++i) {
    BadKey key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (int64_t i = 0; i < insert_count; ++i) {
    BadKey key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(i, value.value_);
  }
  for (int64_t i = 0; i < insert_count / 2; ++i) {
    BadKey key(i);
    Value value(i + 100);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value, true));
  }
  for (int64_t i = 0; i < insert_count / 2; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(i + 100, value.value_);
  }
  for (int64_t i = 0; i < insert_count / 2; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i + 100, value.value_);
  }
  for (int64_t i = 0; i < insert_count / 2; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_HASH_NOT_EXIST, map.get(key, value));
  }
  for (int64_t i = insert_count / 2; i < insert_count; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(i, value.value_);
  }
  for (int64_t i = 0; i < insert_count / 2; ++i) {
    BadKey key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (int64_t i = 0; i < insert_count; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(i, value.value_);
  }
}

TEST_F(TestCuckooHashMap, test_bad_key_iterator)
{
  const int64_t bucket_num = 50;
  const int64_t insert_count = 100;
  hash::ObCuckooHashMap<BadKey, Value> map;
  ObMalloc allocator(ObModIds::TEST);
  int64_t iter_count = 0;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  OB_LOG(INFO, "test bad key iterator");
  for (int64_t i = 0; i < insert_count; ++i) {
    BadKey key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (hash::ObCuckooHashMap<BadKey, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
  }
  iter_count = 0;
  for (int64_t i = 0; i < insert_count / 2; ++i) {
    BadKey key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i, value.value_);
  }
  for (hash::ObCuckooHashMap<BadKey, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
    OB_LOG(INFO, "iter data", K(iter->first));
  }
  ASSERT_EQ(iter_count, insert_count / 2);
}

TEST_F(TestCuckooHashMap, test_normal_key_iterator)
{
  const int64_t bucket_num = 100;
  hash::ObCuckooHashMap<Key, Value> map;
  ObMalloc allocator;
  int64_t iter_count = 0;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(key, value));
    ASSERT_EQ(value.value_, i);
  }
  for (hash::ObCuckooHashMap<Key, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
  }
  ASSERT_EQ(50, iter_count);

  // test overwrite
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i + 50);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value, true));
  }
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i + 100);
    ASSERT_EQ(OB_HASH_EXIST, map.set(key, value, false));
  }
  iter_count = 0;
  for (hash::ObCuckooHashMap<Key, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
  }
  ASSERT_EQ(50, iter_count);

  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i + 50, value.value_);
  }
  iter_count = 0;
  for (hash::ObCuckooHashMap<Key, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
  }
  ASSERT_EQ(0, iter_count);
}

TEST_F(TestCuckooHashMap, test_rehash_iterator)
{
  const int64_t bucket_num = 40;
  hash::ObCuckooHashMap<Key, Value> map;
  ObMalloc allocator;
  int64_t iter_count = 0;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value));
  }
  iter_count = 0;
  for (hash::ObCuckooHashMap<Key, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
  }
  ASSERT_EQ(50, iter_count);

  // test overwrite
  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value(i + 50);
    ASSERT_EQ(OB_SUCCESS, map.set(key, value, true));
  }
  iter_count = 0;
  for (hash::ObCuckooHashMap<Key, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
  }
  ASSERT_EQ(50, iter_count);

  for (int64_t i = 0; i < 50; ++i) {
    Key key(i);
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.erase(key, &value));
    ASSERT_EQ(i + 50, value.value_);
  }
  iter_count = 0;
  for (hash::ObCuckooHashMap<Key, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    Value value;
    ASSERT_EQ(OB_SUCCESS, map.get(iter->first, value));
    ASSERT_EQ(value, iter->second);
    ++iter_count;
  }
  ASSERT_EQ(0, iter_count);
}

int map_random(const int64_t row_num, hash::ObHashMap<ModKey, Value>& map, ModKey& key)
{
  int ret = OB_SUCCESS;
  int64_t iter_count = 1;
  for (hash::ObHashMap<ModKey, Value>::iterator iter = map.begin(); iter != map.end(); ++iter) {
    if (iter_count == row_num) {
      key = iter->first;
      break;
    }
    ++iter_count;
  }
  return ret;
}

int map_insert(const ModKey& mod_key, const Value& value, hash::ObCuckooHashMap<ModKey, Value>& map,
    hash::ObHashMap<ModKey, Value>& right_map)
{
  int ret = OB_SUCCESS;
  Value got_value;
  const int64_t original_size = map.size();
  const int64_t original_right_size = right_map.size();
  if (OB_FAIL(right_map.set_refactored(mod_key, value, true /*overwrite*/))) {
    OB_LOG(WARN, "fail to set to hashmap", K(ret), K(mod_key), K(value));
  } else if (OB_FAIL(map.set(mod_key, value, true /*overwrite*/))) {
    OB_LOG(WARN, "fail to set to cuckoo hashmap", K(ret), K(mod_key), K(value));
  } else if (OB_FAIL(map.get(mod_key, got_value))) {
    OB_LOG(WARN, "fail to get value", K(ret));
  } else if (value != got_value) {
    ret = OB_ERR_UNEXPECTED;
    OB_LOG(WARN, "error unexpected, got value is mismatch", K(value), K(got_value));
  } else if (map.size() != right_map.size()) {
    ret = OB_ERR_UNEXPECTED;
    OB_LOG(WARN,
        "error unexpected, hash map size not match",
        K(ret),
        K(original_size),
        K(original_right_size),
        K(map.size()),
        K(right_map.size()));
  }
  return ret;
}

int map_erase(
    const ModKey& mod_key, hash::ObCuckooHashMap<ModKey, Value>& map, hash::ObHashMap<ModKey, Value>& right_map)
{
  int ret = OB_SUCCESS;
  if (OB_FAIL(right_map.erase_refactored(mod_key))) {
    OB_LOG(WARN, "fail to set to hashmap", K(ret), K(mod_key));
  } else if (OB_FAIL(map.erase(mod_key))) {
    OB_LOG(WARN, "fail to set to cuckoo hashmap", K(ret), K(mod_key));
  } else if (map.size() != right_map.size()) {
    ret = OB_ERR_UNEXPECTED;
    OB_LOG(WARN, "error unexpected, hash map size not match", K(ret), K(map.size()), K(right_map.size()));
  }
  return ret;
}

int map_iterator(hash::ObCuckooHashMap<ModKey, Value>& map, hash::ObHashMap<ModKey, Value>& right_map)
{
  int ret = OB_SUCCESS;
  const int64_t map_size = map.size();
  const int64_t right_map_size = right_map.size();
  if (map_size != right_map_size) {
    ret = OB_ERR_UNEXPECTED;
    OB_LOG(WARN, "map size do not match", K(ret), K(map_size), K(right_map_size));
  } else {
    int64_t iter_count = 0;
    for (hash::ObCuckooHashMap<ModKey, Value>::iterator iter = map.begin(); OB_SUCC(ret) && iter != map.end(); ++iter) {
      Value value;
      if (OB_FAIL(right_map.get_refactored(iter->first, value))) {
        OB_LOG(WARN, "fail to get from right map", K(ret), K(iter->first));
      } else if (iter->second != value) {
        ret = OB_ERR_UNEXPECTED;
        OB_LOG(WARN, "error unexpected, value not match", K(iter->first), K(iter->second), K(value));
      } else {
        ++iter_count;
      }
    }
    if (OB_SUCC(ret)) {
      if (iter_count != map_size) {
        ret = OB_ERR_UNEXPECTED;
        OB_LOG(WARN, "size not match", K(iter_count), K(map_size));
      } else {
        OB_LOG(INFO, "succeed to check map iterator", K(map_size));
      }
    }
  }
  return ret;
}

TEST_F(TestCuckooHashMap, test_random_run)
{
  const int64_t bucket_num = 2;
  hash::ObCuckooHashMap<ModKey, Value> map;
  ObMalloc allocator;
  int64_t iter_count = 0;
  ObRandom random;
  const int64_t start_time = ObTimeUtility::current_time();
  // const int64_t RUN_TIME = 3 * 3600L * 1000 * 1000;
  const int64_t RUN_TIME = 6L * 1000 * 1000;
  int64_t op_types[4][6] = {{0, 0, 0, 1, 2, 3},
      {0, 0, 0, 1, 2, 3},
      {1, 1, 1, 0, 2, 3},
      {1, 1, 1, 0, 2, 3}};  // 0: insert 1: delete 2: iter 3: get
  hash::ObHashMap<ModKey, Value> right_map;
  ASSERT_EQ(OB_SUCCESS, right_map.create(1000000, lib::ObLabel("hashmap")));
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  while (start_time + RUN_TIME > ObTimeUtility::current_time()) {
    const int64_t group_type = random.get(0, 3);
    ModKey key;
    for (int64_t i = 0; i < 100; ++i) {
      const int64_t op_index = random.get(0, 5);
      const int64_t op = op_types[group_type][op_index];
      if (0 == op) {
        key.key_ = random.get(0, 100000);
        Value value(key.key_);
        OB_LOG(INFO, "insert key", K(key), K(value));
        ASSERT_EQ(OB_SUCCESS, map_insert(key, value, map, right_map));
      } else if (1 == op) {
        if (right_map.size() >= 1) {
          const int64_t random_row_num = random.get(1, right_map.size());
          ASSERT_EQ(OB_SUCCESS, map_random(random_row_num, right_map, key));
          OB_LOG(INFO, "erase key", K(key));
          ASSERT_EQ(OB_SUCCESS, map_erase(key, map, right_map));
        }
      } else if (2 == op) {
        ASSERT_EQ(OB_SUCCESS, map_iterator(map, right_map));
      }
    }
  }
}

TEST_F(TestCuckooHashMap, test_rehash_bug)
{
  int64_t macro_id_array[] = {121634816,
      123731968,
      125829120,
      127926272,
      130023424,
      132120576,
      134217728,
      136314880,
      138412032,
      140509184,
      142606336,
      144703488,
      146800640,
      148897792,
      150994944,
      153092096,
      155189248,
      157286400,
      159383552,
      161480704,
      163577856,
      165675008,
      167772160,
      169869312,
      171966464,
      174063616,
      176160768,
      178257920,
      180355072,
      182452224,
      184549376,
      186646528,
      188743680,
      190840832,
      192937984,
      299892736,
      301989888,
      304087040,
      306184192,
      308281344,
      310378496,
      312475648,
      314572800,
      316669952,
      318767104,
      320864256,
      322961408,
      325058560,
      327155712,
      329252864,
      331350016,
      333447168,
      335544320,
      337641472,
      339738624,
      341835776,
      343932928,
      346030080,
      348127232,
      350224384,
      352321536,
      354418688,
      356515840,
      358612992,
      360710144,
      362807296,
      364904448,
      367001600,
      369098752,
      488636416,
      490733568,
      492830720,
      494927872,
      497025024,
      499122176,
      501219328,
      503316480,
      505413632,
      507510784,
      509607936,
      511705088,
      513802240,
      515899392,
      517996544,
      520093696,
      522190848,
      524288000,
      526385152,
      528482304,
      530579456,
      532676608,
      534773760,
      536870912,
      538968064,
      541065216,
      543162368,
      545259520,
      547356672,
      549453824,
      551550976,
      553648128,
      555745280,
      557842432,
      679477248,
      681574400,
      683671552,
      685768704,
      687865856,
      689963008,
      692060160,
      694157312,
      696254464,
      698351616,
      700448768,
      702545920,
      704643072,
      706740224,
      708837376,
      710934528,
      713031680,
      715128832,
      717225984,
      719323136,
      721420288,
      723517440,
      725614592,
      727711744,
      729808896,
      731906048,
      734003200,
      736100352,
      738197504,
      740294656,
      742391808,
      744488960,
      746586112,
      748683264,
      750780416,
      868220928,
      870318080,
      872415232,
      874512384,
      876609536,
      878706688,
      880803840,
      882900992,
      884998144,
      887095296,
      889192448,
      891289600,
      893386752,
      895483904,
      897581056,
      899678208,
      901775360,
      903872512,
      905969664,
      908066816,
      910163968,
      912261120,
      914358272,
      916455424,
      918552576,
      920649728,
      922746880,
      924844032,
      926941184,
      929038336,
      931135488,
      933232640,
      935329792,
      937426944,
      1054867456,
      1056964608,
      1059061760,
      1061158912,
      1063256064,
      1065353216,
      1067450368,
      1069547520,
      1071644672,
      1073741824,
      1075838976,
      1077936128,
      1080033280,
      1082130432,
      1084227584,
      1086324736,
      1088421888,
      1090519040,
      1092616192,
      1094713344,
      1096810496,
      1098907648,
      1101004800,
      1103101952,
      1105199104,
      1107296256,
      1109393408,
      1111490560,
      1113587712,
      1115684864,
      1117782016,
      1119879168,
      1231028224,
      1233125376,
      1235222528,
      1237319680,
      1239416832,
      1241513984,
      1243611136,
      1245708288,
      1247805440,
      1249902592,
      1251999744,
      1254096896,
      1256194048,
      1258291200,
      1260388352,
      1262485504,
      1264582656,
      1266679808,
      1268776960,
      1270874112,
      1272971264,
      1275068416,
      1277165568,
      1279262720,
      1281359872,
      1283457024,
      1285554176,
      1287651328,
      1289748480,
      1291845632,
      1293942784,
      1296039936,
      1298137088,
      1300234240,
      1302331392,
      1419771904,
      1421869056,
      1423966208,
      1426063360,
      1428160512,
      1430257664,
      1432354816,
      1434451968,
      1436549120,
      1438646272,
      1440743424,
      1442840576,
      1444937728,
      1447034880,
      1449132032,
      1451229184,
      1453326336,
      1455423488,
      1457520640,
      1459617792,
      1461714944,
      1463812096,
      1465909248,
      1468006400,
      1470103552,
      1472200704,
      1474297856,
      1476395008,
      1478492160,
      1480589312,
      1482686464,
      1484783616,
      1486880768,
      1589641216,
      1591738368,
      1593835520,
      1595932672,
      1598029824,
      1600126976,
      1602224128,
      1604321280,
      1606418432,
      1608515584,
      1610612736,
      1612709888,
      1614807040,
      1616904192,
      1619001344,
      1621098496,
      1623195648,
      1625292800,
      1627389952,
      1629487104,
      1631584256,
      1633681408,
      1635778560,
      1637875712,
      1639972864,
      1642070016,
      1644167168,
      1646264320,
      1648361472,
      1650458624,
      1652555776,
      1654652928,
      1656750080,
      1765801984,
      1767899136,
      1769996288,
      1772093440,
      1774190592,
      1776287744,
      1778384896,
      1780482048,
      1782579200,
      1784676352,
      1786773504,
      1788870656,
      1790967808,
      1793064960,
      1795162112,
      1797259264,
      1799356416,
      1801453568,
      1803550720,
      1805647872,
      1807745024,
      1809842176,
      1811939328,
      1814036480,
      1816133632,
      1818230784,
      1820327936,
      1822425088,
      1824522240,
      1826619392,
      1828716544,
      1830813696,
      1832910848,
      1944059904,
      1946157056,
      1948254208,
      1950351360,
      1952448512,
      1954545664,
      1956642816,
      1958739968,
      1960837120,
      1962934272,
      1965031424,
      1967128576,
      1969225728,
      1971322880,
      1973420032,
      1975517184,
      1977614336,
      1979711488,
      1981808640,
      1983905792,
      1986002944,
      1988100096,
      1990197248,
      1992294400,
      1994391552,
      1996488704,
      1998585856,
      2000683008,
      2002780160,
      2004877312,
      2006974464,
      2009071616,
      2011168768,
      2124414976,
      2126512128,
      2128609280,
      2130706432,
      2132803584,
      2134900736,
      2136997888,
      2139095040,
      2141192192,
      2143289344,
      2145386496,
      2147483648,
      2149580800,
      2151677952,
      2153775104,
      2155872256,
      2157969408,
      2160066560,
      2162163712,
      2164260864,
      2166358016,
      2168455168,
      2170552320,
      2172649472,
      2174746624,
      2176843776,
      2178940928,
      2181038080,
      2183135232,
      2185232384,
      2187329536,
      2189426688,
      2191523840,
      2313158656,
      2315255808,
      2317352960,
      2319450112,
      2321547264,
      2323644416,
      2325741568,
      2327838720,
      2329935872,
      2332033024,
      2334130176,
      2336227328,
      2338324480,
      2340421632,
      2342518784,
      2344615936,
      2346713088,
      2348810240,
      2350907392,
      2353004544,
      2355101696,
      2357198848,
      2359296000,
      2361393152,
      2363490304,
      2365587456,
      2367684608,
      2369781760,
      2371878912,
      2373976064,
      2376073216,
      2378170368,
      2380267520,
      2382364672,
      2384461824,
      2386558976,
      2388656128,
      2518679552,
      2520776704,
      2522873856,
      2524971008,
      2527068160,
      2529165312,
      2531262464,
      2533359616,
      2535456768,
      2537553920,
      2539651072,
      2541748224,
      2543845376,
      2545942528,
      2548039680,
      2550136832,
      2552233984,
      2554331136,
      2556428288,
      2558525440,
      2560622592,
      2562719744,
      2564816896,
      2566914048,
      2569011200,
      2571108352,
      2573205504,
      2575302656,
      2577399808,
      2579496960,
      2581594112,
      2583691264,
      2585788416,
      2587885568,
      2589982720,
      2592079872,
      2594177024,
      2596274176,
      2717908992,
      2720006144,
      2722103296,
      2724200448,
      2726297600,
      2728394752,
      2730491904,
      2732589056,
      2734686208,
      2736783360,
      2738880512,
      2740977664,
      2743074816,
      2745171968,
      2747269120,
      2749366272,
      2751463424,
      2753560576,
      2755657728,
      2757754880,
      2759852032,
      2761949184,
      2764046336,
      2766143488,
      2768240640,
      2770337792,
      2772434944,
      2774532096,
      2776629248,
      2778726400,
      2780823552,
      2782920704,
      2785017856,
      2787115008,
      2789212160,
      2791309312,
      2910846976,
      2912944128,
      2915041280,
      2917138432,
      2919235584,
      2921332736,
      2923429888,
      2925527040,
      2927624192,
      2929721344,
      2931818496,
      2933915648,
      2936012800,
      2938109952,
      2940207104,
      2942304256,
      2944401408,
      2946498560,
      2948595712,
      2950692864,
      2952790016,
      2954887168,
      2956984320,
      2959081472,
      2961178624,
      2963275776,
      2965372928,
      2967470080,
      2969567232,
      2971664384,
      2973761536,
      2975858688,
      2977955840,
      2980052992,
      2982150144,
      2984247296,
      2986344448,
      104987623424,
      104989720576,
      104991817728,
      104993914880,
      104996012032,
      104998109184,
      105000206336,
      105002303488,
      105004400640,
      105006497792,
      105008594944,
      105010692096,
      105012789248,
      105014886400,
      105016983552,
      105019080704,
      105021177856,
      105023275008,
      105025372160,
      105027469312,
      105029566464,
      105031663616,
      105033760768,
      105035857920,
      105037955072,
      105040052224,
      105042149376,
      105044246528,
      105046343680,
      105048440832,
      105050537984,
      105052635136,
      105054732288,
      105056829440,
      105058926592,
      105061023744,
      105063120896,
      105065218048,
      105067315200};
  hash::ObCuckooHashMap<MacroKey, int64_t> map;
  ObArenaAllocator allocator;
  const int64_t array_size = sizeof(macro_id_array) / sizeof(macro_id_array[0]);
  ASSERT_EQ(OB_SUCCESS, map.create(array_size, &allocator));
  for (int64_t i = 0; i < array_size; ++i) {
    int64_t value = 0;
    ASSERT_EQ(OB_SUCCESS, map.set(MacroKey(macro_id_array[i]), i));
    ASSERT_EQ(OB_SUCCESS, map.get(MacroKey(macro_id_array[i]), value));
  }
  ASSERT_EQ(array_size, map.size());
}

TEST_F(TestCuckooHashMap, test_clear_and_iterate)
{
  const int64_t bucket_num = 2;
  hash::ObCuckooHashMap<int, int> map;
  hash::ObCuckooHashMap<int, int>::iterator iter;
  ObArenaAllocator allocator;
  ASSERT_EQ(OB_SUCCESS, map.create(bucket_num, &allocator));
  ASSERT_EQ(OB_SUCCESS, map.set(0, 0));
  iter = map.begin();
  ASSERT_TRUE(iter != map.end());
  map.clear();
  iter = map.begin();
  ASSERT_TRUE(iter == map.end());
}

int main(int argc, char** argv)
{
  system("rm -f test_cuckoo_hash_map.log*");
  OB_LOGGER.set_log_level("DEBUG");
  OB_LOGGER.set_file_name("test_cuckoo_hash_map.log", true);
  testing::InitGoogleTest(&argc, argv);
  return RUN_ALL_TESTS();
}