diff options
author | snaury <snaury@ydb.tech> | 2023-04-20 10:10:21 +0300 |
---|---|---|
committer | snaury <snaury@ydb.tech> | 2023-04-20 10:10:21 +0300 |
commit | 6e494baf9715cc400ed74aa23f8f99ec25f383e9 (patch) | |
tree | 9ba554a7e8e9df4753d9cc8b684f1e7162448ce4 /library/cpp/containers | |
parent | d5daa23faa0fc9a78178ed324b9bb3bf7525734d (diff) | |
download | ydb-6e494baf9715cc400ed74aa23f8f99ec25f383e9.tar.gz |
Remove dependency on library/cpp/containers/flat_hash
Diffstat (limited to 'library/cpp/containers')
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{}); - } -} |