ydb/util/generic/hash_ut.cpp

#include "hash.h"
#include "vector.h"
#include "hash_set.h"

#include <library/cpp/testing/common/probe.h>
#include <library/cpp/testing/unittest/registar.h>

#include <utility>
#include <util/str_stl.h>
#include <util/digest/multi.h>

static const char star = 42;

class THashTest: public TTestBase {
    UNIT_TEST_SUITE(THashTest);
    UNIT_TEST(TestHMapConstructorsAndAssignments);
    UNIT_TEST(TestHMap1);
    UNIT_TEST(TestHMapEqualityOperator);
    UNIT_TEST(TestHMMapEqualityOperator);
    UNIT_TEST(TestHMMapConstructorsAndAssignments);
    UNIT_TEST(TestHMMap1);
    UNIT_TEST(TestHMMapHas);
    UNIT_TEST(TestHSetConstructorsAndAssignments);
    UNIT_TEST(TestHSetSize);
    UNIT_TEST(TestHSet2);
    UNIT_TEST(TestHSetEqualityOperator);
    UNIT_TEST(TestHMSetConstructorsAndAssignments);
    UNIT_TEST(TestHMSetSize);
    UNIT_TEST(TestHMSet1);
    UNIT_TEST(TestHMSetEqualityOperator);
    UNIT_TEST(TestHMSetEmplace);
    UNIT_TEST(TestInsertErase);
    UNIT_TEST(TestResizeOnInsertSmartPtrBug)
    UNIT_TEST(TestEmpty);
    UNIT_TEST(TestDefaultConstructor);
    UNIT_TEST(TestSizeOf);
    UNIT_TEST(TestInvariants);
    UNIT_TEST(TestAllocation);
    UNIT_TEST(TestInsertCopy);
    UNIT_TEST(TestEmplace);
    UNIT_TEST(TestEmplaceNoresize);
    UNIT_TEST(TestEmplaceDirect);
    UNIT_TEST(TestTryEmplace);
    UNIT_TEST(TestTryEmplaceCopyKey);
    UNIT_TEST(TestInsertOrAssign);
    UNIT_TEST(TestHMMapEmplace);
    UNIT_TEST(TestHMMapEmplaceNoresize);
    UNIT_TEST(TestHMMapEmplaceDirect);
    UNIT_TEST(TestHSetEmplace);
    UNIT_TEST(TestHSetEmplaceNoresize);
    UNIT_TEST(TestHSetEmplaceDirect);
    UNIT_TEST(TestNonCopyable);
    UNIT_TEST(TestValueInitialization);
    UNIT_TEST(TestAssignmentClear);
    UNIT_TEST(TestReleaseNodes);
    UNIT_TEST(TestAt);
    UNIT_TEST(TestHMapInitializerList);
    UNIT_TEST(TestHMMapInitializerList);
    UNIT_TEST(TestHSetInitializerList);
    UNIT_TEST(TestHMSetInitializerList);
    UNIT_TEST(TestHSetInsertInitializerList);
    UNIT_TEST(TestTupleHash);
    UNIT_TEST(TestStringHash);
    UNIT_TEST_SUITE_END();

    using hmset = THashMultiSet<char, hash<char>, TEqualTo<char>>;

protected:
    void TestHMapConstructorsAndAssignments();
    void TestHMap1();
    void TestHMapEqualityOperator();
    void TestHMMapEqualityOperator();
    void TestHMMapConstructorsAndAssignments();
    void TestHMMap1();
    void TestHMMapHas();
    void TestHSetConstructorsAndAssignments();
    void TestHSetSize();
    void TestHSet2();
    void TestHSetEqualityOperator();
    void TestHMSetConstructorsAndAssignments();
    void TestHMSetSize();
    void TestHMSet1();
    void TestHMSetEqualityOperator();
    void TestHMSetEmplace();
    void TestInsertErase();
    void TestResizeOnInsertSmartPtrBug();
    void TestEmpty();
    void TestDefaultConstructor();
    void TestSizeOf();
    void TestInvariants();
    void TestAllocation();
    void TestInsertCopy();
    void TestEmplace();
    void TestEmplaceNoresize();
    void TestEmplaceDirect();
    void TestTryEmplace();
    void TestTryEmplaceCopyKey();
    void TestInsertOrAssign();
    void TestHSetEmplace();
    void TestHSetEmplaceNoresize();
    void TestHSetEmplaceDirect();
    void TestHMMapEmplace();
    void TestHMMapEmplaceNoresize();
    void TestHMMapEmplaceDirect();
    void TestNonCopyable();
    void TestValueInitialization();
    void TestAssignmentClear();
    void TestReleaseNodes();
    void TestAt();
    void TestHMapInitializerList();
    void TestHMMapInitializerList();
    void TestHSetInitializerList();
    void TestHMSetInitializerList();
    void TestHSetInsertInitializerList();
    void TestTupleHash();
    void TestStringHash();
};

UNIT_TEST_SUITE_REGISTRATION(THashTest);

void THashTest::TestHMapConstructorsAndAssignments() {
    using container = THashMap<TString, int>;

    container c1;
    c1["one"] = 1;
    c1["two"] = 2;

    container c2(c1);

    UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(1, c1.at("one")); /* Note: fails under MSVC since it does not support implicit generation of move constructors. */
    UNIT_ASSERT_VALUES_EQUAL(2, c2.at("two"));

    container c3(std::move(c1));

    UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
    UNIT_ASSERT_VALUES_EQUAL(1, c3.at("one"));

    c2["three"] = 3;
    c3 = c2;

    UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
    UNIT_ASSERT_VALUES_EQUAL(3, c3.at("three"));

    c2["four"] = 4;
    c3 = std::move(c2);

    UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
    UNIT_ASSERT_VALUES_EQUAL(4, c3.at("four"));

    const container c4{
        {"one", 1},
        {"two", 2},
        {"three", 3},
        {"four", 4},
    };

    UNIT_ASSERT_VALUES_EQUAL(4, c4.size());
    UNIT_ASSERT_VALUES_EQUAL(1, c4.at("one"));
    UNIT_ASSERT_VALUES_EQUAL(2, c4.at("two"));
    UNIT_ASSERT_VALUES_EQUAL(3, c4.at("three"));
    UNIT_ASSERT_VALUES_EQUAL(4, c4.at("four"));

    // non-existent values must be zero-initialized
    UNIT_ASSERT_VALUES_EQUAL(c1["nonexistent"], 0);
}

void THashTest::TestHMap1() {
    using maptype = THashMap<char, TString, THash<char>, TEqualTo<char>>;
    maptype m;
    // Store mappings between roman numerals and decimals.
    m['l'] = "50";
    m['x'] = "20"; // Deliberate mistake.
    m['v'] = "5";
    m['i'] = "1";
    UNIT_ASSERT(!strcmp(m['x'].c_str(), "20"));
    m['x'] = "10"; // Correct mistake.
    UNIT_ASSERT(!strcmp(m['x'].c_str(), "10"));

    UNIT_ASSERT(!m.contains('z'));
    UNIT_ASSERT(!strcmp(m['z'].c_str(), ""));
    UNIT_ASSERT(m.contains('z'));

    UNIT_ASSERT(m.count('z') == 1);
    auto p = m.insert(std::pair<const char, TString>('c', TString("100")));

    UNIT_ASSERT(p.second);

    p = m.insert(std::pair<const char, TString>('c', TString("100")));
    UNIT_ASSERT(!p.second);

    //Some iterators compare check, really compile time checks
    maptype::iterator ite(m.begin());
    maptype::const_iterator cite(m.begin());
    cite = m.begin();
    maptype const& cm = m;
    cite = cm.begin();

    UNIT_ASSERT((maptype::const_iterator)ite == cite);
    UNIT_ASSERT(!((maptype::const_iterator)ite != cite));
    UNIT_ASSERT(cite == (maptype::const_iterator)ite);
    UNIT_ASSERT(!(cite != (maptype::const_iterator)ite));
}

void THashTest::TestHMapEqualityOperator() {
    using container = THashMap<TString, int>;

    container base;
    base["one"] = 1;
    base["two"] = 2;

    container c1(base);
    UNIT_ASSERT(c1 == base);

    container c2;
    c2["two"] = 2;
    c2["one"] = 1;
    UNIT_ASSERT(c2 == base);

    c2["three"] = 3;
    UNIT_ASSERT(c2 != base);

    container c3(base);
    c3["one"] = 0;
    UNIT_ASSERT(c3 != base);
}

void THashTest::TestHMMapEqualityOperator() {
    using container = THashMultiMap<TString, int>;
    using value = container::value_type;

    container base;
    base.insert(value("one", 1));
    base.insert(value("one", -1));
    base.insert(value("two", 2));

    container c1(base);
    UNIT_ASSERT(c1 == base);

    container c2;
    c2.insert(value("two", 2));
    c2.insert(value("one", -1));
    c2.insert(value("one", 1));
    UNIT_ASSERT(c2 == base);

    c2.insert(value("three", 3));
    UNIT_ASSERT(c2 != base);

    container c3;
    c3.insert(value("one", 0));
    c3.insert(value("one", -1));
    c3.insert(value("two", 2));
    UNIT_ASSERT(c3 != base);

    container c4;
    c4.insert(value("one", 1));
    c4.insert(value("one", -1));
    c4.insert(value("one", 0));
    c4.insert(value("two", 2));
    UNIT_ASSERT(c3 != base);
}

void THashTest::TestHMMapConstructorsAndAssignments() {
    using container = THashMultiMap<TString, int>;

    container c1;
    c1.insert(container::value_type("one", 1));
    c1.insert(container::value_type("two", 2));

    container c2(c1);

    UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c2.size());

    container c3(std::move(c1));

    UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c3.size());

    c2.insert(container::value_type("three", 3));
    c3 = c2;

    UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(3, c3.size());

    c2.insert(container::value_type("four", 4));
    c3 = std::move(c2);

    UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
}

void THashTest::TestHMMap1() {
    using mmap = THashMultiMap<char, int, THash<char>, TEqualTo<char>>;
    mmap m;

    UNIT_ASSERT(m.count('X') == 0);
    m.insert(std::pair<const char, int>('X', 10)); // Standard way.
    UNIT_ASSERT(m.count('X') == 1);

    m.insert(std::pair<const char, int>('X', 20)); // jbuck: standard way
    UNIT_ASSERT(m.count('X') == 2);

    m.insert(std::pair<const char, int>('Y', 32)); // jbuck: standard way
    mmap::iterator i = m.find('X');                // Find first match.

    UNIT_ASSERT((*i).first == 'X');
    UNIT_ASSERT((*i).second == 10);
    ++i;
    UNIT_ASSERT((*i).first == 'X');
    UNIT_ASSERT((*i).second == 20);

    i = m.find('Y');
    UNIT_ASSERT((*i).first == 'Y');
    UNIT_ASSERT((*i).second == 32);

    i = m.find('Z');
    UNIT_ASSERT(i == m.end());

    size_t count = m.erase('X');
    UNIT_ASSERT(count == 2);

    //Some iterators compare check, really compile time checks
    mmap::iterator ite(m.begin());
    mmap::const_iterator cite(m.begin());

    UNIT_ASSERT((mmap::const_iterator)ite == cite);
    UNIT_ASSERT(!((mmap::const_iterator)ite != cite));
    UNIT_ASSERT(cite == (mmap::const_iterator)ite);
    UNIT_ASSERT(!(cite != (mmap::const_iterator)ite));

    using HMapType = THashMultiMap<size_t, size_t>;
    HMapType hmap;

    //We fill the map to implicitely start a rehash.
    for (size_t counter = 0; counter < 3077; ++counter) {
        hmap.insert(HMapType::value_type(1, counter));
    }

    hmap.insert(HMapType::value_type(12325, 1));
    hmap.insert(HMapType::value_type(12325, 2));

    UNIT_ASSERT(hmap.count(12325) == 2);

    //At this point 23 goes to the same bucket as 12325, it used to reveal a bug.
    hmap.insert(HMapType::value_type(23, 0));

    UNIT_ASSERT(hmap.count(12325) == 2);

    UNIT_ASSERT(hmap.bucket_count() > 3000);
    for (size_t n = 0; n < 10; n++) {
        hmap.clear();
        hmap.insert(HMapType::value_type(1, 2));
    }
    UNIT_ASSERT(hmap.bucket_count() < 30);
}

void THashTest::TestHMMapHas() {
    using mmap = THashMultiMap<char, int, THash<char>, TEqualTo<char>>;
    mmap m;
    m.insert(std::pair<const char, int>('X', 10));
    m.insert(std::pair<const char, int>('X', 20));
    m.insert(std::pair<const char, int>('Y', 32));
    UNIT_ASSERT(m.contains('X'));
    UNIT_ASSERT(m.contains('Y'));
    UNIT_ASSERT(!m.contains('Z'));
}

void THashTest::TestHSetConstructorsAndAssignments() {
    using container = THashSet<int>;

    container c1;
    c1.insert(100);
    c1.insert(200);

    container c2(c1);

    UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
    UNIT_ASSERT(c1.contains(100));
    UNIT_ASSERT(c2.contains(200));

    container c3(std::move(c1));

    UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
    UNIT_ASSERT(c3.contains(100));

    c2.insert(300);
    c3 = c2;

    UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
    UNIT_ASSERT(c3.contains(300));

    c2.insert(400);
    c3 = std::move(c2);

    UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
    UNIT_ASSERT(c3.contains(400));

    container c4 = {1, 2, 3};
    UNIT_ASSERT_VALUES_EQUAL(c4.size(), 3);
    UNIT_ASSERT(c4.contains(1));
    UNIT_ASSERT(c4.contains(2));
    UNIT_ASSERT(c4.contains(3));
}

void THashTest::TestHSetSize() {
    using container = THashSet<int>;

    container c;
    c.insert(100);
    c.insert(200);

    UNIT_ASSERT_VALUES_EQUAL(2, c.size());

    c.insert(200);

    UNIT_ASSERT_VALUES_EQUAL(2, c.size());
}

void THashTest::TestHSet2() {
    THashSet<int, THash<int>, TEqualTo<int>> s;
    auto p = s.insert(42);
    UNIT_ASSERT(p.second);
    UNIT_ASSERT(*(p.first) == 42);

    p = s.insert(42);
    UNIT_ASSERT(!p.second);
}

void THashTest::TestHSetEqualityOperator() {
    using container = THashSet<int>;

    container base;
    base.insert(1);
    base.insert(2);

    container c1(base);
    UNIT_ASSERT(c1 == base);

    c1.insert(1);
    UNIT_ASSERT(c1 == base);

    c1.insert(3);
    UNIT_ASSERT(c1 != base);

    container c2;
    c2.insert(2);
    c2.insert(1);
    UNIT_ASSERT(c2 == base);

    container c3;
    c3.insert(1);
    UNIT_ASSERT(c3 != base);
}

void THashTest::TestHMSetConstructorsAndAssignments() {
    using container = THashMultiSet<int>;

    container c1;
    c1.insert(100);
    c1.insert(200);

    container c2(c1);

    UNIT_ASSERT_VALUES_EQUAL(2, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c2.size());
    UNIT_ASSERT(c1.find(100) != c1.end());
    UNIT_ASSERT(c2.find(200) != c2.end());

    container c3(std::move(c1));

    UNIT_ASSERT_VALUES_EQUAL(0, c1.size());
    UNIT_ASSERT_VALUES_EQUAL(2, c3.size());
    UNIT_ASSERT(c3.find(100) != c3.end());

    c2.insert(300);
    c3 = c2;

    UNIT_ASSERT_VALUES_EQUAL(3, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(3, c3.size());
    UNIT_ASSERT(c3.find(300) != c3.end());

    c2.insert(400);
    c3 = std::move(c2);

    UNIT_ASSERT_VALUES_EQUAL(0, c2.size());
    UNIT_ASSERT_VALUES_EQUAL(4, c3.size());
    UNIT_ASSERT(c3.find(400) != c3.end());
}

void THashTest::TestHMSetSize() {
    using container = THashMultiSet<int>;

    container c;
    c.insert(100);
    c.insert(200);

    UNIT_ASSERT_VALUES_EQUAL(2, c.size());

    c.insert(200);

    UNIT_ASSERT_VALUES_EQUAL(3, c.size());
}

void THashTest::TestHMSet1() {
    hmset s;
    UNIT_ASSERT(s.count(star) == 0);
    s.insert(star);
    UNIT_ASSERT(s.count(star) == 1);
    s.insert(star);
    UNIT_ASSERT(s.count(star) == 2);
    auto i = s.find(char(40));
    UNIT_ASSERT(i == s.end());

    i = s.find(star);
    UNIT_ASSERT(i != s.end());
    UNIT_ASSERT(*i == '*');
    UNIT_ASSERT(s.erase(star) == 2);
}

void THashTest::TestHMSetEqualityOperator() {
    using container = THashMultiSet<int>;

    container base;
    base.insert(1);
    base.insert(1);
    base.insert(2);

    container c1(base);
    UNIT_ASSERT(c1 == base);

    c1.insert(1);
    UNIT_ASSERT(!(c1 == base));

    container c2;
    c2.insert(2);
    c2.insert(1);
    c2.insert(1);
    UNIT_ASSERT(c2 == base);

    container c3;
    c3.insert(1);
    c3.insert(2);
    UNIT_ASSERT(!(c3 == base));

    c3.insert(1);
    UNIT_ASSERT(c3 == base);

    c3.insert(3);
    UNIT_ASSERT(!(c3 == base));
}

void THashTest::TestHMSetEmplace() {
    class TKey: public NTesting::TProbe {
    public:
        TKey(NTesting::TProbeState* state, int key)
            : TProbe(state)
            , Key_(key)
        {
        }

        operator size_t() const {
            return THash<int>()(Key_);
        }

        bool operator==(const TKey& other) const {
            return Key_ == other.Key_;
        }

    private:
        int Key_;
    };

    NTesting::TProbeState state;

    {
        THashMultiSet<TKey> c;
        c.emplace(&state, 1);
        c.emplace(&state, 1);
        c.emplace(&state, 2);

        UNIT_ASSERT_EQUAL(state.CopyAssignments, 0);
        UNIT_ASSERT_EQUAL(state.MoveAssignments, 0);
        UNIT_ASSERT_EQUAL(state.Constructors, 3);
        UNIT_ASSERT_EQUAL(state.MoveConstructors, 0);

        UNIT_ASSERT_EQUAL(c.count(TKey(&state, 1)), 2);
        UNIT_ASSERT_EQUAL(c.count(TKey(&state, 2)), 1);
        UNIT_ASSERT_EQUAL(c.count(TKey(&state, 3)), 0);

        UNIT_ASSERT_EQUAL(state.Constructors, 6);
        UNIT_ASSERT_EQUAL(state.Destructors, 3);
    }

    UNIT_ASSERT_EQUAL(state.CopyAssignments, 0);
    UNIT_ASSERT_EQUAL(state.MoveAssignments, 0);
    UNIT_ASSERT_EQUAL(state.CopyConstructors, 0);
    UNIT_ASSERT_EQUAL(state.MoveConstructors, 0);
    UNIT_ASSERT_EQUAL(state.Constructors, 6);
    UNIT_ASSERT_EQUAL(state.Destructors, 6);
}

void THashTest::TestInsertErase() {
    using hmap = THashMap<TString, size_t, THash<TString>, TEqualTo<TString>>;
    using val_type = hmap::value_type;

    {
        hmap values;

        UNIT_ASSERT(values.insert(val_type("foo", 0)).second);
        UNIT_ASSERT(values.insert(val_type("bar", 0)).second);
        UNIT_ASSERT(values.insert(val_type("abc", 0)).second);

        UNIT_ASSERT(values.erase("foo") == 1);
        UNIT_ASSERT(values.erase("bar") == 1);
        UNIT_ASSERT(values.erase("abc") == 1);
    }

    {
        hmap values;

        UNIT_ASSERT(values.insert(val_type("foo", 0)).second);
        UNIT_ASSERT(values.insert(val_type("bar", 0)).second);
        UNIT_ASSERT(values.insert(val_type("abc", 0)).second);

        UNIT_ASSERT(values.erase("abc") == 1);
        UNIT_ASSERT(values.erase("bar") == 1);
        UNIT_ASSERT(values.erase("foo") == 1);
    }
}

namespace {
    struct TItem: public TSimpleRefCount<TItem> {
        const TString Key;
        const TString Value;

        TItem(const TString& key, const TString& value)
            : Key(key)
            , Value(value)
        {
        }
    };

    using TItemPtr = TIntrusivePtr<TItem>;

    struct TSelectKey {
        const TString& operator()(const TItemPtr& item) const {
            return item->Key;
        }
    };

    using TItemMapBase = THashTable<
        TItemPtr,
        TString,
        THash<TString>,
        TSelectKey,
        TEqualTo<TString>,
        std::allocator<TItemPtr>>;

    struct TItemMap: public TItemMapBase {
        TItemMap()
            : TItemMapBase(1, THash<TString>(), TEqualTo<TString>())
        {
        }

        TItem& Add(const TString& key, const TString& value) {
            insert_ctx ins;
            iterator it = find_i(key, ins);
            if (it == end()) {
                it = insert_direct(new TItem(key, value), ins);
            }
            return **it;
        }
    };
}

void THashTest::TestResizeOnInsertSmartPtrBug() {
    TItemMap map;
    map.Add("key1", "value1");
    map.Add("key2", "value2");
    map.Add("key3", "value3");
    map.Add("key4", "value4");
    map.Add("key5", "value5");
    map.Add("key6", "value6");
    map.Add("key7", "value7");
    TItem& item = map.Add("key8", "value8");
    UNIT_ASSERT_EQUAL(item.Key, "key8");
    UNIT_ASSERT_EQUAL(item.Value, "value8");
}

template <typename T>
static void EmptyAndInsertTest(typename T::value_type v) {
    T c;
    UNIT_ASSERT(!c);
    c.insert(v);
    UNIT_ASSERT(c);
}

void THashTest::TestEmpty() {
    EmptyAndInsertTest<THashSet<int>>(1);
    EmptyAndInsertTest<THashMap<int, int>>(std::pair<int, int>(1, 2));
    EmptyAndInsertTest<THashMultiMap<int, int>>(std::pair<int, int>(1, 2));
}

void THashTest::TestDefaultConstructor() {
    THashSet<int> set;

    UNIT_ASSERT(set.begin() == set.end());

    UNIT_ASSERT(set.find(0) == set.end());

    auto range = set.equal_range(0);
    UNIT_ASSERT(range.first == range.second);
}

void THashTest::TestSizeOf() {
    /* This test checks that we don't waste memory when all functors passed to
     * THashTable are empty. It does rely on knowledge of THashTable internals,
     * so if those change, the test will have to be adjusted accordingly. */

    size_t expectedSize = sizeof(uintptr_t) + 3 * sizeof(size_t);

    UNIT_ASSERT_VALUES_EQUAL(sizeof(THashMap<int, int>), expectedSize);
    UNIT_ASSERT_VALUES_EQUAL(sizeof(THashMap<std::pair<int, int>, std::pair<int, int>>), expectedSize);
}

void THashTest::TestInvariants() {
    std::set<int> reference_set;
    THashSet<int> set;

    for (int i = 0; i < 1000; i++) {
        set.insert(i);
        reference_set.insert(i);
    }
    UNIT_ASSERT_VALUES_EQUAL(set.size(), 1000);

    int count0 = 0;
    for (int i = 0; i < 1000; i++) {
        count0 += (set.find(i) != set.end()) ? 1 : 0;
    }
    UNIT_ASSERT_VALUES_EQUAL(count0, 1000);

    int count1 = 0;
    for (auto pos = set.begin(); pos != set.end(); pos++) {
        ++count1;
    }
    UNIT_ASSERT_VALUES_EQUAL(count1, 1000);

    int count2 = 0;
    for (const int& value : set) {
        count2 += (reference_set.find(value) != reference_set.end()) ? 1 : 0;
    }
    UNIT_ASSERT_VALUES_EQUAL(count2, 1000);
}

struct TAllocatorCounters {
    TAllocatorCounters()
        : Allocations(0)
        , Deallocations(0)
    {
    }

    ~TAllocatorCounters() {
        std::allocator<char> allocator;

        /* Release whatever was (intentionally) leaked. */
        for (const auto& chunk : Chunks) {
            allocator.deallocate(static_cast<char*>(chunk.first), chunk.second);
        }
    }

    size_t Allocations;
    size_t Deallocations;
    TSet<std::pair<void*, size_t>> Chunks;
};

template <class T>
class TCountingAllocator: public std::allocator<T> {
    using base_type = std::allocator<T>;

public:
    using size_type = typename base_type::size_type;

    template <class Other>
    struct rebind {
        using other = TCountingAllocator<Other>;
    };

    TCountingAllocator()
        : Counters_(nullptr)
    {
    }

    TCountingAllocator(TAllocatorCounters* counters)
        : Counters_(counters)
    {
        Y_ASSERT(counters);
    }

    template <class Other>
    TCountingAllocator(const TCountingAllocator<Other>& other)
        : Counters_(other.Counters)
    {
    }

    T* allocate(size_type n) {
        auto result = base_type::allocate(n);

        if (Counters_) {
            ++Counters_->Allocations;
            Counters_->Chunks.emplace(result, n * sizeof(T));
        }

        return result;
    }

    void deallocate(T* p, size_type n) {
        if (Counters_) {
            ++Counters_->Deallocations;
            Counters_->Chunks.erase(std::make_pair(p, n * sizeof(T)));
        }

        base_type::deallocate(p, n);
    }

private:
    TAllocatorCounters* Counters_;
};

void THashTest::TestAllocation() {
    TAllocatorCounters counters;

    using int_set = THashSet<int, THash<int>, TEqualTo<int>, TCountingAllocator<int>>;

    {
        int_set set0(&counters);
        int_set set1(set0);
        set0.clear();
        int_set set2(&counters);
        set2 = set1;
        UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 0); /* Copying around null sets should not trigger allocations. */

        set0.insert(0);
        UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 2); /* One for buckets array, one for a new node. */

        set0.clear();
        set1 = set0;
        int_set set3(set0);
        UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 2); /* Copying from an empty set with allocated buckets should not trigger allocations. */

        for (int i = 0; i < 1000; i++) {
            set0.insert(i);
        }
        size_t allocations = counters.Allocations;
        set0.clear();
        UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, allocations); /* clear() should not trigger allocations. */
    }

    UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, counters.Deallocations);
}

template <int Value>
class TNonCopyableInt {
public:
    explicit TNonCopyableInt(int) {
    }

    TNonCopyableInt() = delete;
    TNonCopyableInt(const TNonCopyableInt&) = delete;
    TNonCopyableInt(TNonCopyable&&) = delete;
    TNonCopyableInt& operator=(const TNonCopyable&) = delete;
    TNonCopyableInt& operator=(TNonCopyable&&) = delete;

    operator int() const {
        return Value;
    }
};

void THashTest::TestInsertCopy() {
    THashMap<int, int> hash;

    /* Insertion should not make copies of the provided key. */
    hash[TNonCopyableInt<0>(0)] = 0;
}

void THashTest::TestEmplace() {
    using hash_t = THashMap<int, TNonCopyableInt<0>>;
    hash_t hash;
    hash.emplace(std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(0));
    auto it = hash.find(1);
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(it->second), 0);
}

void THashTest::TestEmplaceNoresize() {
    using hash_t = THashMap<int, TNonCopyableInt<0>>;
    hash_t hash;
    hash.reserve(1);
    hash.emplace_noresize(std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(0));
    auto it = hash.find(1);
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(it->second), 0);
}

void THashTest::TestEmplaceDirect() {
    using hash_t = THashMap<int, TNonCopyableInt<0>>;
    hash_t hash;
    hash_t::insert_ctx ins;
    hash.find(1, ins);
    hash.emplace_direct(ins, std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(0));
    auto it = hash.find(1);
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(it->second), 0);
}

void THashTest::TestTryEmplace() {
    static unsigned counter = 0u;

    struct TCountConstruct {
        explicit TCountConstruct(int v)
            : value(v)
        {
            ++counter;
        }
        TCountConstruct(const TCountConstruct&) = delete;
        int value;
    };

    THashMap<int, TCountConstruct> hash;
    {
        // try_emplace does not copy key if key is rvalue
        auto r = hash.try_emplace(TNonCopyableInt<0>(0), 1);
        UNIT_ASSERT(r.second);
        UNIT_ASSERT_VALUES_EQUAL(1, counter);
        UNIT_ASSERT_VALUES_EQUAL(1, r.first->second.value);
    }
    {
        auto r = hash.try_emplace(0, 2);
        UNIT_ASSERT(!r.second);
        UNIT_ASSERT_VALUES_EQUAL(1, counter);
        UNIT_ASSERT_VALUES_EQUAL(1, r.first->second.value);
    }
}

void THashTest::TestTryEmplaceCopyKey() {
    static unsigned counter = 0u;

    struct TCountCopy {
        explicit TCountCopy(int i)
            : Value(i)
        {
        }
        TCountCopy(const TCountCopy& other)
            : Value(other.Value)
        {
            ++counter;
        }

        operator int() const {
            return Value;
        }

        int Value;
    };

    THashMap<TCountCopy, TNonCopyableInt<0>> hash;
    TCountCopy key(1);
    {
        // try_emplace copy key if key is lvalue
        auto r = hash.try_emplace(key, 1);
        UNIT_ASSERT(r.second);
        UNIT_ASSERT_VALUES_EQUAL(1, counter);
    }
    {
        // no insert - no copy
        auto r = hash.try_emplace(key, 2);
        UNIT_ASSERT(!r.second);
        UNIT_ASSERT_VALUES_EQUAL(1, counter);
    }
}

void THashTest::TestInsertOrAssign() {
    static int constructorCounter = 0;
    static int assignmentCounter = 0;

    struct TCountConstruct {
        explicit TCountConstruct(int v)
            : Value(v)
        {
            ++constructorCounter;
        }

        TCountConstruct& operator=(int v) {
            Value = v;
            ++assignmentCounter;
            return *this;
        }

        TCountConstruct(const TCountConstruct&) = delete;
        int Value;
    };

    THashMap<int, TCountConstruct> hash;
    {
        auto r = hash.insert_or_assign(TNonCopyableInt<4>(4), 1);
        UNIT_ASSERT(r.second);
        UNIT_ASSERT_VALUES_EQUAL(1, hash.size());
        UNIT_ASSERT_VALUES_EQUAL(1, constructorCounter);
        UNIT_ASSERT_VALUES_EQUAL(0, assignmentCounter);
        UNIT_ASSERT_VALUES_EQUAL(1, r.first->second.Value);
    }
    {
        auto r = hash.insert_or_assign(TNonCopyableInt<4>(4), 5);
        UNIT_ASSERT(!r.second);
        UNIT_ASSERT_VALUES_EQUAL(1, hash.size());
        UNIT_ASSERT_VALUES_EQUAL(1, constructorCounter);
        UNIT_ASSERT_VALUES_EQUAL(1, assignmentCounter);
        UNIT_ASSERT_VALUES_EQUAL(5, r.first->second.Value);
    }
    {
        constexpr int iterations = 200;
        for (int iteration = 0; iteration < iterations; ++iteration) {
            hash.insert_or_assign(iteration, iteration);
        }
        UNIT_ASSERT_VALUES_EQUAL(iterations, hash.size());
        UNIT_ASSERT_VALUES_EQUAL(iterations, constructorCounter);
        UNIT_ASSERT_VALUES_EQUAL(2, assignmentCounter);
        UNIT_ASSERT_VALUES_EQUAL(4, hash.at(4).Value);
        UNIT_ASSERT_VALUES_EQUAL(44, hash.at(44).Value);
    }
}

void THashTest::TestHMMapEmplace() {
    using hash_t = THashMultiMap<int, TNonCopyableInt<0>>;
    hash_t hash;
    hash.emplace(std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(0));
    auto it = hash.find(1);
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(it->second), 0);
}

void THashTest::TestHMMapEmplaceNoresize() {
    using hash_t = THashMultiMap<int, TNonCopyableInt<0>>;
    hash_t hash;
    hash.reserve(1);
    hash.emplace_noresize(std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(0));
    auto it = hash.find(1);
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(it->second), 0);
}

void THashTest::TestHMMapEmplaceDirect() {
    using hash_t = THashMultiMap<int, TNonCopyableInt<0>>;
    hash_t hash;
    hash_t::insert_ctx ins;
    hash.find(1, ins);
    hash.emplace_direct(ins, std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(0));
    auto it = hash.find(1);
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(it->second), 0);
}

void THashTest::TestHSetEmplace() {
    using hash_t = THashSet<TNonCopyableInt<0>, THash<int>, TEqualTo<int>>;
    hash_t hash;
    UNIT_ASSERT(!hash.contains(0));
    hash.emplace(0);
    UNIT_ASSERT(hash.contains(0));
    UNIT_ASSERT(!hash.contains(1));
}

void THashTest::TestHSetEmplaceNoresize() {
    using hash_t = THashSet<TNonCopyableInt<0>, THash<int>, TEqualTo<int>>;
    hash_t hash;
    hash.reserve(1);
    UNIT_ASSERT(!hash.contains(0));
    hash.emplace_noresize(0);
    UNIT_ASSERT(hash.contains(0));
    UNIT_ASSERT(!hash.contains(1));
}

void THashTest::TestHSetEmplaceDirect() {
    using hash_t = THashSet<TNonCopyableInt<0>, THash<int>, TEqualTo<int>>;
    hash_t hash;
    UNIT_ASSERT(!hash.contains(0));
    hash_t::insert_ctx ins;
    hash.find(0, ins);
    hash.emplace_direct(ins, 1);
    UNIT_ASSERT(hash.contains(0));
    UNIT_ASSERT(!hash.contains(1));
}

void THashTest::TestNonCopyable() {
    struct TValue: public TNonCopyable {
        int value;
        TValue(int _value = 0)
            : value(_value)
        {
        }
        operator int() {
            return value;
        }
    };

    THashMap<int, TValue> hash;
    hash.emplace(std::piecewise_construct, std::forward_as_tuple(1), std::forward_as_tuple(5));
    auto&& value = hash[1];
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(value), 5);
    auto&& not_inserted = hash[2];
    UNIT_ASSERT_VALUES_EQUAL(static_cast<int>(not_inserted), 0);
}

void THashTest::TestValueInitialization() {
    THashMap<int, int> hash;

    int& value = hash[0];

    /* Implicitly inserted values should be value-initialized. */
    UNIT_ASSERT_VALUES_EQUAL(value, 0);
}

void THashTest::TestAssignmentClear() {
    /* This one tests that assigning an empty hash resets the buckets array.
     * See operator= for details. */

    THashMap<int, int> hash;
    size_t emptyBucketCount = hash.bucket_count();

    for (int i = 0; i < 100; i++) {
        hash[i] = i;
    }

    hash = THashMap<int, int>();

    UNIT_ASSERT_VALUES_EQUAL(hash.bucket_count(), emptyBucketCount);
}

void THashTest::TestReleaseNodes() {
    TAllocatorCounters counters;
    using TIntSet = THashSet<int, THash<int>, TEqualTo<int>, TCountingAllocator<int>>;

    TIntSet set(&counters);
    for (int i = 0; i < 3; i++) {
        set.insert(i);
    }
    UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 4);

    set.release_nodes();
    UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 4);
    UNIT_ASSERT_VALUES_EQUAL(set.size(), 0);

    for (int i = 10; i < 13; i++) {
        set.insert(i);
    }
    UNIT_ASSERT_VALUES_EQUAL(counters.Allocations, 7);
    UNIT_ASSERT(set.contains(10));
    UNIT_ASSERT(!set.contains(0));

    set.basic_clear();
    UNIT_ASSERT_VALUES_EQUAL(counters.Deallocations, 3);

    TIntSet set2;
    set2.release_nodes();
    set2.insert(1);
    UNIT_ASSERT_VALUES_EQUAL(set2.size(), 1);
}

void THashTest::TestAt() {
#define TEST_AT_THROWN_EXCEPTION(SRC_TYPE, DST_TYPE, KEY_TYPE, KEY, MESSAGE)                                                                               \
    {                                                                                                                                                      \
        THashMap<SRC_TYPE, DST_TYPE> testMap;                                                                                                              \
        try {                                                                                                                                              \
            KEY_TYPE testKey = KEY;                                                                                                                        \
            testMap.at(testKey);                                                                                                                           \
            UNIT_ASSERT_C(false, "THashMap::at(\"" << KEY << "\") should throw");                                                                          \
        } catch (const yexception& e) {                                                                                                                    \
            UNIT_ASSERT_C(e.AsStrBuf().Contains(MESSAGE), "Incorrect exception description: got \"" << e.what() << "\", expected: \"" << MESSAGE << "\""); \
        } catch (...) {                                                                                                                                    \
            UNIT_ASSERT_C(false, "THashMap::at(\"" << KEY << "\") should throw yexception");                                                               \
        }                                                                                                                                                  \
    }

    TEST_AT_THROWN_EXCEPTION(TString, TString, TString, "111", "111");
    TEST_AT_THROWN_EXCEPTION(TString, TString, const TString, "111", "111");
    TEST_AT_THROWN_EXCEPTION(TString, TString, TStringBuf, "111", "111");
    TEST_AT_THROWN_EXCEPTION(TString, TString, const TStringBuf, "111", "111");
    TEST_AT_THROWN_EXCEPTION(TStringBuf, TStringBuf, const char*, "111", "111");
    TEST_AT_THROWN_EXCEPTION(int, int, short, 11, "11");
    TEST_AT_THROWN_EXCEPTION(int, int, int, -1, "-1");
    TEST_AT_THROWN_EXCEPTION(int, int, long, 111, "111");
    TEST_AT_THROWN_EXCEPTION(int, int, long long, -1000000000000ll, "-1000000000000");
    TEST_AT_THROWN_EXCEPTION(int, int, unsigned short, 11, "11");
    TEST_AT_THROWN_EXCEPTION(int, int, unsigned int, 2, "2");
    TEST_AT_THROWN_EXCEPTION(int, int, unsigned long, 131, "131");
    TEST_AT_THROWN_EXCEPTION(int, int, unsigned long long, 1000000000000ll, "1000000000000");

    char key[] = {11, 12, 0, 1, 2, 11, 0};
    TEST_AT_THROWN_EXCEPTION(TString, TString, char*, key, "\\x0B\\x0C");
    TEST_AT_THROWN_EXCEPTION(TString, TString, TStringBuf, TStringBuf(key, sizeof(key) - 1), "\\x0B\\x0C\\0\\1\\2\\x0B");

#undef TEST_AT_THROWN_EXCEPTION
}

void THashTest::TestHMapInitializerList() {
    THashMap<TString, TString> h1 = {{"foo", "bar"}, {"bar", "baz"}, {"baz", "qux"}};
    THashMap<TString, TString> h2;
    h2.insert(std::pair<TString, TString>("foo", "bar"));
    h2.insert(std::pair<TString, TString>("bar", "baz"));
    h2.insert(std::pair<TString, TString>("baz", "qux"));
    UNIT_ASSERT_EQUAL(h1, h2);
}

void THashTest::TestHMMapInitializerList() {
    THashMultiMap<TString, TString> h1 = {
        {"foo", "bar"},
        {"foo", "baz"},
        {"baz", "qux"}};
    THashMultiMap<TString, TString> h2;
    h2.insert(std::pair<TString, TString>("foo", "bar"));
    h2.insert(std::pair<TString, TString>("foo", "baz"));
    h2.insert(std::pair<TString, TString>("baz", "qux"));
    UNIT_ASSERT_EQUAL(h1, h2);
}

void THashTest::TestHSetInitializerList() {
    THashSet<TString> h1 = {"foo", "bar", "baz"};
    THashSet<TString> h2;
    h2.insert("foo");
    h2.insert("bar");
    h2.insert("baz");
    UNIT_ASSERT_EQUAL(h1, h2);
}

void THashTest::TestHMSetInitializerList() {
    THashMultiSet<TString> h1 = {"foo", "foo", "bar", "baz"};
    THashMultiSet<TString> h2;
    h2.insert("foo");
    h2.insert("foo");
    h2.insert("bar");
    h2.insert("baz");
    UNIT_ASSERT_EQUAL(h1, h2);
}

namespace {
    struct TFoo {
        int A;
        int B;

        bool operator==(const TFoo& o) const {
            return A == o.A && B == o.B;
        }
    };
}

template <>
struct THash<TFoo> {
    size_t operator()(const TFoo& v) const {
        return v.A ^ v.B;
    }
};

template <>
void Out<TFoo>(IOutputStream& o, const TFoo& v) {
    o << '{' << v.A << ';' << v.B << '}';
}

void THashTest::TestHSetInsertInitializerList() {
    {
        const THashSet<int> x = {1};
        THashSet<int> y;
        y.insert({1});
        UNIT_ASSERT_VALUES_EQUAL(x, y);
    }
    {
        const THashSet<int> x = {1, 2};
        THashSet<int> y;
        y.insert({1, 2});
        UNIT_ASSERT_VALUES_EQUAL(x, y);
    }
    {
        const THashSet<int> x = {1, 2, 3, 4, 5};
        THashSet<int> y;
        y.insert({
            1,
            2,
            3,
            4,
            5,
        });
        UNIT_ASSERT_VALUES_EQUAL(x, y);
    }
    {
        const THashSet<TFoo> x = {{1, 2}};
        THashSet<TFoo> y;
        y.insert({{1, 2}});
        UNIT_ASSERT_VALUES_EQUAL(x, y);
    }
    {
        const THashSet<TFoo> x = {{1, 2}, {3, 4}};
        THashSet<TFoo> y;
        y.insert({{1, 2}, {3, 4}});
        UNIT_ASSERT_VALUES_EQUAL(x, y);
    }
}

/*
* Sequence for MultiHash is reversed as it calculates hash as
* f(head:tail) = f(tail)xHash(head)
*/
void THashTest::TestTupleHash() {
    std::tuple<int, int> tuple{1, 3};
    UNIT_ASSERT_VALUES_EQUAL(THash<decltype(tuple)>()(tuple), MultiHash(3, 1));

    /*
    * This thing checks that we didn't break STL code
    * See https://a.yandex-team.ru/arc/commit/2864838#comment-401
    * for example
    */
    struct A {
        A Foo(const std::tuple<A, float>& v) {
            return std::get<A>(v);
        }
    };
}

void THashTest::TestStringHash() {
    // Make sure that different THash<> variants behave in the same way
    const size_t expected = ComputeHash(TString("hehe"));
    UNIT_ASSERT_VALUES_EQUAL(ComputeHash("hehe"), expected);              // char[5]
    UNIT_ASSERT_VALUES_EQUAL(ComputeHash("hehe"sv), expected);            // std::string_view
    UNIT_ASSERT_VALUES_EQUAL(ComputeHash(TStringBuf("hehe")), expected);  // TStringBuf
    UNIT_ASSERT_VALUES_EQUAL(ComputeHash<const char*>("hehe"), expected); // const char*
}