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/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/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 f26e673..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 GetRunningOnValgrind(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 RunningOnValgrind(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. - ANNOTATE_BENIGN_RACE(&running_on_valgrind, "safe hack"); - if (local_running_on_valgrind == -1) - running_on_valgrind = local_running_on_valgrind = GetRunningOnValgrind(); - return local_running_on_valgrind; -} - -// See the comments in dynamic_annotations.h -double ValgrindSlowdown(void) { - // Same initialization hack as in RunningOnValgrind(). - static volatile double slowdown = 0.0; - double local_slowdown = slowdown; - ANNOTATE_BENIGN_RACE(&slowdown, "safe hack"); - if (RunningOnValgrind() == 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 5ea697b..c470c74 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 // TODO(rogeeff): Remove after the backward compatibility period. #include "absl/base/internal/dynamic_annotations.h" // IWYU pragma: export @@ -90,7 +94,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" { @@ -152,7 +157,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) @@ -417,41 +422,30 @@ #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 RunningOnValgrind() and -// change its return value. -// -int RunningOnValgrind(void); - -// ValgrindSlowdown returns: -// * 1.0, if (RunningOnValgrind() == 0) -// * 50.0, if (RunningOnValgrind() != 0 && getenv("VALGRIND_SLOWDOWN") == -// NULL) -// * atof(getenv("VALGRIND_SLOWDOWN")) otherwise -// This function can be used to scale timeout values: -// EXAMPLE: -// for (;;) { -// DoExpensiveBackgroundTask(); -// SleepForSeconds(5 * ValgrindSlowdown()); -// } -// -double ValgrindSlowdown(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 + +using absl::base_internal::RunningOnValgrind; +using absl::base_internal::ValgrindSlowdown; +#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/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/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());