Roll abseil_revision 41a6263fd0..d39fe6cd6f
Change Log:
https://chromium.googlesource.com/external/github.com/abseil/abseil-cpp/+log/41a6263fd0..d39fe6cd6f
Full diff:
https://chromium.googlesource.com/external/github.com/abseil/abseil-cpp/+/41a6263fd0..d39fe6cd6f
Bug: None
Change-Id: Ifc9f505e30b3b1453efecf5ecc24f8b53987e2bd
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/2322806
Reviewed-by: Henrik Boström <hbos@chromium.org>
Commit-Queue: Danil Chapovalov <danilchap@chromium.org>
Cr-Original-Commit-Position: refs/heads/master@{#792282}
Cr-Mirrored-From: https://chromium.googlesource.com/chromium/src
Cr-Mirrored-Commit: 96387ba24813a78928d5b111e40a70a9134f4104
diff --git a/CMake/AbseilDll.cmake b/CMake/AbseilDll.cmake
index e25174a..c001621 100644
--- a/CMake/AbseilDll.cmake
+++ b/CMake/AbseilDll.cmake
@@ -8,7 +8,6 @@
"base/casts.h"
"base/config.h"
"base/const_init.h"
- "base/dynamic_annotations.cc"
"base/dynamic_annotations.h"
"base/internal/atomic_hook.h"
"base/internal/bits.h"
diff --git a/README.chromium b/README.chromium
index b8c794c..37dbe88 100644
--- a/README.chromium
+++ b/README.chromium
@@ -4,7 +4,7 @@
License: Apache 2.0
License File: LICENSE
Version: 0
-Revision: 41a6263fd0bcc93a90ff739785f17260f8ea061e
+Revision: d39fe6cd6f5eb72dc741f17d3a143a6a5a56538a
Security Critical: yes
Description:
diff --git a/absl/base/BUILD.bazel b/absl/base/BUILD.bazel
index 23f2763..ad29bb0 100644
--- a/absl/base/BUILD.bazel
+++ b/absl/base/BUILD.bazel
@@ -116,7 +116,6 @@
cc_library(
name = "dynamic_annotations",
srcs = [
- "dynamic_annotations.cc",
"internal/dynamic_annotations.h",
],
hdrs = [
@@ -126,6 +125,7 @@
linkopts = ABSL_DEFAULT_LINKOPTS,
deps = [
":config",
+ ":core_headers",
],
)
diff --git a/absl/base/BUILD.gn b/absl/base/BUILD.gn
index c1b9ac5..c234848 100644
--- a/absl/base/BUILD.gn
+++ b/absl/base/BUILD.gn
@@ -66,13 +66,15 @@
}
absl_source_set("dynamic_annotations") {
- sources = [ "dynamic_annotations.cc" ]
public = [ "dynamic_annotations.h" ]
# Abseil's dynamic annotations are only visible inside Abseil because
# their usage is deprecated in Chromium (see README.chromium for more info).
visibility = [ "//third_party/abseil-cpp/absl/*" ]
- deps = [ ":config" ]
+ deps = [
+ ":config",
+ ":core_headers",
+ ]
}
absl_source_set("core_headers") {
diff --git a/absl/base/CMakeLists.txt b/absl/base/CMakeLists.txt
index 62486f9..f5cfc79 100644
--- a/absl/base/CMakeLists.txt
+++ b/absl/base/CMakeLists.txt
@@ -105,7 +105,6 @@
HDRS
"dynamic_annotations.h"
SRCS
- "dynamic_annotations.cc"
"internal/dynamic_annotations.h"
COPTS
${ABSL_DEFAULT_COPTS}
diff --git a/absl/base/attributes.h b/absl/base/attributes.h
index c4fd81b..2cf4b1e 100644
--- a/absl/base/attributes.h
+++ b/absl/base/attributes.h
@@ -594,6 +594,85 @@
#define ABSL_ATTRIBUTE_FUNC_ALIGN(bytes)
#endif
+// ABSL_FALLTHROUGH_INTENDED
+//
+// Annotates implicit fall-through between switch labels, allowing a case to
+// indicate intentional fallthrough and turn off warnings about any lack of a
+// `break` statement. The ABSL_FALLTHROUGH_INTENDED macro should be followed by
+// a semicolon and can be used in most places where `break` can, provided that
+// no statements exist between it and the next switch label.
+//
+// Example:
+//
+// switch (x) {
+// case 40:
+// case 41:
+// if (truth_is_out_there) {
+// ++x;
+// ABSL_FALLTHROUGH_INTENDED; // Use instead of/along with annotations
+// // in comments
+// } else {
+// return x;
+// }
+// case 42:
+// ...
+//
+// Notes: when compiled with clang in C++11 mode, the ABSL_FALLTHROUGH_INTENDED
+// macro is expanded to the [[clang::fallthrough]] attribute, which is analysed
+// when performing switch labels fall-through diagnostic
+// (`-Wimplicit-fallthrough`). See clang documentation on language extensions
+// for details:
+// https://clang.llvm.org/docs/AttributeReference.html#fallthrough-clang-fallthrough
+//
+// When used with unsupported compilers, the ABSL_FALLTHROUGH_INTENDED macro
+// has no effect on diagnostics. In any case this macro has no effect on runtime
+// behavior and performance of code.
+#ifdef ABSL_FALLTHROUGH_INTENDED
+#error "ABSL_FALLTHROUGH_INTENDED should not be defined."
+#endif
+
+// TODO(zhangxy): Use c++17 standard [[fallthrough]] macro, when supported.
+#if defined(__clang__) && defined(__has_warning)
+#if __has_feature(cxx_attributes) && __has_warning("-Wimplicit-fallthrough")
+#define ABSL_FALLTHROUGH_INTENDED [[clang::fallthrough]]
+#endif
+#elif defined(__GNUC__) && __GNUC__ >= 7
+#define ABSL_FALLTHROUGH_INTENDED [[gnu::fallthrough]]
+#endif
+
+#ifndef ABSL_FALLTHROUGH_INTENDED
+#define ABSL_FALLTHROUGH_INTENDED \
+ do { \
+ } while (0)
+#endif
+
+// ABSL_DEPRECATED()
+//
+// Marks a deprecated class, struct, enum, function, method and variable
+// declarations. The macro argument is used as a custom diagnostic message (e.g.
+// suggestion of a better alternative).
+//
+// Examples:
+//
+// class ABSL_DEPRECATED("Use Bar instead") Foo {...};
+//
+// ABSL_DEPRECATED("Use Baz() instead") void Bar() {...}
+//
+// template <typename T>
+// ABSL_DEPRECATED("Use DoThat() instead")
+// void DoThis();
+//
+// Every usage of a deprecated entity will trigger a warning when compiled with
+// clang's `-Wdeprecated-declarations` option. This option is turned off by
+// default, but the warnings will be reported by clang-tidy.
+#if defined(__clang__) && __cplusplus >= 201103L
+#define ABSL_DEPRECATED(message) __attribute__((deprecated(message)))
+#endif
+
+#ifndef ABSL_DEPRECATED
+#define ABSL_DEPRECATED(message)
+#endif
+
// ABSL_CONST_INIT
//
// A variable declaration annotated with the `ABSL_CONST_INIT` attribute will
diff --git a/absl/base/dynamic_annotations.cc b/absl/base/dynamic_annotations.cc
deleted file mode 100644
index 8646a71..0000000
--- a/absl/base/dynamic_annotations.cc
+++ /dev/null
@@ -1,72 +0,0 @@
-// Copyright 2017 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.
-
-#include <stdlib.h>
-#include <string.h>
-
-#include "absl/base/dynamic_annotations.h"
-
-// Compiler-based ThreadSanitizer defines
-// DYNAMIC_ANNOTATIONS_EXTERNAL_IMPL = 1
-// and provides its own definitions of the functions.
-
-#ifndef DYNAMIC_ANNOTATIONS_EXTERNAL_IMPL
-# define DYNAMIC_ANNOTATIONS_EXTERNAL_IMPL 0
-#endif
-
-#if DYNAMIC_ANNOTATIONS_EXTERNAL_IMPL == 0 && !defined(__native_client__)
-
-extern "C" {
-
-static int AbslGetRunningOnValgrind(void) {
-#ifdef RUNNING_ON_VALGRIND
- if (RUNNING_ON_VALGRIND) return 1;
-#endif
- char *running_on_valgrind_str = getenv("RUNNING_ON_VALGRIND");
- if (running_on_valgrind_str) {
- return strcmp(running_on_valgrind_str, "0") != 0;
- }
- return 0;
-}
-
-// See the comments in dynamic_annotations.h
-int AbslRunningOnValgrind(void) {
- static volatile int running_on_valgrind = -1;
- int local_running_on_valgrind = running_on_valgrind;
- // C doesn't have thread-safe initialization of statics, and we
- // don't want to depend on pthread_once here, so hack it.
- ABSL_ANNOTATE_BENIGN_RACE(&running_on_valgrind, "safe hack");
- if (local_running_on_valgrind == -1)
- running_on_valgrind = local_running_on_valgrind = AbslGetRunningOnValgrind();
- return local_running_on_valgrind;
-}
-
-// See the comments in dynamic_annotations.h
-double AbslValgrindSlowdown(void) {
- // Same initialization hack as in AbslRunningOnValgrind().
- static volatile double slowdown = 0.0;
- double local_slowdown = slowdown;
- ABSL_ANNOTATE_BENIGN_RACE(&slowdown, "safe hack");
- if (AbslRunningOnValgrind() == 0) {
- return 1.0;
- }
- if (local_slowdown == 0.0) {
- char *env = getenv("VALGRIND_SLOWDOWN");
- slowdown = local_slowdown = env ? atof(env) : 50.0;
- }
- return local_slowdown;
-}
-
-} // extern "C"
-#endif // DYNAMIC_ANNOTATIONS_EXTERNAL_IMPL == 0
diff --git a/absl/base/dynamic_annotations.h b/absl/base/dynamic_annotations.h
index 427c184..01f0e23 100644
--- a/absl/base/dynamic_annotations.h
+++ b/absl/base/dynamic_annotations.h
@@ -47,7 +47,11 @@
#include <stddef.h>
+#include "absl/base/attributes.h"
#include "absl/base/config.h"
+#ifdef __cplusplus
+#include "absl/base/macros.h"
+#endif
// -------------------------------------------------------------------------
// Decide which features are enabled.
@@ -87,7 +91,8 @@
// Read/write annotations are enabled in Annotalysis mode; disabled otherwise.
#define ABSL_INTERNAL_READS_WRITES_ANNOTATIONS_ENABLED \
ABSL_INTERNAL_ANNOTALYSIS_ENABLED
-#endif
+
+#endif // ABSL_HAVE_THREAD_SANITIZER
#ifdef __cplusplus
#define ABSL_INTERNAL_BEGIN_EXTERN_C extern "C" {
@@ -149,7 +154,7 @@
ABSL_INTERNAL_GLOBAL_SCOPED(AnnotateRWLockCreate)(__FILE__, __LINE__, lock)
// Report that a linker initialized lock has been created at address `lock`.
-#ifdef THREAD_SANITIZER
+#ifdef ABSL_HAVE_THREAD_SANITIZER
#define ABSL_ANNOTATE_RWLOCK_CREATE_STATIC(lock) \
ABSL_INTERNAL_GLOBAL_SCOPED(AnnotateRWLockCreateStatic) \
(__FILE__, __LINE__, lock)
@@ -414,41 +419,28 @@
#endif
+#ifdef __cplusplus
+#ifdef ABSL_HAVE_THREAD_SANITIZER
ABSL_INTERNAL_BEGIN_EXTERN_C
-
-// -------------------------------------------------------------------------
-// Return non-zero value if running under valgrind.
-//
-// If "valgrind.h" is included into dynamic_annotations.cc,
-// the regular valgrind mechanism will be used.
-// See http://valgrind.org/docs/manual/manual-core-adv.html about
-// RUNNING_ON_VALGRIND and other valgrind "client requests".
-// The file "valgrind.h" may be obtained by doing
-// svn co svn://svn.valgrind.org/valgrind/trunk/include
-//
-// If for some reason you can't use "valgrind.h" or want to fake valgrind,
-// there are two ways to make this function return non-zero:
-// - Use environment variable: export RUNNING_ON_VALGRIND=1
-// - Make your tool intercept the function AbslRunningOnValgrind() and
-// change its return value.
-//
-int AbslRunningOnValgrind(void);
-
-// AbslValgrindSlowdown returns:
-// * 1.0, if (AbslRunningOnValgrind() == 0)
-// * 50.0, if (AbslRunningOnValgrind() != 0 && getenv("VALGRIND_SLOWDOWN") ==
-// NULL)
-// * atof(getenv("VALGRIND_SLOWDOWN")) otherwise
-// This function can be used to scale timeout values:
-// EXAMPLE:
-// for (;;) {
-// DoExpensiveBackgroundTask();
-// SleepForSeconds(5 * AbslValgrindSlowdown());
-// }
-//
-double AbslValgrindSlowdown(void);
-
+int RunningOnValgrind();
+double ValgrindSlowdown();
ABSL_INTERNAL_END_EXTERN_C
+#else
+namespace absl {
+ABSL_NAMESPACE_BEGIN
+namespace base_internal {
+ABSL_DEPRECATED(
+ "Don't use this interface. It is misleading and is being deleted.")
+ABSL_ATTRIBUTE_ALWAYS_INLINE inline int RunningOnValgrind() { return 0; }
+ABSL_DEPRECATED(
+ "Don't use this interface. It is misleading and is being deleted.")
+ABSL_ATTRIBUTE_ALWAYS_INLINE inline double ValgrindSlowdown() { return 1.0; }
+} // namespace base_internal
+ABSL_NAMESPACE_END
+} // namespace absl
+
+#endif
+#endif
// -------------------------------------------------------------------------
// Address sanitizer annotations
diff --git a/absl/base/internal/sysinfo.cc b/absl/base/internal/sysinfo.cc
index 6c69683..349d926 100644
--- a/absl/base/internal/sysinfo.cc
+++ b/absl/base/internal/sysinfo.cc
@@ -39,6 +39,7 @@
#endif
#include <string.h>
+
#include <cassert>
#include <cstdint>
#include <cstdio>
@@ -50,6 +51,7 @@
#include <vector>
#include "absl/base/call_once.h"
+#include "absl/base/config.h"
#include "absl/base/internal/raw_logging.h"
#include "absl/base/internal/spinlock.h"
#include "absl/base/internal/unscaledcycleclock.h"
@@ -420,6 +422,18 @@
#endif
+// GetCachedTID() caches the thread ID in thread-local storage (which is a
+// userspace construct) to avoid unnecessary system calls. Without this caching,
+// it can take roughly 98ns, while it takes roughly 1ns with this caching.
+pid_t GetCachedTID() {
+#if ABSL_HAVE_THREAD_LOCAL
+ static thread_local pid_t thread_id = GetTID();
+ return thread_id;
+#else
+ return GetTID();
+#endif // ABSL_HAVE_THREAD_LOCAL
+}
+
} // namespace base_internal
ABSL_NAMESPACE_END
} // namespace absl
diff --git a/absl/base/internal/sysinfo.h b/absl/base/internal/sysinfo.h
index 7246d5d..119cf1f 100644
--- a/absl/base/internal/sysinfo.h
+++ b/absl/base/internal/sysinfo.h
@@ -30,6 +30,7 @@
#include <cstdint>
+#include "absl/base/config.h"
#include "absl/base/port.h"
namespace absl {
@@ -59,6 +60,13 @@
#endif
pid_t GetTID();
+// Like GetTID(), but caches the result in thread-local storage in order
+// to avoid unnecessary system calls. Note that there are some cases where
+// one must call through to GetTID directly, which is why this exists as a
+// separate function. For example, GetCachedTID() is not safe to call in
+// an asynchronous signal-handling context nor right after a call to fork().
+pid_t GetCachedTID();
+
} // namespace base_internal
ABSL_NAMESPACE_END
} // namespace absl
diff --git a/absl/base/macros.h b/absl/base/macros.h
index ea1da65..02dd9ff 100644
--- a/absl/base/macros.h
+++ b/absl/base/macros.h
@@ -55,85 +55,6 @@
ABSL_NAMESPACE_END
} // namespace absl
-// ABSL_FALLTHROUGH_INTENDED
-//
-// Annotates implicit fall-through between switch labels, allowing a case to
-// indicate intentional fallthrough and turn off warnings about any lack of a
-// `break` statement. The ABSL_FALLTHROUGH_INTENDED macro should be followed by
-// a semicolon and can be used in most places where `break` can, provided that
-// no statements exist between it and the next switch label.
-//
-// Example:
-//
-// switch (x) {
-// case 40:
-// case 41:
-// if (truth_is_out_there) {
-// ++x;
-// ABSL_FALLTHROUGH_INTENDED; // Use instead of/along with annotations
-// // in comments
-// } else {
-// return x;
-// }
-// case 42:
-// ...
-//
-// Notes: when compiled with clang in C++11 mode, the ABSL_FALLTHROUGH_INTENDED
-// macro is expanded to the [[clang::fallthrough]] attribute, which is analysed
-// when performing switch labels fall-through diagnostic
-// (`-Wimplicit-fallthrough`). See clang documentation on language extensions
-// for details:
-// https://clang.llvm.org/docs/AttributeReference.html#fallthrough-clang-fallthrough
-//
-// When used with unsupported compilers, the ABSL_FALLTHROUGH_INTENDED macro
-// has no effect on diagnostics. In any case this macro has no effect on runtime
-// behavior and performance of code.
-#ifdef ABSL_FALLTHROUGH_INTENDED
-#error "ABSL_FALLTHROUGH_INTENDED should not be defined."
-#endif
-
-// TODO(zhangxy): Use c++17 standard [[fallthrough]] macro, when supported.
-#if defined(__clang__) && defined(__has_warning)
-#if __has_feature(cxx_attributes) && __has_warning("-Wimplicit-fallthrough")
-#define ABSL_FALLTHROUGH_INTENDED [[clang::fallthrough]]
-#endif
-#elif defined(__GNUC__) && __GNUC__ >= 7
-#define ABSL_FALLTHROUGH_INTENDED [[gnu::fallthrough]]
-#endif
-
-#ifndef ABSL_FALLTHROUGH_INTENDED
-#define ABSL_FALLTHROUGH_INTENDED \
- do { \
- } while (0)
-#endif
-
-// ABSL_DEPRECATED()
-//
-// Marks a deprecated class, struct, enum, function, method and variable
-// declarations. The macro argument is used as a custom diagnostic message (e.g.
-// suggestion of a better alternative).
-//
-// Examples:
-//
-// class ABSL_DEPRECATED("Use Bar instead") Foo {...};
-//
-// ABSL_DEPRECATED("Use Baz() instead") void Bar() {...}
-//
-// template <typename T>
-// ABSL_DEPRECATED("Use DoThat() instead")
-// void DoThis();
-//
-// Every usage of a deprecated entity will trigger a warning when compiled with
-// clang's `-Wdeprecated-declarations` option. This option is turned off by
-// default, but the warnings will be reported by clang-tidy.
-#if defined(__clang__) && __cplusplus >= 201103L
-#define ABSL_DEPRECATED(message) __attribute__((deprecated(message)))
-#endif
-
-#ifndef ABSL_DEPRECATED
-#define ABSL_DEPRECATED(message)
-#endif
-
// ABSL_BAD_CALL_IF()
//
// Used on a function overload to trap bad calls: any call that matches the
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index 67ee752..0c5f936 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -15,6 +15,7 @@
#include "absl/container/btree_test.h"
#include <cstdint>
+#include <limits>
#include <map>
#include <memory>
#include <stdexcept>
@@ -1344,6 +1345,12 @@
constexpr static size_t GetNumValuesPerNode() {
return btree_node<typename Set::params_type>::kNodeValues;
}
+
+ template <typename Set>
+ constexpr static size_t GetMaxFieldType() {
+ return std::numeric_limits<
+ typename btree_node<typename Set::params_type>::field_type>::max();
+ }
};
namespace {
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 996afa6..ab85f7d 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -255,10 +255,6 @@
static void move(Alloc *alloc, slot_type *src, slot_type *dest) {
slot_policy::move(alloc, src, dest);
}
- static void move(Alloc *alloc, slot_type *first, slot_type *last,
- slot_type *result) {
- slot_policy::move(alloc, first, last, result);
- }
};
// A parameters structure for holding the type parameters for a btree_map.
@@ -336,13 +332,6 @@
static void move(Alloc * /*alloc*/, slot_type *src, slot_type *dest) {
*dest = std::move(*src);
}
-
- template <typename Alloc>
- static void move(Alloc *alloc, slot_type *first, slot_type *last,
- slot_type *result) {
- for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
- move(alloc, src, dest);
- }
};
// A parameters structure for holding the type parameters for a btree_set.
@@ -759,14 +748,10 @@
template <typename... Args>
void emplace_value(size_type i, allocator_type *alloc, Args &&... args);
- // Removes the value at position i, shifting all existing values and children
- // at positions > i to the left by 1.
- void remove_value(int i, allocator_type *alloc);
-
- // Removes the values at positions [i, i + to_erase), shifting all values
- // after that range to the left by to_erase. Does not change children at all.
- void remove_values_ignore_children(int i, int to_erase,
- allocator_type *alloc);
+ // Removes the values at positions [i, i + to_erase), shifting all existing
+ // values and children after that range to the left by to_erase. Clears all
+ // children between [i, i + to_erase).
+ void remove_values(field_type i, field_type to_erase, allocator_type *alloc);
// Rebalances a node with its right sibling.
void rebalance_right_to_left(int to_move, btree_node *right,
@@ -778,7 +763,7 @@
void split(int insert_position, btree_node *dest, allocator_type *alloc);
// Merges a node with its right sibling, moving all of the values and the
- // delimiting key in the parent node onto itself.
+ // delimiting key in the parent node onto itself, and deleting the src node.
void merge(btree_node *src, allocator_type *alloc);
// Node allocation/deletion routines.
@@ -799,12 +784,15 @@
absl::container_internal::SanitizerPoisonMemoryRegion(
&mutable_child(start()), (kNodeValues + 1) * sizeof(btree_node *));
}
- void destroy(allocator_type *alloc) {
- for (int i = start(); i < finish(); ++i) {
- value_destroy(i, alloc);
- }
+
+ static void deallocate(const size_type size, btree_node *node,
+ allocator_type *alloc) {
+ absl::container_internal::Deallocate<Alignment()>(alloc, node, size);
}
+ // Deletes a node and all of its children.
+ static void clear_and_delete(btree_node *node, allocator_type *alloc);
+
public:
// Exposed only for tests.
static bool testonly_uses_linear_node_search() {
@@ -813,14 +801,21 @@
private:
template <typename... Args>
- void value_init(const size_type i, allocator_type *alloc, Args &&... args) {
+ void value_init(const field_type i, allocator_type *alloc, Args &&... args) {
absl::container_internal::SanitizerUnpoisonObject(slot(i));
params_type::construct(alloc, slot(i), std::forward<Args>(args)...);
}
- void value_destroy(const size_type i, allocator_type *alloc) {
+ void value_destroy(const field_type i, allocator_type *alloc) {
params_type::destroy(alloc, slot(i));
absl::container_internal::SanitizerPoisonObject(slot(i));
}
+ void value_destroy_n(const field_type i, const field_type n,
+ allocator_type *alloc) {
+ for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) {
+ params_type::destroy(alloc, s);
+ absl::container_internal::SanitizerPoisonObject(s);
+ }
+ }
// Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`.
void transfer(const size_type dest_i, const size_type src_i,
@@ -1423,25 +1418,8 @@
}
// Deletion helper routines.
- void erase_same_node(iterator begin, iterator end);
- iterator erase_from_leaf_node(iterator begin, size_type to_erase);
iterator rebalance_after_delete(iterator iter);
- // Deallocates a node of a certain size in bytes using the allocator.
- void deallocate(const size_type size, node_type *node) {
- absl::container_internal::Deallocate<node_type::Alignment()>(
- mutable_allocator(), node, size);
- }
-
- void delete_internal_node(node_type *node) {
- node->destroy(mutable_allocator());
- deallocate(node_type::InternalSize(), node);
- }
- void delete_leaf_node(node_type *node) {
- node->destroy(mutable_allocator());
- deallocate(node_type::LeafSize(node->max_count()), node);
- }
-
// Rebalances or splits the node iter points to.
void rebalance_or_split(iterator *iter);
@@ -1510,9 +1488,6 @@
template <typename K>
iterator internal_find(const K &key) const;
- // Deletes a node and all of its children.
- void internal_clear(node_type *node);
-
// Verifies the tree structure of node.
int internal_verify(const node_type *node, const key_type *lo,
const key_type *hi) const;
@@ -1580,26 +1555,27 @@
}
template <typename P>
-inline void btree_node<P>::remove_value(const int i, allocator_type *alloc) {
- if (!leaf() && finish() > i + 1) {
- assert(child(i + 1)->count() == 0);
- for (size_type j = i + 1; j < finish(); ++j) {
- set_child(j, child(j + 1));
+inline void btree_node<P>::remove_values(const field_type i,
+ const field_type to_erase,
+ allocator_type *alloc) {
+ // Transfer values after the removed range into their new places.
+ value_destroy_n(i, to_erase, alloc);
+ const field_type orig_finish = finish();
+ const field_type src_i = i + to_erase;
+ transfer_n(orig_finish - src_i, i, src_i, this, alloc);
+
+ if (!leaf()) {
+ // Delete all children between begin and end.
+ for (int j = 0; j < to_erase; ++j) {
+ clear_and_delete(child(i + j + 1), alloc);
}
- clear_child(finish());
+ // Rotate children after end into new positions.
+ for (int j = i + to_erase + 1; j <= orig_finish; ++j) {
+ set_child(j - to_erase, child(j));
+ clear_child(j);
+ }
}
-
- remove_values_ignore_children(i, /*to_erase=*/1, alloc);
-}
-
-template <typename P>
-inline void btree_node<P>::remove_values_ignore_children(
- const int i, const int to_erase, allocator_type *alloc) {
- params_type::move(alloc, slot(i + to_erase), finish_slot(), slot(i));
- for (int j = finish() - to_erase; j < finish(); ++j) {
- value_destroy(j, alloc);
- }
- set_finish(finish() - to_erase);
+ set_finish(orig_finish - to_erase);
}
template <typename P>
@@ -1751,8 +1727,59 @@
set_finish(start() + 1 + count() + src->count());
src->set_finish(src->start());
- // Remove the value on the parent node.
- parent()->remove_value(position(), alloc);
+ // Remove the value on the parent node and delete the src node.
+ parent()->remove_values(position(), /*to_erase=*/1, alloc);
+}
+
+template <typename P>
+void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
+ if (node->leaf()) {
+ node->value_destroy_n(node->start(), node->count(), alloc);
+ deallocate(LeafSize(node->max_count()), node, alloc);
+ return;
+ }
+ if (node->count() == 0) {
+ deallocate(InternalSize(), node, alloc);
+ return;
+ }
+
+ // The parent of the root of the subtree we are deleting.
+ btree_node *delete_root_parent = node->parent();
+
+ // Navigate to the leftmost leaf under node, and then delete upwards.
+ while (!node->leaf()) node = node->start_child();
+ // Use `int` because `pos` needs to be able to hold `kNodeValues+1`, which
+ // isn't guaranteed to be a valid `field_type`.
+ int pos = node->position();
+ btree_node *parent = node->parent();
+ for (;;) {
+ // In each iteration of the next loop, we delete one leaf node and go right.
+ assert(pos <= parent->finish());
+ do {
+ node = parent->child(pos);
+ if (!node->leaf()) {
+ // Navigate to the leftmost leaf under node.
+ while (!node->leaf()) node = node->start_child();
+ pos = node->position();
+ parent = node->parent();
+ }
+ node->value_destroy_n(node->start(), node->count(), alloc);
+ deallocate(LeafSize(node->max_count()), node, alloc);
+ ++pos;
+ } while (pos <= parent->finish());
+
+ // Once we've deleted all children of parent, delete parent and go up/right.
+ assert(pos > parent->finish());
+ do {
+ node = parent;
+ pos = node->position();
+ parent = node->parent();
+ node->value_destroy_n(node->start(), node->count(), alloc);
+ deallocate(InternalSize(), node, alloc);
+ if (parent == delete_root_parent) return;
+ ++pos;
+ } while (pos > parent->finish());
+ }
}
////
@@ -2034,7 +2061,7 @@
bool internal_delete = false;
if (!iter.node->leaf()) {
// Deletion of a value on an internal node. First, move the largest value
- // from our left child here, then delete that position (in remove_value()
+ // from our left child here, then delete that position (in remove_values()
// below). We can get to the largest value from our left child by
// decrementing iter.
iterator internal_iter(iter);
@@ -2046,7 +2073,7 @@
}
// Delete the key from the leaf.
- iter.node->remove_value(iter.position, mutable_allocator());
+ iter.node->remove_values(iter.position, /*to_erase=*/1, mutable_allocator());
--size_;
// We want to return the next value after the one we just erased. If we
@@ -2121,7 +2148,9 @@
}
if (begin.node == end.node) {
- erase_same_node(begin, end);
+ assert(end.position > begin.position);
+ begin.node->remove_values(begin.position, end.position - begin.position,
+ mutable_allocator());
size_ -= count;
return {count, rebalance_after_delete(begin)};
}
@@ -2131,8 +2160,11 @@
if (begin.node->leaf()) {
const size_type remaining_to_erase = size_ - target_size;
const size_type remaining_in_node = begin.node->finish() - begin.position;
- begin = erase_from_leaf_node(
- begin, (std::min)(remaining_to_erase, remaining_in_node));
+ const size_type to_erase =
+ (std::min)(remaining_to_erase, remaining_in_node);
+ begin.node->remove_values(begin.position, to_erase, mutable_allocator());
+ size_ -= to_erase;
+ begin = rebalance_after_delete(begin);
} else {
begin = erase(begin);
}
@@ -2141,51 +2173,6 @@
}
template <typename P>
-void btree<P>::erase_same_node(iterator begin, iterator end) {
- assert(begin.node == end.node);
- assert(end.position > begin.position);
-
- node_type *node = begin.node;
- size_type to_erase = end.position - begin.position;
- if (!node->leaf()) {
- // Delete all children between begin and end.
- for (size_type i = 0; i < to_erase; ++i) {
- internal_clear(node->child(begin.position + i + 1));
- }
- // Rotate children after end into new positions.
- for (size_type i = begin.position + to_erase + 1; i <= node->finish();
- ++i) {
- node->set_child(i - to_erase, node->child(i));
- node->clear_child(i);
- }
- }
- node->remove_values_ignore_children(begin.position, to_erase,
- mutable_allocator());
-
- // Do not need to update rightmost_, because
- // * either end == this->end(), and therefore node == rightmost_, and still
- // exists
- // * or end != this->end(), and therefore rightmost_ hasn't been erased, since
- // it wasn't covered in [begin, end)
-}
-
-template <typename P>
-auto btree<P>::erase_from_leaf_node(iterator begin, size_type to_erase)
- -> iterator {
- node_type *node = begin.node;
- assert(node->leaf());
- assert(node->finish() > begin.position);
- assert(begin.position + to_erase <= node->finish());
-
- node->remove_values_ignore_children(begin.position, to_erase,
- mutable_allocator());
-
- size_ -= to_erase;
-
- return rebalance_after_delete(begin);
-}
-
-template <typename P>
template <typename K>
auto btree<P>::erase_unique(const K &key) -> size_type {
const iterator iter = internal_find(key);
@@ -2213,7 +2200,7 @@
template <typename P>
void btree<P>::clear() {
if (!empty()) {
- internal_clear(root());
+ node_type::clear_and_delete(root(), mutable_allocator());
}
mutable_root() = EmptyNode();
rightmost_ = EmptyNode();
@@ -2354,12 +2341,7 @@
template <typename P>
void btree<P>::merge_nodes(node_type *left, node_type *right) {
left->merge(right, mutable_allocator());
- if (right->leaf()) {
- if (rightmost_ == right) rightmost_ = left;
- delete_leaf_node(right);
- } else {
- delete_internal_node(right);
- }
+ if (rightmost_ == right) rightmost_ = left;
}
template <typename P>
@@ -2416,20 +2398,20 @@
template <typename P>
void btree<P>::try_shrink() {
- if (root()->count() > 0) {
+ node_type *orig_root = root();
+ if (orig_root->count() > 0) {
return;
}
// Deleted the last item on the root node, shrink the height of the tree.
- if (root()->leaf()) {
+ if (orig_root->leaf()) {
assert(size() == 0);
- delete_leaf_node(root());
mutable_root() = rightmost_ = EmptyNode();
} else {
- node_type *child = root()->start_child();
+ node_type *child = orig_root->start_child();
child->make_root();
- delete_internal_node(root());
mutable_root() = child;
}
+ node_type::clear_and_delete(orig_root, mutable_allocator());
}
template <typename P>
@@ -2474,7 +2456,7 @@
old_root->start(), old_root, alloc);
new_root->set_finish(old_root->finish());
old_root->set_finish(old_root->start());
- delete_leaf_node(old_root);
+ node_type::clear_and_delete(old_root, alloc);
mutable_root() = rightmost_ = new_root;
} else {
rebalance_or_split(&iter);
@@ -2578,18 +2560,6 @@
}
template <typename P>
-void btree<P>::internal_clear(node_type *node) {
- if (!node->leaf()) {
- for (int i = node->start(); i <= node->finish(); ++i) {
- internal_clear(node->child(i));
- }
- delete_internal_node(node);
- } else {
- delete_leaf_node(node);
- }
-}
-
-template <typename P>
int btree<P>::internal_verify(const node_type *node, const key_type *lo,
const key_type *hi) const {
assert(node->count() > 0);
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h
index 536ea39..92a61cc 100644
--- a/absl/container/internal/container_memory.h
+++ b/absl/container/internal/container_memory.h
@@ -429,13 +429,6 @@
std::move(src->value));
}
}
-
- template <class Allocator>
- static void move(Allocator* alloc, slot_type* first, slot_type* last,
- slot_type* result) {
- for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
- move(alloc, src, dest);
- }
};
} // namespace container_internal
diff --git a/absl/debugging/internal/demangle.cc b/absl/debugging/internal/demangle.cc
index fc262e5..5f54ef3 100644
--- a/absl/debugging/internal/demangle.cc
+++ b/absl/debugging/internal/demangle.cc
@@ -409,6 +409,7 @@
static bool EndsWith(State *state, const char chr) {
return state->parse_state.out_cur_idx > 0 &&
+ state->parse_state.out_cur_idx < state->out_end_idx &&
chr == state->out[state->parse_state.out_cur_idx - 1];
}
@@ -421,8 +422,10 @@
if (str[0] == '<' && EndsWith(state, '<')) {
Append(state, " ", 1);
}
- // Remember the last identifier name for ctors/dtors.
- if (IsAlpha(str[0]) || str[0] == '_') {
+ // Remember the last identifier name for ctors/dtors,
+ // but only if we haven't yet overflown the buffer.
+ if (state->parse_state.out_cur_idx < state->out_end_idx &&
+ (IsAlpha(str[0]) || str[0] == '_')) {
state->parse_state.prev_name_idx = state->parse_state.out_cur_idx;
state->parse_state.prev_name_length = length;
}
diff --git a/absl/debugging/internal/vdso_support.cc b/absl/debugging/internal/vdso_support.cc
index 559af8d..0ef3bae 100644
--- a/absl/debugging/internal/vdso_support.cc
+++ b/absl/debugging/internal/vdso_support.cc
@@ -80,11 +80,6 @@
// on stack, and so glibc works as if VDSO was not present.
// But going directly to kernel via /proc/self/auxv below bypasses
// Valgrind zapping. So we check for Valgrind separately.
- if (AbslRunningOnValgrind()) {
- vdso_base_.store(nullptr, std::memory_order_relaxed);
- getcpu_fn_.store(&GetCPUViaSyscall, std::memory_order_relaxed);
- return nullptr;
- }
int fd = open("/proc/self/auxv", O_RDONLY);
if (fd == -1) {
// Kernel too old to have a VDSO.
diff --git a/absl/status/status.h b/absl/status/status.h
index 967e606..4253062 100644
--- a/absl/status/status.h
+++ b/absl/status/status.h
@@ -24,24 +24,137 @@
namespace absl {
ABSL_NAMESPACE_BEGIN
+// Sometimes multiple error codes may apply. Services should return
+// the most specific error code that applies. For example, prefer
+// `kOutOfRange` over `kFailedPrecondition` if both codes apply.
+// Similarly prefer `kNotFound` or `kAlreadyExists` over `kFailedPrecondition`.
enum class StatusCode : int {
+ // Not an error; returned on success
kOk = 0,
+
+ // The operation was cancelled, typically by the caller.
kCancelled = 1,
+
+ // Unknown error. For example, errors raised by APIs that do not return
+ // enough error information may be converted to this error.
kUnknown = 2,
+
+ // The client specified an invalid argument. Note that this differs
+ // from `kFailedPrecondition`. `kInvalidArgument` indicates arguments
+ // that are problematic regardless of the state of the system
+ // (such as a malformed file name).
kInvalidArgument = 3,
+
+ // The deadline expired before the operation could complete. For operations
+ // that change the state of the system, this error may be returned
+ // even if the operation has completed successfully. For example, a
+ // successful response from a server could have been delayed long
+ // enough for the deadline to expire.
kDeadlineExceeded = 4,
+
+ // Some requested entity (such as file or directory) was not found.
+ //
+ // Note to server developers: if a request is denied for an entire class
+ // of users, such as gradual feature rollout or undocumented whitelist,
+ // `kNotFound` may be used. If a request is denied for some users within
+ // a class of users, such as user-based access control, `kPermissionDenied`
+ // must be used.
kNotFound = 5,
+
+ // The entity that a client attempted to create (such as file or directory)
+ // already exists.
kAlreadyExists = 6,
+
+ // The caller does not have permission to execute the specified
+ // operation. `kPermissionDenied` must not be used for rejections
+ // caused by exhausting some resource (use `kResourceExhausted`
+ // instead for those errors). `kPermissionDenied` must not be
+ // used if the caller can not be identified (use `kUnauthenticated`
+ // instead for those errors). This error code does not imply the
+ // request is valid or the requested entity exists or satisfies
+ // other pre-conditions.
kPermissionDenied = 7,
+
+ // Some resource has been exhausted, perhaps a per-user quota, or
+ // perhaps the entire file system is out of space.
kResourceExhausted = 8,
+
+ // The operation was rejected because the system is not in a state
+ // required for the operation's execution. For example, the directory
+ // to be deleted is non-empty, an rmdir operation is applied to
+ // a non-directory, etc.
+ //
+ // A litmus test that may help a service implementer in deciding
+ // between `kFailedPrecondition`, `kAborted`, and `kUnavailable`:
+ // (a) Use `kUnavailable` if the client can retry just the failing call.
+ // (b) Use `kAborted` if the client should retry at a higher-level
+ // (such as when a client-specified test-and-set fails, indicating the
+ // client should restart a read-modify-write sequence).
+ // (c) Use `kFailedPrecondition` if the client should not retry until
+ // the system state has been explicitly fixed. For example, if an "rmdir"
+ // fails because the directory is non-empty, `kFailedPrecondition`
+ // should be returned since the client should not retry unless
+ // the files are deleted from the directory.
kFailedPrecondition = 9,
+
+ // The operation was aborted, typically due to a concurrency issue such as
+ // a sequencer check failure or transaction abort.
+ //
+ // See litmus test above for deciding between `kFailedPrecondition`,
+ // `kAborted`, and `kUnavailable`.
kAborted = 10,
+
+ // The operation was attempted past the valid range, such as seeking or
+ // reading past end-of-file.
+ //
+ // Unlike `kInvalidArgument`, this error indicates a problem that may
+ // be fixed if the system state changes. For example, a 32-bit file
+ // system will generate `kInvalidArgument` if asked to read at an
+ // offset that is not in the range [0,2^32-1], but it will generate
+ // `kOutOfRange` if asked to read from an offset past the current
+ // file size.
+ //
+ // There is a fair bit of overlap between `kFailedPrecondition` and
+ // `kOutOfRange`. We recommend using `kOutOfRange` (the more specific
+ // error) when it applies so that callers who are iterating through
+ // a space can easily look for an `kOutOfRange` error to detect when
+ // they are done.
kOutOfRange = 11,
+
+ // The operation is not implemented or is not supported/enabled in this
+ // service.
kUnimplemented = 12,
+
+ // Internal errors. This means that some invariants expected by the
+ // underlying system have been broken. This error code is reserved
+ // for serious errors.
kInternal = 13,
+
+ // The service is currently unavailable. This is most likely a
+ // transient condition, which can be corrected by retrying with
+ // a backoff. Note that it is not always safe to retry
+ // non-idempotent operations.
+ //
+ // See litmus test above for deciding between `kFailedPrecondition`,
+ // `kAborted`, and `kUnavailable`.
kUnavailable = 14,
+
+ // Unrecoverable data loss or corruption.
kDataLoss = 15,
+
+ // The request does not have valid authentication credentials for the
+ // operation.
kUnauthenticated = 16,
+
+ // An extra enum entry to prevent people from writing code that
+ // fails to compile when a new code is added.
+ //
+ // Nobody should ever reference this enumeration entry. In particular,
+ // if you write C++ code that switches on this enumeration, add a default:
+ // case instead of a case that mentions this enumeration entry.
+ //
+ // Nobody should rely on the value (currently 20) listed here. It
+ // may change in the future.
kDoNotUseReservedForFutureExpansionUseDefaultInSwitchInstead_ = 20
};
diff --git a/absl/strings/str_split_test.cc b/absl/strings/str_split_test.cc
index 9d93a87..25e9cd2 100644
--- a/absl/strings/str_split_test.cc
+++ b/absl/strings/str_split_test.cc
@@ -27,7 +27,6 @@
#include "gmock/gmock.h"
#include "gtest/gtest.h"
-#include "absl/base/dynamic_annotations.h" // for AbslRunningOnValgrind
#include "absl/base/macros.h"
#include "absl/container/flat_hash_map.h"
#include "absl/container/node_hash_map.h"
diff --git a/absl/strings/string_view_test.cc b/absl/strings/string_view_test.cc
index 1cb6de2..41dbc97 100644
--- a/absl/strings/string_view_test.cc
+++ b/absl/strings/string_view_test.cc
@@ -1179,7 +1179,7 @@
#ifndef THREAD_SANITIZER // Allocates too much memory for tsan.
TEST(HugeStringView, TwoPointTwoGB) {
- if (sizeof(size_t) <= 4 || AbslRunningOnValgrind())
+ if (sizeof(size_t) <= 4)
return;
// Try a huge string piece.
const size_t size = size_t{2200} * 1000 * 1000;
diff --git a/absl/time/internal/cctz/src/time_zone_info.cc b/absl/time/internal/cctz/src/time_zone_info.cc
index 7ccda11..c7bf044 100644
--- a/absl/time/internal/cctz/src/time_zone_info.cc
+++ b/absl/time/internal/cctz/src/time_zone_info.cc
@@ -365,8 +365,10 @@
std::int_fast64_t jan1_time = jan1 - civil_second();
int jan1_weekday = ToPosixWeekday(get_weekday(jan1));
- Transition dst = {0, dst_ti, civil_second(), civil_second()};
- Transition std = {0, std_ti, civil_second(), civil_second()};
+ Transition dst = {0, static_cast<uint_least8_t>(dst_ti), civil_second(),
+ civil_second()};
+ Transition std = {0, static_cast<uint_least8_t>(std_ti), civil_second(),
+ civil_second()};
for (const year_t limit = last_year_ + 400;; ++last_year_) {
auto dst_trans_off = TransOffset(leap_year, jan1_weekday, posix.dst_start);
auto std_trans_off = TransOffset(leap_year, jan1_weekday, posix.dst_end);
@@ -725,9 +727,9 @@
// Find and use a ZoneInfoSource to load the named zone.
auto zip = cctz_extension::zone_info_source_factory(
- name, [](const std::string& name) -> std::unique_ptr<ZoneInfoSource> {
- if (auto zip = FileZoneInfoSource::Open(name)) return zip;
- if (auto zip = AndroidZoneInfoSource::Open(name)) return zip;
+ name, [](const std::string& n) -> std::unique_ptr<ZoneInfoSource> {
+ if (auto z = FileZoneInfoSource::Open(n)) return z;
+ if (auto z = AndroidZoneInfoSource::Open(n)) return z;
return nullptr;
});
return zip != nullptr && Load(zip.get());
diff --git a/rename_annotations.sh b/rename_annotations.sh
deleted file mode 100755
index 6a95bb6..0000000
--- a/rename_annotations.sh
+++ /dev/null
@@ -1,18 +0,0 @@
-#!/bin/bash
-
-# This script renames all the functions and the macros defined in
-# absl/base/dynamic_annotations.{h,cc}.
-#
-# Chromium's dynamic_annotations live in //base/third_party/dynamic_annotations
-# which conflict with Abseil's versions (ODR violations).
-# In order to avoid problems in Chromium, this copy of Abseil has its own
-# dynamic_annotations renamed.
-
-# -------------------------- dynamic_annotations -------------------------
-for w in \
- GetRunningOnValgrind \
- RunningOnValgrind \
- ValgrindSlowdown \
-; do
- find absl/ -type f -exec sed -i "s/\b$w\b/Absl$w/g" {} \;
-done
