intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 1271 insertions, 0 deletions

diff --git a/util/generic/hash_ut.cpp b/util/generic/hash_ut.cpp
new file mode 100644
index 00000000000..0551d587708
--- /dev/null
+++ b/util/generic/hash_ut.cpp
@@ -0,0 +1,1271 @@
+#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(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_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 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();
+};
+
+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::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);
+        }
+    };
+}