From e7ca23acac146b10edc4f752edd0bd28b0f14ea3 Mon Sep 17 00:00:00 2001 From: Abseil Team Date: Wed, 23 Dec 2020 12:59:21 -0800 Subject: Export of internal Abseil changes -- 7c15492a46380679651a4291bb284980901d04b1 by Andy Getzendanner : Add some internal hooks for ABSL_RAW_LOG and do a bit of tidying up. PiperOrigin-RevId: 348836291 -- 9a438cdcf2bd8d2b7ab27f4955432abf0d087672 by Evan Brown : Fix a bug affecting b-tree extract() when there are multiple keys in the container that are equivalent to the lookup key. In that case, we are supposed to extract the first such key in the container - [reference](https://en.cppreference.com/w/cpp/container/multiset/extract), but we were extracting the first one we found (which was not necessarily the first in the container). Also, optimize internal_lower_bound to not keep searching all the way to the leaf if it finds an equivalent key on an internal node and we can't have multiple equivalent keys for the lookup key. PiperOrigin-RevId: 348822858 -- b5e34c3af3f52815dbca3c6858c26fa8f385a408 by Abseil Team : Fix misleading comment. Ignored object can be either deallocated or leaked. PiperOrigin-RevId: 348705960 -- 64fd9e8c0684bfe86f50161b0e0e9077bb96e05c by Christian Blichmann : Minor cleanups: - Sorting using declarations - Changing the format of a NOLINT statement PiperOrigin-RevId: 348641845 GitOrigin-RevId: 7c15492a46380679651a4291bb284980901d04b1 Change-Id: Ia1ccd844586bd3dced2466651f1175d40caf3d7a --- absl/base/internal/raw_logging.cc | 66 ++++++++++++++++--------------- absl/base/internal/raw_logging.h | 8 ++++ absl/container/btree_test.cc | 48 +++++++++++++++++++++- absl/container/internal/btree.h | 39 +++++++++++++----- absl/container/internal/btree_container.h | 17 ++++---- absl/debugging/leak_check.h | 3 +- absl/strings/numbers.h | 8 ---- absl/strings/numbers_test.cc | 4 +- 8 files changed, 129 insertions(+), 64 deletions(-) diff --git a/absl/base/internal/raw_logging.cc b/absl/base/internal/raw_logging.cc index ae8754c6..bdfb74b8 100644 --- a/absl/base/internal/raw_logging.cc +++ b/absl/base/internal/raw_logging.cc @@ -67,28 +67,32 @@ #undef ABSL_HAVE_RAW_IO #endif +namespace absl { +ABSL_NAMESPACE_BEGIN +namespace raw_logging_internal { +namespace { + // TODO(gfalcon): We want raw-logging to work on as many platforms as possible. -// Explicitly #error out when not ABSL_LOW_LEVEL_WRITE_SUPPORTED, except for a -// selected set of platforms for which we expect not to be able to raw log. +// Explicitly `#error` out when not `ABSL_LOW_LEVEL_WRITE_SUPPORTED`, except for +// a selected set of platforms for which we expect not to be able to raw log. -ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES static absl::base_internal::AtomicHook< - absl::raw_logging_internal::LogPrefixHook> - log_prefix_hook; -ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES static absl::base_internal::AtomicHook< - absl::raw_logging_internal::AbortHook> - abort_hook; +ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES ABSL_DLL + absl::base_internal::AtomicHook + log_prefix_hook; +ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES ABSL_DLL + absl::base_internal::AtomicHook + abort_hook; #ifdef ABSL_LOW_LEVEL_WRITE_SUPPORTED -static const char kTruncated[] = " ... (message truncated)\n"; +constexpr char kTruncated[] = " ... (message truncated)\n"; // sprintf the format to the buffer, adjusting *buf and *size to reflect the // consumed bytes, and return whether the message fit without truncation. If // truncation occurred, if possible leave room in the buffer for the message // kTruncated[]. -inline static bool VADoRawLog(char** buf, int* size, const char* format, - va_list ap) ABSL_PRINTF_ATTRIBUTE(3, 0); -inline static bool VADoRawLog(char** buf, int* size, - const char* format, va_list ap) { +bool VADoRawLog(char** buf, int* size, const char* format, va_list ap) + ABSL_PRINTF_ATTRIBUTE(3, 0); +bool VADoRawLog(char** buf, int* size, const char* format, va_list ap) { int n = vsnprintf(*buf, *size, format, ap); bool result = true; if (n < 0 || n > *size) { @@ -96,7 +100,7 @@ inline static bool VADoRawLog(char** buf, int* size, if (static_cast(*size) > sizeof(kTruncated)) { n = *size - sizeof(kTruncated); // room for truncation message } else { - n = 0; // no room for truncation message + n = 0; // no room for truncation message } } *size -= n; @@ -105,9 +109,7 @@ inline static bool VADoRawLog(char** buf, int* size, } #endif // ABSL_LOW_LEVEL_WRITE_SUPPORTED -static constexpr int kLogBufSize = 3000; - -namespace { +constexpr int kLogBufSize = 3000; // CAVEAT: vsnprintf called from *DoRawLog below has some (exotic) code paths // that invoke malloc() and getenv() that might acquire some locks. @@ -166,7 +168,7 @@ void RawLogVA(absl::LogSeverity severity, const char* file, int line, } else { DoRawLog(&buf, &size, "%s", kTruncated); } - absl::raw_logging_internal::SafeWriteToStderr(buffer, strlen(buffer)); + SafeWriteToStderr(buffer, strlen(buffer)); } #else static_cast(format); @@ -181,11 +183,18 @@ void RawLogVA(absl::LogSeverity severity, const char* file, int line, } } +// Non-formatting version of RawLog(). +// +// TODO(gfalcon): When string_view no longer depends on base, change this +// interface to take its message as a string_view instead. +void DefaultInternalLog(absl::LogSeverity severity, const char* file, int line, + const std::string& message) { + RawLog(severity, file, line, "%.*s", static_cast(message.size()), + message.data()); +} + } // namespace -namespace absl { -ABSL_NAMESPACE_BEGIN -namespace raw_logging_internal { void SafeWriteToStderr(const char *s, size_t len) { #if defined(ABSL_HAVE_SYSCALL_WRITE) syscall(SYS_write, STDERR_FILENO, s, len); @@ -200,8 +209,6 @@ void SafeWriteToStderr(const char *s, size_t len) { #endif } -void RawLog(absl::LogSeverity severity, const char* file, int line, - const char* format, ...) ABSL_PRINTF_ATTRIBUTE(4, 5); void RawLog(absl::LogSeverity severity, const char* file, int line, const char* format, ...) { va_list ap; @@ -210,15 +217,6 @@ void RawLog(absl::LogSeverity severity, const char* file, int line, va_end(ap); } -// Non-formatting version of RawLog(). -// -// TODO(gfalcon): When string_view no longer depends on base, change this -// interface to take its message as a string_view instead. -static void DefaultInternalLog(absl::LogSeverity severity, const char* file, - int line, const std::string& message) { - RawLog(severity, file, line, "%s", message.c_str()); -} - bool RawLoggingFullySupported() { #ifdef ABSL_LOW_LEVEL_WRITE_SUPPORTED return true; @@ -231,6 +229,10 @@ ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES ABSL_DLL absl::base_internal::AtomicHook internal_log_function(DefaultInternalLog); +void RegisterLogPrefixHook(LogPrefixHook func) { log_prefix_hook.Store(func); } + +void RegisterAbortHook(AbortHook func) { abort_hook.Store(func); } + void RegisterInternalLogFunction(InternalLogFunction func) { internal_log_function.Store(func); } diff --git a/absl/base/internal/raw_logging.h b/absl/base/internal/raw_logging.h index 20f4291b..2bf7aaba 100644 --- a/absl/base/internal/raw_logging.h +++ b/absl/base/internal/raw_logging.h @@ -178,6 +178,14 @@ ABSL_INTERNAL_ATOMIC_HOOK_ATTRIBUTES ABSL_DLL extern base_internal::AtomicHook< InternalLogFunction> internal_log_function; +// Registers hooks of the above types. Only a single hook of each type may be +// registered. It is an error to call these functions multiple times with +// different input arguments. +// +// These functions are safe to call at any point during initialization; they do +// not block or malloc, and are async-signal safe. +void RegisterLogPrefixHook(LogPrefixHook func); +void RegisterAbortHook(AbortHook func); void RegisterInternalLogFunction(InternalLogFunction func); } // namespace raw_logging_internal diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc index a933386a..367d75be 100644 --- a/absl/container/btree_test.cc +++ b/absl/container/btree_test.cc @@ -2038,6 +2038,30 @@ TEST(Btree, ExtractAndInsertNodeHandleMultiMap) { EXPECT_EQ(res, ++other.begin()); } +TEST(Btree, ExtractMultiMapEquivalentKeys) { + // Note: using string keys means a three-way comparator. + absl::btree_multimap map; + for (int i = 0; i < 100; ++i) { + for (int j = 0; j < 100; ++j) { + map.insert({absl::StrCat(i), j}); + } + } + + for (int i = 0; i < 100; ++i) { + const std::string key = absl::StrCat(i); + auto node_handle = map.extract(key); + EXPECT_EQ(node_handle.key(), key); + EXPECT_EQ(node_handle.mapped(), 0) << i; + } + + for (int i = 0; i < 100; ++i) { + const std::string key = absl::StrCat(i); + auto node_handle = map.extract(key); + EXPECT_EQ(node_handle.key(), key); + EXPECT_EQ(node_handle.mapped(), 1) << i; + } +} + // For multisets, insert with hint also affects correctness because we need to // insert immediately before the hint if possible. struct InsertMultiHintData { @@ -2726,7 +2750,6 @@ TYPED_TEST_SUITE(BtreeMultiKeyTest, MultiKeyComps); TYPED_TEST(BtreeMultiKeyTest, EqualRange) { absl::btree_set set; - for (int i = 0; i < 100; ++i) { for (int j = 0; j < 100; ++j) { set.insert({i, j}); @@ -2736,11 +2759,32 @@ TYPED_TEST(BtreeMultiKeyTest, EqualRange) { for (int i = 0; i < 100; ++i) { auto equal_range = set.equal_range(i); EXPECT_EQ(equal_range.first->i1, i); - EXPECT_EQ(equal_range.first->i2, 0); + EXPECT_EQ(equal_range.first->i2, 0) << i; EXPECT_EQ(std::distance(equal_range.first, equal_range.second), 100) << i; } } +TYPED_TEST(BtreeMultiKeyTest, Extract) { + absl::btree_set set; + for (int i = 0; i < 100; ++i) { + for (int j = 0; j < 100; ++j) { + set.insert({i, j}); + } + } + + for (int i = 0; i < 100; ++i) { + auto node_handle = set.extract(i); + EXPECT_EQ(node_handle.value().i1, i); + EXPECT_EQ(node_handle.value().i2, 0) << i; + } + + for (int i = 0; i < 100; ++i) { + auto node_handle = set.extract(i); + EXPECT_EQ(node_handle.value().i1, i); + EXPECT_EQ(node_handle.value().i2, 1) << i; + } +} + TYPED_TEST(BtreeMultiKeyTest, Erase) { absl::btree_set set = { {1, 1}, {2, 1}, {2, 2}, {3, 1}}; diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index d863cb30..6f5f01b8 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -1211,7 +1211,7 @@ class btree { return const_reverse_iterator(begin()); } - // Finds the first element whose key is not less than key. + // Finds the first element whose key is not less than `key`. template iterator lower_bound(const K &key) { return internal_end(internal_lower_bound(key).value); @@ -1221,7 +1221,12 @@ class btree { return internal_end(internal_lower_bound(key).value); } - // Finds the first element whose key is greater than key. + // Finds the first element whose key is not less than `key` and also returns + // whether that element is equal to `key`. + template + std::pair lower_bound_equal(const K &key) const; + + // Finds the first element whose key is greater than `key`. template iterator upper_bound(const K &key) { return internal_end(internal_upper_bound(key)); @@ -1303,8 +1308,8 @@ class btree { // to the element after the last erased element. std::pair erase_range(iterator begin, iterator end); - // Finds the iterator corresponding to a key or returns end() if the key is - // not present. + // Finds an element with key equivalent to `key` or returns `end()` if `key` + // is not present. template iterator find(const K &key) { return internal_end(internal_find(key)); @@ -1905,12 +1910,23 @@ constexpr bool btree

::static_assert_validation() { template template -auto btree

::equal_range(const K &key) -> std::pair { +auto btree

::lower_bound_equal(const K &key) const + -> std::pair { const SearchResult res = internal_lower_bound(key); - const iterator lower = internal_end(res.value); - if (res.HasMatch() ? !res.IsEq() - : lower == end() || compare_keys(key, lower.key())) { + const iterator lower = iterator(internal_end(res.value)); + const bool equal = res.HasMatch() + ? res.IsEq() + : lower != end() && !compare_keys(key, lower.key()); + return {lower, equal}; +} + +template +template +auto btree

::equal_range(const K &key) -> std::pair { + const std::pair lower_and_equal = lower_bound_equal(key); + const iterator lower = lower_and_equal.first; + if (!lower_and_equal.second) { return {lower, lower}; } @@ -2510,14 +2526,17 @@ template template auto btree

::internal_lower_bound(const K &key) const -> SearchResult { + if (!params_type::template can_have_multiple_equivalent_keys()) { + SearchResult ret = internal_locate(key); + ret.value = internal_last(ret.value); + return ret; + } iterator iter(const_cast(root())); SearchResult res; bool seen_eq = false; for (;;) { res = iter.node->lower_bound(key, key_comp()); iter.position = res.value; - // TODO(ezb): we should be able to terminate early on IsEq() if there can't - // be multiple equivalent keys in container for this lookup type. if (iter.node->leaf()) { break; } diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h index 887eda41..03be708e 100644 --- a/absl/container/internal/btree_container.h +++ b/absl/container/internal/btree_container.h @@ -338,13 +338,12 @@ class btree_set_container : public btree_container { } // Node extraction routines. - // TODO(ezb): when the comparator is heterogeneous and has different - // equivalence classes for different lookup types, we should extract the first - // equivalent value if there are multiple. template node_type extract(const key_arg &key) { - auto it = this->find(key); - return it == this->end() ? node_type() : extract(it); + const std::pair lower_and_equal = + this->tree_.lower_bound_equal(key); + return lower_and_equal.second ? extract(lower_and_equal.first) + : node_type(); } using super_type::extract; @@ -621,12 +620,12 @@ class btree_multiset_container : public btree_container { } // Node extraction routines. - // TODO(ezb): we are supposed to extract the first equivalent key if there are - // multiple, but this isn't guaranteed to extract the first one. template node_type extract(const key_arg &key) { - auto it = this->find(key); - return it == this->end() ? node_type() : extract(it); + const std::pair lower_and_equal = + this->tree_.lower_bound_equal(key); + return lower_and_equal.second ? extract(lower_and_equal.first) + : node_type(); } using super_type::extract; diff --git a/absl/debugging/leak_check.h b/absl/debugging/leak_check.h index 7a5a22dd..b66a81c3 100644 --- a/absl/debugging/leak_check.h +++ b/absl/debugging/leak_check.h @@ -62,7 +62,8 @@ void DoIgnoreLeak(const void* ptr); // // If the passed `ptr` does not point to an actively allocated object at the // time `IgnoreLeak()` is called, the call is a no-op; if it is actively -// allocated, the object must not get deallocated later. +// allocated, leak sanitizer will assume this object is referenced even if +// there is no actual reference in user memory. // template T* IgnoreLeak(T* ptr) { diff --git a/absl/strings/numbers.h b/absl/strings/numbers.h index 7966e250..ffc738fa 100644 --- a/absl/strings/numbers.h +++ b/absl/strings/numbers.h @@ -1,4 +1,3 @@ -// // Copyright 2017 The Abseil Authors. // // Licensed under the Apache License, Version 2.0 (the "License"); @@ -245,13 +244,6 @@ inline size_t FastHexToBufferZeroPad16(uint64_t val, char* out) { } // namespace numbers_internal -// SimpleAtoi() -// -// Converts a string to an integer, using `safe_strto?()` functions for actual -// parsing, returning `true` if successful. The `safe_strto?()` functions apply -// strict checking; the string must be a base-10 integer, optionally followed or -// preceded by ASCII whitespace, with a value in the range of the corresponding -// integer type. template ABSL_MUST_USE_RESULT bool SimpleAtoi(absl::string_view str, int_type* out) { return numbers_internal::safe_strtoi_base(str, out, 10); diff --git a/absl/strings/numbers_test.cc b/absl/strings/numbers_test.cc index 4ab67fb6..27616bf8 100644 --- a/absl/strings/numbers_test.cc +++ b/absl/strings/numbers_test.cc @@ -46,6 +46,7 @@ namespace { +using absl::SimpleAtoi; using absl::numbers_internal::kSixDigitsToBufferSize; using absl::numbers_internal::safe_strto32_base; using absl::numbers_internal::safe_strto64_base; @@ -55,7 +56,6 @@ using absl::numbers_internal::SixDigitsToBuffer; using absl::strings_internal::Itoa; using absl::strings_internal::strtouint32_test_cases; using absl::strings_internal::strtouint64_test_cases; -using absl::SimpleAtoi; using testing::Eq; using testing::MatchesRegex; @@ -380,7 +380,7 @@ TEST(NumbersTest, Atoi) { VerifySimpleAtoiGood(42, 42); VerifySimpleAtoiGood(42, 42); VerifySimpleAtoiGood(-42, -42); - VerifySimpleAtoiGood(-42, -42); // NOLINT(runtime/int) + VerifySimpleAtoiGood(-42, -42); // NOLINT: runtime-int VerifySimpleAtoiGood(42, 42); VerifySimpleAtoiGood(42, 42); VerifySimpleAtoiGood(42, 42); -- cgit v1.2.3