a4c97d03f7
Co-authored-by: ZenoWang <wzybuaasoft@163.com> Co-authored-by: zhjc1124 <zhjc1124@gmail.com> Co-authored-by: JiahuaChen <garfieldjia@qq.com>
657 lines
25 KiB
C++
657 lines
25 KiB
C++
/**
|
|
* 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/allocator/page_arena.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();
|
|
}
|