aboutsummaryrefslogtreecommitdiffstats
path: root/library/cpp/containers
diff options
context:
space:
mode:
authorsnaury <snaury@ydb.tech>2023-04-20 10:10:21 +0300
committersnaury <snaury@ydb.tech>2023-04-20 10:10:21 +0300
commit6e494baf9715cc400ed74aa23f8f99ec25f383e9 (patch)
tree9ba554a7e8e9df4753d9cc8b684f1e7162448ce4 /library/cpp/containers
parentd5daa23faa0fc9a78178ed324b9bb3bf7525734d (diff)
downloadydb-6e494baf9715cc400ed74aa23f8f99ec25f383e9.tar.gz
Remove dependency on library/cpp/containers/flat_hash
Diffstat (limited to 'library/cpp/containers')
-rw-r--r--library/cpp/containers/CMakeLists.txt1
-rw-r--r--library/cpp/containers/flat_hash/CMakeLists.darwin-x86_64.txt30
-rw-r--r--library/cpp/containers/flat_hash/CMakeLists.linux-aarch64.txt31
-rw-r--r--library/cpp/containers/flat_hash/CMakeLists.linux-x86_64.txt31
-rw-r--r--library/cpp/containers/flat_hash/CMakeLists.txt17
-rw-r--r--library/cpp/containers/flat_hash/CMakeLists.windows-x86_64.txt30
-rw-r--r--library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp180
-rw-r--r--library/cpp/containers/flat_hash/flat_hash.cpp1
-rw-r--r--library/cpp/containers/flat_hash/flat_hash.h120
-rw-r--r--library/cpp/containers/flat_hash/fuzz/dense_map_fuzz/fuzz.cpp60
-rw-r--r--library/cpp/containers/flat_hash/fuzz/flat_map_fuzz/fuzz.cpp53
-rw-r--r--library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.cpp1
-rw-r--r--library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.h223
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/container.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/container.h66
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/iterator.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/iterator.h20
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/size_fitter.h34
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/concepts/value_marker.h34
-rw-r--r--library/cpp/containers/flat_hash/lib/containers.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/containers.h314
-rw-r--r--library/cpp/containers/flat_hash/lib/expanders.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/expanders.h25
-rw-r--r--library/cpp/containers/flat_hash/lib/iterator.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/iterator.h99
-rw-r--r--library/cpp/containers/flat_hash/lib/map.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/map.h233
-rw-r--r--library/cpp/containers/flat_hash/lib/probings.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/probings.h45
-rw-r--r--library/cpp/containers/flat_hash/lib/set.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/set.h147
-rw-r--r--library/cpp/containers/flat_hash/lib/size_fitters.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/size_fitters.h47
-rw-r--r--library/cpp/containers/flat_hash/lib/table.cpp1
-rw-r--r--library/cpp/containers/flat_hash/lib/table.h314
-rw-r--r--library/cpp/containers/flat_hash/lib/value_markers.cpp0
-rw-r--r--library/cpp/containers/flat_hash/lib/value_markers.h130
-rw-r--r--library/cpp/containers/flat_hash/ut/containers_ut.cpp410
-rw-r--r--library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp272
-rw-r--r--library/cpp/containers/flat_hash/ut/iterator_ut.cpp85
-rw-r--r--library/cpp/containers/flat_hash/ut/probings_ut.cpp34
-rw-r--r--library/cpp/containers/flat_hash/ut/size_fitters_ut.cpp51
-rw-r--r--library/cpp/containers/flat_hash/ut/table_ut.cpp411
45 files changed, 0 insertions, 3561 deletions
diff --git a/library/cpp/containers/CMakeLists.txt b/library/cpp/containers/CMakeLists.txt
index b782222041..43fcbe8346 100644
--- a/library/cpp/containers/CMakeLists.txt
+++ b/library/cpp/containers/CMakeLists.txt
@@ -13,7 +13,6 @@ add_subdirectory(bitseq)
add_subdirectory(compact_vector)
add_subdirectory(comptrie)
add_subdirectory(disjoint_interval_tree)
-add_subdirectory(flat_hash)
add_subdirectory(intrusive_avl_tree)
add_subdirectory(intrusive_rb_tree)
add_subdirectory(paged_vector)
diff --git a/library/cpp/containers/flat_hash/CMakeLists.darwin-x86_64.txt b/library/cpp/containers/flat_hash/CMakeLists.darwin-x86_64.txt
deleted file mode 100644
index 17eb5a21b7..0000000000
--- a/library/cpp/containers/flat_hash/CMakeLists.darwin-x86_64.txt
+++ /dev/null
@@ -1,30 +0,0 @@
-
-# This file was generated by the build system used internally in the Yandex monorepo.
-# Only simple modifications are allowed (adding source-files to targets, adding simple properties
-# like target_include_directories). These modifications will be ported to original
-# ya.make files by maintainers. Any complex modifications which can't be ported back to the
-# original buildsystem will not be accepted.
-
-
-
-add_library(cpp-containers-flat_hash)
-target_link_libraries(cpp-containers-flat_hash PUBLIC
- contrib-libs-cxxsupp
- yutil
-)
-target_sources(cpp-containers-flat_hash PRIVATE
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/flat_hash.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/container.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/containers.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/expanders.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/map.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/probings.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/set.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/size_fitters.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/table.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/value_markers.cpp
-)
diff --git a/library/cpp/containers/flat_hash/CMakeLists.linux-aarch64.txt b/library/cpp/containers/flat_hash/CMakeLists.linux-aarch64.txt
deleted file mode 100644
index d5ab2865c7..0000000000
--- a/library/cpp/containers/flat_hash/CMakeLists.linux-aarch64.txt
+++ /dev/null
@@ -1,31 +0,0 @@
-
-# This file was generated by the build system used internally in the Yandex monorepo.
-# Only simple modifications are allowed (adding source-files to targets, adding simple properties
-# like target_include_directories). These modifications will be ported to original
-# ya.make files by maintainers. Any complex modifications which can't be ported back to the
-# original buildsystem will not be accepted.
-
-
-
-add_library(cpp-containers-flat_hash)
-target_link_libraries(cpp-containers-flat_hash PUBLIC
- contrib-libs-linux-headers
- contrib-libs-cxxsupp
- yutil
-)
-target_sources(cpp-containers-flat_hash PRIVATE
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/flat_hash.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/container.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/containers.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/expanders.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/map.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/probings.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/set.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/size_fitters.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/table.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/value_markers.cpp
-)
diff --git a/library/cpp/containers/flat_hash/CMakeLists.linux-x86_64.txt b/library/cpp/containers/flat_hash/CMakeLists.linux-x86_64.txt
deleted file mode 100644
index d5ab2865c7..0000000000
--- a/library/cpp/containers/flat_hash/CMakeLists.linux-x86_64.txt
+++ /dev/null
@@ -1,31 +0,0 @@
-
-# This file was generated by the build system used internally in the Yandex monorepo.
-# Only simple modifications are allowed (adding source-files to targets, adding simple properties
-# like target_include_directories). These modifications will be ported to original
-# ya.make files by maintainers. Any complex modifications which can't be ported back to the
-# original buildsystem will not be accepted.
-
-
-
-add_library(cpp-containers-flat_hash)
-target_link_libraries(cpp-containers-flat_hash PUBLIC
- contrib-libs-linux-headers
- contrib-libs-cxxsupp
- yutil
-)
-target_sources(cpp-containers-flat_hash PRIVATE
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/flat_hash.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/container.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/containers.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/expanders.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/map.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/probings.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/set.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/size_fitters.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/table.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/value_markers.cpp
-)
diff --git a/library/cpp/containers/flat_hash/CMakeLists.txt b/library/cpp/containers/flat_hash/CMakeLists.txt
deleted file mode 100644
index f8b31df0c1..0000000000
--- a/library/cpp/containers/flat_hash/CMakeLists.txt
+++ /dev/null
@@ -1,17 +0,0 @@
-
-# This file was generated by the build system used internally in the Yandex monorepo.
-# Only simple modifications are allowed (adding source-files to targets, adding simple properties
-# like target_include_directories). These modifications will be ported to original
-# ya.make files by maintainers. Any complex modifications which can't be ported back to the
-# original buildsystem will not be accepted.
-
-
-if (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "aarch64" AND NOT HAVE_CUDA)
- include(CMakeLists.linux-aarch64.txt)
-elseif (CMAKE_SYSTEM_NAME STREQUAL "Darwin" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64")
- include(CMakeLists.darwin-x86_64.txt)
-elseif (WIN32 AND CMAKE_SYSTEM_PROCESSOR STREQUAL "AMD64" AND NOT HAVE_CUDA)
- include(CMakeLists.windows-x86_64.txt)
-elseif (CMAKE_SYSTEM_NAME STREQUAL "Linux" AND CMAKE_SYSTEM_PROCESSOR STREQUAL "x86_64" AND NOT HAVE_CUDA)
- include(CMakeLists.linux-x86_64.txt)
-endif()
diff --git a/library/cpp/containers/flat_hash/CMakeLists.windows-x86_64.txt b/library/cpp/containers/flat_hash/CMakeLists.windows-x86_64.txt
deleted file mode 100644
index 17eb5a21b7..0000000000
--- a/library/cpp/containers/flat_hash/CMakeLists.windows-x86_64.txt
+++ /dev/null
@@ -1,30 +0,0 @@
-
-# This file was generated by the build system used internally in the Yandex monorepo.
-# Only simple modifications are allowed (adding source-files to targets, adding simple properties
-# like target_include_directories). These modifications will be ported to original
-# ya.make files by maintainers. Any complex modifications which can't be ported back to the
-# original buildsystem will not be accepted.
-
-
-
-add_library(cpp-containers-flat_hash)
-target_link_libraries(cpp-containers-flat_hash PUBLIC
- contrib-libs-cxxsupp
- yutil
-)
-target_sources(cpp-containers-flat_hash PRIVATE
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/flat_hash.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/container.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/containers.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/expanders.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/iterator.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/map.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/probings.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/set.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/size_fitters.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/table.cpp
- ${CMAKE_SOURCE_DIR}/library/cpp/containers/flat_hash/lib/value_markers.cpp
-)
diff --git a/library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp b/library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp
deleted file mode 100644
index 040cff3fff..0000000000
--- a/library/cpp/containers/flat_hash/benchmark/flat_hash_benchmark.cpp
+++ /dev/null
@@ -1,180 +0,0 @@
-#include <library/cpp/containers/flat_hash/flat_hash.h>
-
-#include <library/cpp/containers/dense_hash/dense_hash.h>
-#include <library/cpp/testing/benchmark/bench.h>
-
-#include <util/random/random.h>
-#include <util/generic/xrange.h>
-#include <util/generic/hash.h>
-
-namespace {
-
-template <class Map, size_t elemCount, class... Args>
-void RunLookupPositiveScalarKeysBench(::NBench::NCpu::TParams& iface, Args&&... args) {
- using key_type = i32;
- static_assert(std::is_same_v<typename Map::key_type, key_type>);
- Map hm(std::forward<Args>(args)...);
-
- TVector<i32> keys(elemCount);
- for (auto& k : keys) {
- k = RandomNumber<ui32>(std::numeric_limits<i32>::max());
- hm.emplace(k, 0);
- }
-
- for (const auto i : xrange(iface.Iterations())) {
- Y_UNUSED(i);
- for (const auto& k : keys) {
- Y_DO_NOT_OPTIMIZE_AWAY(hm[k]);
- }
- }
-}
-
-constexpr size_t TEST1_ELEM_COUNT = 10;
-constexpr size_t TEST2_ELEM_COUNT = 1000;
-constexpr size_t TEST3_ELEM_COUNT = 1000000;
-
-}
-
-/* *********************************** TEST1 ***********************************
- * Insert TEST1_ELEM_COUNT positive integers and than make lookup.
- * No init size provided for tables.
- * key_type - i32
- */
-
-Y_CPU_BENCHMARK(Test1_fh_TFlatHashMap_LinearProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int>, TEST1_ELEM_COUNT>(iface);
-}
-
-/*
-Y_CPU_BENCHMARK(Test1_fh_TFlatHashMap_QuadraticProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
- std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST1_ELEM_COUNT>(iface);
-}
-*/
-
-Y_CPU_BENCHMARK(Test1_fh_TFlatHashMap_DenseProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
- std::equal_to<i32>, NFlatHash::TDenseProbing>, TEST1_ELEM_COUNT>(iface);
-}
-
-
-Y_CPU_BENCHMARK(Test1_fh_TDenseHashMapStaticMarker_LinearProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
- std::equal_to<i32>, NFlatHash::TLinearProbing>, TEST1_ELEM_COUNT>(iface);
-}
-
-/*
-Y_CPU_BENCHMARK(Test1_fh_TDenseHashMapStaticMarker_QuadraticProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
- std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST1_ELEM_COUNT>(iface);
-}
-*/
-
-Y_CPU_BENCHMARK(Test1_fh_TDenseHashMapStaticMarker_DenseProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1>, TEST1_ELEM_COUNT>(iface);
-}
-
-
-Y_CPU_BENCHMARK(Test1_foreign_TDenseHash, iface) {
- RunLookupPositiveScalarKeysBench<TDenseHash<i32, int>, TEST1_ELEM_COUNT>(iface, (i32)-1);
-}
-
-Y_CPU_BENCHMARK(Test1_foreign_THashMap, iface) {
- RunLookupPositiveScalarKeysBench<THashMap<i32, int>, TEST1_ELEM_COUNT>(iface);
-}
-
-/* *********************************** TEST2 ***********************************
- * Insert TEST2_ELEM_COUNT positive integers and than make lookup.
- * No init size provided for tables.
- * key_type - i32
- */
-
-Y_CPU_BENCHMARK(Test2_fh_TFlatHashMap_LinearProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int>, TEST2_ELEM_COUNT>(iface);
-}
-
-/*
-Y_CPU_BENCHMARK(Test2_fh_TFlatHashMap_QuadraticProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
- std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST2_ELEM_COUNT>(iface);
-}
-*/
-
-Y_CPU_BENCHMARK(Test2_fh_TFlatHashMap_DenseProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
- std::equal_to<i32>, NFlatHash::TDenseProbing>, TEST2_ELEM_COUNT>(iface);
-}
-
-
-Y_CPU_BENCHMARK(Test2_fh_TDenseHashMapStaticMarker_LinearProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
- std::equal_to<i32>, NFlatHash::TLinearProbing>, TEST2_ELEM_COUNT>(iface);
-}
-
-/*
-Y_CPU_BENCHMARK(Test2_fh_TDenseHashMapStaticMarker_QuadraticProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
- std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST2_ELEM_COUNT>(iface);
-}
-*/
-
-Y_CPU_BENCHMARK(Test2_fh_TDenseHashMapStaticMarker_DenseProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1>, TEST2_ELEM_COUNT>(iface);
-}
-
-
-Y_CPU_BENCHMARK(Test2_foreign_TDenseHash, iface) {
- RunLookupPositiveScalarKeysBench<TDenseHash<i32, int>, TEST2_ELEM_COUNT>(iface, (i32)-1);
-}
-
-Y_CPU_BENCHMARK(Test2_foreign_THashMap, iface) {
- RunLookupPositiveScalarKeysBench<THashMap<i32, int>, TEST2_ELEM_COUNT>(iface);
-}
-
-/* *********************************** TEST3 ***********************************
- * Insert TEST2_ELEM_COUNT positive integers and than make lookup.
- * No init size provided for tables.
- * key_type - i32
- */
-
-Y_CPU_BENCHMARK(Test3_fh_TFlatHashMap_LinearProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int>, TEST3_ELEM_COUNT>(iface);
-}
-
-/*
-Y_CPU_BENCHMARK(Test3_fh_TFlatHashMap_QuadraticProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
- std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST3_ELEM_COUNT>(iface);
-}
-*/
-
-Y_CPU_BENCHMARK(Test3_fh_TFlatHashMap_DenseProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TFlatHashMap<i32, int, THash<i32>,
- std::equal_to<i32>, NFlatHash::TDenseProbing>, TEST3_ELEM_COUNT>(iface);
-}
-
-
-Y_CPU_BENCHMARK(Test3_fh_TDenseHashMapStaticMarker_LinearProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
- std::equal_to<i32>, NFlatHash::TLinearProbing>, TEST3_ELEM_COUNT>(iface);
-}
-
-/*
-Y_CPU_BENCHMARK(Test3_fh_TDenseHashMapStaticMarker_QuadraticProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1, THash<i32>,
- std::equal_to<i32>, NFlatHash::TQuadraticProbing>, TEST3_ELEM_COUNT>(iface);
-}
-*/
-
-Y_CPU_BENCHMARK(Test3_fh_TDenseHashMapStaticMarker_DenseProbing, iface) {
- RunLookupPositiveScalarKeysBench<NFH::TDenseHashMapStaticMarker<i32, int, -1>, TEST3_ELEM_COUNT>(iface);
-}
-
-
-Y_CPU_BENCHMARK(Test3_foreign_TDenseHash, iface) {
- RunLookupPositiveScalarKeysBench<TDenseHash<i32, int>, TEST3_ELEM_COUNT>(iface, (i32)-1);
-}
-
-Y_CPU_BENCHMARK(Test3_foreign_THashMap, iface) {
- RunLookupPositiveScalarKeysBench<THashMap<i32, int>, TEST3_ELEM_COUNT>(iface);
-}
diff --git a/library/cpp/containers/flat_hash/flat_hash.cpp b/library/cpp/containers/flat_hash/flat_hash.cpp
deleted file mode 100644
index 2a16398bd4..0000000000
--- a/library/cpp/containers/flat_hash/flat_hash.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "flat_hash.h"
diff --git a/library/cpp/containers/flat_hash/flat_hash.h b/library/cpp/containers/flat_hash/flat_hash.h
deleted file mode 100644
index 582b8ae8f5..0000000000
--- a/library/cpp/containers/flat_hash/flat_hash.h
+++ /dev/null
@@ -1,120 +0,0 @@
-#pragma once
-
-#include <library/cpp/containers/flat_hash/lib/map.h>
-#include <library/cpp/containers/flat_hash/lib/containers.h>
-#include <library/cpp/containers/flat_hash/lib/probings.h>
-#include <library/cpp/containers/flat_hash/lib/set.h>
-#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
-#include <library/cpp/containers/flat_hash/lib/expanders.h>
-
-#include <util/str_stl.h>
-
-namespace NPrivate {
-
-template <class Key, class T, class Hash, class KeyEqual, class Probing, class Alloc>
-using TFlatHashMapImpl = NFlatHash::TMap<Key, T, Hash, KeyEqual,
- NFlatHash::TFlatContainer<std::pair<const Key, T>, Alloc>,
- Probing, NFlatHash::TAndSizeFitter,
- NFlatHash::TSimpleExpander>;
-
-template <class Key, class T, auto emptyMarker, class Hash, class KeyEqual, class Probing, class Alloc>
-using TDenseHashMapImpl =
- NFlatHash::TMap<Key, T, Hash, KeyEqual,
- NFlatHash::TDenseContainer<std::pair<const Key, T>,
- NFlatHash::NMap::TStaticValueMarker<emptyMarker, T>,
- Alloc>,
- Probing, NFlatHash::TAndSizeFitter, NFlatHash::TSimpleExpander>;
-
-
-template <class T, class Hash, class KeyEqual, class Probing, class Alloc>
-using TFlatHashSetImpl = NFlatHash::TSet<T, Hash, KeyEqual,
- NFlatHash::TFlatContainer<T, Alloc>,
- Probing, NFlatHash::TAndSizeFitter,
- NFlatHash::TSimpleExpander>;
-
-template <class T, auto emptyMarker, class Hash, class KeyEqual, class Probing, class Alloc>
-using TDenseHashSetImpl =
- NFlatHash::TSet<T, Hash, KeyEqual,
- NFlatHash::TDenseContainer<T, NFlatHash::NSet::TStaticValueMarker<emptyMarker>, Alloc>,
- Probing, NFlatHash::TAndSizeFitter, NFlatHash::TSimpleExpander>;
-
-} // namespace NPrivate
-
-namespace NFH {
-
-/* flat_map: Fast and highly customizable hash map.
- *
- * Most features would be available soon.
- * Until that time we strongly insist on using only class aliases listed below.
- */
-
-/* Simpliest open addressing hash map.
- * Uses additional array to denote status of every bucket.
- * Default probing is linear.
- * Currently available probings:
- * * TLinearProbing
- * * TQuadraticProbing
- * * TDenseProbing
- */
-template <class Key,
- class T,
- class Hash = THash<Key>,
- class KeyEqual = std::equal_to<>,
- class Probing = NFlatHash::TLinearProbing,
- class Alloc = std::allocator<std::pair<const Key, T>>>
-using TFlatHashMap = NPrivate::TFlatHashMapImpl<Key, T, Hash, KeyEqual, Probing, Alloc>;
-
-/* Open addressing table with user specified marker for empty buckets.
- * Currently available probings:
- * * TLinearProbing
- * * TQuadraticProbing
- * * TDenseProbing
- */
-template <class Key,
- class T,
- auto emptyMarker,
- class Hash = THash<Key>,
- class KeyEqual = std::equal_to<>,
- class Probing = NFlatHash::TDenseProbing,
- class Alloc = std::allocator<std::pair<const Key, T>>>
-using TDenseHashMapStaticMarker = NPrivate::TDenseHashMapImpl<Key, T, emptyMarker,
- Hash, KeyEqual, Probing, Alloc>;
-
-
-/* flat_set: Fast and highly customizable hash set.
- *
- * Most features would be available soon.
- * Until that time we strongly insist on using only class aliases listed below.
- */
-
-/* Simpliest open addressing hash map.
- * Uses additional array to denote status of every bucket.
- * Default probing is linear.
- * Currently available probings:
- * * TLinearProbing
- * * TQuadraticProbing
- * * TDenseProbing
- */
-template <class T,
- class Hash = THash<T>,
- class KeyEqual = std::equal_to<>,
- class Probing = NFlatHash::TLinearProbing,
- class Alloc = std::allocator<T>>
-using TFlatHashSet = NPrivate::TFlatHashSetImpl<T, Hash, KeyEqual, Probing, Alloc>;
-
-/* Open addressing table with user specified marker for empty buckets.
- * Currently available probings:
- * * TLinearProbing
- * * TQuadraticProbing
- * * TDenseProbing
- */
-template <class T,
- auto emptyMarker,
- class Hash = THash<T>,
- class KeyEqual = std::equal_to<>,
- class Probing = NFlatHash::TDenseProbing,
- class Alloc = std::allocator<T>>
-using TDenseHashSetStaticMarker = NPrivate::TDenseHashSetImpl<T, emptyMarker,
- Hash, KeyEqual, Probing, Alloc>;
-
-} // namespace NFH
diff --git a/library/cpp/containers/flat_hash/fuzz/dense_map_fuzz/fuzz.cpp b/library/cpp/containers/flat_hash/fuzz/dense_map_fuzz/fuzz.cpp
deleted file mode 100644
index 3d13482a3d..0000000000
--- a/library/cpp/containers/flat_hash/fuzz/dense_map_fuzz/fuzz.cpp
+++ /dev/null
@@ -1,60 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/map.h>
-#include <library/cpp/containers/flat_hash/lib/containers.h>
-#include <library/cpp/containers/flat_hash/lib/probings.h>
-#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
-#include <library/cpp/containers/flat_hash/lib/expanders.h>
-
-#include <library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.h>
-
-#include <util/generic/hash.h>
-#include <util/generic/xrange.h>
-#include <util/generic/bt_exception.h>
-
-using namespace NFlatHash;
-
-namespace {
-
-template <class Key, class T>
-using TDenseModMap = NFlatHash::TMap<Key,
- T,
- THash<Key>,
- std::equal_to<Key>,
- TRemovalDenseContainer<std::pair<const Key, T>,
- NMap::TEqValueMarker<Key, T>,
- NMap::TEqValueMarker<Key, T>>,
- TDenseProbing,
- TAndSizeFitter,
- TSimpleExpander>;
-
-NFuzz::EActionType EvalType(ui8 data) {
- return static_cast<NFuzz::EActionType>((data >> 5) & 0b111);
-}
-
-ui8 EvalKey(ui8 data) {
- return data & 0b11111;
-}
-
-ui8 EvalValue() {
- return RandomNumber<ui8>();
-}
-
-} // namespace
-
-#include <util/datetime/base.h>
-
-extern "C" int LLVMFuzzerTestOneInput(const ui8* const wireData, const size_t wireSize) {
- THashMap<ui8, ui8> etalon;
- // We assume, that markers can't be produced by EvalKey function.
- TDenseModMap<ui8, ui8> testee(8,
- (1 << 5), // Deleted marker
- (1 << 6)); // Empty marker
-
- for (auto i : xrange(wireSize)) {
- auto data = wireData[i];
-
- NFuzz::MakeAction(etalon, testee, EvalKey(data), EvalValue(), EvalType(data));
- NFuzz::CheckInvariants(etalon, testee);
- }
-
- return 0;
-}
diff --git a/library/cpp/containers/flat_hash/fuzz/flat_map_fuzz/fuzz.cpp b/library/cpp/containers/flat_hash/fuzz/flat_map_fuzz/fuzz.cpp
deleted file mode 100644
index 5ae81db9ab..0000000000
--- a/library/cpp/containers/flat_hash/fuzz/flat_map_fuzz/fuzz.cpp
+++ /dev/null
@@ -1,53 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/map.h>
-#include <library/cpp/containers/flat_hash/lib/containers.h>
-#include <library/cpp/containers/flat_hash/lib/probings.h>
-#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
-#include <library/cpp/containers/flat_hash/lib/expanders.h>
-
-#include <library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.h>
-
-#include <util/generic/hash.h>
-#include <util/generic/xrange.h>
-#include <util/generic/bt_exception.h>
-
-using namespace NFlatHash;
-
-namespace {
-
-template <class Key, class T>
-using TFlatLinearModMap = NFlatHash::TMap<Key,
- T,
- THash<Key>,
- std::equal_to<Key>,
- TFlatContainer<std::pair<const Key, T>>,
- TLinearProbing,
- TAndSizeFitter,
- TSimpleExpander>;
-
-NFuzz::EActionType EvalType(ui8 data) {
- return static_cast<NFuzz::EActionType>((data >> 5) & 0b111);
-}
-
-ui8 EvalKey(ui8 data) {
- return data & 0b11111;
-}
-
-ui8 EvalValue() {
- return RandomNumber<ui8>();
-}
-
-} // namespace
-
-extern "C" int LLVMFuzzerTestOneInput(const ui8* const wireData, const size_t wireSize) {
- THashMap<ui8, ui8> etalon;
- TFlatLinearModMap<ui8, ui8> testee;
-
- for (auto i : xrange(wireSize)) {
- auto data = wireData[i];
-
- NFuzz::MakeAction(etalon, testee, EvalKey(data), EvalValue(), EvalType(data));
- NFuzz::CheckInvariants(etalon, testee);
- }
-
- return 0;
-}
diff --git a/library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.cpp b/library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.cpp
deleted file mode 100644
index efc2973d18..0000000000
--- a/library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "fuzz_common.h"
diff --git a/library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.h b/library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.h
deleted file mode 100644
index 71a123d9cf..0000000000
--- a/library/cpp/containers/flat_hash/fuzz/fuzz_common/fuzz_common.h
+++ /dev/null
@@ -1,223 +0,0 @@
-#pragma once
-
-#include <util/generic/bt_exception.h>
-#include <util/generic/vector.h>
-#include <util/generic/xrange.h>
-
-#include <util/random/random.h>
-
-namespace NFlatHash::NFuzz {
-
-#define FUZZ_ASSERT(cond) \
- Y_ENSURE_EX(cond, TWithBackTrace<yexception>() << Y_STRINGIZE(cond) << " assertion failed ")
-
-#define FUZZ_ASSERT_THROW(cond, exc) \
- try { \
- cond; \
- FUZZ_ASSERT(false); \
- } catch (const exc&) { \
- } catch (...) { \
- FUZZ_ASSERT(false); \
- }
-
-enum EActionType {
- AT_INSERT,
- AT_CLEAR,
- AT_REHASH,
- AT_ATOP,
- AT_AT,
- AT_ITERATORS,
- AT_ERASE,
- AT_FIND
-};
-
-template <class EtalonMap, class TesteeMap, class Key, class Value>
-void MakeAction(EtalonMap& etalon, TesteeMap& testee, Key&& key, Value&& value, EActionType type) {
- switch (type) {
- case AT_INSERT: {
- auto itEt = etalon.insert({ key, value });
- if (itEt.second) {
- FUZZ_ASSERT(!testee.contains(key));
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
-
- auto itTs = testee.insert(std::make_pair(key, value));
- FUZZ_ASSERT(itTs.second);
- FUZZ_ASSERT(itTs.first->first == key);
- FUZZ_ASSERT(itTs.first->second == value);
- FUZZ_ASSERT(size + 1 == testee.size());
- FUZZ_ASSERT(bucket_count <= testee.bucket_count());
- } else {
- FUZZ_ASSERT(testee.contains(key));
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
-
- auto itTs = testee.insert(std::make_pair(key, value));
- FUZZ_ASSERT(!itTs.second);
- FUZZ_ASSERT(itTs.first->first == key);
- FUZZ_ASSERT(itTs.first->second == itEt.first->second);
- FUZZ_ASSERT(size == testee.size());
- FUZZ_ASSERT(bucket_count == testee.bucket_count());
- }
- break;
- }
- case AT_CLEAR: {
- auto bucket_count = testee.bucket_count();
- testee.clear();
- for (const auto& v : etalon) {
- FUZZ_ASSERT(!testee.contains(v.first));
- }
- FUZZ_ASSERT(testee.empty());
- FUZZ_ASSERT(testee.size() == 0);
- FUZZ_ASSERT(testee.bucket_count() == bucket_count);
- FUZZ_ASSERT(testee.load_factor() < std::numeric_limits<float>::epsilon());
-
- etalon.clear();
- break;
- }
- case AT_REHASH: {
- testee.rehash(key);
- FUZZ_ASSERT(testee.bucket_count() >= key);
- break;
- }
- case AT_ATOP: {
- if (etalon.contains(key)) {
- FUZZ_ASSERT(testee.contains(key));
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
-
- FUZZ_ASSERT(testee[key] == etalon[key]);
-
- FUZZ_ASSERT(size == testee.size());
- FUZZ_ASSERT(bucket_count == testee.bucket_count());
- } else {
- FUZZ_ASSERT(!testee.contains(key));
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
-
- FUZZ_ASSERT(testee[key] == etalon[key]);
-
- FUZZ_ASSERT(size + 1 == testee.size());
- FUZZ_ASSERT(bucket_count <= testee.bucket_count());
- }
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
-
- etalon[key] = value;
- testee[key] = value;
- FUZZ_ASSERT(testee[key] == etalon[key]);
- FUZZ_ASSERT(testee[key] == value);
-
- FUZZ_ASSERT(size == testee.size());
- FUZZ_ASSERT(bucket_count == testee.bucket_count());
- break;
- }
- case AT_AT: {
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
- if (etalon.contains(key)) {
- FUZZ_ASSERT(testee.contains(key));
-
- FUZZ_ASSERT(testee.at(key) == etalon.at(key));
- testee.at(key) = value;
- etalon.at(key) = value;
- FUZZ_ASSERT(testee.at(key) == etalon.at(key));
- } else {
- FUZZ_ASSERT(!testee.contains(key));
- FUZZ_ASSERT_THROW(testee.at(key) = value, std::out_of_range);
- FUZZ_ASSERT(!testee.contains(key));
- }
- FUZZ_ASSERT(size == testee.size());
- FUZZ_ASSERT(bucket_count == testee.bucket_count());
- break;
- }
- case AT_ITERATORS: {
- auto itBeginTs = testee.begin();
- auto itEndTs = testee.end();
- FUZZ_ASSERT((size_t)std::distance(itBeginTs, itEndTs) == testee.size());
- FUZZ_ASSERT(std::distance(itBeginTs, itEndTs) ==
- std::distance(etalon.begin(), etalon.end()));
- FUZZ_ASSERT(std::distance(testee.cbegin(), testee.cend()) ==
- std::distance(etalon.cbegin(), etalon.cend()));
- break;
- }
- case AT_ERASE: {
- if (etalon.contains(key)) {
- FUZZ_ASSERT(testee.contains(key));
- auto size = testee.size();
- auto bucket_count = testee.bucket_count();
-
- auto itTs = testee.find(key);
- FUZZ_ASSERT(itTs->first == key);
- FUZZ_ASSERT(itTs->second == etalon.at(key));
-
- testee.erase(itTs);
- FUZZ_ASSERT(size - 1 == testee.size());
- FUZZ_ASSERT(bucket_count == testee.bucket_count());
- etalon.erase(key);
- } else {
- FUZZ_ASSERT(!testee.contains(key));
- }
- break;
- }
- case AT_FIND: {
- auto itEt = etalon.find(key);
- if (itEt != etalon.end()) {
- FUZZ_ASSERT(testee.contains(key));
-
- auto itTs = testee.find(key);
- FUZZ_ASSERT(itTs != testee.end());
- FUZZ_ASSERT(itTs->first == key);
- FUZZ_ASSERT(itTs->second == itEt->second);
-
- itTs->second = value;
- itEt->second = value;
- } else {
- FUZZ_ASSERT(!testee.contains(key));
-
- auto itTs = testee.find(key);
- FUZZ_ASSERT(itTs == testee.end());
- }
- break;
- }
- };
-}
-
-template <class EtalonMap, class TesteeMap>
-void CheckInvariants(const EtalonMap& etalon, const TesteeMap& testee) {
- using value_type = std::pair<typename TesteeMap::key_type,
- typename TesteeMap::mapped_type>;
- using size_type = typename TesteeMap::size_type;
-
- TVector<value_type> etalonVals{ etalon.begin(), etalon.end() };
- std::sort(etalonVals.begin(), etalonVals.end());
- TVector<value_type> testeeVals{ testee.begin(), testee.end() };
- std::sort(testeeVals.begin(), testeeVals.end());
-
- FUZZ_ASSERT(testeeVals == etalonVals);
-
- FUZZ_ASSERT(testee.size() == etalon.size());
- FUZZ_ASSERT(testee.empty() == etalon.empty());
- FUZZ_ASSERT(testee.load_factor() < 0.5f + std::numeric_limits<float>::epsilon());
- FUZZ_ASSERT(testee.bucket_count() > testee.size());
-
- size_type buckets = 0;
- for (auto b : xrange(testee.bucket_count())) {
- buckets += testee.bucket_size(b);
- }
- FUZZ_ASSERT(buckets == testee.size());
-
- for (const auto& v : etalon) {
- auto key = v.first;
- auto value = v.second;
-
- FUZZ_ASSERT(testee.contains(key));
- FUZZ_ASSERT(testee.count(key) == 1);
-
- auto it = testee.find(key);
- FUZZ_ASSERT(it->first == key);
- FUZZ_ASSERT(it->second == value);
- }
-}
-
-} // namespace NFlatHash::NFuzz
diff --git a/library/cpp/containers/flat_hash/lib/concepts/container.cpp b/library/cpp/containers/flat_hash/lib/concepts/container.cpp
deleted file mode 100644
index 733484a7d7..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/container.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "container.h"
diff --git a/library/cpp/containers/flat_hash/lib/concepts/container.h b/library/cpp/containers/flat_hash/lib/concepts/container.h
deleted file mode 100644
index eac1803b59..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/container.h
+++ /dev/null
@@ -1,66 +0,0 @@
-#pragma once
-
-#include <type_traits>
-
-/* Concepts:
- * Container
- * RemovalContainer
- */
-namespace NFlatHash::NConcepts {
-
-#define DCV(type) std::declval<type>()
-#define DCT(object) decltype(object)
-
-template <class T, class = void>
-struct Container : std::false_type {};
-
-template <class T>
-struct Container<T, std::void_t<
- typename T::value_type,
- typename T::size_type,
- typename T::difference_type,
- DCT(DCV(T).Node(DCV(typename T::size_type))),
- DCT(DCV(const T).Node(DCV(typename T::size_type))),
- DCT(DCV(const T).Size()),
- DCT(DCV(const T).Taken()),
- DCT(DCV(const T).Empty()),
- DCT(DCV(const T).IsEmpty(DCV(typename T::size_type))),
- DCT(DCV(const T).IsTaken(DCV(typename T::size_type))),
- DCT(DCV(T).Swap(DCV(T&))),
- DCT(DCV(const T).Clone(DCV(typename T::size_type)))>>
- : std::conjunction<std::is_same<DCT(DCV(T).Node(DCV(typename T::size_type))),
- typename T::value_type&>,
- std::is_same<DCT(DCV(const T).Node(DCV(typename T::size_type))),
- const typename T::value_type&>,
- std::is_same<DCT(DCV(const T).Size()), typename T::size_type>,
- std::is_same<DCT(DCV(const T).Taken()), typename T::size_type>,
- std::is_same<DCT(DCV(const T).Empty()), typename T::size_type>,
- std::is_same<DCT(DCV(const T).IsEmpty(DCV(typename T::size_type))), bool>,
- std::is_same<DCT(DCV(const T).IsTaken(DCV(typename T::size_type))), bool>,
- std::is_same<DCT(DCV(const T).Clone(DCV(typename T::size_type))), T>,
- std::is_copy_constructible<T>,
- std::is_move_constructible<T>,
- std::is_copy_assignable<T>,
- std::is_move_assignable<T>> {};
-
-template <class T>
-constexpr bool ContainerV = Container<T>::value;
-
-template <class T, class = void>
-struct RemovalContainer : std::false_type {};
-
-template <class T>
-struct RemovalContainer<T, std::void_t<
- DCT(DCV(T).DeleteNode(DCV(typename T::size_type))),
- DCT(DCV(const T).IsDeleted(DCV(typename T::size_type)))>>
- : std::conjunction<Container<T>,
- std::is_same<DCT(DCV(const T).IsDeleted(DCV(typename T::size_type))),
- bool>> {};
-
-template <class T>
-constexpr bool RemovalContainerV = RemovalContainer<T>::value;
-
-#undef DCV
-#undef DCT
-
-} // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp b/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp
deleted file mode 100644
index 7c5c206cc3..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/iterator.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "iterator.h"
diff --git a/library/cpp/containers/flat_hash/lib/concepts/iterator.h b/library/cpp/containers/flat_hash/lib/concepts/iterator.h
deleted file mode 100644
index b9c1c24c82..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/iterator.h
+++ /dev/null
@@ -1,20 +0,0 @@
-#pragma once
-
-#include <iterator>
-
-/* Concepts:
- * Iterator
- */
-namespace NFlatHash::NConcepts {
-
-template <class T, class = void>
-struct Iterator : std::false_type {};
-
-template <class T>
-struct Iterator<T, std::void_t<typename std::iterator_traits<T>::iterator_category>>
- : std::true_type {};
-
-template <class T>
-constexpr bool IteratorV = Iterator<T>::value;
-
-} // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp b/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp
deleted file mode 100644
index 2afd5b3c63..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/size_fitter.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "size_fitter.h"
diff --git a/library/cpp/containers/flat_hash/lib/concepts/size_fitter.h b/library/cpp/containers/flat_hash/lib/concepts/size_fitter.h
deleted file mode 100644
index 83d1d31304..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/size_fitter.h
+++ /dev/null
@@ -1,34 +0,0 @@
-#pragma once
-
-#include <type_traits>
-
-/* Concepts:
- * SizeFitter
- */
-namespace NFlatHash::NConcepts {
-
-#define DCV(type) std::declval<type>()
-#define DCT(object) decltype(object)
-
-template <class T, class = void>
-struct SizeFitter : std::false_type {};
-
-template <class T>
-struct SizeFitter<T, std::void_t<
- DCT(DCV(const T).EvalIndex(DCV(size_t), DCV(size_t))),
- DCT(DCV(const T).EvalSize(DCV(size_t))),
- DCT(DCV(T).Update(DCV(size_t)))>>
- : std::conjunction<std::is_same<DCT(DCV(const T).EvalIndex(DCV(size_t), DCV(size_t))), size_t>,
- std::is_same<DCT(DCV(const T).EvalSize(DCV(size_t))), size_t>,
- std::is_copy_constructible<T>,
- std::is_move_constructible<T>,
- std::is_copy_assignable<T>,
- std::is_move_assignable<T>> {};
-
-template <class T>
-constexpr bool SizeFitterV = SizeFitter<T>::value;
-
-#undef DCV
-#undef DCT
-
-} // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp b/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp
deleted file mode 100644
index 336ca04737..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/value_marker.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "value_marker.h"
diff --git a/library/cpp/containers/flat_hash/lib/concepts/value_marker.h b/library/cpp/containers/flat_hash/lib/concepts/value_marker.h
deleted file mode 100644
index 9d1e9b210a..0000000000
--- a/library/cpp/containers/flat_hash/lib/concepts/value_marker.h
+++ /dev/null
@@ -1,34 +0,0 @@
-#pragma once
-
-#include <type_traits>
-
-/* Concepts:
- * ValueMarker
- */
-namespace NFlatHash::NConcepts {
-
-#define DCV(type) std::declval<type>()
-#define DCT(object) decltype(object)
-
-template <class T, class = void>
-struct ValueMarker : std::false_type {};
-
-template <class T>
-struct ValueMarker<T, std::void_t<
- typename T::value_type,
- DCT(DCV(const T).Create()),
- DCT(DCV(const T).Equals(DCV(const typename T::value_type&)))>>
- : std::conjunction<std::is_constructible<typename T::value_type, DCT(DCV(const T).Create())>,
- std::is_same<DCT(DCV(const T).Equals(DCV(const typename T::value_type&))), bool>,
- std::is_copy_constructible<T>,
- std::is_move_constructible<T>,
- std::is_copy_assignable<T>,
- std::is_move_assignable<T>> {};
-
-template <class T>
-constexpr bool ValueMarkerV = ValueMarker<T>::value;
-
-#undef DCV
-#undef DCT
-
-} // namespace NFlatHash::NConcepts
diff --git a/library/cpp/containers/flat_hash/lib/containers.cpp b/library/cpp/containers/flat_hash/lib/containers.cpp
deleted file mode 100644
index 0853c23fc1..0000000000
--- a/library/cpp/containers/flat_hash/lib/containers.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "containers.h"
diff --git a/library/cpp/containers/flat_hash/lib/containers.h b/library/cpp/containers/flat_hash/lib/containers.h
deleted file mode 100644
index 82008f2f9c..0000000000
--- a/library/cpp/containers/flat_hash/lib/containers.h
+++ /dev/null
@@ -1,314 +0,0 @@
-#pragma once
-
-#include "concepts/container.h"
-#include "value_markers.h"
-
-#include <util/system/yassert.h>
-
-#include <util/generic/vector.h>
-#include <util/generic/typetraits.h>
-#include <util/generic/utility.h>
-
-#include <optional>
-
-namespace NFlatHash {
-
-/* FLAT CONTAINER */
-
-template <class T, class Alloc = std::allocator<T>>
-class TFlatContainer {
-public:
- using value_type = T;
- using size_type = size_t;
- using difference_type = ptrdiff_t;
- using allocator_type = Alloc;
- using pointer = typename std::allocator_traits<allocator_type>::pointer;
- using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
-
-private:
- class TCage {
- enum ENodeStatus {
- NS_EMPTY,
- NS_TAKEN,
- NS_DELETED
- };
-
- public:
- TCage() noexcept = default;
-
- TCage(const TCage&) = default;
- TCage(TCage&&) = default;
-
- TCage& operator=(const TCage& rhs) {
- switch (rhs.Status_) {
- case NS_TAKEN:
- if constexpr (std::is_copy_assignable_v<value_type>) {
- Value_ = rhs.Value_;
- } else {
- Value_.emplace(rhs.Value());
- }
- break;
- case NS_EMPTY:
- case NS_DELETED:
- if (Value_.has_value()) {
- Value_.reset();
- }
- break;
- default:
- Y_VERIFY(false, "Not implemented");
- }
- Status_ = rhs.Status_;
- return *this;
- }
- // We never call it since all the TCage's are stored in vector
- TCage& operator=(TCage&& rhs) = delete;
-
- template <class... Args>
- void Emplace(Args&&... args) {
- Y_ASSERT(Status_ == NS_EMPTY);
- Value_.emplace(std::forward<Args>(args)...);
- Status_ = NS_TAKEN;
- }
-
- void Reset() noexcept {
- Y_ASSERT(Status_ == NS_TAKEN);
- Value_.reset();
- Status_ = NS_DELETED;
- }
-
- value_type& Value() {
- Y_ASSERT(Status_ == NS_TAKEN);
- return *Value_;
- }
-
- const value_type& Value() const {
- Y_ASSERT(Status_ == NS_TAKEN);
- return *Value_;
- }
-
- bool IsEmpty() const noexcept { return Status_ == NS_EMPTY; }
- bool IsTaken() const noexcept { return Status_ == NS_TAKEN; }
- bool IsDeleted() const noexcept { return Status_ == NS_DELETED; }
-
- ENodeStatus Status() const noexcept { return Status_; }
-
- private:
- std::optional<value_type> Value_;
- ENodeStatus Status_ = NS_EMPTY;
- };
-
-public:
- explicit TFlatContainer(size_type initSize, const allocator_type& alloc = {})
- : Buckets_(initSize, alloc)
- , Taken_(0)
- , Empty_(initSize) {}
-
- TFlatContainer(const TFlatContainer&) = default;
- TFlatContainer(TFlatContainer&& rhs)
- : Buckets_(std::move(rhs.Buckets_))
- , Taken_(rhs.Taken_)
- , Empty_(rhs.Empty_)
- {
- rhs.Taken_ = 0;
- rhs.Empty_ = 0;
- }
-
- TFlatContainer& operator=(const TFlatContainer&) = default;
- TFlatContainer& operator=(TFlatContainer&&) = default;
-
- value_type& Node(size_type idx) { return Buckets_[idx].Value(); }
- const value_type& Node(size_type idx) const { return Buckets_[idx].Value(); }
-
- size_type Size() const noexcept { return Buckets_.size(); }
- size_type Taken() const noexcept { return Taken_; }
- size_type Empty() const noexcept { return Empty_; }
-
- template <class... Args>
- void InitNode(size_type idx, Args&&... args) {
- Buckets_[idx].Emplace(std::forward<Args>(args)...);
- ++Taken_;
- --Empty_;
- }
-
- void DeleteNode(size_type idx) noexcept {
- Buckets_[idx].Reset();
- --Taken_;
- }
-
- bool IsEmpty(size_type idx) const { return Buckets_[idx].IsEmpty(); }
- bool IsTaken(size_type idx) const { return Buckets_[idx].IsTaken(); }
- bool IsDeleted(size_type idx) const { return Buckets_[idx].IsDeleted(); }
-
- void Swap(TFlatContainer& rhs) noexcept {
- DoSwap(Buckets_, rhs.Buckets_);
- DoSwap(Taken_, rhs.Taken_);
- DoSwap(Empty_, rhs.Empty_);
- }
-
- TFlatContainer Clone(size_type newSize) const { return TFlatContainer(newSize, Buckets_.get_allocator()); }
-
-private:
- TVector<TCage, allocator_type> Buckets_;
- size_type Taken_;
- size_type Empty_;
-};
-
-static_assert(NConcepts::ContainerV<TFlatContainer<int>>);
-static_assert(NConcepts::RemovalContainerV<TFlatContainer<int>>);
-
-/* DENSE CONTAINER */
-
-template <class T, class EmptyMarker = NSet::TEqValueMarker<T>, class Alloc = std::allocator<T>>
-class TDenseContainer {
- static_assert(NConcepts::ValueMarkerV<EmptyMarker>);
-
-public:
- using value_type = T;
- using size_type = size_t;
- using difference_type = ptrdiff_t;
- using allocator_type = Alloc;
- using pointer = typename std::allocator_traits<allocator_type>::pointer;
- using const_pointer = typename std::allocator_traits<allocator_type>::const_pointer;
-
-public:
- TDenseContainer(size_type initSize, EmptyMarker emptyMarker = {}, const allocator_type& alloc = {})
- : Buckets_(initSize, emptyMarker.Create(), alloc)
- , Taken_(0)
- , EmptyMarker_(std::move(emptyMarker)) {}
-
- TDenseContainer(const TDenseContainer&) = default;
- TDenseContainer(TDenseContainer&&) = default;
-
- TDenseContainer& operator=(const TDenseContainer& rhs) {
- Taken_ = rhs.Taken_;
- EmptyMarker_ = rhs.EmptyMarker_;
- if constexpr (std::is_copy_assignable_v<value_type>) {
- Buckets_ = rhs.Buckets_;
- } else {
- auto tmp = rhs.Buckets_;
- Buckets_.swap(tmp);
- }
- return *this;
- }
- TDenseContainer& operator=(TDenseContainer&&) = default;
-
- value_type& Node(size_type idx) { return Buckets_[idx]; }
- const value_type& Node(size_type idx) const { return Buckets_[idx]; }
-
- size_type Size() const noexcept { return Buckets_.size(); }
- size_type Taken() const noexcept { return Taken_; }
- size_type Empty() const noexcept { return Size() - Taken(); }
-
- template <class... Args>
- void InitNode(size_type idx, Args&&... args) {
- Node(idx).~value_type();
- new (&Buckets_[idx]) value_type(std::forward<Args>(args)...);
- ++Taken_;
- }
-
- bool IsEmpty(size_type idx) const { return EmptyMarker_.Equals(Buckets_[idx]); }
- bool IsTaken(size_type idx) const { return !IsEmpty(idx); }
-
- void Swap(TDenseContainer& rhs)
- noexcept(noexcept(DoSwap(std::declval<EmptyMarker&>(), std::declval<EmptyMarker&>())))
- {
- DoSwap(Buckets_, rhs.Buckets_);
- DoSwap(EmptyMarker_, rhs.EmptyMarker_);
- DoSwap(Taken_, rhs.Taken_);
- }
-
- TDenseContainer Clone(size_type newSize) const { return { newSize, EmptyMarker_, GetAllocator() }; }
-
-protected:
- allocator_type GetAllocator() const {
- return Buckets_.get_allocator();
- }
-
-protected:
- TVector<value_type, allocator_type> Buckets_;
- size_type Taken_;
- EmptyMarker EmptyMarker_;
-};
-
-static_assert(NConcepts::ContainerV<TDenseContainer<int>>);
-static_assert(!NConcepts::RemovalContainerV<TDenseContainer<int>>);
-
-template <class T, class DeletedMarker = NSet::TEqValueMarker<T>,
- class EmptyMarker = NSet::TEqValueMarker<T>, class Alloc = std::allocator<T>>
-class TRemovalDenseContainer : private TDenseContainer<T, EmptyMarker, Alloc> {
-private:
- static_assert(NConcepts::ValueMarkerV<DeletedMarker>);
-
- using TBase = TDenseContainer<T, EmptyMarker>;
-
-public:
- using typename TBase::value_type;
- using typename TBase::size_type;
- using typename TBase::difference_type;
- using typename TBase::allocator_type;
- using typename TBase::pointer;
- using typename TBase::const_pointer;
-
-public:
- TRemovalDenseContainer(
- size_type initSize,
- DeletedMarker deletedMarker = {},
- EmptyMarker emptyMarker = {},
- const allocator_type& alloc = {})
- : TBase(initSize, std::move(emptyMarker), alloc)
- , DeletedMarker_(std::move(deletedMarker))
- , Empty_(initSize) {}
-
- TRemovalDenseContainer(const TRemovalDenseContainer&) = default;
- TRemovalDenseContainer(TRemovalDenseContainer&&) = default;
-
- TRemovalDenseContainer& operator=(const TRemovalDenseContainer&) = default;
- TRemovalDenseContainer& operator=(TRemovalDenseContainer&&) = default;
-
- using TBase::Node;
- using TBase::Size;
- using TBase::Taken;
- using TBase::InitNode;
- using TBase::IsEmpty;
-
- size_type Empty() const noexcept { return Empty_; }
-
- template <class... Args>
- void InitNode(size_type idx, Args&&... args) {
- TBase::InitNode(idx, std::forward<Args>(args)...);
- --Empty_;
- }
-
- void DeleteNode(size_type idx) {
- if constexpr (!std::is_trivially_destructible_v<value_type>) {
- TBase::Node(idx).~value_type();
- }
- new (&TBase::Node(idx)) value_type(DeletedMarker_.Create());
- --TBase::Taken_;
- }
-
- bool IsTaken(size_type idx) const { return !IsDeleted(idx) && TBase::IsTaken(idx); }
- bool IsDeleted(size_type idx) const { return DeletedMarker_.Equals(Node(idx)); }
-
- void Swap(TRemovalDenseContainer& rhs)
- noexcept(noexcept(std::declval<TBase>().Swap(std::declval<TBase&>())) &&
- noexcept(DoSwap(std::declval<DeletedMarker&>(), std::declval<DeletedMarker&>())))
- {
- TBase::Swap(rhs);
- DoSwap(DeletedMarker_, rhs.DeletedMarker_);
- DoSwap(Empty_, rhs.Empty_);
- }
-
- TRemovalDenseContainer Clone(size_type newSize) const {
- return { newSize, DeletedMarker_, TBase::EmptyMarker_, TBase::GetAllocator() };
- }
-
-private:
- DeletedMarker DeletedMarker_;
- size_type Empty_;
-};
-
-static_assert(NConcepts::ContainerV<TRemovalDenseContainer<int>>);
-static_assert(NConcepts::RemovalContainerV<TRemovalDenseContainer<int>>);
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/expanders.cpp b/library/cpp/containers/flat_hash/lib/expanders.cpp
deleted file mode 100644
index 6bed3c72f3..0000000000
--- a/library/cpp/containers/flat_hash/lib/expanders.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "expanders.h"
diff --git a/library/cpp/containers/flat_hash/lib/expanders.h b/library/cpp/containers/flat_hash/lib/expanders.h
deleted file mode 100644
index 25b10e6bf1..0000000000
--- a/library/cpp/containers/flat_hash/lib/expanders.h
+++ /dev/null
@@ -1,25 +0,0 @@
-#pragma once
-
-#include <utility>
-
-namespace NFlatHash {
-
-struct TSimpleExpander {
- static constexpr bool NeedGrow(size_t size, size_t buckets) noexcept {
- return size >= buckets / 2;
- }
-
- static constexpr bool WillNeedGrow(size_t size, size_t buckets) noexcept {
- return NeedGrow(size + 1, buckets);
- }
-
- static constexpr size_t EvalNewSize(size_t buckets) noexcept {
- return buckets * 2;
- }
-
- static constexpr size_t SuitableSize(size_t size) noexcept {
- return size * 2 + 1;
- }
-};
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/iterator.cpp b/library/cpp/containers/flat_hash/lib/iterator.cpp
deleted file mode 100644
index 7c5c206cc3..0000000000
--- a/library/cpp/containers/flat_hash/lib/iterator.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "iterator.h"
diff --git a/library/cpp/containers/flat_hash/lib/iterator.h b/library/cpp/containers/flat_hash/lib/iterator.h
deleted file mode 100644
index f6b1e74355..0000000000
--- a/library/cpp/containers/flat_hash/lib/iterator.h
+++ /dev/null
@@ -1,99 +0,0 @@
-#pragma once
-
-#include "concepts/container.h"
-
-#include <util/system/yassert.h>
-
-#include <iterator>
-
-namespace NFlatHash {
-
-template <class Container, class T>
-class TIterator {
-private:
- static_assert(NConcepts::ContainerV<std::decay_t<Container>>);
-
-public:
- using iterator_category = std::forward_iterator_tag;
- using value_type = T;
- using difference_type = ptrdiff_t;
- using pointer = typename std::add_pointer<T>::type;
- using reference = typename std::add_lvalue_reference<T>::type;
-
-private:
- using size_type = typename Container::size_type;
-
-public:
- TIterator(Container* cont)
- : Cont_(cont)
- , Idx_(0)
- {
- if (!cont->IsTaken(Idx_)) {
- Next();
- }
- }
-
- TIterator(Container* cont, size_type idx)
- : Cont_(cont)
- , Idx_(idx) {}
-
- template <class C, class U, class = std::enable_if_t<std::is_convertible<C*, Container*>::value &&
- std::is_convertible<U, T>::value>>
- TIterator(const TIterator<C, U>& rhs)
- : Cont_(rhs.Cont_)
- , Idx_(rhs.Idx_) {}
-
- TIterator(const TIterator&) = default;
-
- TIterator& operator=(const TIterator&) = default;
-
- TIterator& operator++() {
- Next();
- return *this;
- }
- TIterator operator++(int) {
- auto idx = Idx_;
- Next();
- return { Cont_, idx };
- }
-
- reference operator*() {
- return Cont_->Node(Idx_);
- }
-
- pointer operator->() {
- return &Cont_->Node(Idx_);
- }
-
- const pointer operator->() const {
- return &Cont_->Node(Idx_);
- }
-
- bool operator==(const TIterator& rhs) const noexcept {
- Y_ASSERT(Cont_ == rhs.Cont_);
- return Idx_ == rhs.Idx_;
- }
-
- bool operator!=(const TIterator& rhs) const noexcept {
- return !operator==(rhs);
- }
-
-private:
- void Next() {
- // Container provider ensures that it's not empty.
- do {
- ++Idx_;
- } while (Idx_ != Cont_->Size() && !Cont_->IsTaken(Idx_));
- }
-
-private:
- template <class C, class U>
- friend class TIterator;
-
- Container* Cont_ = nullptr;
-
-protected:
- size_type Idx_ = 0;
-};
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/map.cpp b/library/cpp/containers/flat_hash/lib/map.cpp
deleted file mode 100644
index b323fbb46d..0000000000
--- a/library/cpp/containers/flat_hash/lib/map.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "map.h"
diff --git a/library/cpp/containers/flat_hash/lib/map.h b/library/cpp/containers/flat_hash/lib/map.h
deleted file mode 100644
index f77c318a61..0000000000
--- a/library/cpp/containers/flat_hash/lib/map.h
+++ /dev/null
@@ -1,233 +0,0 @@
-#pragma once
-
-#include "table.h"
-#include "concepts/iterator.h"
-
-#include <util/generic/algorithm.h>
-#include <util/generic/mapfindptr.h>
-
-namespace NFlatHash {
-
-namespace NPrivate {
-
-struct TMapKeyGetter {
- template <class T>
- static constexpr auto& Apply(T& t) noexcept { return t.first; };
-
- template <class T>
- static constexpr const auto& Apply(const T& t) noexcept { return t.first; };
-};
-
-} // namespace NPrivate
-
-template <class Key,
- class T,
- class Hash,
- class KeyEqual,
- class Container,
- class Probing,
- class SizeFitter,
- class Expander>
-class TMap : private TTable<Hash,
- KeyEqual,
- Container,
- NPrivate::TMapKeyGetter,
- Probing,
- SizeFitter,
- Expander>,
- public TMapOps<TMap<Key,
- T,
- Hash,
- KeyEqual,
- Container,
- Probing,
- SizeFitter,
- Expander>>
-{
-private:
- using TBase = TTable<Hash,
- KeyEqual,
- Container,
- NPrivate::TMapKeyGetter,
- Probing,
- SizeFitter,
- Expander>;
-
- static_assert(std::is_same<std::pair<const Key, T>, typename Container::value_type>::value);
-
-public:
- using key_type = Key;
- using mapped_type = T;
- using typename TBase::value_type;
- using typename TBase::size_type;
- using typename TBase::difference_type;
- using typename TBase::hasher;
- using typename TBase::key_equal;
- using typename TBase::reference;
- using typename TBase::const_reference;
- using typename TBase::iterator;
- using typename TBase::const_iterator;
- using typename TBase::allocator_type;
- using typename TBase::pointer;
- using typename TBase::const_pointer;
-
-private:
- static constexpr size_type INIT_SIZE = 8;
-
-public:
- TMap() : TBase(INIT_SIZE) {}
-
- template <class... Rest>
- TMap(size_type initSize, Rest&&... rest) : TBase(initSize, std::forward<Rest>(rest)...) {}
-
- template <class I, class... Rest>
- TMap(I first, I last,
- std::enable_if_t<NConcepts::IteratorV<I>, size_type> initSize = INIT_SIZE,
- Rest&&... rest)
- : TBase(initSize, std::forward<Rest>(rest)...)
- {
- insert(first, last);
- }
-
- template <class... Rest>
- TMap(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE, Rest&&... rest)
- : TBase(initSize, std::forward<Rest>(rest)...)
- {
- insert(il.begin(), il.end());
- }
-
- TMap(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE)
- : TBase(initSize)
- {
- insert(il.begin(), il.end());
- }
-
- TMap(const TMap&) = default;
- TMap(TMap&&) = default;
-
- TMap& operator=(const TMap&) = default;
- TMap& operator=(TMap&&) = default;
-
- // Iterators
- using TBase::begin;
- using TBase::cbegin;
- using TBase::end;
- using TBase::cend;
-
- // Capacity
- using TBase::empty;
- using TBase::size;
-
- // Modifiers
- using TBase::clear;
- using TBase::insert;
- using TBase::emplace;
- using TBase::emplace_hint;
- using TBase::erase;
- using TBase::swap;
-
- template <class V>
- std::pair<iterator, bool> insert_or_assign(const key_type& k, V&& v) {
- return InsertOrAssignImpl(k, std::forward<V>(v));
- }
- template <class V>
- std::pair<iterator, bool> insert_or_assign(key_type&& k, V&& v) {
- return InsertOrAssignImpl(std::move(k), std::forward<V>(v));
- }
-
- template <class V>
- iterator insert_or_assign(const_iterator, const key_type& k, V&& v) { // TODO(tender-bum)
- return insert_or_assign(k, std::forward<V>(v)).first;
- }
- template <class V>
- iterator insert_or_assign(const_iterator, key_type&& k, V&& v) { // TODO(tender-bum)
- return insert_or_assign(std::move(k), std::forward<V>(v)).first;
- }
-
- template <class... Args>
- std::pair<iterator, bool> try_emplace(const key_type& key, Args&&... args) {
- return TryEmplaceImpl(key, std::forward<Args>(args)...);
- }
- template <class... Args>
- std::pair<iterator, bool> try_emplace(key_type&& key, Args&&... args) {
- return TryEmplaceImpl(std::move(key), std::forward<Args>(args)...);
- }
-
- template <class... Args>
- iterator try_emplace(const_iterator, const key_type& key, Args&&... args) { // TODO(tender-bum)
- return try_emplace(key, std::forward<Args>(args)...).first;
- }
- template <class... Args>
- iterator try_emplace(const_iterator, key_type&& key, Args&&... args) { // TODO(tender-bum)
- return try_emplace(std::move(key), std::forward<Args>(args)...).first;
- }
-
- // Lookup
- using TBase::count;
- using TBase::find;
- using TBase::contains;
-
- template <class K>
- mapped_type& at(const K& key) {
- auto it = find(key);
- if (it == end()) {
- throw std::out_of_range{ "no such key in map" };
- }
- return it->second;
- }
-
- template <class K>
- const mapped_type& at(const K& key) const { return const_cast<TMap*>(this)->at(key); }
-
- template <class K>
- Y_FORCE_INLINE mapped_type& operator[](K&& key) {
- return TBase::TryCreate(key, [&](size_type idx) {
- TBase::Buckets_.InitNode(idx, std::forward<K>(key), mapped_type{});
- }).first->second;
- }
-
- // Bucket interface
- using TBase::bucket_count;
- using TBase::bucket_size;
-
- // Hash policy
- using TBase::load_factor;
- using TBase::rehash;
- using TBase::reserve;
-
- // Observers
- using TBase::hash_function;
- using TBase::key_eq;
-
- friend bool operator==(const TMap& lhs, const TMap& rhs) {
- return lhs.size() == rhs.size() && AllOf(lhs, [&rhs](const auto& v) {
- auto it = rhs.find(v.first);
- return it != rhs.end() && *it == v;
- });
- }
-
- friend bool operator!=(const TMap& lhs, const TMap& rhs) { return !(lhs == rhs); }
-
-private:
- template <class K, class... Args>
- std::pair<iterator, bool> TryEmplaceImpl(K&& key, Args&&... args) {
- return TBase::TryCreate(key, [&](size_type idx) {
- TBase::Buckets_.InitNode(
- idx,
- std::piecewise_construct,
- std::forward_as_tuple(std::forward<K>(key)),
- std::forward_as_tuple(std::forward<Args>(args)...));
- });
- }
-
- template <class K, class V>
- std::pair<iterator, bool> InsertOrAssignImpl(K&& key, V&& v) {
- auto p = try_emplace(std::forward<K>(key), std::forward<V>(v));
- if (!p.second) {
- p.first->second = std::forward<V>(v);
- }
- return p;
- }
-};
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/probings.cpp b/library/cpp/containers/flat_hash/lib/probings.cpp
deleted file mode 100644
index f10c6af113..0000000000
--- a/library/cpp/containers/flat_hash/lib/probings.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "probings.h"
diff --git a/library/cpp/containers/flat_hash/lib/probings.h b/library/cpp/containers/flat_hash/lib/probings.h
deleted file mode 100644
index 886be59cff..0000000000
--- a/library/cpp/containers/flat_hash/lib/probings.h
+++ /dev/null
@@ -1,45 +0,0 @@
-#pragma once
-
-#include <type_traits>
-
-namespace NFlatHash {
-
-class TLinearProbing {
-public:
- template <class SizeFitter, class F>
- static auto FindBucket(SizeFitter sf, size_t idx, size_t sz, F f) {
- idx = sf.EvalIndex(idx, sz);
- while (!f(idx)) {
- idx = sf.EvalIndex(++idx, sz);
- }
- return idx;
- }
-};
-
-class TQuadraticProbing {
-public:
- template <class SizeFitter, class F>
- static auto FindBucket(SizeFitter sf, size_t idx, size_t sz, F f) {
- idx = sf.EvalIndex(idx, sz);
- size_t k = 0;
- while (!f(idx)) {
- idx = sf.EvalIndex(idx + 2 * ++k - 1, sz);
- }
- return idx;
- }
-};
-
-class TDenseProbing {
-public:
- template <class SizeFitter, class F>
- static auto FindBucket(SizeFitter sf, size_t idx, size_t sz, F f) {
- idx = sf.EvalIndex(idx, sz);
- size_t k = 0;
- while (!f(idx)) {
- idx = sf.EvalIndex(idx + ++k, sz);
- }
- return idx;
- }
-};
-
-} // NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/set.cpp b/library/cpp/containers/flat_hash/lib/set.cpp
deleted file mode 100644
index aa2f9c58e1..0000000000
--- a/library/cpp/containers/flat_hash/lib/set.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "set.h"
diff --git a/library/cpp/containers/flat_hash/lib/set.h b/library/cpp/containers/flat_hash/lib/set.h
deleted file mode 100644
index 5266293c6c..0000000000
--- a/library/cpp/containers/flat_hash/lib/set.h
+++ /dev/null
@@ -1,147 +0,0 @@
-#pragma once
-
-#include "table.h"
-#include "concepts/iterator.h"
-
-#include <util/generic/algorithm.h>
-
-namespace NFlatHash {
-
-namespace NPrivate {
-
-struct TSimpleKeyGetter {
- template <class T>
- static constexpr auto& Apply(T& t) noexcept { return t; };
-
- template <class T>
- static constexpr const auto& Apply(const T& t) noexcept { return t; };
-};
-
-} // namespace NPrivate
-
-template <class Key,
- class Hash,
- class KeyEqual,
- class Container,
- class Probing,
- class SizeFitter,
- class Expander>
-class TSet : private TTable<Hash,
- KeyEqual,
- Container,
- NPrivate::TSimpleKeyGetter,
- Probing,
- SizeFitter,
- Expander,
- std::add_const>
-{
-private:
- using TBase = TTable<Hash,
- KeyEqual,
- Container,
- NPrivate::TSimpleKeyGetter,
- Probing,
- SizeFitter,
- Expander,
- std::add_const>;
-
- static_assert(std::is_same_v<Key, typename Container::value_type>);
-
-public:
- using key_type = Key;
- using typename TBase::value_type;
- using typename TBase::size_type;
- using typename TBase::difference_type;
- using typename TBase::hasher;
- using typename TBase::key_equal;
- using typename TBase::reference;
- using typename TBase::const_reference;
- using typename TBase::iterator;
- using typename TBase::const_iterator;
- using typename TBase::allocator_type;
- using typename TBase::pointer;
- using typename TBase::const_pointer;
-
-private:
- static constexpr size_type INIT_SIZE = 8;
-
-public:
- TSet() : TBase(INIT_SIZE) {}
-
- template <class... Rest>
- TSet(size_type initSize, Rest&&... rest) : TBase(initSize, std::forward<Rest>(rest)...) {}
-
- template <class I, class... Rest>
- TSet(I first, I last,
- std::enable_if_t<NConcepts::IteratorV<I>, size_type> initSize = INIT_SIZE,
- Rest&&... rest)
- : TBase(initSize, std::forward<Rest>(rest)...)
- {
- insert(first, last);
- }
-
- template <class... Rest>
- TSet(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE, Rest&&... rest)
- : TBase(initSize, std::forward<Rest>(rest)...)
- {
- insert(il.begin(), il.end());
- }
-
- TSet(std::initializer_list<value_type> il, size_type initSize = INIT_SIZE)
- : TBase(initSize)
- {
- insert(il.begin(), il.end());
- }
-
- TSet(const TSet&) = default;
- TSet(TSet&&) = default;
-
- TSet& operator=(const TSet&) = default;
- TSet& operator=(TSet&&) = default;
-
- // Iterators
- using TBase::begin;
- using TBase::cbegin;
- using TBase::end;
- using TBase::cend;
-
- // Capacity
- using TBase::empty;
- using TBase::size;
-
- // Modifiers
- using TBase::clear;
- using TBase::insert;
- using TBase::emplace;
- using TBase::emplace_hint;
- using TBase::erase;
- using TBase::swap;
-
- // Lookup
- using TBase::count;
- using TBase::find;
- using TBase::contains;
-
- // Bucket interface
- using TBase::bucket_count;
- using TBase::bucket_size;
-
- // Hash policy
- using TBase::load_factor;
- using TBase::rehash;
- using TBase::reserve;
-
- // Observers
- using TBase::hash_function;
- using TBase::key_eq;
-
- friend bool operator==(const TSet& lhs, const TSet& rhs) {
- return lhs.size() == rhs.size() && AllOf(lhs, [&rhs](const auto& v) {
- return rhs.contains(v);
- });
- }
-
- friend bool operator!=(const TSet& lhs, const TSet& rhs) { return !(lhs == rhs); }
-};
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/size_fitters.cpp b/library/cpp/containers/flat_hash/lib/size_fitters.cpp
deleted file mode 100644
index f1431c27e3..0000000000
--- a/library/cpp/containers/flat_hash/lib/size_fitters.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "size_fitters.h"
diff --git a/library/cpp/containers/flat_hash/lib/size_fitters.h b/library/cpp/containers/flat_hash/lib/size_fitters.h
deleted file mode 100644
index 86bd617342..0000000000
--- a/library/cpp/containers/flat_hash/lib/size_fitters.h
+++ /dev/null
@@ -1,47 +0,0 @@
-#pragma once
-
-#include "concepts/size_fitter.h"
-
-#include <util/system/yassert.h>
-#include <util/generic/bitops.h>
-
-namespace NFlatHash {
-
-class TAndSizeFitter {
-public:
- size_t EvalIndex(size_t hs, size_t sz) const noexcept {
- Y_ASSERT(Mask_ == sz - 1);
- return (hs & Mask_);
- }
-
- size_t EvalSize(size_t sz) const noexcept {
- return FastClp2(sz);
- }
-
- void Update(size_t sz) noexcept {
- Y_ASSERT((sz & (sz - 1)) == 0);
- Mask_ = sz - 1;
- }
-
-private:
- size_t Mask_ = 0;
-};
-
-static_assert(NConcepts::SizeFitterV<TAndSizeFitter>);
-
-class TModSizeFitter {
-public:
- constexpr size_t EvalIndex(size_t hs, size_t sz) const noexcept {
- return hs % sz;
- }
-
- constexpr size_t EvalSize(size_t sz) const noexcept {
- return sz;
- }
-
- constexpr void Update(size_t) noexcept {}
-};
-
-static_assert(NConcepts::SizeFitterV<TModSizeFitter>);
-
-} // NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/table.cpp b/library/cpp/containers/flat_hash/lib/table.cpp
deleted file mode 100644
index e89d72ad94..0000000000
--- a/library/cpp/containers/flat_hash/lib/table.cpp
+++ /dev/null
@@ -1 +0,0 @@
-#include "table.h"
diff --git a/library/cpp/containers/flat_hash/lib/table.h b/library/cpp/containers/flat_hash/lib/table.h
deleted file mode 100644
index b84a052be7..0000000000
--- a/library/cpp/containers/flat_hash/lib/table.h
+++ /dev/null
@@ -1,314 +0,0 @@
-#pragma once
-
-#include "iterator.h"
-#include "concepts/container.h"
-#include "concepts/size_fitter.h"
-
-#include <util/generic/utility.h>
-
-#include <functional>
-
-namespace NFlatHash {
-
-namespace NPrivate {
-
-template <class T>
-struct TTypeIdentity { using type = T; };
-
-} // namespace NPrivate
-
-template <
- class Hash,
- class KeyEqual,
- class Container,
- class KeyGetter,
- class Probing,
- class SizeFitter,
- class Expander,
- // Used in the TSet to make iterator behave as const_iterator
- template <class> class IteratorModifier = NPrivate::TTypeIdentity>
-class TTable {
-private:
- static_assert(NConcepts::ContainerV<Container>);
- static_assert(NConcepts::SizeFitterV<SizeFitter>);
-
- template <class C, class V>
- class TIteratorImpl : public TIterator<C, V> {
- private:
- using TBase = TIterator<C, V>;
- friend class TTable;
-
- using TBase::TBase;
-
- public:
- TIteratorImpl() : TBase(nullptr, 0) {}
- };
-
-public:
- using value_type = typename Container::value_type;
- using size_type = typename Container::size_type;
- using difference_type = typename Container::difference_type;
- using hasher = Hash;
- using key_equal = KeyEqual;
-
- using reference = value_type&;
- using const_reference = const value_type&;
-
- using iterator = TIteratorImpl<typename IteratorModifier<Container>::type,
- typename IteratorModifier<value_type>::type>;
- using const_iterator = TIteratorImpl<const Container, const value_type>;
- using allocator_type = typename Container::allocator_type;
- using pointer = typename Container::pointer;
- using const_pointer = typename Container::const_pointer;
-
-private:
- TTable(Container buckets)
- : Buckets_(std::move(buckets))
- {
- SizeFitter_.Update(bucket_count());
- }
-
- static constexpr size_type INIT_SIZE = 8;
-
-public:
- template <class... Rest>
- TTable(size_type initSize, Rest&&... rest)
- : Buckets_(initSize == 0 ? INIT_SIZE : SizeFitter_.EvalSize(initSize),
- std::forward<Rest>(rest)...)
- {
- SizeFitter_.Update(bucket_count());
- }
-
- TTable(const TTable&) = default;
- TTable(TTable&& rhs)
- : SizeFitter_(std::move(rhs.SizeFitter_))
- , Buckets_(std::move(rhs.Buckets_))
- , Hasher_(std::move(rhs.Hasher_))
- , KeyEqual_(std::move(rhs.KeyEqual_))
- {
- TTable tmp{ Buckets_.Clone(INIT_SIZE) };
- tmp.swap(rhs);
- }
-
- TTable& operator=(const TTable&) = default;
- TTable& operator=(TTable&& rhs) {
- TTable tmp(std::move(rhs));
- swap(tmp);
- return *this;
- }
-
- // Iterators
- iterator begin() { return &Buckets_; }
- const_iterator begin() const { return const_cast<TTable*>(this)->begin(); }
- const_iterator cbegin() const { return begin(); }
-
- iterator end() { return { &Buckets_, bucket_count() }; }
- const_iterator end() const { return const_cast<TTable*>(this)->end(); }
- const_iterator cend() const { return end(); }
-
- // Capacity
- bool empty() const noexcept { return size() == 0; }
- size_type size() const noexcept { return Buckets_.Taken(); }
-
- // Modifiers
- void clear() {
- Container tmp(Buckets_.Clone(bucket_count()));
- Buckets_.Swap(tmp);
- }
-
- std::pair<iterator, bool> insert(const value_type& value) { return InsertImpl(value); }
- std::pair<iterator, bool> insert(value_type&& value) { return InsertImpl(std::move(value)); }
-
- template <class T>
- std::enable_if_t<!std::is_same_v<std::decay_t<T>, value_type>,
- std::pair<iterator, bool>> insert(T&& value) {
- return insert(value_type(std::forward<T>(value)));
- }
-
- iterator insert(const_iterator, const value_type& value) { // TODO(tender-bum)
- return insert(value).first;
- }
- iterator insert(const_iterator, value_type&& value) { // TODO(tender-bum)
- return insert(std::move(value)).first;
- }
-
- template <class T>
- iterator insert(const_iterator, T&& value) { // TODO(tender-bum)
- return insert(value_type(std::forward<T>(value))).first;
- }
-
- template <class InputIt>
- void insert(InputIt first, InputIt last) {
- while (first != last) {
- insert(*first++);
- }
- }
-
- void insert(std::initializer_list<value_type> il) {
- insert(il.begin(), il.end());
- }
-
- template <class... Args>
- std::pair<iterator, bool> emplace(Args&&... args) {
- return insert(value_type(std::forward<Args>(args)...));
- }
-
- template <class... Args>
- iterator emplace_hint(const_iterator, Args&&... args) { // TODO(tender-bum)
- return emplace(std::forward<Args>(args)...).first;
- }
-
- void erase(const_iterator pos) {
- static_assert(NConcepts::RemovalContainerV<Container>,
- "That kind of table doesn't allow erasing. Use another table instead.");
- if constexpr (NConcepts::RemovalContainerV<Container>) {
- Buckets_.DeleteNode(pos.Idx_);
- }
- }
-
- void erase(const_iterator f, const_iterator l) {
- while (f != l) {
- auto nxt = f;
- ++nxt;
- erase(f);
- f = nxt;
- }
- }
-
- template <class K>
- std::enable_if_t<!std::is_convertible_v<K, iterator> && !std::is_convertible_v<K, const_iterator>,
- size_type> erase(const K& key) {
- auto it = find(key);
- if (it != end()) {
- erase(it);
- return 1;
- }
- return 0;
- }
-
- void swap(TTable& rhs)
- noexcept(noexcept(std::declval<Container>().Swap(std::declval<Container&>())))
- {
- DoSwap(SizeFitter_, rhs.SizeFitter_);
- Buckets_.Swap(rhs.Buckets_);
- DoSwap(Hasher_, rhs.Hasher_);
- DoSwap(KeyEqual_, rhs.KeyEqual_);
- }
-
- // Lookup
- template <class K>
- size_type count(const K& key) const { return contains(key); }
-
- template <class K>
- iterator find(const K& key) {
- size_type hs = hash_function()(key);
- auto idx = FindProperBucket(hs, key);
- if (Buckets_.IsTaken(idx)) {
- return { &Buckets_, idx };
- }
- return end();
- }
-
- template <class K>
- const_iterator find(const K& key) const { return const_cast<TTable*>(this)->find(key); }
-
- template <class K>
- bool contains(const K& key) const {
- size_type hs = hash_function()(key);
- return Buckets_.IsTaken(FindProperBucket(hs, key));
- }
-
- // Bucket interface
- size_type bucket_count() const noexcept { return Buckets_.Size(); }
- size_type bucket_size(size_type idx) const { return Buckets_.IsTaken(idx); }
-
- // Hash policy
- float load_factor() const noexcept {
- return (float)(bucket_count() - Buckets_.Empty()) / bucket_count();
- }
-
- void rehash(size_type sz) {
- if (sz != 0) {
- auto newBuckets = SizeFitter_.EvalSize(sz);
- size_type occupied = bucket_count() - Buckets_.Empty();
- if (Expander::NeedGrow(occupied, newBuckets)) {
- newBuckets = Max(newBuckets, SizeFitter_.EvalSize(Expander::SuitableSize(size())));
- }
- RehashImpl(newBuckets);
- } else {
- RehashImpl(SizeFitter_.EvalSize(Expander::SuitableSize(size())));
- }
- }
-
- void reserve(size_type sz) { rehash(sz); } // TODO(tender-bum)
-
- // Observers
- constexpr auto hash_function() const noexcept { return Hasher_; }
- constexpr auto key_eq() const noexcept { return KeyEqual_; }
-
-public:
- template <class T>
- std::pair<iterator, bool> InsertImpl(T&& value) {
- return TryCreate(KeyGetter::Apply(value), [&](size_type idx) {
- Buckets_.InitNode(idx, std::forward<T>(value));
- });
- }
-
- template <class T, class F>
- Y_FORCE_INLINE std::pair<iterator, bool> TryCreate(const T& key, F nodeInit) {
- size_type hs = hash_function()(key);
- size_type idx = FindProperBucket(hs, key);
- if (!Buckets_.IsTaken(idx)) {
- if (Expander::WillNeedGrow(bucket_count() - Buckets_.Empty(), bucket_count())) {
- RehashImpl();
- idx = FindProperBucket(hs, key);
- }
- nodeInit(idx);
- return { iterator{ &Buckets_, idx }, true };
- }
- return { iterator{ &Buckets_, idx }, false };
- }
-
- template <class K>
- size_type FindProperBucket(size_type hs, const K& key) const {
- return Probing::FindBucket(SizeFitter_, hs, bucket_count(), [&](size_type idx) {
- if constexpr (NConcepts::RemovalContainerV<Container>) {
- return Buckets_.IsEmpty(idx) ||
- Buckets_.IsTaken(idx) && key_eq()(KeyGetter::Apply(Buckets_.Node(idx)), key);
- } else {
- return Buckets_.IsEmpty(idx) || key_eq()(KeyGetter::Apply(Buckets_.Node(idx)), key);
- }
- });
- }
-
- void RehashImpl() {
- if constexpr (NConcepts::RemovalContainerV<Container>) {
- size_type occupied = bucket_count() - Buckets_.Empty();
- if (size() < occupied / 2) {
- rehash(bucket_count()); // Just clearing all deleted elements
- } else {
- RehashImpl(SizeFitter_.EvalSize(Expander::EvalNewSize(bucket_count())));
- }
- } else {
- RehashImpl(SizeFitter_.EvalSize(Expander::EvalNewSize(bucket_count())));
- }
- }
-
- void RehashImpl(size_type newSize) {
- TTable tmp = Buckets_.Clone(newSize);
- for (auto& value : *this) {
- size_type hs = hash_function()(KeyGetter::Apply(value));
- tmp.Buckets_.InitNode(
- tmp.FindProperBucket(hs, KeyGetter::Apply(value)), std::move_if_noexcept(value));
- }
- swap(tmp);
- }
-
-public:
- SizeFitter SizeFitter_;
- Container Buckets_;
- hasher Hasher_;
- key_equal KeyEqual_;
-};
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/lib/value_markers.cpp b/library/cpp/containers/flat_hash/lib/value_markers.cpp
deleted file mode 100644
index e69de29bb2..0000000000
--- a/library/cpp/containers/flat_hash/lib/value_markers.cpp
+++ /dev/null
diff --git a/library/cpp/containers/flat_hash/lib/value_markers.h b/library/cpp/containers/flat_hash/lib/value_markers.h
deleted file mode 100644
index 99351586b5..0000000000
--- a/library/cpp/containers/flat_hash/lib/value_markers.h
+++ /dev/null
@@ -1,130 +0,0 @@
-#pragma once
-
-#include "concepts/value_marker.h"
-
-#include <type_traits>
-#include <tuple>
-
-namespace NFlatHash {
-
-namespace NSet {
-
-template <auto Value>
-struct TStaticValueMarker {
- using value_type = decltype(Value);
-
- constexpr auto Create() const noexcept {
- return Value;
- }
-
- template <class U>
- bool Equals(const U& rhs) const {
- return Value == rhs;
- }
-};
-
-static_assert(NConcepts::ValueMarkerV<TStaticValueMarker<5>>);
-
-template <class T>
-class TEqValueMarker {
-public:
- using value_type = T;
-
- template <class V, class = std::enable_if_t<std::is_constructible_v<T, std::decay_t<V>>>>
- TEqValueMarker(V&& v) : Value_(std::forward<V>(v)) {}
-
- TEqValueMarker(const TEqValueMarker&) = default;
- TEqValueMarker(TEqValueMarker&&) = default;
-
- TEqValueMarker& operator=(const TEqValueMarker&) = default;
- TEqValueMarker& operator=(TEqValueMarker&&) = default;
-
- const T& Create() const noexcept {
- return Value_;
- }
-
- template <class U>
- bool Equals(const U& rhs) const {
- return Value_ == rhs;
- }
-
-private:
- T Value_;
-};
-
-static_assert(NConcepts::ValueMarkerV<TEqValueMarker<int>>);
-
-} // namespace NSet
-
-namespace NMap {
-
-template <auto Key, class T>
-class TStaticValueMarker {
- static_assert(std::is_default_constructible_v<T>);
-
-public:
- using value_type = std::pair<decltype(Key), T>;
-
- TStaticValueMarker() = default;
-
- TStaticValueMarker(const TStaticValueMarker&) {}
- TStaticValueMarker(TStaticValueMarker&&) {}
-
- TStaticValueMarker& operator=(const TStaticValueMarker&) noexcept { return *this; }
- TStaticValueMarker& operator=(TStaticValueMarker&&) noexcept { return *this; }
-
- std::pair<decltype(Key), const T&> Create() const noexcept { return { Key, Value_ }; }
-
- template <class U>
- bool Equals(const U& rhs) const {
- return Key == rhs.first;
- }
-
-private:
- T Value_;
-};
-
-static_assert(NConcepts::ValueMarkerV<TStaticValueMarker<5, int>>);
-
-template <class Key, class T>
-class TEqValueMarker {
- static_assert(std::is_default_constructible_v<T>);
-
-public:
- using value_type = std::pair<Key, T>;
-
- template <class V, class = std::enable_if_t<std::is_constructible_v<Key, std::decay_t<V>>>>
- TEqValueMarker(V&& v) : Key_(std::forward<V>(v)) {}
-
- TEqValueMarker(const TEqValueMarker& vm)
- : Key_(vm.Key_) {}
- TEqValueMarker(TEqValueMarker&& vm) noexcept(std::is_nothrow_move_constructible_v<Key>
- && std::is_nothrow_constructible_v<T>)
- : Key_(std::move(vm.Key_)) {}
-
- TEqValueMarker& operator=(const TEqValueMarker& vm) {
- Key_ = vm.Key_;
- return *this;
- }
- TEqValueMarker& operator=(TEqValueMarker&& vm) noexcept(std::is_nothrow_move_assignable_v<Key>) {
- Key_ = std::move(vm.Key_);
- return *this;
- }
-
- auto Create() const noexcept { return std::tie(Key_, Value_); }
-
- template <class U>
- bool Equals(const U& rhs) const {
- return Key_ == rhs.first;
- }
-
-private:
- Key Key_;
- T Value_;
-};
-
-static_assert(NConcepts::ValueMarkerV<TEqValueMarker<int, int>>);
-
-} // namespace NMap
-
-} // namespace NFlatHash
diff --git a/library/cpp/containers/flat_hash/ut/containers_ut.cpp b/library/cpp/containers/flat_hash/ut/containers_ut.cpp
deleted file mode 100644
index b17b30fa80..0000000000
--- a/library/cpp/containers/flat_hash/ut/containers_ut.cpp
+++ /dev/null
@@ -1,410 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/containers.h>
-
-#include <library/cpp/testing/unittest/registar.h>
-
-#include <util/generic/algorithm.h>
-#include <util/random/random.h>
-#include <util/random/shuffle.h>
-
-using namespace NFlatHash;
-
-namespace {
- constexpr size_t INIT_SIZE = 128;
-
- struct TDummy {
- static size_t Count;
-
- TDummy() { ++Count; }
- TDummy(const TDummy&) { ++Count; }
- ~TDummy() { --Count; }
- };
- size_t TDummy::Count = 0;
-
- struct TAlmostDummy {
- static size_t Count;
-
- TAlmostDummy(int j = 0) : Junk(j) { ++Count; }
- TAlmostDummy(const TAlmostDummy& d) : Junk(d.Junk) { ++Count; }
- ~TAlmostDummy() { --Count; }
-
- bool operator==(const TAlmostDummy& r) const { return Junk == r.Junk; };
- bool operator!=(const TAlmostDummy& r) const { return !operator==(r); };
-
- int Junk;
- };
- size_t TAlmostDummy::Count = 0;
-
- struct TNotSimple {
- enum class EType {
- Value,
- Empty,
- Deleted
- } Type_ = EType::Value;
-
- TString Junk = "something"; // to prevent triviality propagation
- int Value = 0;
-
- static int CtorCalls;
- static int DtorCalls;
- static int CopyCtorCalls;
- static int MoveCtorCalls;
-
- TNotSimple() {
- ++CtorCalls;
- }
- explicit TNotSimple(int value)
- : Value(value)
- {
- ++CtorCalls;
- }
-
- TNotSimple(const TNotSimple& rhs) {
- ++CopyCtorCalls;
- Value = rhs.Value;
- Type_ = rhs.Type_;
- }
- TNotSimple(TNotSimple&& rhs) {
- ++MoveCtorCalls;
- Value = rhs.Value;
- Type_ = rhs.Type_;
- }
-
- ~TNotSimple() {
- ++DtorCalls;
- }
-
- TNotSimple& operator=(const TNotSimple& rhs) {
- ++CopyCtorCalls;
- Value = rhs.Value;
- Type_ = rhs.Type_;
- return *this;
- }
- TNotSimple& operator=(TNotSimple&& rhs) {
- ++MoveCtorCalls;
- Value = rhs.Value;
- Type_ = rhs.Type_;
- return *this;
- }
-
- static TNotSimple Empty() {
- TNotSimple ret;
- ret.Type_ = EType::Empty;
- return ret;
- }
-
- static TNotSimple Deleted() {
- TNotSimple ret;
- ret.Type_ = EType::Deleted;
- return ret;
- }
-
- bool operator==(const TNotSimple& rhs) const noexcept {
- return Value == rhs.Value;
- }
-
- static void ResetStats() {
- CtorCalls = 0;
- DtorCalls = 0;
- CopyCtorCalls = 0;
- MoveCtorCalls = 0;
- }
- };
-
- int TNotSimple::CtorCalls = 0;
- int TNotSimple::DtorCalls = 0;
- int TNotSimple::CopyCtorCalls = 0;
- int TNotSimple::MoveCtorCalls = 0;
-
- struct TNotSimpleEmptyMarker {
- using value_type = TNotSimple;
-
- value_type Create() const {
- return TNotSimple::Empty();
- }
-
- bool Equals(const value_type& rhs) const {
- return rhs.Type_ == TNotSimple::EType::Empty;
- }
- };
-
- struct TNotSimpleDeletedMarker {
- using value_type = TNotSimple;
-
- value_type Create() const {
- return TNotSimple::Deleted();
- }
-
- bool Equals(const value_type& rhs) const {
- return rhs.Type_ == TNotSimple::EType::Deleted;
- }
- };
-
- template <class Container>
- void CheckContainersEqual(const Container& a, const Container& b) {
- UNIT_ASSERT_EQUAL(a.Size(), b.Size());
- UNIT_ASSERT_EQUAL(a.Taken(), b.Empty());
- for (typename Container::size_type i = 0; i < a.Size(); ++i) {
- if (a.IsTaken(i)) {
- UNIT_ASSERT(b.IsTaken(i));
- UNIT_ASSERT_EQUAL(a.Node(i), b.Node(i));
- }
- }
- }
-
- template <class Container, class... Args>
- void SmokingTest(typename Container::size_type size, Args&&... args) {
- using size_type = typename Container::size_type;
- using value_type = typename Container::value_type;
-
- Container cont(size, std::forward<Args>(args)...);
- UNIT_ASSERT_EQUAL(cont.Size(), size);
- UNIT_ASSERT_EQUAL(cont.Taken(), 0);
-
- for (size_type i = 0; i < cont.Size(); ++i) {
- UNIT_ASSERT(cont.IsEmpty(i));
- UNIT_ASSERT(!cont.IsTaken(i));
- }
-
- // Filling the container till half
- TVector<size_type> toInsert(cont.Size());
- Iota(toInsert.begin(), toInsert.end(), 0);
- Shuffle(toInsert.begin(), toInsert.end());
- toInsert.resize(toInsert.size() / 2);
- for (auto i : toInsert) {
- UNIT_ASSERT(cont.IsEmpty(i));
- UNIT_ASSERT(!cont.IsTaken(i));
- value_type value(RandomNumber<size_type>(cont.Size()));
- cont.InitNode(i, value);
- UNIT_ASSERT(!cont.IsEmpty(i));
- UNIT_ASSERT(cont.IsTaken(i));
- UNIT_ASSERT_EQUAL(cont.Node(i), value);
- }
- UNIT_ASSERT_EQUAL(cont.Taken(), toInsert.size());
-
- // Copy construction test
- auto cont2 = cont;
- CheckContainersEqual(cont, cont2);
-
- // Copy assignment test
- cont2 = cont2.Clone(0);
- UNIT_ASSERT_EQUAL(cont2.Size(), 0);
- UNIT_ASSERT_EQUAL(cont2.Taken(), 0);
-
- // Copy assignment test
- cont2 = cont;
- CheckContainersEqual(cont, cont2);
-
- // Move construction test
- auto cont3 = std::move(cont2);
- UNIT_ASSERT_EQUAL(cont2.Size(), 0);
- CheckContainersEqual(cont, cont3);
-
- // Move assignment test
- cont2 = std::move(cont3);
- UNIT_ASSERT_EQUAL(cont3.Size(), 0);
- CheckContainersEqual(cont, cont2);
- }
-}
-
-Y_UNIT_TEST_SUITE(TFlatContainerTest) {
- Y_UNIT_TEST(SmokingTest) {
- SmokingTest<TFlatContainer<int>>(INIT_SIZE);
- }
-
- Y_UNIT_TEST(SmokingTestNotSimpleType) {
- TNotSimple::ResetStats();
- SmokingTest<TFlatContainer<TNotSimple>>(INIT_SIZE);
-
- UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls + TNotSimple::CopyCtorCalls + TNotSimple::MoveCtorCalls,
- TNotSimple::DtorCalls);
- UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls, INIT_SIZE / 2 /* created while filling */);
- UNIT_ASSERT_EQUAL(TNotSimple::DtorCalls, INIT_SIZE / 2 /* removed filling temporary */
- + INIT_SIZE / 2 /* removed while cloning */
- + INIT_SIZE /* 3 containers dtors */);
- UNIT_ASSERT_EQUAL(TNotSimple::CopyCtorCalls, INIT_SIZE / 2 /* 3 created while filling */
- + INIT_SIZE / 2 /* created while copy constructing */
- + INIT_SIZE / 2/* created while copy assigning */);
- UNIT_ASSERT_EQUAL(TNotSimple::MoveCtorCalls, 0);
- }
-
- Y_UNIT_TEST(DummyHalfSizeTest) {
- using TContainer = TFlatContainer<TDummy>;
- using size_type = typename TContainer::size_type;
-
- {
- TContainer cont(INIT_SIZE);
- UNIT_ASSERT_EQUAL(TDummy::Count, 0);
-
- TVector<size_type> toInsert(cont.Size());
- Iota(toInsert.begin(), toInsert.end(), 0);
- Shuffle(toInsert.begin(), toInsert.end());
- toInsert.resize(toInsert.size() / 2);
- for (auto i : toInsert) {
- UNIT_ASSERT(cont.IsEmpty(i));
- UNIT_ASSERT(!cont.IsTaken(i));
- cont.InitNode(i);
- UNIT_ASSERT_EQUAL(TDummy::Count, cont.Taken());
- UNIT_ASSERT(!cont.IsEmpty(i));
- UNIT_ASSERT(cont.IsTaken(i));
- }
- UNIT_ASSERT_EQUAL(cont.Taken(), cont.Size() / 2);
- UNIT_ASSERT_EQUAL(TDummy::Count, cont.Taken());
- }
- UNIT_ASSERT_EQUAL(TDummy::Count, 0);
- }
-
- Y_UNIT_TEST(DeleteTest) {
- using TContainer = TFlatContainer<TDummy>;
- using size_type = typename TContainer::size_type;
-
- TContainer cont(INIT_SIZE);
- auto idx = RandomNumber<size_type>(INIT_SIZE);
- UNIT_ASSERT(!cont.IsTaken(idx));
- UNIT_ASSERT(!cont.IsDeleted(idx));
- UNIT_ASSERT_EQUAL(TDummy::Count, 0);
-
- cont.InitNode(idx);
- UNIT_ASSERT_EQUAL(cont.Taken(), 1);
- UNIT_ASSERT(cont.IsTaken(idx));
- UNIT_ASSERT(!cont.IsDeleted(idx));
- UNIT_ASSERT_EQUAL(TDummy::Count, 1);
-
- cont.DeleteNode(idx);
- UNIT_ASSERT(!cont.IsTaken(idx));
- UNIT_ASSERT(cont.IsDeleted(idx));
- UNIT_ASSERT_EQUAL(TDummy::Count, 0);
- }
-}
-
-Y_UNIT_TEST_SUITE(TDenseContainerTest) {
- Y_UNIT_TEST(SmokingTest) {
- SmokingTest<TDenseContainer<int, NSet::TStaticValueMarker<-1>>>(INIT_SIZE);
- }
-
- Y_UNIT_TEST(NotSimpleTypeSmokingTest) {
- TNotSimple::ResetStats();
- SmokingTest<TDenseContainer<TNotSimple, TNotSimpleEmptyMarker>>(INIT_SIZE);
-
- UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls + TNotSimple::CopyCtorCalls + TNotSimple::MoveCtorCalls,
- TNotSimple::DtorCalls);
- UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls, INIT_SIZE / 2 /* created while filling */
- + 2 /* created by empty marker */);
- UNIT_ASSERT_EQUAL(TNotSimple::DtorCalls, 1 /* removed empty marker temporary */
- + INIT_SIZE /* half removed while resetting in container,
- half removed inserted temporary */
- + INIT_SIZE /* removed while cloning */
- + 1 /* removed empty marker temporary */
- + INIT_SIZE * 2 /* 3 containers dtors */);
- UNIT_ASSERT_EQUAL(TNotSimple::CopyCtorCalls, INIT_SIZE /* created while constructing */
- + INIT_SIZE / 2 /* 3 created while filling */
- + INIT_SIZE /* created while copy constructing */
- + INIT_SIZE /* created while copy assigning */);
- UNIT_ASSERT_EQUAL(TNotSimple::MoveCtorCalls, 0);
- }
-
- Y_UNIT_TEST(RemovalContainerSmokingTest) {
- SmokingTest<TRemovalDenseContainer<int, NSet::TStaticValueMarker<-1>,
- NSet::TStaticValueMarker<-2>>>(INIT_SIZE);
- }
-
- Y_UNIT_TEST(NotSimpleTypeRemovalContainerSmokingTest) {
- TNotSimple::ResetStats();
- SmokingTest<TRemovalDenseContainer<TNotSimple, TNotSimpleEmptyMarker,
- TNotSimpleDeletedMarker>>(INIT_SIZE);
-
- UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls + TNotSimple::CopyCtorCalls + TNotSimple::MoveCtorCalls,
- TNotSimple::DtorCalls);
- UNIT_ASSERT_EQUAL(TNotSimple::CtorCalls, INIT_SIZE / 2 /* created while filling */
- + 2 /* created by empty marker */);
- UNIT_ASSERT_EQUAL(TNotSimple::DtorCalls, 1 /* removed empty marker temporary */
- + INIT_SIZE /* half removed while resetting in container,
- half removed inserted temporary */
- + INIT_SIZE /* removed while cloning */
- + 1 /* removed empty marker temporary */
- + INIT_SIZE * 2 /* 3 containers dtors */);
- UNIT_ASSERT_EQUAL(TNotSimple::CopyCtorCalls, INIT_SIZE /* created while constructing */
- + INIT_SIZE / 2 /* 3 created while filling */
- + INIT_SIZE /* created while copy constructing */
- + INIT_SIZE /* created while copy assigning */);
- UNIT_ASSERT_EQUAL(TNotSimple::MoveCtorCalls, 0);
- }
-
- Y_UNIT_TEST(DummyHalfSizeTest) {
- using TContainer = TDenseContainer<TAlmostDummy, NSet::TEqValueMarker<TAlmostDummy>>;
- using size_type = typename TContainer::size_type;
-
- {
- TContainer cont(INIT_SIZE, TAlmostDummy{-1});
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 1); // 1 for empty marker
-
- TVector<size_type> toInsert(cont.Size());
- Iota(toInsert.begin(), toInsert.end(), 0);
- Shuffle(toInsert.begin(), toInsert.end());
- toInsert.resize(toInsert.size() / 2);
- for (auto i : toInsert) {
- UNIT_ASSERT(cont.IsEmpty(i));
- UNIT_ASSERT(!cont.IsTaken(i));
- cont.InitNode(i, (int)RandomNumber<size_type>(cont.Size()));
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 1);
- UNIT_ASSERT(!cont.IsEmpty(i));
- UNIT_ASSERT(cont.IsTaken(i));
- }
- UNIT_ASSERT_EQUAL(cont.Taken(), toInsert.size());
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 1);
- }
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, 0);
- }
-
- Y_UNIT_TEST(DeleteTest) {
- using TContainer = TRemovalDenseContainer<TAlmostDummy, NSet::TEqValueMarker<TAlmostDummy>,
- NSet::TEqValueMarker<TAlmostDummy>>;
- using size_type = typename TContainer::size_type;
-
- TContainer cont(INIT_SIZE, TAlmostDummy{ -2 }, TAlmostDummy{ -1 });
- auto idx = RandomNumber<size_type>(cont.Size());
- UNIT_ASSERT(!cont.IsTaken(idx));
- UNIT_ASSERT(!cont.IsDeleted(idx));
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 2); // 2 for markers
-
- cont.InitNode(idx, (int)RandomNumber<size_type>(cont.Size()));
- UNIT_ASSERT_EQUAL(cont.Taken(), 1);
- UNIT_ASSERT(cont.IsTaken(idx));
- UNIT_ASSERT(!cont.IsDeleted(idx));
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 2);
-
- cont.DeleteNode(idx);
- UNIT_ASSERT(!cont.IsTaken(idx));
- UNIT_ASSERT(cont.IsDeleted(idx));
- UNIT_ASSERT_EQUAL(TAlmostDummy::Count, cont.Size() + 2);
- }
-
- Y_UNIT_TEST(FancyInitsTest) {
- {
- using TContainer = TDenseContainer<int>;
- TContainer cont{ INIT_SIZE, -1 };
- }
- {
- using TContainer = TDenseContainer<int, NSet::TStaticValueMarker<-1>>;
- TContainer cont{ INIT_SIZE };
- static_assert(!std::is_constructible_v<TContainer, size_t, int>);
- }
- {
- using TContainer = TDenseContainer<int, NSet::TEqValueMarker<int>>;
- TContainer cont{ INIT_SIZE, -1 };
- TContainer cont2{ INIT_SIZE, NSet::TEqValueMarker<int>{ -1 } };
- }
- {
- using TContainer = TRemovalDenseContainer<int>;
- TContainer cont{ INIT_SIZE, -1, -2 };
- TContainer cont2{ INIT_SIZE, NSet::TEqValueMarker<int>{ -1 },
- NSet::TEqValueMarker<int>{ -2 } };
- }
- {
- using TContainer = TRemovalDenseContainer<int, NSet::TStaticValueMarker<-1>,
- NSet::TStaticValueMarker<-1>>;
- TContainer cont{ INIT_SIZE };
- static_assert(!std::is_constructible_v<TContainer, size_t, int>);
- static_assert(!std::is_constructible_v<TContainer, size_t, int, int>);
- }
- }
-}
diff --git a/library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp b/library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp
deleted file mode 100644
index 2b9d6a1dc2..0000000000
--- a/library/cpp/containers/flat_hash/ut/flat_hash_ut.cpp
+++ /dev/null
@@ -1,272 +0,0 @@
-#include <library/cpp/containers/flat_hash/flat_hash.h>
-
-#include <library/cpp/testing/unittest/registar.h>
-
-using namespace NFH;
-
-namespace {
-
-constexpr size_t TEST_INIT_SIZE = 25;
-constexpr std::initializer_list<int> SET_INPUT_SAMPLE{1, 2, 3, 4, 5};
-const std::initializer_list<std::pair<const int, TString>> MAP_INPUT_SAMPLE{
- {1, "a"},
- {2, "b"},
- {3, "c"},
- {4, "d"},
- {5, "e"}
-};
-
-} // namespace
-
-template <class Map>
-class TMapTest : public TTestBase {
- void AllocatorTest();
-
- void SmokingTest() {
- Map mp;
- mp.emplace(5, "abc");
-
- UNIT_ASSERT_EQUAL(mp.size(), 1);
- UNIT_ASSERT(mp.contains(5));
-
- auto it = mp.find(5);
- UNIT_ASSERT_EQUAL(mp.begin(), it);
- UNIT_ASSERT(!mp.empty());
- }
-
- void CopyConstructionTest() {
- Map st(MAP_INPUT_SAMPLE);
- auto st2 = st;
-
- UNIT_ASSERT(!st.empty());
- UNIT_ASSERT(!st2.empty());
- UNIT_ASSERT_EQUAL(st, st2);
- }
-
- void MoveConstructionTest() {
- Map st(MAP_INPUT_SAMPLE);
- auto st2 = std::move(st);
-
- UNIT_ASSERT(st.empty());
- UNIT_ASSERT(!st2.empty());
- UNIT_ASSERT_UNEQUAL(st, st2);
- }
-
- void CopyAssignmentTest() {
- Map st(MAP_INPUT_SAMPLE);
- Map st2;
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(st2.empty());
-
- st2 = st;
- UNIT_ASSERT_EQUAL(st, st2);
- UNIT_ASSERT(!st2.empty());
- }
-
- void DoubleCopyAssignmentTest() {
- Map st(MAP_INPUT_SAMPLE);
- Map st2;
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(st2.empty());
-
- st2 = st;
- UNIT_ASSERT_EQUAL(st, st2);
- UNIT_ASSERT(!st2.empty());
-
- st2 = st;
- UNIT_ASSERT_EQUAL(st, st2);
- UNIT_ASSERT(!st2.empty());
- }
-
- void MoveAssignmentTest() {
- Map st(MAP_INPUT_SAMPLE);
- Map st2;
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(st2.empty());
-
- st2 = std::move(st);
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(!st2.empty());
- UNIT_ASSERT(st.empty());
- }
-
- void InsertOrAssignTest() {
- Map mp;
-
- auto p = mp.insert_or_assign(5, "abc");
- UNIT_ASSERT_EQUAL(p.first, mp.begin());
- UNIT_ASSERT(p.second);
- UNIT_ASSERT_EQUAL(p.first->first, 5);
- UNIT_ASSERT_EQUAL(p.first->second, "abc");
-
- auto p2 = mp.insert_or_assign(5, "def");
- UNIT_ASSERT_EQUAL(p.first, p2.first);
- UNIT_ASSERT(!p2.second);
- UNIT_ASSERT_EQUAL(p2.first->first, 5);
- UNIT_ASSERT_EQUAL(p2.first->second, "def");
- }
-
- void TryEmplaceTest() {
- Map mp;
-
- auto p = mp.try_emplace(5, "abc");
- UNIT_ASSERT_EQUAL(p.first, mp.begin());
- UNIT_ASSERT(p.second);
- UNIT_ASSERT_EQUAL(p.first->first, 5);
- UNIT_ASSERT_EQUAL(p.first->second, "abc");
-
- auto p2 = mp.try_emplace(5, "def");
- UNIT_ASSERT_EQUAL(p.first, p2.first);
- UNIT_ASSERT(!p2.second);
- UNIT_ASSERT_EQUAL(p2.first->first, 5);
- UNIT_ASSERT_EQUAL(p.first->second, "abc");
- }
-
- UNIT_TEST_SUITE_DEMANGLE(TMapTest);
- UNIT_TEST(AllocatorTest);
- UNIT_TEST(SmokingTest);
- UNIT_TEST(CopyConstructionTest);
- UNIT_TEST(MoveConstructionTest);
- UNIT_TEST(CopyAssignmentTest);
- UNIT_TEST(DoubleCopyAssignmentTest);
- UNIT_TEST(MoveAssignmentTest);
- UNIT_TEST(InsertOrAssignTest);
- UNIT_TEST(TryEmplaceTest);
- UNIT_TEST_SUITE_END();
-};
-
-template <>
-void TMapTest<TFlatHashMap<int, TString>>::AllocatorTest() {
- using Map = TFlatHashMap<int, TString>;
- Map mp(3, typename Map::allocator_type());
-}
-
-template <>
-void TMapTest<TDenseHashMapStaticMarker<int, TString, -1>>::AllocatorTest() {
- using Map = TDenseHashMapStaticMarker<int, TString, -1>;
- Map mp(3, NFlatHash::NMap::TStaticValueMarker<-1, TString>(), typename Map::allocator_type());
-}
-
-using TFlatHashMapTest = TMapTest<TFlatHashMap<int, TString>>;
-using TDenseHashMapTest = TMapTest<TDenseHashMapStaticMarker<int, TString, -1>>;
-
-UNIT_TEST_SUITE_REGISTRATION(TFlatHashMapTest);
-UNIT_TEST_SUITE_REGISTRATION(TDenseHashMapTest);
-
-
-template <class Set>
-class TSetTest : public TTestBase {
- void AllocatorTest();
- void DefaultConstructTest() {
- Set st;
-
- UNIT_ASSERT(st.empty());
- UNIT_ASSERT_EQUAL(st.size(), 0);
- UNIT_ASSERT(st.bucket_count() > 0);
- UNIT_ASSERT_EQUAL(st.begin(), st.end());
- UNIT_ASSERT(st.load_factor() < std::numeric_limits<float>::epsilon());
- }
-
- void InitCapacityConstructTest() {
- Set st(TEST_INIT_SIZE);
-
- UNIT_ASSERT(st.empty());
- UNIT_ASSERT_EQUAL(st.size(), 0);
- UNIT_ASSERT(st.bucket_count() >= TEST_INIT_SIZE);
- UNIT_ASSERT_EQUAL(st.begin(), st.end());
- UNIT_ASSERT(st.load_factor() < std::numeric_limits<float>::epsilon());
- }
-
- void IteratorsConstructTest() {
- Set st(SET_INPUT_SAMPLE.begin(), SET_INPUT_SAMPLE.end());
-
- UNIT_ASSERT(!st.empty());
- UNIT_ASSERT_EQUAL(st.size(), SET_INPUT_SAMPLE.size());
- UNIT_ASSERT(st.bucket_count() >= st.size());
- UNIT_ASSERT_UNEQUAL(st.begin(), st.end());
- UNIT_ASSERT_EQUAL(static_cast<size_t>(std::distance(st.begin(), st.end())), st.size());
- UNIT_ASSERT(st.load_factor() > 0);
- }
-
- void InitializerListConstructTest() {
- Set st(SET_INPUT_SAMPLE);
-
- UNIT_ASSERT(!st.empty());
- UNIT_ASSERT(st.size() > 0);
- UNIT_ASSERT(st.bucket_count() > 0);
- UNIT_ASSERT_UNEQUAL(st.begin(), st.end());
- UNIT_ASSERT_EQUAL(static_cast<size_t>(std::distance(st.begin(), st.end())), st.size());
- UNIT_ASSERT(st.load_factor() > 0);
- }
-
- void CopyConstructionTest() {
- Set st(SET_INPUT_SAMPLE);
- auto st2 = st;
-
- UNIT_ASSERT(!st.empty());
- UNIT_ASSERT(!st2.empty());
- UNIT_ASSERT_EQUAL(st, st2);
- }
-
- void MoveConstructionTest() {
- Set st(SET_INPUT_SAMPLE);
- auto st2 = std::move(st);
-
- UNIT_ASSERT(st.empty());
- UNIT_ASSERT(!st2.empty());
- UNIT_ASSERT_UNEQUAL(st, st2);
- }
-
- void CopyAssignmentTest() {
- Set st(SET_INPUT_SAMPLE);
- Set st2;
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(st2.empty());
-
- st2 = st;
- UNIT_ASSERT_EQUAL(st, st2);
- UNIT_ASSERT(!st2.empty());
- }
-
- void MoveAssignmentTest() {
- Set st(SET_INPUT_SAMPLE);
- Set st2;
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(st2.empty());
-
- st2 = std::move(st);
- UNIT_ASSERT_UNEQUAL(st, st2);
- UNIT_ASSERT(!st2.empty());
- UNIT_ASSERT(st.empty());
- }
-
- UNIT_TEST_SUITE_DEMANGLE(TSetTest);
- UNIT_TEST(AllocatorTest);
- UNIT_TEST(DefaultConstructTest);
- UNIT_TEST(InitCapacityConstructTest);
- UNIT_TEST(IteratorsConstructTest);
- UNIT_TEST(InitializerListConstructTest);
- UNIT_TEST(CopyConstructionTest);
- UNIT_TEST(MoveConstructionTest);
- UNIT_TEST(CopyAssignmentTest);
- UNIT_TEST(MoveAssignmentTest);
- UNIT_TEST_SUITE_END();
-};
-
-template <>
-void TSetTest<TFlatHashSet<int>>::AllocatorTest() {
- using Map = TFlatHashSet<int>;
- Map mp(3, typename Map::allocator_type());
-}
-
-template <>
-void TSetTest<TDenseHashSetStaticMarker<int, -1>>::AllocatorTest() {
- using Map = TDenseHashSetStaticMarker<int, -1>;
- Map mp(3, NFlatHash::NSet::TStaticValueMarker<-1>(), typename Map::allocator_type());
-}
-
-using TFlatHashSetTest = TSetTest<TFlatHashSet<int, THash<int>>>;
-using TDenseHashSetTest = TSetTest<TDenseHashSetStaticMarker<int, -1>>;
-
-UNIT_TEST_SUITE_REGISTRATION(TFlatHashSetTest);
-UNIT_TEST_SUITE_REGISTRATION(TDenseHashSetTest);
diff --git a/library/cpp/containers/flat_hash/ut/iterator_ut.cpp b/library/cpp/containers/flat_hash/ut/iterator_ut.cpp
deleted file mode 100644
index 0b77bf043f..0000000000
--- a/library/cpp/containers/flat_hash/ut/iterator_ut.cpp
+++ /dev/null
@@ -1,85 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/iterator.h>
-#include <library/cpp/containers/flat_hash/lib/containers.h>
-
-#include <library/cpp/testing/unittest/registar.h>
-
-#include <util/random/random.h>
-#include <util/generic/algorithm.h>
-
-using namespace NFlatHash;
-
-namespace {
- constexpr size_t INIT_SIZE = 128;
-
- template <class Container>
- void SmokingTest(Container& cont) {
- using value_type = typename Container::value_type;
- using iterator = TIterator<Container, value_type>;
- using size_type = typename Container::size_type;
-
- iterator f(&cont), l(&cont, cont.Size());
- UNIT_ASSERT_EQUAL(f, l);
- UNIT_ASSERT_EQUAL((size_type)std::distance(f, l), cont.Taken());
-
- TVector<std::pair<size_type, value_type>> toAdd{
- { 0, (int)RandomNumber<size_type>(INIT_SIZE) },
- { 1 + RandomNumber<size_type>(INIT_SIZE - 2), (int)RandomNumber<size_type>(INIT_SIZE) },
- { INIT_SIZE - 1, (int)RandomNumber<size_type>(INIT_SIZE) }
- };
-
- for (const auto& p : toAdd) {
- UNIT_ASSERT(cont.IsEmpty(p.first));
- cont.InitNode(p.first, p.second);
- }
- UNIT_ASSERT_EQUAL(cont.Size(), INIT_SIZE);
- f = iterator{ &cont };
- l = iterator{ &cont, INIT_SIZE };
- UNIT_ASSERT_UNEQUAL(f, l);
- UNIT_ASSERT_EQUAL((size_type)std::distance(f, l), cont.Taken());
-
- TVector<value_type> added(f, l);
- UNIT_ASSERT(::Equal(toAdd.begin(), toAdd.end(), added.begin(), [](const auto& p, auto v) {
- return p.second == v;
- }));
- }
-
- template <class Container>
- void ConstTest(Container& cont) {
- using value_type = typename Container::value_type;
- using iterator = TIterator<Container, value_type>;
- using const_iterator = TIterator<const Container, const value_type>;
-
- iterator it{ &cont, INIT_SIZE / 2 };
- const_iterator cit1{ it };
- const_iterator cit2{ &cont, INIT_SIZE / 2 };
-
- UNIT_ASSERT_EQUAL(cit1, cit2);
-
- static_assert(std::is_same<decltype(*it), value_type&>::value);
- static_assert(std::is_same<decltype(*cit1), const value_type&>::value);
- }
-}
-
-Y_UNIT_TEST_SUITE(TIteratorTest) {
- Y_UNIT_TEST(SmokingTest) {
- {
- TFlatContainer<int> cont(INIT_SIZE);
- SmokingTest(cont);
- }
- {
- TDenseContainer<int, NSet::TStaticValueMarker<-1>> cont(INIT_SIZE);
- SmokingTest(cont);
- }
- }
-
- Y_UNIT_TEST(ConstTest) {
- {
- TFlatContainer<int> cont(INIT_SIZE);
- ConstTest(cont);
- }
- {
- TDenseContainer<int, NSet::TStaticValueMarker<-1>> cont(INIT_SIZE);
- ConstTest(cont);
- }
- }
-}
diff --git a/library/cpp/containers/flat_hash/ut/probings_ut.cpp b/library/cpp/containers/flat_hash/ut/probings_ut.cpp
deleted file mode 100644
index 593f8cbb1b..0000000000
--- a/library/cpp/containers/flat_hash/ut/probings_ut.cpp
+++ /dev/null
@@ -1,34 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/probings.h>
-
-#include <library/cpp/testing/unittest/registar.h>
-
-using namespace NFlatHash;
-
-namespace {
- struct TDummySizeFitter {
- constexpr auto EvalIndex(size_t idx, size_t) const {
- return idx;
- }
- };
-
- constexpr TDummySizeFitter SIZE_FITTER;
-
- auto atLeast13 = [](size_t idx) { return idx >= 13; };
-}
-
-Y_UNIT_TEST_SUITE(TProbingsTest) {
- Y_UNIT_TEST(LinearProbingTest) {
- using TProbing = TLinearProbing;
- UNIT_ASSERT_EQUAL(TProbing::FindBucket(SIZE_FITTER, 1, 0, atLeast13), 13);
- }
-
- Y_UNIT_TEST(QuadraticProbingTest) {
- using TProbing = TQuadraticProbing;
- UNIT_ASSERT_EQUAL(TProbing::FindBucket(SIZE_FITTER, 1, 0, atLeast13), 17);
- }
-
- Y_UNIT_TEST(DenseProbingTest) {
- using TProbing = TDenseProbing;
- UNIT_ASSERT_EQUAL(TProbing::FindBucket(SIZE_FITTER, 1, 0, atLeast13), 16);
- }
-}
diff --git a/library/cpp/containers/flat_hash/ut/size_fitters_ut.cpp b/library/cpp/containers/flat_hash/ut/size_fitters_ut.cpp
deleted file mode 100644
index 4167947ece..0000000000
--- a/library/cpp/containers/flat_hash/ut/size_fitters_ut.cpp
+++ /dev/null
@@ -1,51 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
-
-#include <library/cpp/testing/unittest/registar.h>
-
-using namespace NFlatHash;
-
-Y_UNIT_TEST_SUITE(TAndSizeFitterTest) {
- Y_UNIT_TEST(EvalSizeTest) {
- TAndSizeFitter sf;
- UNIT_ASSERT_EQUAL(sf.EvalSize(5), 8);
- UNIT_ASSERT_EQUAL(sf.EvalSize(8), 8);
- UNIT_ASSERT_EQUAL(sf.EvalSize(13), 16);
- UNIT_ASSERT_EQUAL(sf.EvalSize(25), 32);
- for (size_t i = 1; i < 100; ++i) {
- UNIT_ASSERT_EQUAL(sf.EvalSize(i), FastClp2(i));
- }
- }
-
- Y_UNIT_TEST(EvalIndexTest) {
- TAndSizeFitter sf;
- for (size_t j = 1; j < 10; ++j) {
- sf.Update(1 << j);
- for (size_t i = 0; i < 100; ++i) {
- UNIT_ASSERT_EQUAL(sf.EvalIndex(i, 1 << j), i & ((1 << j) - 1));
- }
- }
- }
-}
-
-Y_UNIT_TEST_SUITE(TModSizeFitterTest) {
- Y_UNIT_TEST(EvalSizeTest) {
- TModSizeFitter sf;
- UNIT_ASSERT_EQUAL(sf.EvalSize(5), 5);
- UNIT_ASSERT_EQUAL(sf.EvalSize(8), 8);
- UNIT_ASSERT_EQUAL(sf.EvalSize(13), 13);
- UNIT_ASSERT_EQUAL(sf.EvalSize(25), 25);
- for (size_t i = 1; i < 100; ++i) {
- UNIT_ASSERT_EQUAL(sf.EvalSize(i), i);
- }
- }
-
- Y_UNIT_TEST(EvalIndexTest) {
- TModSizeFitter sf;
- for (size_t j = 1; j < 10; ++j) {
- sf.Update(1 << j); // just for integrity
- for (size_t i = 0; i < 100; ++i) {
- UNIT_ASSERT_EQUAL(sf.EvalIndex(i, 1 << j), i % (1 << j));
- }
- }
- }
-}
diff --git a/library/cpp/containers/flat_hash/ut/table_ut.cpp b/library/cpp/containers/flat_hash/ut/table_ut.cpp
deleted file mode 100644
index ea511e2c6a..0000000000
--- a/library/cpp/containers/flat_hash/ut/table_ut.cpp
+++ /dev/null
@@ -1,411 +0,0 @@
-#include <library/cpp/containers/flat_hash/lib/containers.h>
-#include <library/cpp/containers/flat_hash/lib/expanders.h>
-#include <library/cpp/containers/flat_hash/lib/probings.h>
-#include <library/cpp/containers/flat_hash/lib/size_fitters.h>
-#include <library/cpp/containers/flat_hash/lib/table.h>
-
-#include <library/cpp/testing/unittest/registar.h>
-
-#include <util/generic/algorithm.h>
-#include <util/random/random.h>
-#include <util/random/shuffle.h>
-
-using namespace NFlatHash;
-
-namespace {
- template <class T>
- struct TJustType {
- using type = T;
- };
-
- template <class... Ts>
- struct TTypePack {};
-
- template <class F, class... Ts>
- constexpr void ForEachType(F&& f, TTypePack<Ts...>) {
- ApplyToMany(std::forward<F>(f), TJustType<Ts>{}...);
- }
-
-/* Usage example:
- *
- * TForEachType<int, float, TString>::Apply([](auto t) {
- * using T = GET_TYPE(t);
- * });
- * So T would be:
- * int on #0 iteration
- * float on #1 iteration
- * TString on #2 iteration
- */
-#define GET_TYPE(ti) typename decltype(ti)::type
-
- constexpr size_t INIT_SIZE = 32;
- constexpr size_t BIG_INIT_SIZE = 128;
-
- template <class T>
- struct TSimpleKeyGetter {
- static constexpr T& Apply(T& t) { return t; }
- static constexpr const T& Apply(const T& t) { return t; }
- };
-
- template <class T,
- class KeyEqual = std::equal_to<T>,
- class ValueEqual = std::equal_to<T>,
- class KeyGetter = TSimpleKeyGetter<T>,
- class F,
- class... Containers>
- void ForEachTable(F f, TTypePack<Containers...> cs) {
- ForEachType([&](auto p) {
- using TProbing = GET_TYPE(p);
-
- ForEachType([&](auto sf) {
- using TSizeFitter = GET_TYPE(sf);
-
- ForEachType([&](auto t) {
- using TContainer = GET_TYPE(t);
- static_assert(std::is_same_v<typename TContainer::value_type, T>);
-
- using TTable = TTable<THash<T>,
- KeyEqual,
- TContainer,
- KeyGetter,
- TProbing,
- TSizeFitter,
- TSimpleExpander>;
-
- f(TJustType<TTable>{});
- }, cs);
- }, TTypePack<TAndSizeFitter, TModSizeFitter>{});
- }, TTypePack<TLinearProbing, TQuadraticProbing, TDenseProbing>{});
- }
-
- using TAtomContainers = TTypePack<TFlatContainer<int>,
- TDenseContainer<int, NSet::TStaticValueMarker<-1>>>;
- using TContainers = TTypePack<TFlatContainer<int>,
- TDenseContainer<int, NSet::TStaticValueMarker<-1>>>;
- using TRemovalContainers = TTypePack<TFlatContainer<int>,
- TRemovalDenseContainer<int, NSet::TStaticValueMarker<-2>,
- NSet::TStaticValueMarker<-1>>>;
-}
-
-Y_UNIT_TEST_SUITE(TCommonTableAtomsTest) {
- Y_UNIT_TEST(InitTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- UNIT_ASSERT(table.empty());
- UNIT_ASSERT_EQUAL(table.size(), 0);
- UNIT_ASSERT_EQUAL(table.bucket_count(), INIT_SIZE);
- UNIT_ASSERT_EQUAL(table.bucket_size(RandomNumber<size_t>(INIT_SIZE)), 0);
- }, TAtomContainers{});
- }
-
- Y_UNIT_TEST(IteratorTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- auto first = table.begin();
- auto last = table.end();
- UNIT_ASSERT_EQUAL(first, last);
- UNIT_ASSERT_EQUAL(std::distance(first, last), 0);
-
- auto cFirst = table.cbegin();
- auto cLast = table.cend();
- UNIT_ASSERT_EQUAL(cFirst, cLast);
- UNIT_ASSERT_EQUAL(std::distance(cFirst, cLast), 0);
- }, TAtomContainers{});
- }
-
- Y_UNIT_TEST(ContainsAndCountTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- for (int i = 0; i < 100; ++i) {
- UNIT_ASSERT_EQUAL(table.count(i), 0);
- UNIT_ASSERT(!table.contains(i));
- }
- }, TAtomContainers{});
- }
-
- Y_UNIT_TEST(FindTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- for (int i = 0; i < 100; ++i) {
- auto it = table.find(i);
- UNIT_ASSERT_EQUAL(it, table.end());
- }
- }, TAtomContainers{});
- }
-}
-
-Y_UNIT_TEST_SUITE(TCommonTableTest) {
- Y_UNIT_TEST(InsertTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- UNIT_ASSERT(table.empty());
- UNIT_ASSERT_EQUAL(table.size(), 0);
-
- int toInsert = RandomNumber<size_t>(100);
- UNIT_ASSERT_EQUAL(table.count(toInsert), 0);
- UNIT_ASSERT(!table.contains(toInsert));
-
- auto p = table.insert(toInsert);
- UNIT_ASSERT_EQUAL(p.first, table.begin());
- UNIT_ASSERT(p.second);
-
- UNIT_ASSERT(!table.empty());
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(toInsert), 1);
- UNIT_ASSERT(table.contains(toInsert));
-
- auto it = table.find(toInsert);
- UNIT_ASSERT_UNEQUAL(it, table.end());
- UNIT_ASSERT_EQUAL(it, table.begin());
- UNIT_ASSERT_EQUAL(*it, toInsert);
-
- auto p2 = table.insert(toInsert);
- UNIT_ASSERT_EQUAL(p.first, p2.first);
- UNIT_ASSERT(!p2.second);
-
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(toInsert), 1);
- UNIT_ASSERT(table.contains(toInsert));
- }, TContainers{});
- }
-
- Y_UNIT_TEST(ClearTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- TVector<int> toInsert(INIT_SIZE);
- Iota(toInsert.begin(), toInsert.end(), 0);
- ShuffleRange(toInsert);
- toInsert.resize(INIT_SIZE / 3);
-
- for (auto i : toInsert) {
- auto p = table.insert(i);
- UNIT_ASSERT_EQUAL(*p.first, i);
- UNIT_ASSERT(p.second);
- }
- UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table.begin(), table.end()), toInsert.size());
-
- for (auto i : toInsert) {
- UNIT_ASSERT(table.contains(i));
- UNIT_ASSERT_EQUAL(table.count(i), 1);
- }
-
- auto bc = table.bucket_count();
- table.clear();
- UNIT_ASSERT(table.empty());
- UNIT_ASSERT_EQUAL(table.bucket_count(), bc);
-
- for (auto i : toInsert) {
- UNIT_ASSERT(!table.contains(i));
- UNIT_ASSERT_EQUAL(table.count(i), 0);
- }
-
- table.insert(toInsert.front());
- UNIT_ASSERT(!table.empty());
- }, TContainers{});
- }
-
- Y_UNIT_TEST(CopyMoveTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- TVector<int> toInsert(INIT_SIZE);
- Iota(toInsert.begin(), toInsert.end(), 0);
- ShuffleRange(toInsert);
- toInsert.resize(INIT_SIZE / 3);
-
- for (auto i : toInsert) {
- auto p = table.insert(i);
- UNIT_ASSERT_EQUAL(*p.first, i);
- UNIT_ASSERT(p.second);
- }
- UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table.begin(), table.end()), toInsert.size());
-
- for (auto i : toInsert) {
- UNIT_ASSERT(table.contains(i));
- UNIT_ASSERT_EQUAL(table.count(i), 1);
- }
-
- // Copy construction test
- auto table2 = table;
- UNIT_ASSERT_EQUAL(table2.size(), table.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table2.begin(), table2.end()), table.size());
- for (auto i : table) {
- UNIT_ASSERT(table2.contains(i));
- UNIT_ASSERT_EQUAL(table2.count(i), 1);
- }
-
- table2.clear();
- UNIT_ASSERT(table2.empty());
-
- // Copy assignment test
- table2 = table;
- UNIT_ASSERT_EQUAL(table2.size(), table.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table2.begin(), table2.end()), table.size());
- for (auto i : table) {
- UNIT_ASSERT(table2.contains(i));
- UNIT_ASSERT_EQUAL(table2.count(i), 1);
- }
-
- // Move construction test
- auto table3 = std::move(table2);
- UNIT_ASSERT(table2.empty());
- UNIT_ASSERT(table2.bucket_count() > 0);
-
- UNIT_ASSERT_EQUAL(table3.size(), table.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table3.begin(), table3.end()), table.size());
- for (auto i : table) {
- UNIT_ASSERT(table3.contains(i));
- UNIT_ASSERT_EQUAL(table3.count(i), 1);
- }
-
- table2.insert(toInsert.front());
- UNIT_ASSERT(!table2.empty());
- UNIT_ASSERT_EQUAL(table2.size(), 1);
- UNIT_ASSERT_UNEQUAL(table2.bucket_count(), 0);
-
- // Move assignment test
- table2 = std::move(table3);
- UNIT_ASSERT(table3.empty());
- UNIT_ASSERT(table3.bucket_count() > 0);
-
- UNIT_ASSERT_EQUAL(table2.size(), table.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table2.begin(), table2.end()), table.size());
- for (auto i : table) {
- UNIT_ASSERT(table2.contains(i));
- UNIT_ASSERT_EQUAL(table2.count(i), 1);
- }
-
- table3.insert(toInsert.front());
- UNIT_ASSERT(!table3.empty());
- UNIT_ASSERT_EQUAL(table3.size(), 1);
- UNIT_ASSERT_UNEQUAL(table3.bucket_count(), 0);
- }, TContainers{});
- }
-
- Y_UNIT_TEST(RehashTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- TVector<int> toInsert(INIT_SIZE);
- Iota(toInsert.begin(), toInsert.end(), 0);
- ShuffleRange(toInsert);
- toInsert.resize(INIT_SIZE / 3);
-
- for (auto i : toInsert) {
- table.insert(i);
- }
-
- auto bc = table.bucket_count();
- table.rehash(bc * 2);
- UNIT_ASSERT(bc * 2 <= table.bucket_count());
-
- UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
- UNIT_ASSERT_EQUAL((size_t)std::distance(table.begin(), table.end()), toInsert.size());
- for (auto i : toInsert) {
- UNIT_ASSERT(table.contains(i));
- UNIT_ASSERT_EQUAL(table.count(i), 1);
- }
-
- TVector<int> tmp(table.begin(), table.end());
- Sort(toInsert.begin(), toInsert.end());
- Sort(tmp.begin(), tmp.end());
-
- UNIT_ASSERT_VALUES_EQUAL(tmp, toInsert);
-
- table.rehash(0);
- UNIT_ASSERT_EQUAL(table.size(), toInsert.size());
- UNIT_ASSERT(table.bucket_count() > table.size());
-
- table.clear();
- UNIT_ASSERT(table.empty());
- table.rehash(INIT_SIZE);
- UNIT_ASSERT(table.bucket_count() >= INIT_SIZE);
-
- table.rehash(0);
- UNIT_ASSERT(table.bucket_count() > 0);
- }, TContainers{});
- }
-
- Y_UNIT_TEST(EraseTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ INIT_SIZE };
-
- int value = RandomNumber<ui32>();
- table.insert(value);
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(value), 1);
-
- auto it = table.find(value);
- table.erase(it);
-
- UNIT_ASSERT_EQUAL(table.size(), 0);
- UNIT_ASSERT_EQUAL(table.count(value), 0);
-
- table.insert(value);
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(value), 1);
-
- table.erase(value);
-
- UNIT_ASSERT_EQUAL(table.size(), 0);
- UNIT_ASSERT_EQUAL(table.count(value), 0);
-
- table.insert(value);
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(value), 1);
-
- table.erase(table.find(value), table.end());
-
- UNIT_ASSERT_EQUAL(table.size(), 0);
- UNIT_ASSERT_EQUAL(table.count(value), 0);
-
- table.erase(value);
-
- UNIT_ASSERT_EQUAL(table.size(), 0);
- UNIT_ASSERT_EQUAL(table.count(value), 0);
- }, TRemovalContainers{});
- }
-
- Y_UNIT_TEST(EraseBigTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ BIG_INIT_SIZE };
-
- for (int i = 0; i < 1000; ++i) {
- for (int j = 0; j < static_cast<int>(BIG_INIT_SIZE); ++j) {
- table.emplace(j);
- }
- for (int j = 0; j < static_cast<int>(BIG_INIT_SIZE); ++j) {
- table.erase(j);
- }
- }
- UNIT_ASSERT(table.bucket_count() <= BIG_INIT_SIZE * 8);
- }, TRemovalContainers{});
- }
-
- Y_UNIT_TEST(ConstructWithSizeTest) {
- ForEachTable<int>([](auto t) {
- GET_TYPE(t) table{ 1000 };
- UNIT_ASSERT(table.bucket_count() >= 1000);
-
- int value = RandomNumber<ui32>();
- table.insert(value);
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(value), 1);
- UNIT_ASSERT(table.bucket_count() >= 1000);
-
- table.rehash(10);
- UNIT_ASSERT_EQUAL(table.size(), 1);
- UNIT_ASSERT_EQUAL(table.count(value), 1);
- UNIT_ASSERT(table.bucket_count() < 1000);
- UNIT_ASSERT(table.bucket_count() >= 10);
- }, TContainers{});
- }
-}