diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake index 2e3a2f2..b615da8 100644 --- a/CMake/AbseilDll.cmake +++ b/CMake/AbseilDll.cmake
@@ -523,6 +523,7 @@ "any_invocable" "atomic_hook" "base" + "base_cpu_detect" "base_internal" "bind_front" "bits" @@ -545,7 +546,6 @@ "core_headers" "counting_allocator" "crc_cord_state" - "crc_cpu_detect" "crc_internal" "crc32c" "debugging"
diff --git a/absl/base/attributes.h b/absl/base/attributes.h index 7261417..8f2bb2c 100644 --- a/absl/base/attributes.h +++ b/absl/base/attributes.h
@@ -202,13 +202,10 @@ // // Deprecated: Prefer the `[[noreturn]]` attribute standardized by C++11 over // this macro. -#if ABSL_HAVE_ATTRIBUTE(noreturn) || (defined(__GNUC__) && !defined(__clang__)) -#define ABSL_ATTRIBUTE_NORETURN __attribute__((noreturn)) -#elif defined(_MSC_VER) -#define ABSL_ATTRIBUTE_NORETURN __declspec(noreturn) -#else -#define ABSL_ATTRIBUTE_NORETURN +#ifdef ABSL_ATTRIBUTE_NORETURN +#error "ABSL_ATTRIBUTE_NORETURN should not be defined." #endif +#define ABSL_ATTRIBUTE_NORETURN [[noreturn]] // ABSL_ATTRIBUTE_NO_SANITIZE_ADDRESS // @@ -375,9 +372,9 @@ // link. // #define ABSL_ATTRIBUTE_SECTION_START(name) \ - (reinterpret_cast<void *>(__start_##name)) + (reinterpret_cast<void*>(__start_##name)) #define ABSL_ATTRIBUTE_SECTION_STOP(name) \ - (reinterpret_cast<void *>(__stop_##name)) + (reinterpret_cast<void*>(__stop_##name)) #else // !ABSL_HAVE_ATTRIBUTE_SECTION @@ -389,8 +386,8 @@ #define ABSL_INIT_ATTRIBUTE_SECTION_VARS(name) #define ABSL_DEFINE_ATTRIBUTE_SECTION_VARS(name) #define ABSL_DECLARE_ATTRIBUTE_SECTION_VARS(name) -#define ABSL_ATTRIBUTE_SECTION_START(name) (reinterpret_cast<void *>(0)) -#define ABSL_ATTRIBUTE_SECTION_STOP(name) (reinterpret_cast<void *>(0)) +#define ABSL_ATTRIBUTE_SECTION_START(name) (reinterpret_cast<void*>(0)) +#define ABSL_ATTRIBUTE_SECTION_STOP(name) (reinterpret_cast<void*>(0)) #endif // ABSL_ATTRIBUTE_SECTION @@ -419,8 +416,7 @@ // // Tells the compiler to warn about unused results. // -// For code or headers that are assured to only build with C++17 and up, prefer -// just using the standard `[[nodiscard]]` directly over this macro. +// Deprecated: Use the standard C++17 `[[nodiscard]]` instead. // // When annotating a function, it must appear as the first part of the // declaration or definition. The compiler will warn if the return value from @@ -442,20 +438,10 @@ // // Sprocket* SprocketPointer(); // SprocketPointer(); // Does *not* trigger a warning. -// -// ABSL_MUST_USE_RESULT allows using cast-to-void to suppress the unused result -// warning. For that, warn_unused_result is used only for clang but not for gcc. -// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=66425 -// -// Note: past advice was to place the macro after the argument list. -// -// TODO(b/176172494): Use ABSL_HAVE_CPP_ATTRIBUTE(nodiscard) when all code is -// compliant with the stricter [[nodiscard]]. -#if defined(__clang__) && ABSL_HAVE_ATTRIBUTE(warn_unused_result) -#define ABSL_MUST_USE_RESULT __attribute__((warn_unused_result)) -#else -#define ABSL_MUST_USE_RESULT +#ifdef ABSL_MUST_USE_RESULT +#error "ABSL_MUST_USE_RESULT should not be defined." #endif +#define ABSL_MUST_USE_RESULT [[nodiscard]] // ABSL_ATTRIBUTE_HOT, ABSL_ATTRIBUTE_COLD // @@ -577,12 +563,10 @@ // Due to differences in positioning requirements between the old, compiler // specific __attribute__ syntax and the now standard `[[maybe_unused]]`, this // macro does not attempt to take advantage of `[[maybe_unused]]`. -#if ABSL_HAVE_ATTRIBUTE(unused) || (defined(__GNUC__) && !defined(__clang__)) -#undef ABSL_ATTRIBUTE_UNUSED -#define ABSL_ATTRIBUTE_UNUSED __attribute__((__unused__)) -#else -#define ABSL_ATTRIBUTE_UNUSED +#ifdef ABSL_ATTRIBUTE_UNUSED +#error "ABSL_ATTRIBUTE_UNUSED should not be defined." #endif +#define ABSL_ATTRIBUTE_UNUSED [[maybe_unused]] // ABSL_ATTRIBUTE_INITIAL_EXEC // @@ -660,8 +644,7 @@ // declarations. The macro argument is used as a custom diagnostic message (e.g. // suggestion of a better alternative). // -// For code or headers that are assured to only build with C++14 and up, prefer -// just using the standard `[[deprecated("message")]]` directly over this macro. +// Deprecated: Use the standard `[[deprecated("message")]]` macro instead. // // Examples: // @@ -682,7 +665,25 @@ // turns this warning off by default, instead relying on clang-tidy to report // new uses of deprecated code. #if ABSL_HAVE_ATTRIBUTE(deprecated) +#if defined(__cplusplus) && defined(__clang__) && \ + ABSL_HAVE_ATTRIBUTE(diagnose_if) && !defined(SWIG) +struct [[deprecated( + "Use [[deprecated(...)]] instead.")]] _absl_deprecated_macro; +// Trick: We use __attribute__((diagnose_if(...))) to refer to our own +// deprecated symbol, which then causes a deprecation message to be emitted when +// the macro is used. Since diagnose_if() isn't valid on every declaration, we +// also suppress the warning regarding that. +#define ABSL_DEPRECATED(message) \ + _Pragma("clang diagnostic push") /* */ \ + _Pragma("clang diagnostic ignored \"-Wignored-attributes\"") \ + __attribute__((diagnose_if( \ + sizeof(_absl_deprecated_macro*) == 0, "", \ + "warning"))) /* */ \ + _Pragma("clang diagnostic pop") /* */ \ + __attribute__((deprecated(message))) +#else #define ABSL_DEPRECATED(message) __attribute__((deprecated(message))) +#endif #else #define ABSL_DEPRECATED(message) #endif @@ -692,7 +693,7 @@ // deprecated code can be surrounded with these directives to achieve that // result. // -// class ABSL_DEPRECATED("Use Bar instead") Foo; +// class [[deprecated("Use Bar instead")]] Foo; // // ABSL_INTERNAL_DISABLE_DEPRECATED_DECLARATION_WARNING // Baz ComputeBazFromFoo(Foo f); @@ -700,8 +701,8 @@ #if defined(__GNUC__) || defined(__clang__) // Clang also supports these GCC pragmas. #define ABSL_INTERNAL_DISABLE_DEPRECATED_DECLARATION_WARNING \ - _Pragma("GCC diagnostic push") \ - _Pragma("GCC diagnostic ignored \"-Wdeprecated-declarations\"") + _Pragma("GCC diagnostic push") \ + _Pragma("GCC diagnostic ignored \"-Wdeprecated-declarations\"") #define ABSL_INTERNAL_RESTORE_DEPRECATED_DECLARATION_WARNING \ _Pragma("GCC diagnostic pop") #elif defined(_MSC_VER) @@ -737,40 +738,36 @@ // // See the upstream documentation for more details: // https://clang.llvm.org/docs/AttributeReference.html#require-explicit-initialization -#ifdef __cplusplus -#if ABSL_HAVE_CPP_ATTRIBUTE(clang::require_explicit_initialization) -// clang-format off -#define ABSL_REQUIRE_EXPLICIT_INIT \ +#if defined(__cplusplus) && !defined(SWIG) +#if defined(_MSC_VER) && !defined(__clang__) +// Workaround for MSVC: https://github.com/abseil/abseil-cpp/issues/2157 +#define ABSL_REQUIRE_EXPLICIT_INIT +#elif ABSL_HAVE_CPP_ATTRIBUTE(clang::require_explicit_initialization) +#define ABSL_REQUIRE_EXPLICIT_INIT \ [[clang::require_explicit_initialization]] = \ - AbslInternal_YouForgotToExplicitlyInitializeAField::v + AbslInternal_YouForgotToExplicitlyInitializeAField::v #else #define ABSL_REQUIRE_EXPLICIT_INIT \ = AbslInternal_YouForgotToExplicitlyInitializeAField::v #endif -// clang-format on #else -// clang-format off #if ABSL_HAVE_ATTRIBUTE(require_explicit_initialization) #define ABSL_REQUIRE_EXPLICIT_INIT \ __attribute__((require_explicit_initialization)) #else -#define ABSL_REQUIRE_EXPLICIT_INIT \ - /* No portable fallback for C is available */ +// No portable fallback for C is available +#define ABSL_REQUIRE_EXPLICIT_INIT #endif -// clang-format on #endif -#ifdef __cplusplus +#if defined(__cplusplus) && !defined(SWIG) struct AbslInternal_YouForgotToExplicitlyInitializeAField { // A portable version of [[clang::require_explicit_initialization]] that // never builds, as a last resort for all toolchains. // The error messages are poor, so we don't rely on this unless we have to. template <class T> -#if !defined(SWIG) - constexpr -#endif - operator T() const /* NOLINT */ { - const void *volatile deliberately_volatile_ptr = nullptr; + constexpr operator T() const /* NOLINT */ { + const void* volatile deliberately_volatile_ptr = nullptr; // Infinite loop to prevent constexpr compilation for (;;) { // This assignment ensures the 'this' pointer is not optimized away, so @@ -1047,7 +1044,8 @@ // overriding the compiler flag. // // See https://clang.llvm.org/docs/AttributeReference.html#uninitialized -// and https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html#index-uninitialized-variable-attribute +// and +// https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html#index-uninitialized-variable-attribute #if ABSL_HAVE_CPP_ATTRIBUTE(clang::uninitialized) #define ABSL_ATTRIBUTE_UNINITIALIZED [[clang::uninitialized]] #elif ABSL_HAVE_CPP_ATTRIBUTE(gnu::uninitialized)
diff --git a/absl/base/attributes_test.cc b/absl/base/attributes_test.cc index 5d213a4..058d1be 100644 --- a/absl/base/attributes_test.cc +++ b/absl/base/attributes_test.cc
@@ -14,6 +14,8 @@ #include "absl/base/attributes.h" +#include <type_traits> + #include "gtest/gtest.h" #include "absl/base/config.h" @@ -24,20 +26,32 @@ int f1; int f2 ABSL_REQUIRE_EXPLICIT_INIT; }; - Agg good1 ABSL_ATTRIBUTE_UNUSED = {1, 2}; + Agg good1 [[maybe_unused]] = {1, 2}; #if ABSL_INTERNAL_CPLUSPLUS_LANG >= 202002L - Agg good2 ABSL_ATTRIBUTE_UNUSED(1, 2); + Agg good2 [[maybe_unused]] (1, 2); #endif - Agg good3 ABSL_ATTRIBUTE_UNUSED{1, 2}; - Agg good4 ABSL_ATTRIBUTE_UNUSED = {1, 2}; - Agg good5 ABSL_ATTRIBUTE_UNUSED = Agg{1, 2}; - Agg good6[1] ABSL_ATTRIBUTE_UNUSED = {{1, 2}}; - Agg good7[1] ABSL_ATTRIBUTE_UNUSED = {Agg{1, 2}}; + Agg good3 [[maybe_unused]]{1, 2}; + Agg good4 [[maybe_unused]] = {1, 2}; + Agg good5 [[maybe_unused]] = Agg{1, 2}; + Agg good6 [[maybe_unused]][1] = {{1, 2}}; + Agg good7 [[maybe_unused]][1] = {Agg{1, 2}}; union { Agg agg; - } good8 ABSL_ATTRIBUTE_UNUSED = {{1, 2}}; - constexpr Agg good9 ABSL_ATTRIBUTE_UNUSED = {1, 2}; - constexpr Agg good10 ABSL_ATTRIBUTE_UNUSED{1, 2}; + } good8 [[maybe_unused]] = {{1, 2}}; + constexpr Agg good9 [[maybe_unused]] = {1, 2}; + constexpr Agg good10 [[maybe_unused]]{1, 2}; +} + +TEST(Attributes, MSVCBug) { + struct ImplicitlyConstructible { + // NOLINTNEXTLINE(google-explicit-constructor) + ImplicitlyConstructible(const char*) {} + }; + struct Agg { + ImplicitlyConstructible f1 ABSL_REQUIRE_EXPLICIT_INIT; + }; + static_assert(std::is_convertible_v<const char*, ImplicitlyConstructible>); + Agg good1 [[maybe_unused]] = {ImplicitlyConstructible("hello")}; } } // namespace
diff --git a/absl/base/config.h b/absl/base/config.h index e3e2c96..4761f25 100644 --- a/absl/base/config.h +++ b/absl/base/config.h
@@ -328,7 +328,7 @@ // AsmJS __asmjs__ // WebAssembly (Emscripten) __EMSCRIPTEN__ // Fuchsia __Fuchsia__ -// WebAssembly (WASI) _WASI_EMULATED_MMAN (implies __wasi__) +// WebAssembly (WASI) __wasi__ // // Note that since Android defines both __ANDROID__ and __linux__, one // may probe for either Linux or Android by simply testing for __linux__. @@ -339,13 +339,12 @@ // POSIX.1-2001. #ifdef ABSL_HAVE_MMAP #error ABSL_HAVE_MMAP cannot be directly set -#elif defined(__linux__) || defined(__APPLE__) || defined(__FreeBSD__) || \ - defined(_AIX) || defined(__ros__) || defined(__asmjs__) || \ - defined(__EMSCRIPTEN__) || defined(__Fuchsia__) || defined(__sun) || \ - defined(__myriad2__) || defined(__HAIKU__) || defined(__OpenBSD__) || \ - defined(__NetBSD__) || defined(__QNX__) || defined(__VXWORKS__) || \ - defined(__hexagon__) || defined(__XTENSA__) || \ - defined(_WASI_EMULATED_MMAN) +#elif defined(__wasi__) +// Avoid mmap on WASI unless _WASI_EMULATED_MMAN is defined. +#if defined(_WASI_EMULATED_MMAN) +#define ABSL_HAVE_MMAP 1 +#endif +#elif __has_include(<sys/mman.h>) #define ABSL_HAVE_MMAP 1 #endif
diff --git a/absl/base/dynamic_annotations.h b/absl/base/dynamic_annotations.h index 1e679a6..5d08c51 100644 --- a/absl/base/dynamic_annotations.h +++ b/absl/base/dynamic_annotations.h
@@ -86,9 +86,7 @@ #if defined(__clang__) #define ABSL_INTERNAL_ANNOTALYSIS_ENABLED 1 -#if !defined(SWIG) #define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 1 -#endif #else #define ABSL_INTERNAL_ANNOTALYSIS_ENABLED 0 #endif
diff --git a/absl/base/internal/cpu_detect.cc b/absl/base/internal/cpu_detect.cc index a939bbf..b498465 100644 --- a/absl/base/internal/cpu_detect.cc +++ b/absl/base/internal/cpu_detect.cc
@@ -221,6 +221,8 @@ return CpuType::kAmdGenoa; case 0x44: // Stepping A0 return CpuType::kAmdRyzenV3000; + case 0xA0: // Stepping A0 + return CpuType::kAmdSiena; default: return CpuType::kUnknown; } @@ -302,8 +304,12 @@ } return CpuType::kArmNeoverseV2; } + case 0xd84: + return CpuType::kArmNeoverseV3; case 0xd8e: return CpuType::kArmNeoverseN3; + case 0xd94: + return CpuType::kArmNeoverseN4; default: return CpuType::kUnknown; }
diff --git a/absl/base/internal/cpu_detect.h b/absl/base/internal/cpu_detect.h index 43c7c38..5ca993f 100644 --- a/absl/base/internal/cpu_detect.h +++ b/absl/base/internal/cpu_detect.h
@@ -30,6 +30,7 @@ kAmdNaples, kAmdMilan, kAmdGenoa, + kAmdSiena, kAmdTurin, kAmdRyzenV3000, kIntelCascadelakeXeon, @@ -48,7 +49,9 @@ kAmpereSiryn, kArmNeoverseN2, kArmNeoverseV2, + kArmNeoverseV3, kArmNeoverseN3, + kArmNeoverseN4, kNvidiaGrace, };
diff --git a/absl/base/internal/dynamic_annotations.h b/absl/base/internal/dynamic_annotations.h index 537a2fe..71072f1 100644 --- a/absl/base/internal/dynamic_annotations.h +++ b/absl/base/internal/dynamic_annotations.h
@@ -42,6 +42,8 @@ // If neither Dynamic Annotations nor Clang thread-safety warnings are // enabled, then all annotation-macros expand to empty. +// SKIP_ABSL_INLINE_NAMESPACE_CHECK + #ifndef ABSL_BASE_INTERNAL_DYNAMIC_ANNOTATIONS_H_ #define ABSL_BASE_INTERNAL_DYNAMIC_ANNOTATIONS_H_ @@ -56,7 +58,7 @@ #define DYNAMIC_ANNOTATIONS_ENABLED 0 #endif -#if defined(__clang__) && !defined(SWIG) +#if defined(__clang__) #define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 1 #endif
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index 91f79d6..8c12057 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -1279,7 +1279,6 @@ "//absl/base:config", "//absl/base:core_headers", "//absl/base:raw_logging_internal", - "//absl/flags:flag", "//absl/hash:hash_testing", "//absl/memory", "//absl/random", @@ -1292,6 +1291,33 @@ ], ) +cc_test( + name = "btree_instantiate_test", + size = "large", + srcs = [ + "btree_instantiate_test.cc", + ], + copts = ABSL_TEST_COPTS, + linkopts = ABSL_DEFAULT_LINKOPTS, + shard_count = 10, + tags = [ + "no_test:os:ios", + "no_test_ios", + "no_test_wasm", + ], + visibility = ["//visibility:private"], + deps = [ + ":btree", + ":btree_test_common", + "//absl/base:config", + "//absl/base:raw_logging_internal", + "//absl/flags:flag", + "//absl/strings:cord", + "@googletest//:gtest", + "@googletest//:gtest_main", + ], +) + cc_binary( name = "btree_benchmark", testonly = True,
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index cf460f0..cb0b6de 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -89,6 +89,25 @@ GTest::gmock_main ) +absl_cc_test( + NAME + btree_instantiate_test + SRCS + "btree_instantiate_test.cc" + COPTS + ${ABSL_TEST_COPTS} + LINKOPTS + ${ABSL_DEFAULT_LINKOPTS} + DEPS + absl::btree + absl::btree_test_common + absl::cord + absl::core_headers + absl::flags + absl::raw_logging_internal + GTest::gmock_main +) + # Internal-only target, do not depend on directly. absl_cc_library( NAME
diff --git a/absl/container/btree_instantiate_test.cc b/absl/container/btree_instantiate_test.cc new file mode 100644 index 0000000..e9e198f --- /dev/null +++ b/absl/container/btree_instantiate_test.cc
@@ -0,0 +1,731 @@ +// Copyright 2026 The Abseil Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// https://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// +// ----------------------------------------------------------------------------- +// File: btree_instantiate_test.cc +// ----------------------------------------------------------------------------- +// +// Various tests for btree containers with diverse value types and +// configurations. +// NOTE: There are more tests in btree_test.cc. +// The main reason to have this file separate is to improve build times. + +#include <cstdint> +#include <functional> +#include <map> +#include <memory> +#include <set> +#include <string> +#include <utility> +#include <vector> + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include "absl/base/config.h" +#include "absl/base/internal/raw_logging.h" +#include "absl/container/btree_map.h" +#include "absl/container/btree_set.h" +#include "absl/container/btree_test.h" +#include "absl/flags/flag.h" +#include "absl/strings/cord.h" + +ABSL_FLAG(int, test_values, 10000, "The number of values to use for tests"); + +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace container_internal { + +namespace { + +template <typename T, typename U> +void CheckPairEquals(const T& x, const U& y) { + ABSL_INTERNAL_CHECK(x == y, "Values are unequal."); +} + +template <typename T, typename U, typename V, typename W> +void CheckPairEquals(const std::pair<T, U>& x, const std::pair<V, W>& y) { + CheckPairEquals(x.first, y.first); + CheckPairEquals(x.second, y.second); +} + +} // namespace + +// The base class for a sorted associative container checker. TreeType is the +// container type to check and CheckerType is the container type to check +// against. TreeType is expected to be btree_{set,map,multiset,multimap} and +// CheckerType is expected to be {set,map,multiset,multimap}. +template <typename TreeType, typename CheckerType> +class base_checker { + public: + using key_type = typename TreeType::key_type; + using value_type = typename TreeType::value_type; + using key_compare = typename TreeType::key_compare; + using pointer = typename TreeType::pointer; + using const_pointer = typename TreeType::const_pointer; + using reference = typename TreeType::reference; + using const_reference = typename TreeType::const_reference; + using size_type = typename TreeType::size_type; + using difference_type = typename TreeType::difference_type; + using iterator = typename TreeType::iterator; + using const_iterator = typename TreeType::const_iterator; + using reverse_iterator = typename TreeType::reverse_iterator; + using const_reverse_iterator = typename TreeType::const_reverse_iterator; + + public: + base_checker() : const_tree_(tree_) {} + base_checker(const base_checker& other) + : tree_(other.tree_), const_tree_(tree_), checker_(other.checker_) {} + template <typename InputIterator> + base_checker(InputIterator b, InputIterator e) + : tree_(b, e), const_tree_(tree_), checker_(b, e) {} + + iterator begin() { return tree_.begin(); } + const_iterator begin() const { return tree_.begin(); } + iterator end() { return tree_.end(); } + const_iterator end() const { return tree_.end(); } + reverse_iterator rbegin() { return tree_.rbegin(); } + const_reverse_iterator rbegin() const { return tree_.rbegin(); } + reverse_iterator rend() { return tree_.rend(); } + const_reverse_iterator rend() const { return tree_.rend(); } + + template <typename IterType, typename CheckerIterType> + IterType iter_check(IterType tree_iter, CheckerIterType checker_iter) const { + if (tree_iter == tree_.end()) { + ABSL_INTERNAL_CHECK(checker_iter == checker_.end(), + "Checker iterator not at end."); + } else { + CheckPairEquals(*tree_iter, *checker_iter); + } + return tree_iter; + } + template <typename IterType, typename CheckerIterType> + IterType riter_check(IterType tree_iter, CheckerIterType checker_iter) const { + if (tree_iter == tree_.rend()) { + ABSL_INTERNAL_CHECK(checker_iter == checker_.rend(), + "Checker iterator not at rend."); + } else { + CheckPairEquals(*tree_iter, *checker_iter); + } + return tree_iter; + } + void value_check(const value_type& v) { + typename KeyOfValue<typename TreeType::key_type, + typename TreeType::value_type>::type key_of_value; + const key_type& key = key_of_value(v); + CheckPairEquals(*find(key), v); + lower_bound(key); + upper_bound(key); + equal_range(key); + contains(key); + count(key); + } + void erase_check(const key_type& key) { + EXPECT_FALSE(tree_.contains(key)); + EXPECT_EQ(tree_.find(key), const_tree_.end()); + EXPECT_FALSE(const_tree_.contains(key)); + EXPECT_EQ(const_tree_.find(key), tree_.end()); + EXPECT_EQ(tree_.equal_range(key).first, + const_tree_.equal_range(key).second); + } + + iterator lower_bound(const key_type& key) { + return iter_check(tree_.lower_bound(key), checker_.lower_bound(key)); + } + const_iterator lower_bound(const key_type& key) const { + return iter_check(tree_.lower_bound(key), checker_.lower_bound(key)); + } + iterator upper_bound(const key_type& key) { + return iter_check(tree_.upper_bound(key), checker_.upper_bound(key)); + } + const_iterator upper_bound(const key_type& key) const { + return iter_check(tree_.upper_bound(key), checker_.upper_bound(key)); + } + std::pair<iterator, iterator> equal_range(const key_type& key) { + std::pair<typename CheckerType::iterator, typename CheckerType::iterator> + checker_res = checker_.equal_range(key); + std::pair<iterator, iterator> tree_res = tree_.equal_range(key); + iter_check(tree_res.first, checker_res.first); + iter_check(tree_res.second, checker_res.second); + return tree_res; + } + std::pair<const_iterator, const_iterator> equal_range( + const key_type& key) const { + std::pair<typename CheckerType::const_iterator, + typename CheckerType::const_iterator> + checker_res = checker_.equal_range(key); + std::pair<const_iterator, const_iterator> tree_res = tree_.equal_range(key); + iter_check(tree_res.first, checker_res.first); + iter_check(tree_res.second, checker_res.second); + return tree_res; + } + iterator find(const key_type& key) { + return iter_check(tree_.find(key), checker_.find(key)); + } + const_iterator find(const key_type& key) const { + return iter_check(tree_.find(key), checker_.find(key)); + } + bool contains(const key_type& key) const { return find(key) != end(); } + size_type count(const key_type& key) const { + size_type res = checker_.count(key); + EXPECT_EQ(res, tree_.count(key)); + return res; + } + + base_checker& operator=(const base_checker& other) { + tree_ = other.tree_; + checker_ = other.checker_; + return *this; + } + + int erase(const key_type& key) { + int size = tree_.size(); + int res = checker_.erase(key); + EXPECT_EQ(res, tree_.count(key)); + EXPECT_EQ(res, tree_.erase(key)); + EXPECT_EQ(tree_.count(key), 0); + EXPECT_EQ(tree_.size(), size - res); + erase_check(key); + return res; + } + iterator erase(iterator iter) { + key_type key = iter.key(); + int size = tree_.size(); + int count = tree_.count(key); + auto checker_iter = checker_.lower_bound(key); + for (iterator tmp(tree_.lower_bound(key)); tmp != iter; ++tmp) { + ++checker_iter; + } + auto checker_next = checker_iter; + ++checker_next; + checker_.erase(checker_iter); + iter = tree_.erase(iter); + EXPECT_EQ(tree_.size(), checker_.size()); + EXPECT_EQ(tree_.size(), size - 1); + EXPECT_EQ(tree_.count(key), count - 1); + if (count == 1) { + erase_check(key); + } + return iter_check(iter, checker_next); + } + + void erase(iterator begin, iterator end) { + int size = tree_.size(); + int count = std::distance(begin, end); + auto checker_begin = checker_.lower_bound(begin.key()); + for (iterator tmp(tree_.lower_bound(begin.key())); tmp != begin; ++tmp) { + ++checker_begin; + } + auto checker_end = + end == tree_.end() ? checker_.end() : checker_.lower_bound(end.key()); + if (end != tree_.end()) { + for (iterator tmp(tree_.lower_bound(end.key())); tmp != end; ++tmp) { + ++checker_end; + } + } + const auto checker_ret = checker_.erase(checker_begin, checker_end); + const auto tree_ret = tree_.erase(begin, end); + EXPECT_EQ(std::distance(checker_.begin(), checker_ret), + std::distance(tree_.begin(), tree_ret)); + EXPECT_EQ(tree_.size(), checker_.size()); + EXPECT_EQ(tree_.size(), size - count); + } + + void clear() { + tree_.clear(); + checker_.clear(); + } + void swap(base_checker& other) { + tree_.swap(other.tree_); + checker_.swap(other.checker_); + } + + void verify() const { + tree_.verify(); + EXPECT_EQ(tree_.size(), checker_.size()); + + // Move through the forward iterators using increment. + auto checker_iter = checker_.begin(); + const_iterator tree_iter(tree_.begin()); + for (; tree_iter != tree_.end(); ++tree_iter, ++checker_iter) { + CheckPairEquals(*tree_iter, *checker_iter); + } + + // Move through the forward iterators using decrement. + for (int n = tree_.size() - 1; n >= 0; --n) { + iter_check(tree_iter, checker_iter); + --tree_iter; + --checker_iter; + } + EXPECT_EQ(tree_iter, tree_.begin()); + EXPECT_EQ(checker_iter, checker_.begin()); + + // Move through the reverse iterators using increment. + auto checker_riter = checker_.rbegin(); + const_reverse_iterator tree_riter(tree_.rbegin()); + for (; tree_riter != tree_.rend(); ++tree_riter, ++checker_riter) { + CheckPairEquals(*tree_riter, *checker_riter); + } + + // Move through the reverse iterators using decrement. + for (int n = tree_.size() - 1; n >= 0; --n) { + riter_check(tree_riter, checker_riter); + --tree_riter; + --checker_riter; + } + EXPECT_EQ(tree_riter, tree_.rbegin()); + EXPECT_EQ(checker_riter, checker_.rbegin()); + } + + const TreeType& tree() const { return tree_; } + + size_type size() const { + EXPECT_EQ(tree_.size(), checker_.size()); + return tree_.size(); + } + size_type max_size() const { return tree_.max_size(); } + bool empty() const { + EXPECT_EQ(tree_.empty(), checker_.empty()); + return tree_.empty(); + } + + protected: + TreeType tree_; + const TreeType& const_tree_; + CheckerType checker_; +}; + +namespace { + +// A checker for unique sorted associative containers. TreeType is expected to +// be btree_{set,map} and CheckerType is expected to be {set,map}. +template <typename TreeType, typename CheckerType> +class unique_checker : public base_checker<TreeType, CheckerType> { + using super_type = base_checker<TreeType, CheckerType>; + + public: + using iterator = typename super_type::iterator; + using value_type = typename super_type::value_type; + + public: + unique_checker() : super_type() {} + unique_checker(const unique_checker& other) : super_type(other) {} + template <class InputIterator> + unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {} + unique_checker& operator=(const unique_checker&) = default; + + // Insertion routines. + std::pair<iterator, bool> insert(const value_type& v) { + int size = this->tree_.size(); + std::pair<typename CheckerType::iterator, bool> checker_res = + this->checker_.insert(v); + std::pair<iterator, bool> tree_res = this->tree_.insert(v); + CheckPairEquals(*tree_res.first, *checker_res.first); + EXPECT_EQ(tree_res.second, checker_res.second); + EXPECT_EQ(this->tree_.size(), this->checker_.size()); + EXPECT_EQ(this->tree_.size(), size + tree_res.second); + return tree_res; + } + iterator insert(iterator position, const value_type& v) { + int size = this->tree_.size(); + std::pair<typename CheckerType::iterator, bool> checker_res = + this->checker_.insert(v); + iterator tree_res = this->tree_.insert(position, v); + CheckPairEquals(*tree_res, *checker_res.first); + EXPECT_EQ(this->tree_.size(), this->checker_.size()); + EXPECT_EQ(this->tree_.size(), size + checker_res.second); + return tree_res; + } + template <typename InputIterator> + void insert(InputIterator b, InputIterator e) { + for (; b != e; ++b) { + insert(*b); + } + } +}; + +// A checker for multiple sorted associative containers. TreeType is expected +// to be btree_{multiset,multimap} and CheckerType is expected to be +// {multiset,multimap}. +template <typename TreeType, typename CheckerType> +class multi_checker : public base_checker<TreeType, CheckerType> { + using super_type = base_checker<TreeType, CheckerType>; + + public: + using iterator = typename super_type::iterator; + using value_type = typename super_type::value_type; + + public: + multi_checker() : super_type() {} + multi_checker(const multi_checker& other) : super_type(other) {} + template <class InputIterator> + multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {} + multi_checker& operator=(const multi_checker&) = default; + + // Insertion routines. + iterator insert(const value_type& v) { + int size = this->tree_.size(); + auto checker_res = this->checker_.insert(v); + iterator tree_res = this->tree_.insert(v); + CheckPairEquals(*tree_res, *checker_res); + EXPECT_EQ(this->tree_.size(), this->checker_.size()); + EXPECT_EQ(this->tree_.size(), size + 1); + return tree_res; + } + iterator insert(iterator position, const value_type& v) { + int size = this->tree_.size(); + auto checker_res = this->checker_.insert(v); + iterator tree_res = this->tree_.insert(position, v); + CheckPairEquals(*tree_res, *checker_res); + EXPECT_EQ(this->tree_.size(), this->checker_.size()); + EXPECT_EQ(this->tree_.size(), size + 1); + return tree_res; + } + template <typename InputIterator> + void insert(InputIterator b, InputIterator e) { + for (; b != e; ++b) { + insert(*b); + } + } +}; + +template <typename T, typename V> +void DoTest(const char* name, T* b, const std::vector<V>& values) { + typename KeyOfValue<typename T::key_type, V>::type key_of_value; + + T& mutable_b = *b; + const T& const_b = *b; + + // Test insert. + for (int i = 0; i < values.size(); ++i) { + mutable_b.insert(values[i]); + mutable_b.value_check(values[i]); + } + ASSERT_EQ(mutable_b.size(), values.size()); + + const_b.verify(); + + // Test copy constructor. + T b_copy(const_b); + EXPECT_EQ(b_copy.size(), const_b.size()); + for (int i = 0; i < values.size(); ++i) { + CheckPairEquals(*b_copy.find(key_of_value(values[i])), values[i]); + } + + // Test range constructor. + T b_range(const_b.begin(), const_b.end()); + EXPECT_EQ(b_range.size(), const_b.size()); + for (int i = 0; i < values.size(); ++i) { + CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); + } + + // Test range insertion for values that already exist. + b_range.insert(b_copy.begin(), b_copy.end()); + b_range.verify(); + + // Test range insertion for new values. + b_range.clear(); + b_range.insert(b_copy.begin(), b_copy.end()); + EXPECT_EQ(b_range.size(), b_copy.size()); + for (int i = 0; i < values.size(); ++i) { + CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); + } + + // Test assignment to self. Nothing should change. + b_range.operator=(b_range); + EXPECT_EQ(b_range.size(), b_copy.size()); + + // Test assignment of new values. + b_range.clear(); + b_range = b_copy; + EXPECT_EQ(b_range.size(), b_copy.size()); + + // Test swap. + b_range.clear(); + b_range.swap(b_copy); + EXPECT_EQ(b_copy.size(), 0); + EXPECT_EQ(b_range.size(), const_b.size()); + for (int i = 0; i < values.size(); ++i) { + CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); + } + b_range.swap(b_copy); + + // Test non-member function swap. + swap(b_range, b_copy); + EXPECT_EQ(b_copy.size(), 0); + EXPECT_EQ(b_range.size(), const_b.size()); + for (int i = 0; i < values.size(); ++i) { + CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); + } + swap(b_range, b_copy); + + // Test erase via values. + for (int i = 0; i < values.size(); ++i) { + mutable_b.erase(key_of_value(values[i])); + // Erasing a non-existent key should have no effect. + ASSERT_EQ(mutable_b.erase(key_of_value(values[i])), 0); + } + + const_b.verify(); + EXPECT_EQ(const_b.size(), 0); + + // Test erase via iterators. + mutable_b = b_copy; + for (int i = 0; i < values.size(); ++i) { + mutable_b.erase(mutable_b.find(key_of_value(values[i]))); + } + + const_b.verify(); + EXPECT_EQ(const_b.size(), 0); + + // Test insert with hint. + for (int i = 0; i < values.size(); i++) { + mutable_b.insert(mutable_b.upper_bound(key_of_value(values[i])), values[i]); + } + + const_b.verify(); + + // Test range erase. + mutable_b.erase(mutable_b.begin(), mutable_b.end()); + EXPECT_EQ(mutable_b.size(), 0); + const_b.verify(); + + // First half. + mutable_b = b_copy; + typename T::iterator mutable_iter_end = mutable_b.begin(); + for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_end; + mutable_b.erase(mutable_b.begin(), mutable_iter_end); + EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 2); + const_b.verify(); + + // Second half. + mutable_b = b_copy; + typename T::iterator mutable_iter_begin = mutable_b.begin(); + for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_begin; + mutable_b.erase(mutable_iter_begin, mutable_b.end()); + EXPECT_EQ(mutable_b.size(), values.size() / 2); + const_b.verify(); + + // Second quarter. + mutable_b = b_copy; + mutable_iter_begin = mutable_b.begin(); + for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_begin; + mutable_iter_end = mutable_iter_begin; + for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_end; + mutable_b.erase(mutable_iter_begin, mutable_iter_end); + EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 4); + const_b.verify(); + + mutable_b.clear(); +} + +template <typename T> +void ConstTest() { + using value_type = typename T::value_type; + typename KeyOfValue<typename T::key_type, value_type>::type key_of_value; + + T mutable_b; + const T& const_b = mutable_b; + + // Insert a single value into the container and test looking it up. + value_type value = Generator<value_type>(2)(2); + mutable_b.insert(value); + EXPECT_TRUE(mutable_b.contains(key_of_value(value))); + EXPECT_NE(mutable_b.find(key_of_value(value)), const_b.end()); + EXPECT_TRUE(const_b.contains(key_of_value(value))); + EXPECT_NE(const_b.find(key_of_value(value)), mutable_b.end()); + EXPECT_EQ(*const_b.lower_bound(key_of_value(value)), value); + EXPECT_EQ(const_b.upper_bound(key_of_value(value)), const_b.end()); + EXPECT_EQ(*const_b.equal_range(key_of_value(value)).first, value); + + // We can only create a non-const iterator from a non-const container. + typename T::iterator mutable_iter(mutable_b.begin()); + EXPECT_EQ(mutable_iter, const_b.begin()); + EXPECT_NE(mutable_iter, const_b.end()); + EXPECT_EQ(const_b.begin(), mutable_iter); + EXPECT_NE(const_b.end(), mutable_iter); + typename T::reverse_iterator mutable_riter(mutable_b.rbegin()); + EXPECT_EQ(mutable_riter, const_b.rbegin()); + EXPECT_NE(mutable_riter, const_b.rend()); + EXPECT_EQ(const_b.rbegin(), mutable_riter); + EXPECT_NE(const_b.rend(), mutable_riter); + + // We can create a const iterator from a non-const iterator. + typename T::const_iterator const_iter(mutable_iter); + EXPECT_EQ(const_iter, mutable_b.begin()); + EXPECT_NE(const_iter, mutable_b.end()); + EXPECT_EQ(mutable_b.begin(), const_iter); + EXPECT_NE(mutable_b.end(), const_iter); + typename T::const_reverse_iterator const_riter(mutable_riter); + EXPECT_EQ(const_riter, mutable_b.rbegin()); + EXPECT_NE(const_riter, mutable_b.rend()); + EXPECT_EQ(mutable_b.rbegin(), const_riter); + EXPECT_NE(mutable_b.rend(), const_riter); + + // Make sure various methods can be invoked on a const container. + const_b.verify(); + ASSERT_TRUE(!const_b.empty()); + EXPECT_EQ(const_b.size(), 1); + EXPECT_GT(const_b.max_size(), 0); + EXPECT_TRUE(const_b.contains(key_of_value(value))); + EXPECT_EQ(const_b.count(key_of_value(value)), 1); +} + +template <typename T, typename C> +void BtreeTest() { + ConstTest<T>(); + + using V = typename remove_pair_const<typename T::value_type>::type; + const std::vector<V> random_values = GenerateValuesWithSeed<V>( + absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values), + GTEST_FLAG_GET(random_seed)); + + unique_checker<T, C> container; + + // Test key insertion/deletion in sorted order. + std::vector<V> sorted_values(random_values); + std::sort(sorted_values.begin(), sorted_values.end()); + DoTest("sorted: ", &container, sorted_values); + + // Test key insertion/deletion in reverse sorted order. + std::reverse(sorted_values.begin(), sorted_values.end()); + DoTest("rsorted: ", &container, sorted_values); + + // Test key insertion/deletion in random order. + DoTest("random: ", &container, random_values); +} + +template <typename T, typename C> +void BtreeMultiTest() { + ConstTest<T>(); + + using V = typename remove_pair_const<typename T::value_type>::type; + const std::vector<V> random_values = GenerateValuesWithSeed<V>( + absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values), + GTEST_FLAG_GET(random_seed)); + + multi_checker<T, C> container; + + // Test keys in sorted order. + std::vector<V> sorted_values(random_values); + std::sort(sorted_values.begin(), sorted_values.end()); + DoTest("sorted: ", &container, sorted_values); + + // Test keys in reverse sorted order. + std::reverse(sorted_values.begin(), sorted_values.end()); + DoTest("rsorted: ", &container, sorted_values); + + // Test keys in random order. + DoTest("random: ", &container, random_values); + + // Test keys in random order w/ duplicates. + std::vector<V> duplicate_values(random_values); + duplicate_values.insert(duplicate_values.end(), random_values.begin(), + random_values.end()); + DoTest("duplicates:", &container, duplicate_values); + + // Test all identical keys. + std::vector<V> identical_values(100); + std::fill(identical_values.begin(), identical_values.end(), + Generator<V>(2)(2)); + DoTest("identical: ", &container, identical_values); +} + +template <typename T> +void BtreeMapTest() { + using value_type = typename T::value_type; + using mapped_type = typename T::mapped_type; + + mapped_type m = Generator<mapped_type>(0)(0); + (void)m; + + T b; + + // Verify we can insert using operator[]. + for (int i = 0; i < 1000; i++) { + value_type v = Generator<value_type>(1000)(i); + b[v.first] = v.second; + } + EXPECT_EQ(b.size(), 1000); + + // Test whether we can use the "->" operator on iterators and + // reverse_iterators. This stresses the btree_map_params::pair_pointer + // mechanism. + EXPECT_EQ(b.begin()->first, Generator<value_type>(1000)(0).first); + EXPECT_EQ(b.begin()->second, Generator<value_type>(1000)(0).second); + EXPECT_EQ(b.rbegin()->first, Generator<value_type>(1000)(999).first); + EXPECT_EQ(b.rbegin()->second, Generator<value_type>(1000)(999).second); +} + +template <typename T> +void BtreeMultiMapTest() { + using mapped_type = typename T::mapped_type; + mapped_type m = Generator<mapped_type>(0)(0); + (void)m; +} + +template <typename K, int N = 256> +void SetTest() { + EXPECT_EQ(sizeof(absl::btree_set<K>), + 2 * sizeof(void*) + sizeof(typename absl::btree_set<K>::size_type)); + using BtreeSet = absl::btree_set<K>; + BtreeTest<BtreeSet, std::set<K>>(); +} + +template <typename K, int N = 256> +void MapTest() { + EXPECT_EQ( + sizeof(absl::btree_map<K, K>), + 2 * sizeof(void*) + sizeof(typename absl::btree_map<K, K>::size_type)); + using BtreeMap = absl::btree_map<K, K>; + BtreeTest<BtreeMap, std::map<K, K>>(); + BtreeMapTest<BtreeMap>(); +} + +TEST(Btree, set_int32) { SetTest<int32_t>(); } +TEST(Btree, set_string) { SetTest<std::string>(); } +TEST(Btree, set_cord) { SetTest<absl::Cord>(); } +TEST(Btree, map_int32) { MapTest<int32_t>(); } +TEST(Btree, map_string) { MapTest<std::string>(); } +TEST(Btree, map_cord) { MapTest<absl::Cord>(); } + +template <typename K, int N = 256> +void MultiSetTest() { + EXPECT_EQ( + sizeof(absl::btree_multiset<K>), + 2 * sizeof(void*) + sizeof(typename absl::btree_multiset<K>::size_type)); + using BtreeMSet = absl::btree_multiset<K>; + BtreeMultiTest<BtreeMSet, std::multiset<K>>(); +} + +template <typename K, int N = 256> +void MultiMapTest() { + EXPECT_EQ(sizeof(absl::btree_multimap<K, K>), + 2 * sizeof(void*) + + sizeof(typename absl::btree_multimap<K, K>::size_type)); + using BtreeMMap = absl::btree_multimap<K, K>; + BtreeMultiTest<BtreeMMap, std::multimap<K, K>>(); + BtreeMultiMapTest<BtreeMMap>(); +} + +TEST(Btree, multiset_int32) { MultiSetTest<int32_t>(); } +TEST(Btree, multiset_string) { MultiSetTest<std::string>(); } +TEST(Btree, multiset_cord) { MultiSetTest<absl::Cord>(); } +TEST(Btree, multimap_int32) { MultiMapTest<int32_t>(); } +TEST(Btree, multimap_string) { MultiMapTest<std::string>(); } +TEST(Btree, multimap_cord) { MultiMapTest<absl::Cord>(); } + +} // namespace +} // namespace container_internal +ABSL_NAMESPACE_END +} // namespace absl
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index a2c8648..fd078d2 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc
@@ -11,6 +11,14 @@ // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. // See the License for the specific language governing permissions and // limitations under the License. +// +// ----------------------------------------------------------------------------- +// File: btree_test.cc +// ----------------------------------------------------------------------------- +// +// General tests for btree containers without many diverse value types. +// NOTE: There are more tests in btree_instantiate_test.cc that test +// diverse value types. #include "absl/container/btree_test.h" @@ -43,7 +51,6 @@ #include "absl/container/btree_set.h" #include "absl/container/internal/test_allocator.h" #include "absl/container/internal/test_instance_tracker.h" -#include "absl/flags/flag.h" #include "absl/hash/hash_testing.h" #include "absl/memory/memory.h" #include "absl/random/random.h" @@ -53,8 +60,6 @@ #include "absl/strings/string_view.h" #include "absl/types/compare.h" -ABSL_FLAG(int, test_values, 10000, "The number of values to use for tests"); - namespace absl { ABSL_NAMESPACE_BEGIN namespace container_internal { @@ -70,681 +75,9 @@ using ::testing::Pair; using ::testing::SizeIs; -template <typename T, typename U> -void CheckPairEquals(const T &x, const U &y) { - ABSL_INTERNAL_CHECK(x == y, "Values are unequal."); -} - -template <typename T, typename U, typename V, typename W> -void CheckPairEquals(const std::pair<T, U> &x, const std::pair<V, W> &y) { - CheckPairEquals(x.first, y.first); - CheckPairEquals(x.second, y.second); -} } // namespace -// The base class for a sorted associative container checker. TreeType is the -// container type to check and CheckerType is the container type to check -// against. TreeType is expected to be btree_{set,map,multiset,multimap} and -// CheckerType is expected to be {set,map,multiset,multimap}. -template <typename TreeType, typename CheckerType> -class base_checker { - public: - using key_type = typename TreeType::key_type; - using value_type = typename TreeType::value_type; - using key_compare = typename TreeType::key_compare; - using pointer = typename TreeType::pointer; - using const_pointer = typename TreeType::const_pointer; - using reference = typename TreeType::reference; - using const_reference = typename TreeType::const_reference; - using size_type = typename TreeType::size_type; - using difference_type = typename TreeType::difference_type; - using iterator = typename TreeType::iterator; - using const_iterator = typename TreeType::const_iterator; - using reverse_iterator = typename TreeType::reverse_iterator; - using const_reverse_iterator = typename TreeType::const_reverse_iterator; - - public: - base_checker() : const_tree_(tree_) {} - base_checker(const base_checker &other) - : tree_(other.tree_), const_tree_(tree_), checker_(other.checker_) {} - template <typename InputIterator> - base_checker(InputIterator b, InputIterator e) - : tree_(b, e), const_tree_(tree_), checker_(b, e) {} - - iterator begin() { return tree_.begin(); } - const_iterator begin() const { return tree_.begin(); } - iterator end() { return tree_.end(); } - const_iterator end() const { return tree_.end(); } - reverse_iterator rbegin() { return tree_.rbegin(); } - const_reverse_iterator rbegin() const { return tree_.rbegin(); } - reverse_iterator rend() { return tree_.rend(); } - const_reverse_iterator rend() const { return tree_.rend(); } - - template <typename IterType, typename CheckerIterType> - IterType iter_check(IterType tree_iter, CheckerIterType checker_iter) const { - if (tree_iter == tree_.end()) { - ABSL_INTERNAL_CHECK(checker_iter == checker_.end(), - "Checker iterator not at end."); - } else { - CheckPairEquals(*tree_iter, *checker_iter); - } - return tree_iter; - } - template <typename IterType, typename CheckerIterType> - IterType riter_check(IterType tree_iter, CheckerIterType checker_iter) const { - if (tree_iter == tree_.rend()) { - ABSL_INTERNAL_CHECK(checker_iter == checker_.rend(), - "Checker iterator not at rend."); - } else { - CheckPairEquals(*tree_iter, *checker_iter); - } - return tree_iter; - } - void value_check(const value_type &v) { - typename KeyOfValue<typename TreeType::key_type, - typename TreeType::value_type>::type key_of_value; - const key_type &key = key_of_value(v); - CheckPairEquals(*find(key), v); - lower_bound(key); - upper_bound(key); - equal_range(key); - contains(key); - count(key); - } - void erase_check(const key_type &key) { - EXPECT_FALSE(tree_.contains(key)); - EXPECT_EQ(tree_.find(key), const_tree_.end()); - EXPECT_FALSE(const_tree_.contains(key)); - EXPECT_EQ(const_tree_.find(key), tree_.end()); - EXPECT_EQ(tree_.equal_range(key).first, - const_tree_.equal_range(key).second); - } - - iterator lower_bound(const key_type &key) { - return iter_check(tree_.lower_bound(key), checker_.lower_bound(key)); - } - const_iterator lower_bound(const key_type &key) const { - return iter_check(tree_.lower_bound(key), checker_.lower_bound(key)); - } - iterator upper_bound(const key_type &key) { - return iter_check(tree_.upper_bound(key), checker_.upper_bound(key)); - } - const_iterator upper_bound(const key_type &key) const { - return iter_check(tree_.upper_bound(key), checker_.upper_bound(key)); - } - std::pair<iterator, iterator> equal_range(const key_type &key) { - std::pair<typename CheckerType::iterator, typename CheckerType::iterator> - checker_res = checker_.equal_range(key); - std::pair<iterator, iterator> tree_res = tree_.equal_range(key); - iter_check(tree_res.first, checker_res.first); - iter_check(tree_res.second, checker_res.second); - return tree_res; - } - std::pair<const_iterator, const_iterator> equal_range( - const key_type &key) const { - std::pair<typename CheckerType::const_iterator, - typename CheckerType::const_iterator> - checker_res = checker_.equal_range(key); - std::pair<const_iterator, const_iterator> tree_res = tree_.equal_range(key); - iter_check(tree_res.first, checker_res.first); - iter_check(tree_res.second, checker_res.second); - return tree_res; - } - iterator find(const key_type &key) { - return iter_check(tree_.find(key), checker_.find(key)); - } - const_iterator find(const key_type &key) const { - return iter_check(tree_.find(key), checker_.find(key)); - } - bool contains(const key_type &key) const { return find(key) != end(); } - size_type count(const key_type &key) const { - size_type res = checker_.count(key); - EXPECT_EQ(res, tree_.count(key)); - return res; - } - - base_checker &operator=(const base_checker &other) { - tree_ = other.tree_; - checker_ = other.checker_; - return *this; - } - - int erase(const key_type &key) { - int size = tree_.size(); - int res = checker_.erase(key); - EXPECT_EQ(res, tree_.count(key)); - EXPECT_EQ(res, tree_.erase(key)); - EXPECT_EQ(tree_.count(key), 0); - EXPECT_EQ(tree_.size(), size - res); - erase_check(key); - return res; - } - iterator erase(iterator iter) { - key_type key = iter.key(); - int size = tree_.size(); - int count = tree_.count(key); - auto checker_iter = checker_.lower_bound(key); - for (iterator tmp(tree_.lower_bound(key)); tmp != iter; ++tmp) { - ++checker_iter; - } - auto checker_next = checker_iter; - ++checker_next; - checker_.erase(checker_iter); - iter = tree_.erase(iter); - EXPECT_EQ(tree_.size(), checker_.size()); - EXPECT_EQ(tree_.size(), size - 1); - EXPECT_EQ(tree_.count(key), count - 1); - if (count == 1) { - erase_check(key); - } - return iter_check(iter, checker_next); - } - - void erase(iterator begin, iterator end) { - int size = tree_.size(); - int count = std::distance(begin, end); - auto checker_begin = checker_.lower_bound(begin.key()); - for (iterator tmp(tree_.lower_bound(begin.key())); tmp != begin; ++tmp) { - ++checker_begin; - } - auto checker_end = - end == tree_.end() ? checker_.end() : checker_.lower_bound(end.key()); - if (end != tree_.end()) { - for (iterator tmp(tree_.lower_bound(end.key())); tmp != end; ++tmp) { - ++checker_end; - } - } - const auto checker_ret = checker_.erase(checker_begin, checker_end); - const auto tree_ret = tree_.erase(begin, end); - EXPECT_EQ(std::distance(checker_.begin(), checker_ret), - std::distance(tree_.begin(), tree_ret)); - EXPECT_EQ(tree_.size(), checker_.size()); - EXPECT_EQ(tree_.size(), size - count); - } - - void clear() { - tree_.clear(); - checker_.clear(); - } - void swap(base_checker &other) { - tree_.swap(other.tree_); - checker_.swap(other.checker_); - } - - void verify() const { - tree_.verify(); - EXPECT_EQ(tree_.size(), checker_.size()); - - // Move through the forward iterators using increment. - auto checker_iter = checker_.begin(); - const_iterator tree_iter(tree_.begin()); - for (; tree_iter != tree_.end(); ++tree_iter, ++checker_iter) { - CheckPairEquals(*tree_iter, *checker_iter); - } - - // Move through the forward iterators using decrement. - for (int n = tree_.size() - 1; n >= 0; --n) { - iter_check(tree_iter, checker_iter); - --tree_iter; - --checker_iter; - } - EXPECT_EQ(tree_iter, tree_.begin()); - EXPECT_EQ(checker_iter, checker_.begin()); - - // Move through the reverse iterators using increment. - auto checker_riter = checker_.rbegin(); - const_reverse_iterator tree_riter(tree_.rbegin()); - for (; tree_riter != tree_.rend(); ++tree_riter, ++checker_riter) { - CheckPairEquals(*tree_riter, *checker_riter); - } - - // Move through the reverse iterators using decrement. - for (int n = tree_.size() - 1; n >= 0; --n) { - riter_check(tree_riter, checker_riter); - --tree_riter; - --checker_riter; - } - EXPECT_EQ(tree_riter, tree_.rbegin()); - EXPECT_EQ(checker_riter, checker_.rbegin()); - } - - const TreeType &tree() const { return tree_; } - - size_type size() const { - EXPECT_EQ(tree_.size(), checker_.size()); - return tree_.size(); - } - size_type max_size() const { return tree_.max_size(); } - bool empty() const { - EXPECT_EQ(tree_.empty(), checker_.empty()); - return tree_.empty(); - } - - protected: - TreeType tree_; - const TreeType &const_tree_; - CheckerType checker_; -}; - namespace { -// A checker for unique sorted associative containers. TreeType is expected to -// be btree_{set,map} and CheckerType is expected to be {set,map}. -template <typename TreeType, typename CheckerType> -class unique_checker : public base_checker<TreeType, CheckerType> { - using super_type = base_checker<TreeType, CheckerType>; - - public: - using iterator = typename super_type::iterator; - using value_type = typename super_type::value_type; - - public: - unique_checker() : super_type() {} - unique_checker(const unique_checker &other) : super_type(other) {} - template <class InputIterator> - unique_checker(InputIterator b, InputIterator e) : super_type(b, e) {} - unique_checker &operator=(const unique_checker &) = default; - - // Insertion routines. - std::pair<iterator, bool> insert(const value_type &v) { - int size = this->tree_.size(); - std::pair<typename CheckerType::iterator, bool> checker_res = - this->checker_.insert(v); - std::pair<iterator, bool> tree_res = this->tree_.insert(v); - CheckPairEquals(*tree_res.first, *checker_res.first); - EXPECT_EQ(tree_res.second, checker_res.second); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + tree_res.second); - return tree_res; - } - iterator insert(iterator position, const value_type &v) { - int size = this->tree_.size(); - std::pair<typename CheckerType::iterator, bool> checker_res = - this->checker_.insert(v); - iterator tree_res = this->tree_.insert(position, v); - CheckPairEquals(*tree_res, *checker_res.first); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + checker_res.second); - return tree_res; - } - template <typename InputIterator> - void insert(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert(*b); - } - } -}; - -// A checker for multiple sorted associative containers. TreeType is expected -// to be btree_{multiset,multimap} and CheckerType is expected to be -// {multiset,multimap}. -template <typename TreeType, typename CheckerType> -class multi_checker : public base_checker<TreeType, CheckerType> { - using super_type = base_checker<TreeType, CheckerType>; - - public: - using iterator = typename super_type::iterator; - using value_type = typename super_type::value_type; - - public: - multi_checker() : super_type() {} - multi_checker(const multi_checker &other) : super_type(other) {} - template <class InputIterator> - multi_checker(InputIterator b, InputIterator e) : super_type(b, e) {} - multi_checker &operator=(const multi_checker &) = default; - - // Insertion routines. - iterator insert(const value_type &v) { - int size = this->tree_.size(); - auto checker_res = this->checker_.insert(v); - iterator tree_res = this->tree_.insert(v); - CheckPairEquals(*tree_res, *checker_res); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + 1); - return tree_res; - } - iterator insert(iterator position, const value_type &v) { - int size = this->tree_.size(); - auto checker_res = this->checker_.insert(v); - iterator tree_res = this->tree_.insert(position, v); - CheckPairEquals(*tree_res, *checker_res); - EXPECT_EQ(this->tree_.size(), this->checker_.size()); - EXPECT_EQ(this->tree_.size(), size + 1); - return tree_res; - } - template <typename InputIterator> - void insert(InputIterator b, InputIterator e) { - for (; b != e; ++b) { - insert(*b); - } - } -}; - -template <typename T, typename V> -void DoTest(const char *name, T *b, const std::vector<V> &values) { - typename KeyOfValue<typename T::key_type, V>::type key_of_value; - - T &mutable_b = *b; - const T &const_b = *b; - - // Test insert. - for (int i = 0; i < values.size(); ++i) { - mutable_b.insert(values[i]); - mutable_b.value_check(values[i]); - } - ASSERT_EQ(mutable_b.size(), values.size()); - - const_b.verify(); - - // Test copy constructor. - T b_copy(const_b); - EXPECT_EQ(b_copy.size(), const_b.size()); - for (int i = 0; i < values.size(); ++i) { - CheckPairEquals(*b_copy.find(key_of_value(values[i])), values[i]); - } - - // Test range constructor. - T b_range(const_b.begin(), const_b.end()); - EXPECT_EQ(b_range.size(), const_b.size()); - for (int i = 0; i < values.size(); ++i) { - CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); - } - - // Test range insertion for values that already exist. - b_range.insert(b_copy.begin(), b_copy.end()); - b_range.verify(); - - // Test range insertion for new values. - b_range.clear(); - b_range.insert(b_copy.begin(), b_copy.end()); - EXPECT_EQ(b_range.size(), b_copy.size()); - for (int i = 0; i < values.size(); ++i) { - CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); - } - - // Test assignment to self. Nothing should change. - b_range.operator=(b_range); - EXPECT_EQ(b_range.size(), b_copy.size()); - - // Test assignment of new values. - b_range.clear(); - b_range = b_copy; - EXPECT_EQ(b_range.size(), b_copy.size()); - - // Test swap. - b_range.clear(); - b_range.swap(b_copy); - EXPECT_EQ(b_copy.size(), 0); - EXPECT_EQ(b_range.size(), const_b.size()); - for (int i = 0; i < values.size(); ++i) { - CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); - } - b_range.swap(b_copy); - - // Test non-member function swap. - swap(b_range, b_copy); - EXPECT_EQ(b_copy.size(), 0); - EXPECT_EQ(b_range.size(), const_b.size()); - for (int i = 0; i < values.size(); ++i) { - CheckPairEquals(*b_range.find(key_of_value(values[i])), values[i]); - } - swap(b_range, b_copy); - - // Test erase via values. - for (int i = 0; i < values.size(); ++i) { - mutable_b.erase(key_of_value(values[i])); - // Erasing a non-existent key should have no effect. - ASSERT_EQ(mutable_b.erase(key_of_value(values[i])), 0); - } - - const_b.verify(); - EXPECT_EQ(const_b.size(), 0); - - // Test erase via iterators. - mutable_b = b_copy; - for (int i = 0; i < values.size(); ++i) { - mutable_b.erase(mutable_b.find(key_of_value(values[i]))); - } - - const_b.verify(); - EXPECT_EQ(const_b.size(), 0); - - // Test insert with hint. - for (int i = 0; i < values.size(); i++) { - mutable_b.insert(mutable_b.upper_bound(key_of_value(values[i])), values[i]); - } - - const_b.verify(); - - // Test range erase. - mutable_b.erase(mutable_b.begin(), mutable_b.end()); - EXPECT_EQ(mutable_b.size(), 0); - const_b.verify(); - - // First half. - mutable_b = b_copy; - typename T::iterator mutable_iter_end = mutable_b.begin(); - for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_end; - mutable_b.erase(mutable_b.begin(), mutable_iter_end); - EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 2); - const_b.verify(); - - // Second half. - mutable_b = b_copy; - typename T::iterator mutable_iter_begin = mutable_b.begin(); - for (int i = 0; i < values.size() / 2; ++i) ++mutable_iter_begin; - mutable_b.erase(mutable_iter_begin, mutable_b.end()); - EXPECT_EQ(mutable_b.size(), values.size() / 2); - const_b.verify(); - - // Second quarter. - mutable_b = b_copy; - mutable_iter_begin = mutable_b.begin(); - for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_begin; - mutable_iter_end = mutable_iter_begin; - for (int i = 0; i < values.size() / 4; ++i) ++mutable_iter_end; - mutable_b.erase(mutable_iter_begin, mutable_iter_end); - EXPECT_EQ(mutable_b.size(), values.size() - values.size() / 4); - const_b.verify(); - - mutable_b.clear(); -} - -template <typename T> -void ConstTest() { - using value_type = typename T::value_type; - typename KeyOfValue<typename T::key_type, value_type>::type key_of_value; - - T mutable_b; - const T &const_b = mutable_b; - - // Insert a single value into the container and test looking it up. - value_type value = Generator<value_type>(2)(2); - mutable_b.insert(value); - EXPECT_TRUE(mutable_b.contains(key_of_value(value))); - EXPECT_NE(mutable_b.find(key_of_value(value)), const_b.end()); - EXPECT_TRUE(const_b.contains(key_of_value(value))); - EXPECT_NE(const_b.find(key_of_value(value)), mutable_b.end()); - EXPECT_EQ(*const_b.lower_bound(key_of_value(value)), value); - EXPECT_EQ(const_b.upper_bound(key_of_value(value)), const_b.end()); - EXPECT_EQ(*const_b.equal_range(key_of_value(value)).first, value); - - // We can only create a non-const iterator from a non-const container. - typename T::iterator mutable_iter(mutable_b.begin()); - EXPECT_EQ(mutable_iter, const_b.begin()); - EXPECT_NE(mutable_iter, const_b.end()); - EXPECT_EQ(const_b.begin(), mutable_iter); - EXPECT_NE(const_b.end(), mutable_iter); - typename T::reverse_iterator mutable_riter(mutable_b.rbegin()); - EXPECT_EQ(mutable_riter, const_b.rbegin()); - EXPECT_NE(mutable_riter, const_b.rend()); - EXPECT_EQ(const_b.rbegin(), mutable_riter); - EXPECT_NE(const_b.rend(), mutable_riter); - - // We can create a const iterator from a non-const iterator. - typename T::const_iterator const_iter(mutable_iter); - EXPECT_EQ(const_iter, mutable_b.begin()); - EXPECT_NE(const_iter, mutable_b.end()); - EXPECT_EQ(mutable_b.begin(), const_iter); - EXPECT_NE(mutable_b.end(), const_iter); - typename T::const_reverse_iterator const_riter(mutable_riter); - EXPECT_EQ(const_riter, mutable_b.rbegin()); - EXPECT_NE(const_riter, mutable_b.rend()); - EXPECT_EQ(mutable_b.rbegin(), const_riter); - EXPECT_NE(mutable_b.rend(), const_riter); - - // Make sure various methods can be invoked on a const container. - const_b.verify(); - ASSERT_TRUE(!const_b.empty()); - EXPECT_EQ(const_b.size(), 1); - EXPECT_GT(const_b.max_size(), 0); - EXPECT_TRUE(const_b.contains(key_of_value(value))); - EXPECT_EQ(const_b.count(key_of_value(value)), 1); -} - -template <typename T, typename C> -void BtreeTest() { - ConstTest<T>(); - - using V = typename remove_pair_const<typename T::value_type>::type; - const std::vector<V> random_values = GenerateValuesWithSeed<V>( - absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values), - GTEST_FLAG_GET(random_seed)); - - unique_checker<T, C> container; - - // Test key insertion/deletion in sorted order. - std::vector<V> sorted_values(random_values); - std::sort(sorted_values.begin(), sorted_values.end()); - DoTest("sorted: ", &container, sorted_values); - - // Test key insertion/deletion in reverse sorted order. - std::reverse(sorted_values.begin(), sorted_values.end()); - DoTest("rsorted: ", &container, sorted_values); - - // Test key insertion/deletion in random order. - DoTest("random: ", &container, random_values); -} - -template <typename T, typename C> -void BtreeMultiTest() { - ConstTest<T>(); - - using V = typename remove_pair_const<typename T::value_type>::type; - const std::vector<V> random_values = GenerateValuesWithSeed<V>( - absl::GetFlag(FLAGS_test_values), 4 * absl::GetFlag(FLAGS_test_values), - GTEST_FLAG_GET(random_seed)); - - multi_checker<T, C> container; - - // Test keys in sorted order. - std::vector<V> sorted_values(random_values); - std::sort(sorted_values.begin(), sorted_values.end()); - DoTest("sorted: ", &container, sorted_values); - - // Test keys in reverse sorted order. - std::reverse(sorted_values.begin(), sorted_values.end()); - DoTest("rsorted: ", &container, sorted_values); - - // Test keys in random order. - DoTest("random: ", &container, random_values); - - // Test keys in random order w/ duplicates. - std::vector<V> duplicate_values(random_values); - duplicate_values.insert(duplicate_values.end(), random_values.begin(), - random_values.end()); - DoTest("duplicates:", &container, duplicate_values); - - // Test all identical keys. - std::vector<V> identical_values(100); - std::fill(identical_values.begin(), identical_values.end(), - Generator<V>(2)(2)); - DoTest("identical: ", &container, identical_values); -} - -template <typename T> -void BtreeMapTest() { - using value_type = typename T::value_type; - using mapped_type = typename T::mapped_type; - - mapped_type m = Generator<mapped_type>(0)(0); - (void)m; - - T b; - - // Verify we can insert using operator[]. - for (int i = 0; i < 1000; i++) { - value_type v = Generator<value_type>(1000)(i); - b[v.first] = v.second; - } - EXPECT_EQ(b.size(), 1000); - - // Test whether we can use the "->" operator on iterators and - // reverse_iterators. This stresses the btree_map_params::pair_pointer - // mechanism. - EXPECT_EQ(b.begin()->first, Generator<value_type>(1000)(0).first); - EXPECT_EQ(b.begin()->second, Generator<value_type>(1000)(0).second); - EXPECT_EQ(b.rbegin()->first, Generator<value_type>(1000)(999).first); - EXPECT_EQ(b.rbegin()->second, Generator<value_type>(1000)(999).second); -} - -template <typename T> -void BtreeMultiMapTest() { - using mapped_type = typename T::mapped_type; - mapped_type m = Generator<mapped_type>(0)(0); - (void)m; -} - -template <typename K, int N = 256> -void SetTest() { - EXPECT_EQ( - sizeof(absl::btree_set<K>), - 2 * sizeof(void *) + sizeof(typename absl::btree_set<K>::size_type)); - using BtreeSet = absl::btree_set<K>; - BtreeTest<BtreeSet, std::set<K>>(); -} - -template <typename K, int N = 256> -void MapTest() { - EXPECT_EQ( - sizeof(absl::btree_map<K, K>), - 2 * sizeof(void *) + sizeof(typename absl::btree_map<K, K>::size_type)); - using BtreeMap = absl::btree_map<K, K>; - BtreeTest<BtreeMap, std::map<K, K>>(); - BtreeMapTest<BtreeMap>(); -} - -TEST(Btree, set_int32) { SetTest<int32_t>(); } -TEST(Btree, set_string) { SetTest<std::string>(); } -TEST(Btree, set_cord) { SetTest<absl::Cord>(); } -TEST(Btree, map_int32) { MapTest<int32_t>(); } -TEST(Btree, map_string) { MapTest<std::string>(); } -TEST(Btree, map_cord) { MapTest<absl::Cord>(); } - -template <typename K, int N = 256> -void MultiSetTest() { - EXPECT_EQ( - sizeof(absl::btree_multiset<K>), - 2 * sizeof(void *) + sizeof(typename absl::btree_multiset<K>::size_type)); - using BtreeMSet = absl::btree_multiset<K>; - BtreeMultiTest<BtreeMSet, std::multiset<K>>(); -} - -template <typename K, int N = 256> -void MultiMapTest() { - EXPECT_EQ(sizeof(absl::btree_multimap<K, K>), - 2 * sizeof(void *) + - sizeof(typename absl::btree_multimap<K, K>::size_type)); - using BtreeMMap = absl::btree_multimap<K, K>; - BtreeMultiTest<BtreeMMap, std::multimap<K, K>>(); - BtreeMultiMapTest<BtreeMMap>(); -} - -TEST(Btree, multiset_int32) { MultiSetTest<int32_t>(); } -TEST(Btree, multiset_string) { MultiSetTest<std::string>(); } -TEST(Btree, multiset_cord) { MultiSetTest<absl::Cord>(); } -TEST(Btree, multimap_int32) { MultiMapTest<int32_t>(); } -TEST(Btree, multimap_string) { MultiMapTest<std::string>(); } -TEST(Btree, multimap_cord) { MultiMapTest<absl::Cord>(); } struct CompareIntToString { bool operator()(const std::string &a, const std::string &b) const {
diff --git a/absl/container/internal/raw_hash_set.cc b/absl/container/internal/raw_hash_set.cc index fb68468..3b0cf42 100644 --- a/absl/container/internal/raw_hash_set.cc +++ b/absl/container/internal/raw_hash_set.cc
@@ -102,20 +102,12 @@ .offset() < RehashProbabilityConstant(); } -// Find a non-deterministic hash for single group table. -// Last two bits are used to find a position for a newly inserted element after -// resize. -// This function basically using H2 last bits to save on shift operation. -size_t SingleGroupTableH1(size_t hash, PerTableSeed seed) { - return hash ^ seed.seed(); -} - // Returns the offset of the new element after resize from capacity 1 to 3. -size_t Resize1To3NewOffset(size_t hash, PerTableSeed seed) { +size_t Resize1To3NewOffset(size_t hash) { // After resize from capacity 1 to 3, we always have exactly the slot with // index 1 occupied, so we need to insert either at index 0 or index 2. static_assert(SooSlotIndex() == 1); - return SingleGroupTableH1(hash, seed) & 2; + return hash & 2; } // Returns the address of the ith slot in slots where each slot occupies @@ -1720,7 +1712,7 @@ h2_t new_h2 = H2(new_hash); size_t orig_hash = policy.hash_slot(policy.hash_fn(common), old_slots, common.seed().seed()); - size_t offset = Resize1To3NewOffset(new_hash, common.seed()); + size_t offset = Resize1To3NewOffset(new_hash); InitializeThreeElementsControlBytes(H2(orig_hash), new_h2, offset, new_ctrl); void* old_element_target = NextSlot(new_slots, slot_size); @@ -1786,8 +1778,7 @@ new_capacity); // We put the new element either at the beginning or at the end of the // table with approximately equal probability. - offset = - SingleGroupTableH1(new_hash, common.seed()) & 1 ? 0 : new_capacity - 1; + offset = new_hash & 1 ? 0 : new_capacity - 1; ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[offset])); SetCtrlInSingleGroupTable(common, offset, new_h2, policy.slot_size); @@ -2142,7 +2133,7 @@ policy.hash_fn(common), common.soo_data(), common.seed().seed())); const size_t new_hash = get_hash(common.seed().seed()); - const size_t offset = Resize1To3NewOffset(new_hash, common.seed()); + const size_t offset = Resize1To3NewOffset(new_hash); InitializeThreeElementsControlBytes(soo_slot_h2, H2(new_hash), offset, new_ctrl);
diff --git a/absl/crc/crc32c.cc b/absl/crc/crc32c.cc index ed826e2..3c5e59b 100644 --- a/absl/crc/crc32c.cc +++ b/absl/crc/crc32c.cc
@@ -17,7 +17,6 @@ #include <cstddef> #include <cstdint> -#include "absl/base/config.h" #include "absl/crc/internal/crc.h" #include "absl/crc/internal/crc32c.h" #include "absl/crc/internal/crc_memcpy.h" @@ -75,7 +74,7 @@ crc32c_t MemcpyCrc32c(void* dest, const void* src, size_t count, crc32c_t initial_crc) { return static_cast<crc32c_t>( - crc_internal::Crc32CAndCopy(dest, src, count, initial_crc, false)); + crc_internal::Crc32CAndCopy(dest, src, count, initial_crc)); } // Remove a Suffix of given size from a buffer
diff --git a/absl/crc/internal/crc.cc b/absl/crc/internal/crc.cc index d135e3c..8019248 100644 --- a/absl/crc/internal/crc.cc +++ b/absl/crc/internal/crc.cc
@@ -43,9 +43,9 @@ #include <cstddef> #include <cstdint> +#include <cstring> #include <iterator> -#include "absl/base/config.h" #include "absl/base/internal/endian.h" #include "absl/base/internal/raw_logging.h" #include "absl/base/prefetch.h" @@ -291,8 +291,7 @@ // starting at `ptr` and twelve zero bytes, so that four CRCs can be // built incrementally and combined at the end. const auto step_swath = [this](uint32_t crc_in, const std::uint8_t* ptr) { - return absl::little_endian::Load32(ptr) ^ - this->table_[3][crc_in & 0xff] ^ + return absl::little_endian::Load32(ptr) ^ this->table_[3][crc_in & 0xff] ^ this->table_[2][(crc_in >> 8) & 0xff] ^ this->table_[1][(crc_in >> 16) & 0xff] ^ this->table_[0][crc_in >> 24]; @@ -426,6 +425,12 @@ CRC::~CRC() {} CRC::CRC() {} +void CRC::ExtendAndCopy(uint32_t* crc, void* __restrict dst, + const void* __restrict src, size_t length) const { + std::memcpy(dst, src, length); + Extend(crc, dst, length); +} + // The "constructor" for a CRC32C with a standard polynomial. CRC* CRC::Crc32c() { static CRC* singleton = CRCImpl::NewInternal();
diff --git a/absl/crc/internal/crc.h b/absl/crc/internal/crc.h index 90e05f1..49487c6 100644 --- a/absl/crc/internal/crc.h +++ b/absl/crc/internal/crc.h
@@ -47,6 +47,11 @@ virtual void Extend(uint32_t* crc, const void* bytes, size_t length) const = 0; + // Copy 'length' bytes from 'src' to 'dst' and extend the CRC with the copied + // bytes. + virtual void ExtendAndCopy(uint32_t* crc, void* __restrict dst, + const void* __restrict src, size_t length) const; + // Equivalent to Extend(crc, bytes, length) where "bytes" // points to an array of "length" zero bytes. virtual void ExtendByZeroes(uint32_t* crc, size_t length) const = 0;
diff --git a/absl/crc/internal/crc32_x86_arm_combined_simd.h b/absl/crc/internal/crc32_x86_arm_combined_simd.h index c50a301..3acde80 100644 --- a/absl/crc/internal/crc32_x86_arm_combined_simd.h +++ b/absl/crc/internal/crc32_x86_arm_combined_simd.h
@@ -16,8 +16,11 @@ #define ABSL_CRC_INTERNAL_CRC32_X86_ARM_COMBINED_SIMD_H_ #include <array> +#include <cstddef> #include <cstdint> +#include <cstring> +#include "absl/base/attributes.h" #include "absl/base/config.h" #ifdef __SSE4_2__ @@ -55,6 +58,22 @@ #endif +// We try to force AVX instructions so that we can use them when AVX is +// available at runtime even if the translation unit isn't built with AVX +// support. Clang on Windows has gnu::target but does not make AVX types like +// __m256i available when trying to force specific functions to use AVX +// compiles. +#if ABSL_HAVE_CPP_ATTRIBUTE(gnu::target) && !defined(_MSC_VER) && \ + (defined(__x86_64__) || defined(__i386__)) +#define ABSL_INTERNAL_CAN_FORCE_AVX 1 +#endif + +#if defined(ABSL_INTERNAL_CAN_FORCE_AVX) +#define ABSL_INTERNAL_ATTRIBUTE_AVX [[gnu::target("avx")]] +#else +#define ABSL_INTERNAL_ATTRIBUTE_AVX +#endif + namespace absl { ABSL_NAMESPACE_BEGIN namespace crc_internal { @@ -70,11 +89,13 @@ using V128 = __m128i; #endif -#if defined(__AVX__) +#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) using V256 = __m256i; #else // Placeholder for V256 when AVX is not available. -using V256 = std::array<uint64_t, 4>; +struct alignas(32) V256 { + std::array<uint64_t, 4> val; +}; #endif // Starting with the initial value in |crc|, accumulates a CRC32 value for @@ -137,17 +158,41 @@ // Add packed 64-bit integers in |l| and |r|. V128 V128_Add64(const V128 l, const V128 r); -#if defined(__AVX__) -inline V256 V256_LoadU(const V256* src); -inline V256 V256_Broadcast128(const V128* src); +// Performs a store fence on architectures that require it. +void StoreFence(); + +#if defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX) +ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_LoadU(const void* src); +ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_Broadcast128(const V128* src); +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreU(void* dst, V256 data); +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreNonTemporal(void* dst, + V256 data); #else template <typename T = V256> -T V256_LoadU(const T* src); +T V256_LoadU(const void* src); template <typename T = V256> T V256_Broadcast128(const V128* src); + +template <typename T = V256> +void V256_StoreU(void* dst, const T& data); + +template <typename T = V256> +void V256_StoreNonTemporal(void* dst, const T& data); #endif +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_LoadPairU(const void* src, + V256* v0, V256* v1); +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairU(void* dst, V256 v0, + V256 v1); +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairNonTemporal(void* dst, + V256 v0, + V256 v1); +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairU(void* dst, + const void* src); +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairNonTemporal( + void* dst, const void* src); + #endif #if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) @@ -217,6 +262,8 @@ return _mm_add_epi64(l, r); } +inline void StoreFence() { _mm_sfence(); } + #elif defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) inline uint32_t CRC32_u8(uint32_t crc, uint8_t v) { return __crc32cb(crc, v); } @@ -303,12 +350,11 @@ return V128_Xor(V128_Xor(a, b), c); } -inline V128 V128_From64WithZeroFill(const uint64_t r){ +inline V128 V128_From64WithZeroFill(const uint64_t r) { constexpr uint64x2_t kZero = {0, 0}; return vsetq_lane_u64(r, kZero, 0); } - template <int imm> inline int V128_Extract32(const V128 l) { return vgetq_lane_s32(vreinterpretq_s32_u64(l), imm); @@ -325,21 +371,36 @@ inline V128 V128_Add64(const V128 l, const V128 r) { return vaddq_u64(l, r); } +inline void StoreFence() {} + #endif -#if defined(__AVX__) && defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) -inline V256 V256_LoadU(const V256* src) { return _mm256_loadu_si256(src); } +#if (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ + defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) +ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_LoadU(const void* src) { + return _mm256_loadu_si256(reinterpret_cast<const __m256i*>(src)); +} -inline V256 V256_Broadcast128(const V128* src) { +ABSL_INTERNAL_ATTRIBUTE_AVX inline V256 V256_Broadcast128(const V128* src) { return _mm256_castps_si256( _mm256_broadcast_ps(reinterpret_cast<const __m128*>(src))); } + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreU(void* dst, V256 data) { + _mm256_storeu_si256(reinterpret_cast<__m256i*>(dst), data); +} + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StoreNonTemporal(void* dst, + V256 data) { + _mm256_stream_si256(reinterpret_cast<__m256i*>(dst), data); +} #elif defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) || \ defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) template <typename T> -inline T V256_LoadU(const T* src) { - (void)src; - return T{}; +inline T V256_LoadU(const void* src) { + T res; + std::memcpy(&res, src, sizeof(T)); + return res; } template <typename T> @@ -347,8 +408,60 @@ (void)src; return T{}; } + +template <typename T> +inline void V256_StoreU(void* dst, const T& data) { + std::memcpy(dst, &data, sizeof(T)); +} + +template <typename T> +inline void V256_StoreNonTemporal(void* dst, const T& data) { + std::memcpy(dst, &data, sizeof(T)); +} #endif +#if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || \ + defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_LoadPairU(const void* src, + V256* v0, V256* v1) { + const char* src_ptr = reinterpret_cast<const char*>(src); + *v0 = V256_LoadU(src_ptr); + *v1 = V256_LoadU(src_ptr + sizeof(V256)); +} + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairU(void* dst, V256 v0, + V256 v1) { + char* dst_ptr = reinterpret_cast<char*>(dst); + V256_StoreU(dst_ptr, v0); + V256_StoreU(dst_ptr + sizeof(V256), v1); +} + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_StorePairNonTemporal(void* dst, + V256 v0, + V256 v1) { + char* dst_ptr = reinterpret_cast<char*>(dst); + V256_StoreNonTemporal(dst_ptr, v0); + V256_StoreNonTemporal(dst_ptr + sizeof(V256), v1); +} + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairU(void* dst, + const void* src) { + V256 v0, v1; + V256_LoadPairU(src, &v0, &v1); + V256_StorePairU(dst, v0, v1); +} + +ABSL_INTERNAL_ATTRIBUTE_AVX inline void V256_CopyPairNonTemporal( + void* dst, const void* src) { + V256 v0, v1; + V256_LoadPairU(src, &v0, &v1); + V256_StorePairNonTemporal(dst, v0, v1); +} + +#endif // defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) || + // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) + } // namespace crc_internal ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/crc/internal/crc_memcpy.h b/absl/crc/internal/crc_memcpy.h index a0fed65..72d7ce4 100644 --- a/absl/crc/internal/crc_memcpy.h +++ b/absl/crc/internal/crc_memcpy.h
@@ -16,10 +16,12 @@ #define ABSL_CRC_INTERNAL_CRC_MEMCPY_H_ #include <cstddef> +#include <cstdint> #include <memory> #include "absl/base/config.h" #include "absl/crc/crc32c.h" +#include "absl/crc/internal/crc.h" #include "absl/crc/internal/crc32_x86_arm_combined_simd.h" // Defined if the class AcceleratedCrcMemcpyEngine exists. @@ -50,11 +52,12 @@ public: static crc32c_t CrcAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - crc32c_t initial_crc = crc32c_t{0}, - bool non_temporal = false) { - static const ArchSpecificEngines engines = GetArchSpecificEngines(); - auto* engine = non_temporal ? engines.non_temporal : engines.temporal; - return engine->Compute(dst, src, length, initial_crc); + crc32c_t initial_crc = crc32c_t{0}) { + uint32_t crc = static_cast<uint32_t>(initial_crc); + crc ^= 0xffffffffU; + CRC::Crc32c()->ExtendAndCopy(&crc, dst, src, length); + crc ^= 0xffffffffU; + return crc32c_t{crc}; } // For testing only: get an architecture-specific engine for tests. @@ -110,9 +113,8 @@ // the generic fallback version. inline crc32c_t Crc32CAndCopy(void* __restrict dst, const void* __restrict src, std::size_t length, - crc32c_t initial_crc = crc32c_t{0}, - bool non_temporal = false) { - return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc, non_temporal); + crc32c_t initial_crc = crc32c_t{0}) { + return CrcMemcpy::CrcAndCopy(dst, src, length, initial_crc); } } // namespace crc_internal
diff --git a/absl/crc/internal/crc_x86_arm_combined.cc b/absl/crc/internal/crc_x86_arm_combined.cc index edffd36..42c100d 100644 --- a/absl/crc/internal/crc_x86_arm_combined.cc +++ b/absl/crc/internal/crc_x86_arm_combined.cc
@@ -16,6 +16,7 @@ #include <cstddef> #include <cstdint> +#include <cstring> #include <memory> #include <vector> @@ -200,7 +201,7 @@ // Instruction" // https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/crc-iscsi-polynomial-crc32-instruction-paper.pdf // We only need every 4th value, because we unroll loop by 4. -constexpr uint64_t kClmulConstants[] = { +alignas(16) constexpr uint64_t kClmulConstants[] = { 0x09e4addf8, 0x0ba4fc28e, 0x00d3b6092, 0x09e4addf8, 0x0ab7aff2a, 0x102f9b8a2, 0x0b9e02b86, 0x00d3b6092, 0x1bf2e8b8a, 0x18266e456, 0x0d270f1a2, 0x0ab7aff2a, 0x11eef4f8e, 0x083348832, 0x0dd7e3b0c, @@ -217,6 +218,7 @@ }; enum class PclmulStreamType { + NONE, PCLMUL, VPCLMUL, NEON_PCLMUL, @@ -228,6 +230,12 @@ class CRC32AcceleratedX86ARMCombinedMultipleStreamsBase : public CRC32AcceleratedX86ARMCombined { protected: + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE static void + Copy64Bytes(char* dst, const uint8_t* src) { + PrefetchToLocalCache(reinterpret_cast<const char*>(src) + kPrefetchHorizon); + V256_CopyPairU(dst, src); + } + // Update partialCRC with crc of 64 byte block. Calling FinalizePclmulStream // would produce a single crc checksum, but it is expensive. PCLMULQDQ has a // high latency, so we run 4 128-bit partial checksums that can be reduced to @@ -239,7 +247,7 @@ #if defined(ABSL_CRC_INTERNAL_HAVE_ARM_SIMD) template <bool kUseEor3 = false> ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul( - const uint8_t* p, V128* partialCRC) const { + V256 v0, V256 v1, V128* partialCRC) const { V128 loopMultiplicands = V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -252,10 +260,12 @@ V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); - V128 data1 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 0)); - V128 data2 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 1)); - V128 data3 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 2)); - V128 data4 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 3)); + const V128* data_ptr0 = reinterpret_cast<const V128*>(&v0); + const V128* data_ptr1 = reinterpret_cast<const V128*>(&v1); + V128 data1 = data_ptr0[0]; + V128 data2 = data_ptr0[1]; + V128 data3 = data_ptr1[0]; + V128 data4 = data_ptr1[1]; partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); @@ -308,15 +318,16 @@ return crc; } - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(const uint8_t*, + template <bool copy_data = false> + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul(V256, V256, V128*) const {} ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128*) const { return 0; } #else - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesPclmul( - const uint8_t* p, V128* partialCRC) const { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + Process64BytesPclmul(V256 v0, V256 v1, V128* partialCRC) const { V128 loopMultiplicands = V128_Load(reinterpret_cast<const V128*>(kFoldAcross512Bits)); @@ -329,10 +340,12 @@ V128 tmp2 = V128_PMulHi(partialCRC2, loopMultiplicands); V128 tmp3 = V128_PMulHi(partialCRC3, loopMultiplicands); V128 tmp4 = V128_PMulHi(partialCRC4, loopMultiplicands); - V128 data1 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 0)); - V128 data2 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 1)); - V128 data3 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 2)); - V128 data4 = V128_LoadU(reinterpret_cast<const V128*>(p + 16 * 3)); + const V128* data_ptr0 = reinterpret_cast<const V128*>(&v0); + const V128* data_ptr1 = reinterpret_cast<const V128*>(&v1); + V128 data1 = data_ptr0[0]; + V128 data2 = data_ptr0[1]; + V128 data3 = data_ptr1[0]; + V128 data4 = data_ptr1[1]; partialCRC1 = V128_PMulLow(partialCRC1, loopMultiplicands); partialCRC2 = V128_PMulLow(partialCRC2, loopMultiplicands); partialCRC3 = V128_PMulLow(partialCRC3, loopMultiplicands); @@ -353,7 +366,7 @@ // Reduce partialCRC produced by Process64BytesPclmul into a single value, // that represents crc checksum of all the processed bytes. - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128* partialCRC) const { V128 partialCRC1 = partialCRC[0]; V128 partialCRC2 = partialCRC[1]; @@ -392,11 +405,12 @@ } template <bool kUseEor3 = false> - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesNeonPclmul(const uint8_t*, - V128*) const {} + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + Process64BytesNeonPclmul(V256, V256, V128*) const {} template <bool kUseEor3 = false> - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeNeonPclmulStream(V128*) const { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + FinalizeNeonPclmulStream(V128*) const { return 0; } #endif @@ -452,7 +466,8 @@ crc[2] = crc2; } -#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ + (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ (!defined(_MSC_VER) || defined(__clang__)) // This is only used if we have vector version of PCLMULQDQ. // We don't have it on arm, and it isn't supported by default @@ -461,7 +476,7 @@ // with new and default flags or use inline asm. // The code below is the same as FinalizePclmulStream, but with // PCLMUL and XOR operating on 2 values in a vector at the same time. - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeVpclmulStream(V256* partialCRC) const { uint64_t crc = 0; uint64_t low64, high64; @@ -492,8 +507,9 @@ return crc; } - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul( - const uint8_t* p, V256* vpartialCRC, V256 loopMultiplicands) const { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + Process64BytesVpclmul(V256 v0, V256 v1, V256* vpartialCRC, + V256 loopMultiplicands) const { __asm__ volatile( "vpclmulqdq $0x11, %3, %0, %%ymm0 \n" "vpclmulqdq $0x11, %3, %1, %%ymm1 \n" @@ -501,23 +517,23 @@ "vpclmulqdq $0x00, %3, %1, %1 \n" "vpxor %%ymm0, %0, %0 \n" "vpxor %%ymm1, %1, %1 \n" - "vpxor (%2), %0, %0 \n" - "vpxor 32(%2), %1, %1 \n" + "vpxor %2, %0, %0 \n" + "vpxor %4, %1, %1 \n" : "+x"(vpartialCRC[0]), "+x"(vpartialCRC[1]) - : "r"(p), "x"(loopMultiplicands) + : "x"(v0), "x"(loopMultiplicands), "x"(v1) : "ymm0", "ymm1"); } #else template <typename T = V256> - ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul(const uint8_t*, T*, - T) const { + ABSL_ATTRIBUTE_ALWAYS_INLINE void Process64BytesVpclmul(T, T, T*, T) const { static_assert(sizeof(T) == 0, "Vector PCLMUL not supported"); } ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizeVpclmulStream(V256*) const { return 0; } -#endif // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && - // (!defined(_MSC_VER) || defined(__clang__)) +#endif // defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && (defined(__AVX__) || + // defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && (!defined(_MSC_VER) || + // defined(__clang__)) // Constants generated by './scripts/gen-crc-consts.py x86_pclmul // crc32_lsb_0x82f63b78' from the Linux kernel. @@ -551,33 +567,60 @@ PclmulStreamType pclmul_stream_type> class CRC32AcceleratedX86ARMCombinedMultipleStreams : public CRC32AcceleratedX86ARMCombinedMultipleStreamsBase { - ABSL_ATTRIBUTE_HOT + public: void Extend(uint32_t* crc, const void* bytes, const size_t length) const override { + Extend<false>(crc, bytes, length); + } + + void ExtendAndCopy(uint32_t* crc, void* __restrict dst, + const void* __restrict src, size_t length) const override { + Extend<true>(crc, src, length, dst); + StoreFence(); + } + + template <bool copy = false> + ABSL_ATTRIBUTE_HOT void Extend(uint32_t* crc, const void* bytes, + const size_t length, + void* __restrict dst = nullptr) const { + if constexpr (pclmul_stream_type != PclmulStreamType::NONE) { + if (length >= kMediumCutoff) { + ExtendWithPclmul<copy>(crc, bytes, length, dst); + return; + } + } + ExtendWithoutPclmul<copy>(crc, bytes, length, dst); + } + + template <bool copy = false> + ABSL_ATTRIBUTE_HOT void ExtendWithoutPclmul( + uint32_t* crc, const void* bytes, const size_t length, + void* __restrict dst = nullptr) const { static_assert(num_crc_streams >= 1 && num_crc_streams <= kMaxStreams, "Invalid number of crc streams"); static_assert(num_pclmul_streams >= 0 && num_pclmul_streams <= kMaxStreams, "Invalid number of pclmul streams"); const uint8_t* p = static_cast<const uint8_t*>(bytes); const uint8_t* e = p + length; + char* d = static_cast<char*>(dst); uint32_t l = *crc; uint64_t l64; + if constexpr (copy) { + std::memcpy(d, p, length); + } // For small blocks just run simple loop, because cost of combining multiple // streams is significant. if (num_crc_streams > 1 && (length < kSmallCutoff)) { // fallthrough; Use the same strategy as we do for processing the // remaining bytes after any other strategy. - } else if (length < kMediumCutoff) { - // For medium blocks we run 3 crc streams and combine them as described in - // Intel paper above. Running 4th stream doesn't help, because crc - // instruction has latency 3 and throughput 1. + } else { l64 = l; if (num_crc_streams > 1) { - uint64_t l641 = 0; - uint64_t l642 = 0; const size_t blockSize = 32; size_t bs = static_cast<size_t>(e - p) / kGroupsSmall / blockSize; + uint64_t l641 = 0; + uint64_t l642 = 0; const uint8_t* p1 = p + bs * blockSize; const uint8_t* p2 = p1 + bs * blockSize; @@ -599,7 +642,19 @@ ABSL_INTERNAL_STEP8BY3(l64, l641, l642, p, p1, p2); ABSL_INTERNAL_STEP8BY2(l64, l641, p, p1); - V128 magic = *(reinterpret_cast<const V128*>(kClmulConstants) + bs - 1); + // kClmulConstants stores precomputed constants for up to 32 blocks + // (bs <= 32). + constexpr size_t kMaxPrecomputedBlocks = std::size(kClmulConstants) / 2; + V128 magic; + if (bs <= kMaxPrecomputedBlocks) { + magic = V128_Load(reinterpret_cast<const V128*>(kClmulConstants) + + bs - 1); + } else { + uint32_t high = ComputeZeroConstant(32 * bs); + uint32_t low = MultiplyWithExtraX33(high, high); + alignas(16) uint64_t dynamic_magic[2] = {low, high}; + magic = V128_Load(reinterpret_cast<const V128*>(dynamic_magic)); + } V128 tmp = V128_From64WithZeroFill(l64); @@ -621,127 +676,6 @@ } } l = static_cast<uint32_t>(l64); - } else { - // There is a lot of data, we can ignore combine costs and run all - // requested streams (num_crc_streams + num_pclmul_streams), - // using prefetch. CRC and PCLMULQDQ use different cpu execution units, - // so on some cpus it makes sense to execute both of them for different - // streams. - - // Point x at first 8-byte aligned byte in string. - const uint8_t* x = RoundUp<8>(p); - // Process bytes until p is 8-byte aligned, if that isn't past the end. - while (p != x) { - ABSL_INTERNAL_STEP1(l, p); - } - - size_t bs = static_cast<size_t>(e - p) / - (num_crc_streams + num_pclmul_streams) / 64; - const uint8_t* stream_start = p; - const uint8_t* crc_streams[kMaxStreams]; - for (size_t i = 0; i < num_crc_streams; i++) { - crc_streams[i] = stream_start; - stream_start += bs * 64; - } - const uint8_t* pclmul_streams[kMaxStreams]; - for (size_t i = 0; i < num_pclmul_streams; i++) { - pclmul_streams[i] = stream_start; - stream_start += bs * 64; - } - - // Per stream crc sums. - uint64_t l64_crc[kMaxStreams] = {l}; - uint64_t l64_pclmul[kMaxStreams] = {0}; - - // Peel first iteration, because PCLMULQDQ stream, needs setup. - if (num_crc_streams == 1) { - l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); - crc_streams[0] += 16 * 4; - } else if (num_crc_streams == 2) { - Process64BytesCRC2Streams(crc_streams[0], crc_streams[1], l64_crc); - crc_streams[0] += 16 * 4; - crc_streams[1] += 16 * 4; - } else { - Process64BytesCRC3Streams(crc_streams[0], crc_streams[1], - crc_streams[2], l64_crc); - crc_streams[0] += 16 * 4; - crc_streams[1] += 16 * 4; - crc_streams[2] += 16 * 4; - } - - // Align to 32 bytes for vpclmul implementation. - alignas(32) V128 partialCRC[kMaxStreams][4]; - for (size_t i = 0; i < num_pclmul_streams; i++) { - InitPclmulStream(&pclmul_streams[i], partialCRC[i]); - } - - for (size_t i = 1; i < bs; i++) { - // Prefetch data for next iterations. - for (size_t j = 0; j < num_crc_streams; j++) { - PrefetchToLocalCache( - reinterpret_cast<const char*>(crc_streams[j] + kPrefetchHorizon)); - } - for (size_t j = 0; j < num_pclmul_streams; j++) { - PrefetchToLocalCache(reinterpret_cast<const char*>(pclmul_streams[j] + - kPrefetchHorizon)); - } - - // We process each stream in 64 byte blocks. This can be written as - // for (int i = 0; i < num_pclmul_streams; i++) { - // Process64BytesPclmul(pclmul_streams[i], partialCRC[i]); - // pclmul_streams[i] += 16 * 4; - // } - // for (int i = 0; i < num_crc_streams; i++) { - // l64_crc[i] = Process64BytesCRC(crc_streams[i], l64_crc[i]); - // crc_streams[i] += 16*4; - // } - // But unrolling and interleaving PCLMULQDQ and CRC blocks manually - // gives ~2% performance boost. - if (num_crc_streams == 1) { - l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); - crc_streams[0] += 16 * 4; - } else if (num_crc_streams == 2) { - Process64BytesCRC2Streams(crc_streams[0], crc_streams[1], l64_crc); - crc_streams[0] += 16 * 4; - crc_streams[1] += 16 * 4; - } else { - Process64BytesCRC3Streams(crc_streams[0], crc_streams[1], - crc_streams[2], l64_crc); - crc_streams[0] += 16 * 4; - crc_streams[1] += 16 * 4; - crc_streams[2] += 16 * 4; - } - for (size_t j = 0; j < num_pclmul_streams; j++) { - ProcessPclmulStream(&pclmul_streams[j], partialCRC[j]); - } - } - - // PCLMULQDQ based streams require special final step; - // CRC based don't. - for (size_t i = 0; i < num_pclmul_streams; i++) { - l64_pclmul[i] = FinalizePclmulStream(partialCRC[i]); - } - - // Combine all streams into single result. - static_assert(64 % (1 << kNumDroppedBits) == 0); - uint32_t magic = ComputeZeroConstant(bs * 64); - l64 = l64_crc[0]; - for (size_t i = 1; i < num_crc_streams; i++) { - l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); - l64 ^= l64_crc[i]; - } - for (size_t i = 0; i < num_pclmul_streams; i++) { - l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); - l64 ^= l64_pclmul[i]; - } - - // Update p. - if constexpr (num_pclmul_streams > 0) { - p = pclmul_streams[num_pclmul_streams - 1]; - } else { - p = crc_streams[num_crc_streams - 1]; - } - l = static_cast<uint32_t>(l64); } uint64_t remaining_bytes = static_cast<uint64_t>(e - p); @@ -767,50 +701,275 @@ *crc = l; } + template <bool copy = false> + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_HOT void ExtendWithPclmul( + uint32_t* crc, const void* bytes, const size_t length, + void* __restrict dst = nullptr) const { + static_assert(num_crc_streams >= 1 && num_crc_streams <= kMaxStreams, + "Invalid number of crc streams"); + static_assert(num_pclmul_streams >= 0 && num_pclmul_streams <= kMaxStreams, + "Invalid number of pclmul streams"); + const uint8_t* p = static_cast<const uint8_t*>(bytes); + const uint8_t* e = p + length; + char* d = static_cast<char*>(dst); + uint32_t l = *crc; + uint64_t l64; + + if constexpr (copy) { + // Align destination pointer for V256 non-temporal stores. + constexpr size_t kAlignment = 64; + uintptr_t dst_addr = reinterpret_cast<uintptr_t>(d); + size_t bytes_to_align = + (kAlignment - (dst_addr & (kAlignment - 1))) & (kAlignment - 1); + std::memcpy(d, p, bytes_to_align); + d += bytes_to_align; + while (bytes_to_align >= 8) { + ABSL_INTERNAL_STEP8(l, p); + bytes_to_align -= 8; + } + while (bytes_to_align > 0) { + ABSL_INTERNAL_STEP1(l, p); + bytes_to_align -= 1; + } + } else { + // Point x at first 8-byte aligned byte in string. + const uint8_t* x = RoundUp<8>(p); + // Process bytes until p is 8-byte aligned, if that isn't past the end. + while (p != x) { + ABSL_INTERNAL_STEP1(l, p); + } + } + + size_t bs = static_cast<size_t>(e - p) / + (num_crc_streams + num_pclmul_streams) / 64; + const uint8_t* stream_start = p; + const uint8_t* crc_streams[kMaxStreams]; + for (size_t i = 0; i < num_crc_streams; i++) { + crc_streams[i] = stream_start; + stream_start += bs * 64; + } + const uint8_t* pclmul_streams[kMaxStreams]; + for (size_t i = 0; i < num_pclmul_streams; i++) { + pclmul_streams[i] = stream_start; + stream_start += bs * 64; + } + + uint8_t* dst_crc_streams[kMaxStreams]; + uint8_t* dst_pclmul_streams[kMaxStreams]; + if constexpr (copy) { + uint8_t* dst_stream_start = reinterpret_cast<uint8_t*>(d); + for (size_t i = 0; i < num_crc_streams; i++) { + dst_crc_streams[i] = dst_stream_start; + dst_stream_start += bs * 64; + } + for (size_t i = 0; i < num_pclmul_streams; i++) { + dst_pclmul_streams[i] = dst_stream_start; + dst_stream_start += bs * 64; + } + } + + // Per stream crc sums. + uint64_t l64_crc[kMaxStreams] = {l}; + uint64_t l64_pclmul[kMaxStreams] = {0}; + + V256 pclmul_v0_0[kMaxStreams]; + V256 pclmul_v1_0[kMaxStreams]; + for (size_t j = 0; j < num_pclmul_streams; j++) { + V256_LoadPairU(pclmul_streams[j], &pclmul_v0_0[j], &pclmul_v1_0[j]); + } + + if constexpr (copy) { + for (size_t j = 0; j < num_crc_streams; j++) { + V256_CopyPairNonTemporal(dst_crc_streams[j], crc_streams[j]); + dst_crc_streams[j] += 64; + } + for (size_t j = 0; j < num_pclmul_streams; j++) { + V256_StorePairNonTemporal(dst_pclmul_streams[j], pclmul_v0_0[j], + pclmul_v1_0[j]); + dst_pclmul_streams[j] += 64; + } + } + + if (num_crc_streams == 1) { + l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); + crc_streams[0] += 16 * 4; + } else if (num_crc_streams == 2) { + Process64BytesCRC2Streams(crc_streams[0], crc_streams[1], l64_crc); + crc_streams[0] += 16 * 4; + crc_streams[1] += 16 * 4; + } else { + Process64BytesCRC3Streams(crc_streams[0], crc_streams[1], crc_streams[2], + l64_crc); + crc_streams[0] += 16 * 4; + crc_streams[1] += 16 * 4; + crc_streams[2] += 16 * 4; + } + + // Align to 32 bytes for vpclmul implementation. + alignas(32) V128 partialCRC[kMaxStreams][4]; + for (size_t i = 0; i < num_pclmul_streams; i++) { + InitPclmulStream(pclmul_v0_0[i], pclmul_v1_0[i], partialCRC[i]); + pclmul_streams[i] += 64; + } + + for (size_t i = 1; i < bs; i++) { + // Prefetch data for next iterations. + for (size_t j = 0; j < num_crc_streams; j++) { + PrefetchToLocalCache(crc_streams[j] + kPrefetchHorizon); + } + for (size_t j = 0; j < num_pclmul_streams; j++) { + PrefetchToLocalCache(pclmul_streams[j] + kPrefetchHorizon); + } + + for (size_t j = 0; j < num_pclmul_streams; j++) { + if constexpr (copy) { + ProcessPclmulStream<true>(pclmul_streams[j], dst_pclmul_streams[j], + partialCRC[j]); + dst_pclmul_streams[j] += 64; + } else { + ProcessPclmulStream<false>(pclmul_streams[j], nullptr, partialCRC[j]); + } + pclmul_streams[j] += 64; + } + + if (num_crc_streams == 1) { + l64_crc[0] = Process64BytesCRC(crc_streams[0], l64_crc[0]); + crc_streams[0] += 16 * 4; + } else if (num_crc_streams == 2) { + Process64BytesCRC2Streams(crc_streams[0], crc_streams[1], l64_crc); + crc_streams[0] += 16 * 4; + crc_streams[1] += 16 * 4; + } else { + Process64BytesCRC3Streams(crc_streams[0], crc_streams[1], + crc_streams[2], l64_crc); + crc_streams[0] += 16 * 4; + crc_streams[1] += 16 * 4; + crc_streams[2] += 16 * 4; + } + if constexpr (copy) { + for (size_t j = 0; j < num_crc_streams; j++) { + V256_CopyPairNonTemporal(dst_crc_streams[j], crc_streams[j] - 64); + dst_crc_streams[j] += 64; + } + } + } + + // PCLMULQDQ based streams require special final step; + // CRC based don't. + for (size_t i = 0; i < num_pclmul_streams; i++) { + l64_pclmul[i] = FinalizePclmulStream(partialCRC[i]); + } + + // Combine all streams into single result. + static_assert(64 % (1 << kNumDroppedBits) == 0); + uint32_t magic = ComputeZeroConstant(bs * 64); + l64 = l64_crc[0]; + for (size_t i = 1; i < num_crc_streams; i++) { + l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); + l64 ^= l64_crc[i]; + } + for (size_t i = 0; i < num_pclmul_streams; i++) { + l64 = MultiplyWithExtraX33(static_cast<uint32_t>(l64), magic); + l64 ^= l64_pclmul[i]; + } + + // Update p and d. + if constexpr (num_pclmul_streams > 0) { + p = pclmul_streams[num_pclmul_streams - 1]; + if constexpr (copy) { + d = reinterpret_cast<char*>(dst_pclmul_streams[num_pclmul_streams - 1]); + size_t remaining_to_copy = static_cast<size_t>(e - p); + std::memcpy(d, p, remaining_to_copy); + } + } else { + p = crc_streams[num_crc_streams - 1]; + if constexpr (copy) { + d = reinterpret_cast<char*>(dst_crc_streams[num_crc_streams - 1]); + size_t remaining_to_copy = static_cast<size_t>(e - p); + std::memcpy(d, p, remaining_to_copy); + } + } + + l = static_cast<uint32_t>(l64); + + uint64_t remaining_bytes = static_cast<uint64_t>(e - p); + // Process the remaining bytes. + while ((e - p) >= 16) { + ABSL_INTERNAL_STEP8(l, p); + ABSL_INTERNAL_STEP8(l, p); + } + + if (remaining_bytes & 8) { + ABSL_INTERNAL_STEP8(l, p); + } + if (remaining_bytes & 4) { + ABSL_INTERNAL_STEP4(l, p); + } + if (remaining_bytes & 2) { + ABSL_INTERNAL_STEP2(l, p); + } + if (remaining_bytes & 1) { + ABSL_INTERNAL_STEP1(l, p); + } + + *crc = l; + } + private: - ABSL_ATTRIBUTE_ALWAYS_INLINE void InitPclmulStream( - const uint8_t** pclmul_stream, V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + InitPclmulStream(V256 v0, V256 v1, V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { + return; + } else if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { V256* vpartialCRC = reinterpret_cast<V256*>(partialCRC); - vpartialCRC[0] = - V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 0)); - vpartialCRC[1] = - V256_LoadU(reinterpret_cast<const V256*>(*pclmul_stream + 32 * 1)); + vpartialCRC[0] = v0; + vpartialCRC[1] = v1; } else { - partialCRC[0] = - V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 0)); - partialCRC[1] = - V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 1)); - partialCRC[2] = - V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 2)); - partialCRC[3] = - V128_LoadU(reinterpret_cast<const V128*>(*pclmul_stream + 16 * 3)); + const V128* data_ptr0 = reinterpret_cast<const V128*>(&v0); + const V128* data_ptr1 = reinterpret_cast<const V128*>(&v1); + partialCRC[0] = data_ptr0[0]; + partialCRC[1] = data_ptr0[1]; + partialCRC[2] = data_ptr1[0]; + partialCRC[3] = data_ptr1[1]; } - *pclmul_stream += 16 * 4; } - ABSL_ATTRIBUTE_ALWAYS_INLINE void ProcessPclmulStream( - const uint8_t** pclmul_stream, V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { - V256 loopMultiplicands = - V256_Broadcast128(reinterpret_cast<const V128*>(kFoldAcross512Bits)); - Process64BytesVpclmul(*pclmul_stream, reinterpret_cast<V256*>(partialCRC), - loopMultiplicands); - } else if constexpr (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL || - pclmul_stream_type == - PclmulStreamType::NEON_PCLMUL_EOR3) { - constexpr bool kUseEor3 = - (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL_EOR3); - Process64BytesNeonPclmul<kUseEor3>(*pclmul_stream, partialCRC); + template <bool copy = false> + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE void + ProcessPclmulStream(const uint8_t* stream, uint8_t* dst_stream, + V128* partialCRC) const { + if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { + return; } else { - Process64BytesPclmul(*pclmul_stream, partialCRC); + const uint8_t* src_ptr = stream; + V256 v0, v1; + V256_LoadPairU(src_ptr, &v0, &v1); + if constexpr (copy) { + V256_StorePairNonTemporal(dst_stream, v0, v1); + } + if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + V256 loopMultiplicands = V256_Broadcast128( + reinterpret_cast<const V128*>(kFoldAcross512Bits)); + Process64BytesVpclmul(v0, v1, reinterpret_cast<V256*>(partialCRC), + loopMultiplicands); + } else if constexpr (pclmul_stream_type == + PclmulStreamType::NEON_PCLMUL || + pclmul_stream_type == + PclmulStreamType::NEON_PCLMUL_EOR3) { + constexpr bool kUseEor3 = + (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL_EOR3); + Process64BytesNeonPclmul<kUseEor3>(v0, v1, partialCRC); + } else { + Process64BytesPclmul(v0, v1, partialCRC); + } } - *pclmul_stream += 16 * 4; } - ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t + ABSL_INTERNAL_ATTRIBUTE_AVX ABSL_ATTRIBUTE_ALWAYS_INLINE uint64_t FinalizePclmulStream(V128* partialCRC) const { - if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { + if constexpr (pclmul_stream_type == PclmulStreamType::NONE) { + return 0; + } else if constexpr (pclmul_stream_type == PclmulStreamType::VPCLMUL) { return FinalizeVpclmulStream(reinterpret_cast<V256*>(partialCRC)); } else if constexpr (pclmul_stream_type == PclmulStreamType::NEON_PCLMUL || pclmul_stream_type == @@ -848,8 +1007,10 @@ 3, 1, PclmulStreamType::PCLMUL>(); case CpuType::kAmdMilan: case CpuType::kAmdGenoa: + case CpuType::kAmdSiena: case CpuType::kAmdTurin: -#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && defined(__AVX__) && \ +#if defined(ABSL_CRC_INTERNAL_HAVE_X86_SIMD) && \ + (defined(__AVX__) || defined(ABSL_INTERNAL_CAN_FORCE_AVX)) && \ (!defined(_MSC_VER) || defined(__clang__)) // We don't have vector pclmul on arm, but this still needs to // compile. @@ -875,13 +1036,14 @@ case CpuType::kIntelSandybridge: case CpuType::kIntelWestmere: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, PclmulStreamType::PCLMUL>(); + 3, 0, PclmulStreamType::NONE>(); case CpuType::kArmNeoverseN1: case CpuType::kArmNeoverseV1: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 1, 1, PclmulStreamType::NEON_PCLMUL>(); case CpuType::kArmNeoverseN2: case CpuType::kArmNeoverseN3: + case CpuType::kArmNeoverseN4: case CpuType::kNvidiaGrace: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 1, 1, PclmulStreamType::NEON_PCLMUL_EOR3>(); @@ -889,6 +1051,7 @@ return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 3, 2, PclmulStreamType::NEON_PCLMUL_EOR3>(); case CpuType::kArmNeoverseV2: + case CpuType::kArmNeoverseV3: return new CRC32AcceleratedX86ARMCombinedMultipleStreams< 1, 2, PclmulStreamType::NEON_PCLMUL_EOR3>(); #if defined(__aarch64__) @@ -905,7 +1068,7 @@ default: // Something else, play it safe and assume slow PCLMULQDQ. return new CRC32AcceleratedX86ARMCombinedMultipleStreams< - 3, 0, PclmulStreamType::PCLMUL>(); + 3, 0, PclmulStreamType::NONE>(); #endif } }
diff --git a/absl/debugging/internal/stacktrace_emscripten-inl.inc b/absl/debugging/internal/stacktrace_emscripten-inl.inc index 3c125e2..ce0ac22 100644 --- a/absl/debugging/internal/stacktrace_emscripten-inl.inc +++ b/absl/debugging/internal/stacktrace_emscripten-inl.inc
@@ -51,7 +51,7 @@ static std::atomic<bool> disable_stacktraces(true); // Disabled until healthy. // Waiting until static initializers run seems to be late enough. // This file is included into stacktrace.cc so this will only run once. -ABSL_ATTRIBUTE_UNUSED static int stacktraces_enabler = []() { +[[maybe_unused]] static int stacktraces_enabler = []() { disable_stacktraces.store(false, std::memory_order_relaxed); return 0; }();
diff --git a/absl/debugging/internal/stacktrace_generic-inl.inc b/absl/debugging/internal/stacktrace_generic-inl.inc index c94bf3e..36a6560 100644 --- a/absl/debugging/internal/stacktrace_generic-inl.inc +++ b/absl/debugging/internal/stacktrace_generic-inl.inc
@@ -45,7 +45,7 @@ static std::atomic<bool> disable_stacktraces(true); // Disabled until healthy. // Waiting until static initializers run seems to be late enough. // This file is included into stacktrace.cc so this will only run once. -ABSL_ATTRIBUTE_UNUSED static int stacktraces_enabler = []() { +[[maybe_unused]] static int stacktraces_enabler = []() { void* unused_stack[1]; // Force the first backtrace to happen early to get the one-time shared lib // loading (allocation) out of the way. After the first call it is much safer
diff --git a/absl/debugging/stacktrace.cc b/absl/debugging/stacktrace.cc index 9689337..6dc366c 100644 --- a/absl/debugging/stacktrace.cc +++ b/absl/debugging/stacktrace.cc
@@ -161,8 +161,14 @@ custom.store(w, std::memory_order_release); } -int DefaultStackUnwinder(void** pcs, int* sizes, int depth, int skip, - const void* uc, int* min_dropped_frames) { +// As of LLVM commit go/compilers/fc1afa6edce98a973ce2ce969c589da4f3aee975, +// CFI functions are inlinable in the ThinLTO backend. As a result, these +// wrappers were inlined into their callers, causing stack unwinding to skip an +// extra caller frame. Prevent inlining to ensure their stack frames are +// preserved when calculating `skip_count`. +ABSL_ATTRIBUTE_NOINLINE ABSL_ATTRIBUTE_NO_TAIL_CALL int DefaultStackUnwinder( + void** pcs, int* sizes, int depth, int skip, const void* uc, + int* min_dropped_frames) { skip++; // For this function decltype(&UnwindImpl<false, false>) f; if (sizes == nullptr) {
diff --git a/absl/debugging/symbolize_elf.inc b/absl/debugging/symbolize_elf.inc index 182d0fd..e5e171c 100644 --- a/absl/debugging/symbolize_elf.inc +++ b/absl/debugging/symbolize_elf.inc
@@ -774,6 +774,25 @@ return SYMBOL_NOT_FOUND; } + // In the ELF specification, sh_entsize is a generic section header field that + // holds the entry size in bytes for sections containing fixed-size entries. + // For symbol tables (SHT_SYMTAB and SHT_DYNSYM), the ELF specification + // mandates that each entry is an ElfW(Sym), so sh_entsize should always equal + // sizeof(ElfW(Sym)). + // + // However, because sh_entsize is read directly from the untrusted object + // file, a crafted or corrupt file can specify an unexpected value: + // 1. Setting sh_entsize to 0 would cause a division-by-zero (SIGFPE) in the + // num_symbols calculation below. + // 2. Setting sh_entsize to a value other than sizeof(ElfW(Sym)) would + // desynchronize our fixed-size ElfW(Sym) buffer reads from the per-entry + // stride in the file. + // Reject such malformed tables, mirroring the e_shentsize check we apply to + // section headers. + if (symtab->sh_entsize != sizeof(ElfW(Sym))) { + return SYMBOL_NOT_FOUND; + } + // Read multiple symbols at once to save read() calls. ElfW(Sym) *buf = reinterpret_cast<ElfW(Sym) *>(tmp_buf); const size_t buf_entries = tmp_buf_size / sizeof(buf[0]);
diff --git a/absl/debugging/symbolize_test.cc b/absl/debugging/symbolize_test.cc index 2cb1638..f3b15e1 100644 --- a/absl/debugging/symbolize_test.cc +++ b/absl/debugging/symbolize_test.cc
@@ -14,6 +14,7 @@ #include "absl/debugging/symbolize.h" +#include <cerrno> #include <cstddef> #include <cstdint> #include <cstring> @@ -27,6 +28,7 @@ #include "absl/base/attributes.h" #include "absl/base/casts.h" #include "absl/base/config.h" +#include "absl/base/internal/direct_mmap.h" #include "absl/base/internal/low_level_alloc.h" #include "absl/base/internal/per_thread_tls.h" #include "absl/base/optimization.h" @@ -46,6 +48,7 @@ #ifndef _WIN32 #include <fcntl.h> #include <sys/mman.h> +#include <unistd.h> #endif #if defined(MAP_ANON) && !defined(MAP_ANONYMOUS) @@ -440,6 +443,120 @@ close(fd); } + +#if defined(ABSL_INTERNAL_HAVE_ELF_SYMBOLIZE) +// Builds a minimal ELF image whose SHT_SYMTAB section header carries the given +// sh_entsize. Everything else is just enough to reach FindSymbol(): a single +// executable PT_LOAD segment (so the object is initialized) and a symbol table +// whose sh_link points at the null section header. +static std::string MakeElfWithSymtabEntSize(uint64_t sym_entsize) { + ElfW(Ehdr) ehdr; + memset(&ehdr, 0, sizeof(ehdr)); + memcpy(ehdr.e_ident, ELFMAG, SELFMAG); + ehdr.e_ident[EI_CLASS] = (sizeof(void*) == 8) ? ELFCLASS64 : ELFCLASS32; + ehdr.e_ident[EI_DATA] = ELFDATA2LSB; + ehdr.e_ident[EI_VERSION] = EV_CURRENT; + ehdr.e_type = ET_DYN; + ehdr.e_version = EV_CURRENT; + ehdr.e_phoff = sizeof(ElfW(Ehdr)); + ehdr.e_phentsize = sizeof(ElfW(Phdr)); + ehdr.e_phnum = 1; + ehdr.e_shoff = sizeof(ElfW(Ehdr)) + sizeof(ElfW(Phdr)); + ehdr.e_shentsize = sizeof(ElfW(Shdr)); + ehdr.e_shnum = 2; + ehdr.e_shstrndx = 0; + + ElfW(Phdr) phdr; + memset(&phdr, 0, sizeof(phdr)); + phdr.p_type = PT_LOAD; + phdr.p_flags = PF_R | PF_X; + phdr.p_filesz = 0x1000; + phdr.p_memsz = 0x1000; + phdr.p_align = 0x1000; + + // Section 0 is the mandatory null header, which also serves as the string + // table referenced by sh_link below (its contents are irrelevant here). + ElfW(Shdr) null_shdr; + memset(&null_shdr, 0, sizeof(null_shdr)); + + ElfW(Shdr) symtab; + memset(&symtab, 0, sizeof(symtab)); + symtab.sh_type = SHT_SYMTAB; + symtab.sh_link = 0; + symtab.sh_size = sizeof(ElfW(Sym)); + symtab.sh_entsize = sym_entsize; + symtab.sh_offset = ehdr.e_shoff + 2 * sizeof(ElfW(Shdr)); + + std::string image; + image.append(reinterpret_cast<const char*>(&ehdr), sizeof(ehdr)); + image.append(reinterpret_cast<const char*>(&phdr), sizeof(phdr)); + image.append(reinterpret_cast<const char*>(&null_shdr), sizeof(null_shdr)); + image.append(reinterpret_cast<const char*>(&symtab), sizeof(symtab)); + // Pad so the symtab sh_offset lands inside the file. + image.resize(image.size() + sizeof(ElfW(Sym)), '\0'); + return image; +} + +// Helper class that creates a temporary file on disk with the given content +// and unlinks it upon destruction. +class TempFile { + public: + explicit TempFile(absl::string_view content) { + std::string dir = testing::TempDir(); + if (dir.empty() || dir.back() != '/') { + dir.push_back('/'); + } + path_ = dir + "absl_bad_symtab_XXXXXX"; + int fd = mkstemp(path_.data()); + CHECK_NE(fd, -1); + CHECK_EQ(write(fd, content.data(), content.size()), + static_cast<ssize_t>(content.size())); + close(fd); + } + ~TempFile() { unlink(path_.c_str()); } + + TempFile(const TempFile&) = delete; + TempFile& operator=(const TempFile&) = delete; + + const char* path() const { return path_.c_str(); } + + private: + std::string path_; +}; + +// A crafted object file can set the symbol table's sh_entsize to zero, which is +// used verbatim as the divisor for the symbol count in FindSymbol(). Before +// the fix this divided by zero (SIGFPE) while symbolizing; now the malformed +// table is skipped and the address simply fails to resolve. +TEST(Symbolize, InvalidSymtabEntSizeDoesNotCrash) { + TempFile file(MakeElfWithSymtabEntSize(/*sym_entsize=*/0)); + + // Map an executable page to provide a memory address to symbolize. + const size_t page_size = static_cast<size_t>(sysconf(_SC_PAGESIZE)); + void* region = + absl::base_internal::DirectMmap(nullptr, page_size, PROT_READ | PROT_EXEC, + MAP_ANONYMOUS | MAP_PRIVATE, -1, 0); + if (region == MAP_FAILED) { + GTEST_SKIP() << "Unable to map an executable page: errno=" << errno; + } + absl::Cleanup unmap = [&] { + absl::base_internal::DirectMunmap(region, page_size); + }; + + // absl::Symbolize() needs this file mapping hint to associate addresses + // within the mapped region with the ELF file on disk and attempt + // symbolization. + ASSERT_TRUE(absl::debugging_internal::RegisterFileMappingHint( + region, static_cast<char*>(region) + page_size, 0, file.path())); + + // Output buffer for absl::Symbolize(). 512 bytes is arbitrarily chosen to + // receive any demangled symbol name for the purposes of this test. + char symbol_buf[512]; + // The point of the test is that this returns instead of crashing with SIGFPE. + EXPECT_FALSE(absl::Symbolize(static_cast<char*>(region) + 8, symbol_buf, + sizeof(symbol_buf))); +} +#endif // ABSL_INTERNAL_HAVE_ELF_SYMBOLIZE #endif // !ABSL_INTERNAL_HAVE_DARWIN_SYMBOLIZE && // !ABSL_INTERNAL_HAVE_EMSCRIPTEN_SYMBOLIZE
diff --git a/absl/hash/BUILD.bazel b/absl/hash/BUILD.bazel index 5fae4e2..fe76a1d 100644 --- a/absl/hash/BUILD.bazel +++ b/absl/hash/BUILD.bazel
@@ -96,9 +96,8 @@ "//absl/base:config", "//absl/container:flat_hash_map", "//absl/container:flat_hash_set", - "//absl/memory", - "//absl/meta:type_traits", "//absl/numeric:bits", + "//absl/strings", "//absl/strings:cord", "//absl/strings:cord_test_helpers", "//absl/strings:string_view",
diff --git a/absl/hash/CMakeLists.txt b/absl/hash/CMakeLists.txt index 0c7e7f4..2ced4b1 100644 --- a/absl/hash/CMakeLists.txt +++ b/absl/hash/CMakeLists.txt
@@ -74,10 +74,9 @@ absl::flat_hash_set absl::hash absl::hash_testing - absl::memory - absl::meta absl::spy_hash_state absl::string_view + absl::strings GTest::gmock_main )
diff --git a/absl/hash/hash_test.cc b/absl/hash/hash_test.cc index 2afa986..0e98bbf 100644 --- a/absl/hash/hash_test.cc +++ b/absl/hash/hash_test.cc
@@ -25,6 +25,7 @@ #include <initializer_list> #include <ios> #include <limits> +#include <map> #include <memory> #include <optional> #include <ostream> @@ -50,6 +51,7 @@ #include "absl/numeric/bits.h" #include "absl/strings/cord.h" #include "absl/strings/cord_test_helpers.h" +#include "absl/strings/escaping.h" #include "absl/strings/string_view.h" #ifdef ABSL_INTERNAL_STD_FILESYSTEM_PATH_HASH_AVAILABLE @@ -1267,23 +1269,27 @@ #if defined(__ANDROID__) && defined(__arm__) GTEST_SKIP() << "Fails on 32-bit Android due to layout changes."; #endif - std::string s1 = "00"; - std::string s2 = "000"; constexpr char kMinChar = 0; - constexpr char kMaxChar = 32; - for (s1[0] = kMinChar; s1[0] < kMaxChar; ++s1[0]) { - for (s1[1] = kMinChar; s1[1] < kMaxChar; ++s1[1]) { - for (s2[0] = kMinChar; s2[0] < kMaxChar; ++s2[0]) { - for (s2[1] = kMinChar; s2[1] < kMaxChar; ++s2[1]) { - for (s2[2] = kMinChar; s2[2] < kMaxChar; ++s2[2]) { - ASSERT_NE(absl::HashOf(s1), absl::HashOf(s2)) - << "s1[0]: " << static_cast<int>(s1[0]) - << "; s1[1]: " << static_cast<int>(s1[1]) - << "; s2[0]: " << static_cast<int>(s2[0]) - << "; s2[1]: " << static_cast<int>(s2[1]) - << "; s2[2]: " << static_cast<int>(s2[2]); - } - } + constexpr char kMaxChar = sizeof(size_t) * 4; + // We use standard map to avoid the second dependency on the same hash. + std::map<size_t, std::string> hashes; + { + std::string s1 = "00"; + for (s1[0] = kMinChar; s1[0] < kMaxChar; ++s1[0]) { + for (s1[1] = kMinChar; s1[1] < kMaxChar; ++s1[1]) { + auto [it, inserted] = hashes.insert({absl::HashOf(s1), s1}); + ASSERT_TRUE(inserted) << "Collision found for " << absl::CEscape(s1) + << " and " << absl::CEscape(it->second); + } + } + } + std::string s2 = "000"; + for (s2[0] = kMinChar; s2[0] < kMaxChar; ++s2[0]) { + for (s2[1] = kMinChar; s2[1] < kMaxChar; ++s2[1]) { + for (s2[2] = kMinChar; s2[2] < kMaxChar; ++s2[2]) { + auto [it, inserted] = hashes.insert({absl::HashOf(s2), s2}); + ASSERT_TRUE(inserted) << "Collision found for " << absl::CEscape(s2) + << " and " << absl::CEscape(it->second); } } }
diff --git a/absl/log/check_test_impl.inc b/absl/log/check_test_impl.inc index c78bbd4..9ec3506 100644 --- a/absl/log/check_test_impl.inc +++ b/absl/log/check_test_impl.inc
@@ -48,7 +48,7 @@ using ::testing::HasSubstr; using ::testing::Not; -auto* test_env ABSL_ATTRIBUTE_UNUSED = ::testing::AddGlobalTestEnvironment( +auto* test_env [[maybe_unused]] = ::testing::AddGlobalTestEnvironment( new absl::log_internal::LogTestEnvironment); #if GTEST_HAS_DEATH_TEST
diff --git a/absl/random/log_uniform_int_distribution.h b/absl/random/log_uniform_int_distribution.h index cbd5e0c..99abe05 100644 --- a/absl/random/log_uniform_int_distribution.h +++ b/absl/random/log_uniform_int_distribution.h
@@ -16,13 +16,14 @@ #define ABSL_RANDOM_LOG_UNIFORM_INT_DISTRIBUTION_H_ #include <algorithm> -#include <cassert> #include <cmath> +#include <ios> #include <istream> #include <limits> #include <ostream> #include "absl/base/config.h" +#include "absl/base/macros.h" #include "absl/random/internal/iostream_state_saver.h" #include "absl/random/internal/traits.h" #include "absl/random/uniform_int_distribution.h" @@ -60,15 +61,18 @@ range_(static_cast<unsigned_type>(max_) - static_cast<unsigned_type>(min_)), log_range_(0) { - assert(max_ >= min_); - assert(base_ > 1); + ABSL_HARDENING_ASSERT(max_ >= min_); + ABSL_HARDENING_ASSERT(base_ > 1); if (base_ == 2) { // Determine where the first set bit is on range(), giving a log2(range) // value which can be used to construct bounds. log_range_ = (std::min)(random_internal::BitWidth(range()), std::numeric_limits<unsigned_type>::digits); - } else { + } else if (base_ > 2) { + // An out-of-contract base_ (<= 1) skips this branch entirely so that + // no floating-point undefined behavior is reached. + // // NOTE: Computing the logN(x) introduces error from 2 sources: // 1. Conversion of int to double loses precision for values >= // 2^53, which may cause some log() computations to operate on @@ -240,9 +244,16 @@ auto saver = random_internal::make_istream_state_saver(is); is >> min >> max >> base; if (!is.fail()) { - x.param(param_type(static_cast<result_type>(min), - static_cast<result_type>(max), - static_cast<result_type>(base))); + const result_type min_val = static_cast<result_type>(min); + const result_type max_val = static_cast<result_type>(max); + const result_type base_val = static_cast<result_type>(base); + if (max_val < min_val || base_val <= 1) { + // The input violates the param_type preconditions; signal failure by + // setting the failbit instead of constructing an invalid param_type. + is.setstate(is.rdstate() | std::ios_base::failbit); + } else { + x.param(param_type(min_val, max_val, base_val)); + } } return is; }
diff --git a/absl/random/log_uniform_int_distribution_test.cc b/absl/random/log_uniform_int_distribution_test.cc index 591b5b3..4404111 100644 --- a/absl/random/log_uniform_int_distribution_test.cc +++ b/absl/random/log_uniform_int_distribution_test.cc
@@ -116,6 +116,26 @@ } } +// operator>> must reject input that violates the param_type preconditions +// (max >= min and base > 1) by setting failbit and leaving the distribution +// unchanged, rather than constructing an out-of-contract param_type. +TYPED_TEST(LogUniformIntDistributionTypeTest, DeserializeRejectsInvalidParams) { + for (const char* input : { + "0 100 1", // base == 1 + "0 100 0", // base == 0 + "100 0 2", // max < min + }) { + absl::log_uniform_int_distribution<TypeParam> dist(3, 6, 17); + const auto before = dist.param(); + + std::istringstream is(input); + is >> dist; + + EXPECT_TRUE(is.fail()) << input; + EXPECT_EQ(dist.param(), before) << input; + } +} + using log_uniform_i32 = absl::log_uniform_int_distribution<int32_t>; class LogUniformIntChiSquaredTest
diff --git a/absl/status/internal/status_internal.h b/absl/status/internal/status_internal.h index 1cc87ab..3bd7b1b 100644 --- a/absl/status/internal/status_internal.h +++ b/absl/status/internal/status_internal.h
@@ -37,8 +37,6 @@ #include "absl/types/source_location.h" #include "absl/types/span.h" -#ifndef SWIG -// Disabled for SWIG as it doesn't parse attributes correctly. namespace absl { ABSL_NAMESPACE_BEGIN // Returned Status objects may not be ignored. Codesearch doesn't handle ifdefs @@ -54,13 +52,6 @@ Status; #endif -ABSL_NAMESPACE_END -} // namespace absl -#endif // !SWIG - -namespace absl { -ABSL_NAMESPACE_BEGIN - enum class StatusCode : int; enum class StatusToStringMode : int; @@ -69,12 +60,9 @@ class StatusOr; namespace status_internal { -#ifndef SWIG class StatusPrivateAccessor; class StatusPrivateAccessorForStatusBuilder; -#endif // !SWIG -#ifndef SWIG // Container for status payloads. struct Payload { std::string type_url; @@ -178,7 +166,6 @@ const absl::Status* absl_nonnull status, const char* absl_nonnull prefix); } // namespace status_internal -#endif // SWIG ABSL_NAMESPACE_END } // namespace absl
diff --git a/absl/status/status.cc b/absl/status/status.cc index e9b0eab..dc7d622 100644 --- a/absl/status/status.cc +++ b/absl/status/status.cc
@@ -424,7 +424,9 @@ case ENETRESET: // Connection aborted by network case ENETUNREACH: // Network unreachable case ENOLCK: // No locks available +#ifdef ENOLINK case ENOLINK: // Link has been severed +#endif #ifdef ENONET case ENONET: // Machine is not on the network #endif
diff --git a/absl/status/statusor.h b/absl/status/statusor.h index e56656a..e54c61b 100644 --- a/absl/status/statusor.h +++ b/absl/status/statusor.h
@@ -724,7 +724,7 @@ std::enable_if_t<absl::HasOstreamOperator<T>::value, int> = 0> std::ostream& operator<<(std::ostream& os, const StatusOr<T>& status_or) { if (status_or.ok()) { - os << status_or.value(); + os << *status_or; } else { os << internal_statusor::StringifyRandom::OpenBrackets() << status_or.status() @@ -741,7 +741,7 @@ std::enable_if_t<absl::HasAbslStringify<T>::value, int> = 0> void AbslStringify(Sink& sink, const StatusOr<T>& status_or) { if (status_or.ok()) { - absl::Format(&sink, "%v", status_or.value()); + absl::Format(&sink, "%v", *status_or); } else { absl::Format(&sink, "%s%v%s", internal_statusor::StringifyRandom::OpenBrackets(),
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel index 4505932..19692b3 100644 --- a/absl/strings/BUILD.bazel +++ b/absl/strings/BUILD.bazel
@@ -104,6 +104,7 @@ ":internal", ":resize_and_overwrite", ":string_view", + "//absl/algorithm:container", "//absl/base", "//absl/base:config", "//absl/base:core_headers",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt index 2d301d8..23a32c9 100644 --- a/absl/strings/CMakeLists.txt +++ b/absl/strings/CMakeLists.txt
@@ -70,6 +70,7 @@ COPTS ${ABSL_DEFAULT_COPTS} DEPS + absl::algorithm_container absl::base absl::bits absl::charset
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc index 6d9dd10..1b60404 100644 --- a/absl/strings/cord.cc +++ b/absl/strings/cord.cc
@@ -558,6 +558,7 @@ if (src.size() <= kMaxBytesToCopy) { Append(absl::string_view(src)); } else { + contents_.MaybeRemoveEmptyCrcNode(); CordRep* rep = CordRepFromString(std::forward<T>(src)); contents_.AppendTree(rep, CordzUpdateTracker::kAppendString); } @@ -637,6 +638,7 @@ if (src.size() <= kMaxBytesToCopy) { Prepend(absl::string_view(src)); } else { + contents_.MaybeRemoveEmptyCrcNode(); CordRep* rep = CordRepFromString(std::forward<T>(src)); contents_.PrependTree(rep, CordzUpdateTracker::kPrependString); }
diff --git a/absl/strings/cord_test.cc b/absl/strings/cord_test.cc index 1ff172e..1ae1f63 100644 --- a/absl/strings/cord_test.cc +++ b/absl/strings/cord_test.cc
@@ -3031,6 +3031,11 @@ [](absl::Cord& c) { c.RemoveSuffix(10); } }, { + "append large string", + [](absl::Cord& c) { c.Append(std::string(1000, 'x')); }, + [](absl::Cord& c) { c.RemoveSuffix(1000); } + }, + { "append cord", [](absl::Cord& c) { c.Append(absl::MakeFragmentedCord({"12345", "67890"})); @@ -3076,6 +3081,11 @@ [](absl::Cord& c) { c.RemovePrefix(10); } }, { + "prepend large string", + [](absl::Cord& c) { c.Prepend(std::string(1000, 'x')); }, + [](absl::Cord& c) { c.RemovePrefix(1000); } + }, + { "prepend cord", [](absl::Cord& c) { c.Prepend(absl::MakeFragmentedCord({"98765", "43210"}));
diff --git a/absl/strings/internal/str_join_internal.h b/absl/strings/internal/str_join_internal.h index 7698cfa..8f9c11a 100644 --- a/absl/strings/internal/str_join_internal.h +++ b/absl/strings/internal/str_join_internal.h
@@ -42,6 +42,7 @@ #include <type_traits> #include <utility> +#include "absl/algorithm/container.h" #include "absl/base/config.h" #include "absl/base/internal/iterator_traits.h" #include "absl/base/internal/raw_logging.h" @@ -231,7 +232,7 @@ template <typename Iterator, typename = std::enable_if_t< base_internal::IsAtLeastForwardIterator<Iterator>::value>> -std::string JoinAlgorithm(Iterator start, Iterator end, absl::string_view s, +std::string JoinAlgorithm(Iterator start, Iterator end, absl::string_view sep, NoFormatter) { std::string result; if (start != end) { @@ -241,7 +242,7 @@ // in memory strings to overflow a uint64_t. uint64_t result_size = start_value.size(); for (Iterator it = start; ++it != end;) { - result_size += s.size(); + result_size += sep.size(); result_size += (*it).size(); } @@ -252,17 +253,14 @@ StringResizeAndOverwrite( result, static_cast<size_t>(result_size), - [&start, &end, &start_value, s](char* result_buf, - size_t result_buf_size) { + [&start, &end, &start_value, sep](char* result_buf, + size_t result_buf_size) { // Joins strings - memcpy(result_buf, start_value.data(), start_value.size()); - result_buf += start_value.size(); + result_buf = absl::c_copy(start_value, result_buf); for (Iterator it = start; ++it != end;) { - memcpy(result_buf, s.data(), s.size()); - result_buf += s.size(); + result_buf = absl::c_copy(sep, result_buf); auto&& value = *it; - memcpy(result_buf, value.data(), value.size()); - result_buf += value.size(); + result_buf = absl::c_copy(value, result_buf); } return result_buf_size; });
diff --git a/absl/strings/str_join_test.cc b/absl/strings/str_join_test.cc index 6657248..6e7fe61 100644 --- a/absl/strings/str_join_test.cc +++ b/absl/strings/str_join_test.cc
@@ -137,6 +137,16 @@ // { + // Test the code path where default-constructed string_views are + // used. Hopefully a sanitizer will flag it if nullptr gets passed to + // memcpy. + std::vector<absl::string_view> v = {absl::string_view(), + absl::string_view()}; + EXPECT_EQ(absl::StrJoin(v, absl::string_view()), ""); + EXPECT_EQ(absl::StrJoin(v, ":"), ":"); + } + + { // Empty range yields an empty string. std::vector<std::string> v; EXPECT_EQ("", absl::StrJoin(v, "-"));
diff --git a/absl/time/duration.cc b/absl/time/duration.cc index 487ccdd..961fc61 100644 --- a/absl/time/duration.cc +++ b/absl/time/duration.cc
@@ -897,7 +897,16 @@ return false; } if (int_part != 0) dur += sign * int_part * unit; - if (frac_part != 0) dur += sign * frac_part * unit / frac_scale; + if (frac_part != 0) { + // Scale the unit's tick count directly rather than forming + // frac_part * unit as a Duration first: for a long fraction of a large + // unit (e.g. "0.3000000000000000h") that product saturates to infinity + // before the division by frac_scale can bring it back into range. + const uint128 ticks = MakeU128Ticks(unit) * + static_cast<uint64_t>(frac_part) / + static_cast<uint64_t>(frac_scale); + dur += MakeDurationFromU128(ticks, sign < 0); + } } *d = dur; return true;
diff --git a/absl/time/duration_test.cc b/absl/time/duration_test.cc index 8fffa95..6645c53 100644 --- a/absl/time/duration_test.cc +++ b/absl/time/duration_test.cc
@@ -1831,6 +1831,17 @@ EXPECT_TRUE(absl::ParseDuration("0.429496729501234567890123456789s", &d)); EXPECT_EQ(absl::Nanoseconds(429496729) + absl::Nanoseconds(1) / 2, d); + // Huge fractional counts of a large unit. The scaled intermediate must not + // saturate to infinity before it is divided back down. + EXPECT_TRUE(absl::ParseDuration("0.3000000000000000h", &d)); + EXPECT_EQ(absl::Minutes(18), d); + EXPECT_TRUE(absl::ParseDuration("0.200000000000000000m", &d)); + EXPECT_EQ(absl::Seconds(12), d); + EXPECT_TRUE(absl::ParseDuration("0.999999999999999999h", &d)); + EXPECT_EQ(absl::Hours(1) - absl::Nanoseconds(1) / 4, d); + EXPECT_TRUE(absl::ParseDuration("-0.999999999999999999h", &d)); + EXPECT_EQ(-(absl::Hours(1) - absl::Nanoseconds(1) / 4), d); + // Negative durations. EXPECT_TRUE(absl::ParseDuration("-1s", &d)); EXPECT_EQ(absl::Seconds(-1), d);
diff --git a/absl/time/internal/cctz/include/cctz/time_zone.h b/absl/time/internal/cctz/include/cctz/time_zone.h index 5b232f5..7acce2f 100644 --- a/absl/time/internal/cctz/include/cctz/time_zone.h +++ b/absl/time/internal/cctz/include/cctz/time_zone.h
@@ -25,6 +25,7 @@ #include <limits> #include <ratio> // NOLINT: We use std::ratio in this header #include <string> +#include <type_traits> #include <utility> #include "absl/base/config.h" @@ -271,15 +272,20 @@ bool parse(const std::string&, const std::string&, const time_zone&, time_point<seconds>*, femtoseconds*, std::string* err = nullptr); template <typename Rep, std::intmax_t Denom> -bool join_seconds( +typename std::enable_if<std::is_integral<Rep>::value, bool>::type join_seconds( const time_point<seconds>& sec, const femtoseconds& fs, time_point<std::chrono::duration<Rep, std::ratio<1, Denom>>>* tpp); +template <typename Rep, std::intmax_t Num, std::intmax_t Denom> +typename std::enable_if<std::is_floating_point<Rep>::value, bool>::type +join_seconds( + const time_point<seconds>& sec, const femtoseconds& fs, + time_point<std::chrono::duration<Rep, std::ratio<Num, Denom>>>* tpp); template <typename Rep, std::intmax_t Num> -bool join_seconds( +typename std::enable_if<std::is_integral<Rep>::value, bool>::type join_seconds( const time_point<seconds>& sec, const femtoseconds& fs, time_point<std::chrono::duration<Rep, std::ratio<Num, 1>>>* tpp); template <typename Rep> -bool join_seconds( +typename std::enable_if<std::is_integral<Rep>::value, bool>::type join_seconds( const time_point<seconds>& sec, const femtoseconds& fs, time_point<std::chrono::duration<Rep, std::ratio<1, 1>>>* tpp); bool join_seconds(const time_point<seconds>& sec, const femtoseconds&, @@ -369,13 +375,19 @@ // if (cctz::parse("%Y-%m-%d", "2015-10-09", tz, &tp)) { // ... // } -template <typename D> -inline bool parse(const std::string& fmt, const std::string& input, - const time_zone& tz, time_point<D>* tpp) { +template <typename Rep, typename Period> +bool parse(const std::string& fmt, const std::string& input, + const time_zone& tz, + time_point<std::chrono::duration<Rep, Period>>* tpp) { time_point<seconds> sec; detail::femtoseconds fs; - return detail::parse(fmt, input, tz, &sec, &fs) && - detail::join_seconds(sec, fs, tpp); + if (!detail::parse(fmt, input, tz, &sec, &fs)) return false; + + time_point<std::chrono::duration<Rep, typename Period::type>> tp; + if (!detail::join_seconds(sec, fs, &tp)) return false; + + *tpp = tp; + return true; } namespace detail { @@ -389,9 +401,15 @@ std::pair<time_point<seconds>, D> split_seconds(const time_point<D>& tp) { auto sec = std::chrono::time_point_cast<seconds>(tp); auto sub = tp - sec; - if (sub.count() < 0) { - sec -= seconds(1); - sub += seconds(1); + // time_point_cast truncates towards zero, so for negative tp with fractional + // seconds (e.g., -1.5s), sec is truncated (-1s) and sub is negative (-0.5s). + // Adjust sec and sub so that sec is floored (-2s) and sub is in [0, 1s) + // (+0.5s). This adjustment is done after computing sub to avoid overflow + // when tp is near time_point<D>::min(), where floored sec cannot be converted + // to D. + if (sub < D::zero()) { + sec -= seconds{1}; + sub += seconds{1}; } return {sec, std::chrono::duration_cast<D>(sub)}; } @@ -405,18 +423,58 @@ // Floors to the resolution of time_point<D>. Returns false if time_point<D> // is not of sufficient range. template <typename Rep, std::intmax_t Denom> -bool join_seconds( +typename std::enable_if<std::is_integral<Rep>::value, bool>::type join_seconds( const time_point<seconds>& sec, const femtoseconds& fs, time_point<std::chrono::duration<Rep, std::ratio<1, Denom>>>* tpp) { using D = std::chrono::duration<Rep, std::ratio<1, Denom>>; - // TODO(#199): Return false if result unrepresentable as a time_point<D>. + using D_check = std::chrono::duration<std::intmax_t, std::ratio<1, Denom>>; + const std::intmax_t count = sec.time_since_epoch().count(); + const auto sub = + std::chrono::duration_cast<D_check>(fs).count(); // [0, Denom) + + // Check for overflow. + if (sub > (std::numeric_limits<Rep>::max)()) { + // If subseconds alone exceed the max representable value, any non-negative + // seconds count will cause overflow. Negative seconds might bring it back + // into range, which is handled by the underflow check below. + if (count >= 0) return false; + } else { + // Equivalent to: count * Denom + sub > max, but safe from overflow. + if (count > ((std::numeric_limits<Rep>::max)() - sub) / Denom) return false; + } + + // Check for underflow. + // Equivalent to: count * Denom + sub < lowest, but safe from underflow. + // We cannot use "lowest - sub" directly as it would underflow. + const auto min_div = (std::numeric_limits<Rep>::lowest)() / Denom; + if (count < min_div) { + // If count is less than min_div - 1, it's definitely underflow. + if (count < min_div - 1) return false; + // If count is exactly min_div - 1, we must check if subseconds are + // sufficient to bring the total value back above lowest. + const auto min_mod = (std::numeric_limits<Rep>::lowest)() % Denom; + if (sub < Denom + min_mod) return false; + *tpp = + time_point<D>() + D{static_cast<Rep>(min_div * Denom + (sub - Denom))}; + return true; + } + *tpp = time_point<D>() + D{static_cast<Rep>(count * Denom + sub)}; + return true; +} + +template <typename Rep, std::intmax_t Num, std::intmax_t Denom> +typename std::enable_if<std::is_floating_point<Rep>::value, bool>::type +join_seconds( + const time_point<seconds>& sec, const femtoseconds& fs, + time_point<std::chrono::duration<Rep, std::ratio<Num, Denom>>>* tpp) { + using D = std::chrono::duration<Rep, std::ratio<Num, Denom>>; *tpp = std::chrono::time_point_cast<D>(sec); *tpp += std::chrono::duration_cast<D>(fs); return true; } template <typename Rep, std::intmax_t Num> -bool join_seconds( +typename std::enable_if<std::is_integral<Rep>::value, bool>::type join_seconds( const time_point<seconds>& sec, const femtoseconds&, time_point<std::chrono::duration<Rep, std::ratio<Num, 1>>>* tpp) { using D = std::chrono::duration<Rep, std::ratio<Num, 1>>; @@ -428,19 +486,19 @@ count -= 1; } if (count > (std::numeric_limits<Rep>::max)()) return false; - if (count < (std::numeric_limits<Rep>::min)()) return false; + if (count < (std::numeric_limits<Rep>::lowest)()) return false; *tpp = time_point<D>() + D{static_cast<Rep>(count)}; return true; } template <typename Rep> -bool join_seconds( +typename std::enable_if<std::is_integral<Rep>::value, bool>::type join_seconds( const time_point<seconds>& sec, const femtoseconds&, time_point<std::chrono::duration<Rep, std::ratio<1, 1>>>* tpp) { using D = std::chrono::duration<Rep, std::ratio<1, 1>>; auto count = sec.time_since_epoch().count(); if (count > (std::numeric_limits<Rep>::max)()) return false; - if (count < (std::numeric_limits<Rep>::min)()) return false; + if (count < (std::numeric_limits<Rep>::lowest)()) return false; *tpp = time_point<D>() + D{static_cast<Rep>(count)}; return true; }
diff --git a/absl/time/internal/cctz/src/time_zone_format.cc b/absl/time/internal/cctz/src/time_zone_format.cc index f97de2f..ee4341d 100644 --- a/absl/time/internal/cctz/src/time_zone_format.cc +++ b/absl/time/internal/cctz/src/time_zone_format.cc
@@ -34,6 +34,7 @@ // declare strptime. #include <time.h> +#include <cassert> #include <cctype> #include <chrono> #include <cstddef> @@ -708,6 +709,14 @@ bool parse(const std::string& format, const std::string& input, const time_zone& tz, time_point<seconds>* sec, detail::femtoseconds* fs, std::string* err) { +#if __cplusplus < 202002L + // Assert that the std::chrono::system_clock epoch is the Unix epoch. + // This is required by C++20, but was also ubiquitous before that. + // We use this in join_seconds() to simplify overflow detection. + assert(std::chrono::system_clock::from_time_t(0).time_since_epoch() == + std::chrono::system_clock::duration::zero()); +#endif + // The unparsed input. Even though we allow NULs in input, and // match them against corresponding NULs in format, we depend on // *edata being a NUL so that we can call strptime(). This also
diff --git a/absl/time/internal/cctz/src/time_zone_format_test.cc b/absl/time/internal/cctz/src/time_zone_format_test.cc index 8793a80..cbaf09a 100644 --- a/absl/time/internal/cctz/src/time_zone_format_test.cc +++ b/absl/time/internal/cctz/src/time_zone_format_test.cc
@@ -15,6 +15,7 @@ #include <chrono> #include <cstdint> #include <iomanip> +#include <ratio> // NOLINT: We use std::ratio in this header #include <sstream> #include <string> @@ -229,6 +230,10 @@ TestFormatSpecifier(tp, tz, "%x", "01/01/70"); TestFormatSpecifier(tp, tz, "%X", "00:00:00"); + // %I renders midnight and noon as 12, with %p disambiguating them. + TestFormatSpecifier(tp, tz, "%I %p", "12 AM"); + TestFormatSpecifier(tp + chrono::hours(12), tz, "%I %p", "12 PM"); + #if defined(__linux__) // SU/C99/TZ extensions TestFormatSpecifier(tp, tz, "%h", "Jan"); // Same as %b @@ -863,9 +868,19 @@ EXPECT_TRUE(parse(kFmt, "03:04:05", utc, &tp_m)); EXPECT_EQ("03:04:00", absl::time_internal::cctz::format(kFmt, tp_m, utc)); + // Verify that pre-epoch times floor towards negative infinity. + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:59:05+00:00", utc, &tp_m)); + EXPECT_EQ("1969-12-31T23:59:00+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp_m, utc)); + time_point<chrono::hours> tp_h; EXPECT_TRUE(parse(kFmt, "03:04:05", utc, &tp_h)); EXPECT_EQ("03:00:00", absl::time_internal::cctz::format(kFmt, tp_h, utc)); + + // Verify that pre-epoch times floor towards negative infinity. + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:59:05+00:00", utc, &tp_h)); + EXPECT_EQ("1969-12-31T23:00:00+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp_h, utc)); } TEST(Parse, TimePointExtendedResolution) { @@ -1161,6 +1176,22 @@ EXPECT_TRUE(parse("%I %p", "5 PM", tz, &tp)); EXPECT_EQ(17, convert(tp, tz).hour()); + // %I maps 12 to 0 and a following %p shifts to the afternoon, + // so "12 AM" is midnight and "12 PM" is noon. + tp = reset; + EXPECT_TRUE(parse("%I %p", "12 AM", tz, &tp)); + EXPECT_EQ(0, convert(tp, tz).hour()); + tp = reset; + EXPECT_TRUE(parse("%I %p", "12 PM", tz, &tp)); + EXPECT_EQ(12, convert(tp, tz).hour()); + + tp = reset; + EXPECT_TRUE(parse("%I %p", "01 AM", tz, &tp)); + EXPECT_EQ(1, convert(tp, tz).hour()); + tp = reset; + EXPECT_TRUE(parse("%I %p", "11 PM", tz, &tp)); + EXPECT_EQ(23, convert(tp, tz).hour()); + tp = reset; EXPECT_TRUE(parse("%x", "02/03/04", tz, &tp)); if (convert(tp, tz).month() == 2) { @@ -1196,6 +1227,19 @@ EXPECT_EQ(44, convert(tp, tz).minute()); EXPECT_EQ(55, convert(tp, tz).second()); + // %r must land on the correct side of the AM/PM boundary too. + tp = reset; + EXPECT_TRUE(parse("%r", "12:00:00 AM", tz, &tp)); + EXPECT_EQ(0, convert(tp, tz).hour()); + EXPECT_EQ(0, convert(tp, tz).minute()); + EXPECT_EQ(0, convert(tp, tz).second()); + + tp = reset; + EXPECT_TRUE(parse("%r", "12:00:00 PM", tz, &tp)); + EXPECT_EQ(12, convert(tp, tz).hour()); + EXPECT_EQ(0, convert(tp, tz).minute()); + EXPECT_EQ(0, convert(tp, tz).second()); + #if defined(__GLIBC__) tp = reset; EXPECT_TRUE(parse("%Ec", "Tue Nov 19 05:06:07 2013", tz, &tp)); @@ -1708,57 +1752,193 @@ TEST(Parse, TimePointOverflow) { const time_zone utc = utc_time_zone(); + { + // Test with nanosecond resolution (typical 64-bit time_point). + using D = chrono::duration<std::int64_t, std::nano>; + time_point<D> tp; - using D = chrono::duration<std::int64_t, std::nano>; + // Max time_point<D> is 2262-04-11T23:47:16.854775807+00:00. + EXPECT_TRUE( + parse(RFC3339_full, "2262-04-11T23:47:16.8547758079+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::max()); + EXPECT_EQ("2262-04-11T23:47:16.854775807+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 nanosecond beyond max should fail. + EXPECT_FALSE( + parse(RFC3339_full, "2262-04-11T23:47:16.8547758080+00:00", utc, &tp)); + + // Min time_point<D> is 1677-09-21T00:12:43.145224192+00:00. + EXPECT_TRUE( + parse(RFC3339_full, "1677-09-21T00:12:43.1452241920+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::min()); + EXPECT_EQ("1677-09-21T00:12:43.145224192+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 nanosecond below min should fail. + EXPECT_FALSE( + parse(RFC3339_full, "1677-09-21T00:12:43.1452241919+00:00", utc, &tp)); + } + { + // Test with femtosecond resolution. + using D = chrono::duration<std::int64_t, std::femto>; + time_point<D> tp; + + // Max time_point<D> is 1970-01-01T02:33:43.372036854775807+00:00. + EXPECT_TRUE(parse(RFC3339_full, + "1970-01-01T02:33:43.3720368547758079+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), time_point<D>::max().time_since_epoch()); + EXPECT_EQ("1970-01-01T02:33:43.372036854775807+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 femtosecond beyond max should fail. + EXPECT_FALSE(parse(RFC3339_full, + "1970-01-01T02:33:43.3720368547758080+00:00", utc, &tp)); + + // Min time_point<D> is 1969-12-31T21:26:16.627963145224192+00:00. + EXPECT_TRUE(parse(RFC3339_full, + "1969-12-31T21:26:16.6279631452241920+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), time_point<D>::min().time_since_epoch()); + EXPECT_EQ("1969-12-31T21:26:16.627963145224192+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 femtosecond below min should fail. + EXPECT_FALSE(parse(RFC3339_full, + "1969-12-31T21:26:16.6279631452241919+00:00", utc, &tp)); + } + { + // Test with attosecond resolution. + using D = chrono::duration<std::int64_t, std::atto>; + time_point<D> tp; + + // Max time_point<D> is 1970-01-01T00:00:09.223372036854775807+00:00, + // but cctz::parse() truncates (towards zero) to a femtosecond boundary, + // so the last three decimal places are lost. + EXPECT_TRUE(parse(RFC3339_full, + "1970-01-01T00:00:09.223372036854775807+00:00", utc, + &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{9223372036854775000LL}); + EXPECT_EQ("1970-01-01T00:00:09.223372036854775+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // Moving into the next femtosecond should fail. + EXPECT_FALSE(parse(RFC3339_full, + "1970-01-01T00:00:09.223372036854776000+00:00", utc, + &tp)); + + // Min time_point<D> is 1969-12-31T23:59:50.776627963145224192+00:00, + // but cctz::parse() truncates (towards zero) to a femtosecond boundary, + // so we must round up. + EXPECT_TRUE(parse(RFC3339_full, + "1969-12-31T23:59:50.776627963145225000+00:00", utc, + &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{-9223372036854775000LL}); + EXPECT_EQ("1969-12-31T23:59:50.776627963145225+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 attosecond below min should fail. + EXPECT_FALSE(parse(RFC3339_full, + "1969-12-31T23:59:50.776627963145224999+00:00", utc, + &tp)); + } + { + // Test with 1-second resolution using int8_t ([-128, 127] seconds). + using D = chrono::duration<std::int8_t>; + time_point<D> tp; + + // Max time_point<D> is 1970-01-01T00:02:07+00:00. + EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T00:02:07.9+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::max()); + EXPECT_EQ("1970-01-01T00:02:07+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 second beyond max should fail. + EXPECT_FALSE(parse(RFC3339_full, "1970-01-01T00:02:08+00:00", utc, &tp)); + + // Min time_point<D> is 1969-12-31T23:57:52+00:00. + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:57:52+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::min()); + EXPECT_EQ("1969-12-31T23:57:52+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 second below min should fail. + EXPECT_FALSE(parse(RFC3339_full, "1969-12-31T23:57:51+00:00", utc, &tp)); + } + { + // Test with 1-minute resolution using int8_t ([-128, 127] minutes). + using D = chrono::duration<std::int8_t, std::ratio<60>>; + time_point<D> tp; + + // Max time_point<D> is 1970-01-01T02:07:00+00:00. + EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T02:07:00+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::max()); + EXPECT_EQ("1970-01-01T02:07:00+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 minute beyond max should fail. + EXPECT_FALSE(parse(RFC3339_full, "1970-01-01T02:08:00+00:00", utc, &tp)); + + // Min time_point<D> is 1969-12-31T21:52:00+00:00. + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T21:52:00+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::min()); + EXPECT_EQ("1969-12-31T21:52:00+00:00", + absl::time_internal::cctz::format(RFC3339_full, tp, utc)); + // 1 minute below min should fail. + EXPECT_FALSE(parse(RFC3339_full, "1969-12-31T21:51:00+00:00", utc, &tp)); + } + { + // Test with millisecond resolution using int8_t ([-128, 127] milliseconds). + // This tests the case where Denom (1000) is larger than Rep max/min. + using D = chrono::duration<std::int8_t, std::milli>; + time_point<D> tp; + + // Max time_point<D> is 1970-01-01T00:00:00.127+00:00. + EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T00:00:00.127+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::max()); + // 1 millisecond beyond max should fail (tests sub > max check). + EXPECT_FALSE( + parse(RFC3339_full, "1970-01-01T00:00:00.128+00:00", utc, &tp)); + + // Min time_point<D> is 1969-12-31T23:59:59.872+00:00. + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:59:59.872+00:00", utc, &tp)); + EXPECT_EQ(tp, time_point<D>::min()); + // 1 millisecond below min should fail (tests min with Denom > -min). + EXPECT_FALSE( + parse(RFC3339_full, "1969-12-31T23:59:59.871+00:00", utc, &tp)); + } +} + +TEST(Parse, TimePointFloatingPoint) { + const time_zone utc = utc_time_zone(); + { + using D = chrono::duration<double>; + time_point<D> tp; + + EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T00:00:59.25+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{59.25}); + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:59:00.75+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{-59.25}); + } + { + using D = chrono::duration<double, std::milli>; + time_point<D> tp; + + EXPECT_TRUE( + parse(RFC3339_full, "1970-01-01T00:00:00.015625+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{15.625}); + EXPECT_TRUE( + parse(RFC3339_full, "1969-12-31T23:59:59.984375+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{-15.625}); + } + { + using D = chrono::duration<double, std::ratio<60>>; + time_point<D> tp; + + EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T00:01:15+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{1.25}); + EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:58:45+00:00", utc, &tp)); + EXPECT_EQ(tp.time_since_epoch(), D{-1.25}); + } +} + +TEST(Parse, RatioNonLowestTerms) { + const time_zone utc = utc_time_zone(); + using D = chrono::duration<std::int64_t, std::ratio<2, 2>>; time_point<D> tp; - EXPECT_TRUE( - parse(RFC3339_full, "2262-04-11T23:47:16.8547758079+00:00", utc, &tp)); - EXPECT_EQ(tp, time_point<D>::max()); - EXPECT_EQ("2262-04-11T23:47:16.854775807+00:00", - absl::time_internal::cctz::format(RFC3339_full, tp, utc)); -#if 0 - // TODO(#199): Will fail until cctz::parse() properly detects overflow. - EXPECT_FALSE( - parse(RFC3339_full, "2262-04-11T23:47:16.8547758080+00:00", utc, &tp)); - EXPECT_TRUE( - parse(RFC3339_full, "1677-09-21T00:12:43.1452241920+00:00", utc, &tp)); - EXPECT_EQ(tp, time_point<D>::min()); - EXPECT_EQ("1677-09-21T00:12:43.145224192+00:00", - absl::time_internal::cctz::format(RFC3339_full, tp, utc)); - EXPECT_FALSE( - parse(RFC3339_full, "1677-09-21T00:12:43.1452241919+00:00", utc, &tp)); -#endif - - using DS = chrono::duration<std::int8_t, chrono::seconds::period>; - time_point<DS> stp; - - EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T00:02:07.9+00:00", utc, &stp)); - EXPECT_EQ(stp, time_point<DS>::max()); - EXPECT_EQ("1970-01-01T00:02:07+00:00", - absl::time_internal::cctz::format(RFC3339_full, stp, utc)); - EXPECT_FALSE(parse(RFC3339_full, "1970-01-01T00:02:08+00:00", utc, &stp)); - - EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T23:57:52+00:00", utc, &stp)); - EXPECT_EQ(stp, time_point<DS>::min()); - EXPECT_EQ("1969-12-31T23:57:52+00:00", - absl::time_internal::cctz::format(RFC3339_full, stp, utc)); - EXPECT_FALSE(parse(RFC3339_full, "1969-12-31T23:57:51.9+00:00", utc, &stp)); - - using DM = chrono::duration<std::int8_t, chrono::minutes::period>; - time_point<DM> mtp; - - EXPECT_TRUE(parse(RFC3339_full, "1970-01-01T02:07:59+00:00", utc, &mtp)); - EXPECT_EQ(mtp, time_point<DM>::max()); - EXPECT_EQ("1970-01-01T02:07:00+00:00", - absl::time_internal::cctz::format(RFC3339_full, mtp, utc)); - EXPECT_FALSE(parse(RFC3339_full, "1970-01-01T02:08:00+00:00", utc, &mtp)); - - EXPECT_TRUE(parse(RFC3339_full, "1969-12-31T21:52:00+00:00", utc, &mtp)); - EXPECT_EQ(mtp, time_point<DM>::min()); - EXPECT_EQ("1969-12-31T21:52:00+00:00", - absl::time_internal::cctz::format(RFC3339_full, mtp, utc)); - EXPECT_FALSE(parse(RFC3339_full, "1969-12-31T21:51:59+00:00", utc, &mtp)); + EXPECT_TRUE(parse(RFC3339_full, "2026-08-17T11:42:16-04:00", utc, &tp)); + ExpectTime(tp, utc, 2026, 8, 17, 15, 42, 16, 0, false, "UTC"); } TEST(Parse, TimePointOverflowFloor) { @@ -1772,8 +1952,6 @@ EXPECT_EQ(tp, time_point<D>::max()); EXPECT_EQ("294247-01-10T04:00:54.775807+00:00", absl::time_internal::cctz::format(RFC3339_full, tp, utc)); -#if 0 - // TODO(#199): Will fail until cctz::parse() properly detects overflow. EXPECT_FALSE( parse(RFC3339_full, "294247-01-10T04:00:54.7758080+00:00", utc, &tp)); EXPECT_TRUE( @@ -1783,7 +1961,6 @@ absl::time_internal::cctz::format(RFC3339_full, tp, utc)); EXPECT_FALSE( parse(RFC3339_full, "-290308-12-21T19:59:05.2241919+00:00", utc, &tp)); -#endif } //
diff --git a/absl/time/internal/cctz/src/time_zone_info.cc b/absl/time/internal/cctz/src/time_zone_info.cc index 9abbde7..9d385b2 100644 --- a/absl/time/internal/cctz/src/time_zone_info.cc +++ b/absl/time/internal/cctz/src/time_zone_info.cc
@@ -415,6 +415,9 @@ #ifndef O_CLOEXEC #define O_CLOEXEC 0 #endif +#ifndef O_NONBLOCK +#define O_NONBLOCK 0 +#endif const int fd = open(path, O_RDONLY | O_NONBLOCK | O_CLOEXEC); if (fd >= 0) { #if defined(__APPLE__)
diff --git a/absl/time/internal/cctz/testdata/version b/absl/time/internal/cctz/testdata/version index 9217a2d..b62e268 100644 --- a/absl/time/internal/cctz/testdata/version +++ b/absl/time/internal/cctz/testdata/version
@@ -1 +1 @@ -2026c +2026d
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/America/Bogota b/absl/time/internal/cctz/testdata/zoneinfo/America/Bogota index 85b9033..8b37a3d 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/America/Bogota +++ b/absl/time/internal/cctz/testdata/zoneinfo/America/Bogota Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/America/Inuvik b/absl/time/internal/cctz/testdata/zoneinfo/America/Inuvik index 86639f6..20b2ad1 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/America/Inuvik +++ b/absl/time/internal/cctz/testdata/zoneinfo/America/Inuvik Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/Asia/Tehran b/absl/time/internal/cctz/testdata/zoneinfo/Asia/Tehran index 6fd31e0..2a46cf7 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/Asia/Tehran +++ b/absl/time/internal/cctz/testdata/zoneinfo/Asia/Tehran Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/CST6CDT b/absl/time/internal/cctz/testdata/zoneinfo/CST6CDT index b016880..cc2cb27 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/CST6CDT +++ b/absl/time/internal/cctz/testdata/zoneinfo/CST6CDT Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/EST5EDT b/absl/time/internal/cctz/testdata/zoneinfo/EST5EDT index 2b6c2ee..cc944f0 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/EST5EDT +++ b/absl/time/internal/cctz/testdata/zoneinfo/EST5EDT Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/Iran b/absl/time/internal/cctz/testdata/zoneinfo/Iran index 6fd31e0..2a46cf7 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/Iran +++ b/absl/time/internal/cctz/testdata/zoneinfo/Iran Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/MST7MDT b/absl/time/internal/cctz/testdata/zoneinfo/MST7MDT index 09e54e5..f155fa9 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/MST7MDT +++ b/absl/time/internal/cctz/testdata/zoneinfo/MST7MDT Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/PST8PDT b/absl/time/internal/cctz/testdata/zoneinfo/PST8PDT index aaf0778..6a27aeb 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/PST8PDT +++ b/absl/time/internal/cctz/testdata/zoneinfo/PST8PDT Binary files differ
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab b/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab index 635eabc..0c6a15c 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab +++ b/absl/time/internal/cctz/testdata/zoneinfo/zone1970.tab
@@ -114,7 +114,7 @@ CA +5017-10750 America/Swift_Current CST - SK (midwest) CA +5333-11328 America/Edmonton CST - AB, BC(E), NT(E), SK(W) CA +690650-1050310 America/Cambridge_Bay Mountain - NU (west) -CA +682059-1334300 America/Inuvik Mountain - NT (west) +CA +682059-1334300 America/Inuvik CST - NT (west) CA +4916-12307 America/Vancouver MST - BC (most areas) CA +5546-12014 America/Dawson_Creek MST - BC (Dawson Cr, Ft St John) CA +5848-12242 America/Fort_Nelson MST - BC (Ft Nelson)
diff --git a/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab b/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab index 9c3a8cf..1c9b44b 100644 --- a/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab +++ b/absl/time/internal/cctz/testdata/zoneinfo/zonenow.tab
@@ -65,10 +65,10 @@ XX +332654-1120424 America/Phoenix Mountain Standard (MST) - Arizona; western Mexico; Yukon # # -07/-06 - MST/MDT (North America DST) -XX +394421-1045903 America/Denver Mountain (MST/MDT) - US; Mexico near US border; northern Canada +XX +394421-1045903 America/Denver Mountain (MST/MDT) - US; Mexico near US border; western Nunavut # # -07/-06 - MST/MDT (North America DST) until 2026-11-01 02:00; then CST -XX +5333-11328 America/Edmonton Central Standard (CST) - Alberta and some neighbors +XX +5333-11328 America/Edmonton Central Standard (CST) - Alberta, NWT, and some neighbors # # -06 XX -0054-08936 Pacific/Galapagos Galápagos