summaryrefslogtreecommitdiff
path: root/absl
diff options
context:
space:
mode:
Diffstat (limited to 'absl')
-rw-r--r--absl/base/attributes.h14
-rw-r--r--absl/container/BUILD.bazel1
-rw-r--r--absl/container/CMakeLists.txt1
-rw-r--r--absl/container/btree_test.cc51
-rw-r--r--absl/container/internal/btree.h562
-rw-r--r--absl/container/internal/btree_container.h2
-rw-r--r--absl/random/mocking_bit_gen.h2
-rw-r--r--absl/strings/BUILD.bazel1
-rw-r--r--absl/strings/CMakeLists.txt1
-rw-r--r--absl/strings/cord.cc472
-rw-r--r--absl/strings/cord.h1
-rw-r--r--absl/strings/cord_analysis.cc41
-rw-r--r--absl/strings/internal/cord_internal.cc42
-rw-r--r--absl/strings/internal/cord_internal.h30
-rw-r--r--absl/strings/internal/cord_rep_concat.cc63
-rw-r--r--absl/strings/internal/cord_rep_consume.cc81
-rw-r--r--absl/strings/internal/cord_rep_flat.h8
-rw-r--r--absl/strings/internal/cord_rep_test_util.h3
-rw-r--r--absl/strings/internal/cordz_info.cc38
-rw-r--r--absl/strings/internal/cordz_info_statistics_test.cc4
20 files changed, 450 insertions, 968 deletions
diff --git a/absl/base/attributes.h b/absl/base/attributes.h
index 91aabffe..5721356d 100644
--- a/absl/base/attributes.h
+++ b/absl/base/attributes.h
@@ -646,6 +646,9 @@
// declarations. The macro argument is used as a custom diagnostic message (e.g.
// suggestion of a better alternative).
//
+// For code or headers that are assured to only build with C++14 and up, prefer
+// just using the standard `[[deprecated("message")]]` directly over this macro.
+//
// Examples:
//
// class ABSL_DEPRECATED("Use Bar instead") Foo {...};
@@ -661,13 +664,12 @@
// };
//
// 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__) && defined(__cplusplus) && __cplusplus >= 201103L
+// GCC/Clang's `-Wdeprecated-declarations` option. Google's production toolchain
+// turns this warning off by default, instead relying on clang-tidy to report
+// new uses of deprecated code.
+#if ABSL_HAVE_ATTRIBUTE(deprecated)
#define ABSL_DEPRECATED(message) __attribute__((deprecated(message)))
-#endif
-
-#ifndef ABSL_DEPRECATED
+#else
#define ABSL_DEPRECATED(message)
#endif
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel
index 728c4be1..bc25bac9 100644
--- a/absl/container/BUILD.bazel
+++ b/absl/container/BUILD.bazel
@@ -914,6 +914,7 @@ cc_library(
":container_memory",
":layout",
"//absl/base:core_headers",
+ "//absl/base:raw_logging_internal",
"//absl/base:throw_delegate",
"//absl/memory",
"//absl/meta:type_traits",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt
index b819deeb..648a3dba 100644
--- a/absl/container/CMakeLists.txt
+++ b/absl/container/CMakeLists.txt
@@ -35,6 +35,7 @@ absl_cc_library(
absl::core_headers
absl::layout
absl::memory
+ absl::raw_logging_internal
absl::strings
absl::throw_delegate
absl::type_traits
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index b2c3d73f..e829e0ba 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -1213,6 +1213,11 @@ class BtreeNodePeer {
constexpr static bool UsesLinearNodeSearch() {
return btree_node<typename Btree::params_type>::use_linear_search::value;
}
+
+ template <typename Btree>
+ constexpr static bool UsesGenerations() {
+ return Btree::params_type::kEnableGenerations;
+ }
};
namespace {
@@ -1478,8 +1483,10 @@ TEST(Btree, MovesComparisonsCopiesSwapsTracking) {
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
if (sizeof(void *) == 8) {
- EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
- BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>());
+ EXPECT_EQ(
+ BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+ // When we have generations, there is one fewer slot.
+ BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
}
// Test key insertion/deletion in random order.
@@ -1533,8 +1540,10 @@ TEST(Btree, MovesComparisonsCopiesSwapsTrackingThreeWayCompare) {
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>(), 61);
EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<decltype(set100)>(), 100);
if (sizeof(void *) == 8) {
- EXPECT_EQ(BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
- BtreeNodePeer::GetNumSlotsPerNode<decltype(set61)>());
+ EXPECT_EQ(
+ BtreeNodePeer::GetNumSlotsPerNode<absl::btree_set<int32_t>>(),
+ // When we have generations, there is one fewer slot.
+ BtreeNodePeer::UsesGenerations<absl::btree_set<int32_t>>() ? 60 : 61);
}
// Test key insertion/deletion in random order.
@@ -3020,8 +3029,38 @@ TEST(Btree, InvalidComparatorsCaught) {
}
};
absl::btree_set<int, ThreeWaySumGreaterZeroCmp> set;
- EXPECT_DEATH(set.insert({0, 1, 2}),
- R"regex(lhs_comp_rhs < 0 -> rhs_comp_lhs > 0)regex");
+ EXPECT_DEATH(set.insert({0, 1, 2}), "lhs_comp_rhs < 0 -> rhs_comp_lhs > 0");
+ }
+}
+#endif
+
+#ifndef _MSC_VER
+// This test crashes on MSVC.
+TEST(Btree, InvalidIteratorUse) {
+ if (!BtreeNodePeer::UsesGenerations<absl::btree_set<int>>())
+ GTEST_SKIP() << "Generation validation for iterators is disabled.";
+
+ {
+ absl::btree_set<int> set;
+ for (int i = 0; i < 10; ++i) set.insert(i);
+ auto it = set.begin();
+ set.erase(it++);
+ EXPECT_DEATH(set.erase(it++), "invalidated iterator");
+ }
+ {
+ absl::btree_set<int> set;
+ for (int i = 0; i < 10; ++i) set.insert(i);
+ auto it = set.insert(20).first;
+ set.insert(30);
+ EXPECT_DEATH(*it, "invalidated iterator");
+ }
+ {
+ absl::btree_set<int> set;
+ for (int i = 0; i < 10000; ++i) set.insert(i);
+ auto it = set.find(5000);
+ ASSERT_NE(it, set.end());
+ set.erase(1);
+ EXPECT_DEATH(*it, "invalidated iterator");
}
}
#endif
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index bbc319c1..6c10b00f 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -58,6 +58,7 @@
#include <type_traits>
#include <utility>
+#include "absl/base/internal/raw_logging.h"
#include "absl/base/macros.h"
#include "absl/container/internal/common.h"
#include "absl/container/internal/compressed_tuple.h"
@@ -74,6 +75,16 @@ namespace absl {
ABSL_NAMESPACE_BEGIN
namespace container_internal {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+#error ABSL_BTREE_ENABLE_GENERATIONS cannot be directly set
+#elif defined(ABSL_HAVE_ADDRESS_SANITIZER) || \
+ defined(ABSL_HAVE_MEMORY_SANITIZER)
+// When compiled in sanitizer mode, we add generation integers to the nodes and
+// iterators. When iterators are used, we validate that the container has not
+// been mutated since the iterator was constructed.
+#define ABSL_BTREE_ENABLE_GENERATIONS
+#endif
+
template <typename Compare, typename T, typename U>
using compare_result_t = absl::result_of_t<const Compare(const T &, const U &)>;
@@ -348,6 +359,12 @@ struct common_params {
static constexpr bool kIsKeyCompareTransparent =
IsTransparent<original_key_compare>::value ||
kIsKeyCompareStringAdapted;
+ static constexpr bool kEnableGenerations =
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ true;
+#else
+ false;
+#endif
// A type which indicates if we have a key-compare-to functor or a plain old
// key-compare functor.
@@ -518,6 +535,13 @@ class btree_node {
// // A pointer to the node's parent.
// btree_node *parent;
//
+ // // When ABSL_BTREE_ENABLE_GENERATIONS is defined, we also have a
+ // // generation integer in order to check that when iterators are
+ // // used, they haven't been invalidated already. Only the generation on
+ // // the root is used, but we have one on each node because whether a node
+ // // is root or not can change.
+ // uint32_t generation;
+ //
// // The position of the node in the node's parent.
// field_type position;
// // The index of the first populated value in `values`.
@@ -564,13 +588,16 @@ class btree_node {
btree_node() = default;
private:
- using layout_type = absl::container_internal::Layout<btree_node *, field_type,
- slot_type, btree_node *>;
+ using layout_type =
+ absl::container_internal::Layout<btree_node *, uint32_t, field_type,
+ slot_type, btree_node *>;
constexpr static size_type SizeWithNSlots(size_type n) {
- return layout_type(/*parent*/ 1,
- /*position, start, finish, max_count*/ 4,
- /*slots*/ n,
- /*children*/ 0)
+ return layout_type(
+ /*parent*/ 1,
+ /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+ /*position, start, finish, max_count*/ 4,
+ /*slots*/ n,
+ /*children*/ 0)
.AllocSize();
}
// A lower bound for the overhead of fields other than slots in a leaf node.
@@ -609,16 +636,20 @@ class btree_node {
// Leaves can have less than kNodeSlots values.
constexpr static layout_type LeafLayout(const int slot_count = kNodeSlots) {
- return layout_type(/*parent*/ 1,
- /*position, start, finish, max_count*/ 4,
- /*slots*/ slot_count,
- /*children*/ 0);
+ return layout_type(
+ /*parent*/ 1,
+ /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+ /*position, start, finish, max_count*/ 4,
+ /*slots*/ slot_count,
+ /*children*/ 0);
}
constexpr static layout_type InternalLayout() {
- return layout_type(/*parent*/ 1,
- /*position, start, finish, max_count*/ 4,
- /*slots*/ kNodeSlots,
- /*children*/ kNodeSlots + 1);
+ return layout_type(
+ /*parent*/ 1,
+ /*generation*/ params_type::kEnableGenerations ? 1 : 0,
+ /*position, start, finish, max_count*/ 4,
+ /*slots*/ kNodeSlots,
+ /*children*/ kNodeSlots + 1);
}
constexpr static size_type LeafSize(const int slot_count = kNodeSlots) {
return LeafLayout(slot_count).AllocSize();
@@ -632,44 +663,47 @@ class btree_node {
template <size_type N>
inline typename layout_type::template ElementType<N> *GetField() {
// We assert that we don't read from values that aren't there.
- assert(N < 3 || !leaf());
+ assert(N < 4 || is_internal());
return InternalLayout().template Pointer<N>(reinterpret_cast<char *>(this));
}
template <size_type N>
inline const typename layout_type::template ElementType<N> *GetField() const {
- assert(N < 3 || !leaf());
+ assert(N < 4 || is_internal());
return InternalLayout().template Pointer<N>(
reinterpret_cast<const char *>(this));
}
void set_parent(btree_node *p) { *GetField<0>() = p; }
- field_type &mutable_finish() { return GetField<1>()[2]; }
- slot_type *slot(int i) { return &GetField<2>()[i]; }
+ field_type &mutable_finish() { return GetField<2>()[2]; }
+ slot_type *slot(int i) { return &GetField<3>()[i]; }
slot_type *start_slot() { return slot(start()); }
slot_type *finish_slot() { return slot(finish()); }
- const slot_type *slot(int i) const { return &GetField<2>()[i]; }
- void set_position(field_type v) { GetField<1>()[0] = v; }
- void set_start(field_type v) { GetField<1>()[1] = v; }
- void set_finish(field_type v) { GetField<1>()[2] = v; }
+ const slot_type *slot(int i) const { return &GetField<3>()[i]; }
+ void set_position(field_type v) { GetField<2>()[0] = v; }
+ void set_start(field_type v) { GetField<2>()[1] = v; }
+ void set_finish(field_type v) { GetField<2>()[2] = v; }
// This method is only called by the node init methods.
- void set_max_count(field_type v) { GetField<1>()[3] = v; }
+ void set_max_count(field_type v) { GetField<2>()[3] = v; }
public:
// Whether this is a leaf node or not. This value doesn't change after the
// node is created.
- bool leaf() const { return GetField<1>()[3] != kInternalNodeMaxCount; }
+ bool is_leaf() const { return GetField<2>()[3] != kInternalNodeMaxCount; }
+ // Whether this is an internal node or not. This value doesn't change after
+ // the node is created.
+ bool is_internal() const { return !is_leaf(); }
// Getter for the position of this node in its parent.
- field_type position() const { return GetField<1>()[0]; }
+ field_type position() const { return GetField<2>()[0]; }
// Getter for the offset of the first value in the `values` array.
field_type start() const {
- // TODO(ezb): when floating storage is implemented, return GetField<1>()[1];
- assert(GetField<1>()[1] == 0);
+ // TODO(ezb): when floating storage is implemented, return GetField<2>()[1];
+ assert(GetField<2>()[1] == 0);
return 0;
}
// Getter for the offset after the last value in the `values` array.
- field_type finish() const { return GetField<1>()[2]; }
+ field_type finish() const { return GetField<2>()[2]; }
// Getters for the number of values stored in this node.
field_type count() const {
@@ -679,7 +713,7 @@ class btree_node {
field_type max_count() const {
// Internal nodes have max_count==kInternalNodeMaxCount.
// Leaf nodes have max_count in [1, kNodeSlots].
- const field_type max_count = GetField<1>()[3];
+ const field_type max_count = GetField<2>()[3];
return max_count == field_type{kInternalNodeMaxCount}
? field_type{kNodeSlots}
: max_count;
@@ -690,21 +724,44 @@ class btree_node {
// Getter for whether the node is the root of the tree. The parent of the
// root of the tree is the leftmost node in the tree which is guaranteed to
// be a leaf.
- bool is_root() const { return parent()->leaf(); }
+ bool is_root() const { return parent()->is_leaf(); }
void make_root() {
assert(parent()->is_root());
+ set_generation(parent()->generation());
set_parent(parent()->parent());
}
+ // Gets the root node's generation integer, which is the one used by the tree.
+ uint32_t *get_root_generation() const {
+ assert(params_type::kEnableGenerations);
+ const btree_node *curr = this;
+ for (; !curr->is_root(); curr = curr->parent()) continue;
+ return const_cast<uint32_t *>(&curr->GetField<1>()[0]);
+ }
+
+ // Returns the generation for iterator validation.
+ uint32_t generation() const {
+ return params_type::kEnableGenerations ? *get_root_generation() : 0;
+ }
+ // Updates generation. Should only be called on a root node or during node
+ // initialization.
+ void set_generation(uint32_t generation) {
+ if (params_type::kEnableGenerations) GetField<1>()[0] = generation;
+ }
+ // Updates the generation. We do this whenever the node is mutated.
+ void next_generation() {
+ if (params_type::kEnableGenerations) ++*get_root_generation();
+ }
+
// Getters for the key/value at position i in the node.
const key_type &key(int i) const { return params_type::key(slot(i)); }
reference value(int i) { return params_type::element(slot(i)); }
const_reference value(int i) const { return params_type::element(slot(i)); }
// Getters/setter for the child at position i in the node.
- btree_node *child(int i) const { return GetField<3>()[i]; }
+ btree_node *child(int i) const { return GetField<4>()[i]; }
btree_node *start_child() const { return child(start()); }
- btree_node *&mutable_child(int i) { return GetField<3>()[i]; }
+ btree_node *&mutable_child(int i) { return GetField<4>()[i]; }
void clear_child(int i) {
absl::container_internal::SanitizerPoisonObject(&mutable_child(i));
}
@@ -861,7 +918,8 @@ class btree_node {
void merge(btree_node *src, allocator_type *alloc);
// Node allocation/deletion routines.
- void init_leaf(btree_node *parent, int max_count) {
+ void init_leaf(int max_count, btree_node *parent) {
+ set_generation(0);
set_parent(parent);
set_position(0);
set_start(0);
@@ -871,7 +929,7 @@ class btree_node {
start_slot(), max_count * sizeof(slot_type));
}
void init_internal(btree_node *parent) {
- init_leaf(parent, kNodeSlots);
+ init_leaf(kNodeSlots, parent);
// Set `max_count` to a sentinel value to indicate that this node is
// internal.
set_max_count(kInternalNodeMaxCount);
@@ -890,15 +948,18 @@ class btree_node {
private:
template <typename... Args>
void value_init(const field_type i, allocator_type *alloc, Args &&... args) {
+ next_generation();
absl::container_internal::SanitizerUnpoisonObject(slot(i));
params_type::construct(alloc, slot(i), std::forward<Args>(args)...);
}
void value_destroy(const field_type i, allocator_type *alloc) {
+ next_generation();
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) {
+ next_generation();
for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) {
params_type::destroy(alloc, s);
absl::container_internal::SanitizerPoisonObject(s);
@@ -914,6 +975,7 @@ class btree_node {
// 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,
btree_node *src_node, allocator_type *alloc) {
+ next_generation();
transfer(slot(dest_i), src_node->slot(src_i), alloc);
}
@@ -922,6 +984,7 @@ class btree_node {
void transfer_n(const size_type n, const size_type dest_i,
const size_type src_i, btree_node *src_node,
allocator_type *alloc) {
+ next_generation();
for (slot_type *src = src_node->slot(src_i), *end = src + n,
*dest = slot(dest_i);
src != end; ++src, ++dest) {
@@ -934,6 +997,7 @@ class btree_node {
void transfer_n_backward(const size_type n, const size_type dest_i,
const size_type src_i, btree_node *src_node,
allocator_type *alloc) {
+ next_generation();
for (slot_type *src = src_node->slot(src_i + n - 1), *end = src - n,
*dest = slot(dest_i + n - 1);
src != end; --src, --dest) {
@@ -944,14 +1008,13 @@ class btree_node {
template <typename P>
friend class btree;
template <typename N, typename R, typename P>
- friend struct btree_iterator;
+ friend class btree_iterator;
friend class BtreeNodePeer;
friend struct btree_access;
};
template <typename Node, typename Reference, typename Pointer>
-struct btree_iterator {
- private:
+class btree_iterator {
using key_type = typename Node::key_type;
using size_type = typename Node::size_type;
using params_type = typename Node::params_type;
@@ -979,9 +1042,15 @@ struct btree_iterator {
using reference = Reference;
using iterator_category = std::bidirectional_iterator_tag;
- btree_iterator() : node(nullptr), position(-1) {}
- explicit btree_iterator(Node *n) : node(n), position(n->start()) {}
- btree_iterator(Node *n, int p) : node(n), position(p) {}
+ btree_iterator() : btree_iterator(nullptr, -1) {}
+ explicit btree_iterator(Node *n) : btree_iterator(n, n->start()) {}
+ btree_iterator(Node *n, int p) : node_(n), position_(p) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ // Use `~uint32_t{}` as a sentinel value for iterator generations so it
+ // doesn't match the initial value for the actual generation.
+ generation_ = n != nullptr ? n->generation() : ~uint32_t{};
+#endif
+ }
// NOTE: this SFINAE allows for implicit conversions from iterator to
// const_iterator, but it specifically avoids hiding the copy constructor so
@@ -992,58 +1061,32 @@ struct btree_iterator {
std::is_same<btree_iterator, const_iterator>::value,
int> = 0>
btree_iterator(const btree_iterator<N, R, P> other) // NOLINT
- : node(other.node), position(other.position) {}
-
- private:
- // This SFINAE allows explicit conversions from const_iterator to
- // iterator, but also avoids hiding the copy constructor.
- // NOTE: the const_cast is safe because this constructor is only called by
- // non-const methods and the container owns the nodes.
- template <typename N, typename R, typename P,
- absl::enable_if_t<
- std::is_same<btree_iterator<N, R, P>, const_iterator>::value &&
- std::is_same<btree_iterator, iterator>::value,
- int> = 0>
- explicit btree_iterator(const btree_iterator<N, R, P> other)
- : node(const_cast<node_type *>(other.node)), position(other.position) {}
-
- // Increment/decrement the iterator.
- void increment() {
- if (node->leaf() && ++position < node->finish()) {
- return;
- }
- increment_slow();
- }
- void increment_slow();
-
- void decrement() {
- if (node->leaf() && --position >= node->start()) {
- return;
- }
- decrement_slow();
+ : node_(other.node_), position_(other.position_) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ generation_ = other.generation_;
+#endif
}
- void decrement_slow();
- public:
bool operator==(const iterator &other) const {
- return node == other.node && position == other.position;
+ return node_ == other.node_ && position_ == other.position_;
}
bool operator==(const const_iterator &other) const {
- return node == other.node && position == other.position;
+ return node_ == other.node_ && position_ == other.position_;
}
bool operator!=(const iterator &other) const {
- return node != other.node || position != other.position;
+ return node_ != other.node_ || position_ != other.position_;
}
bool operator!=(const const_iterator &other) const {
- return node != other.node || position != other.position;
+ return node_ != other.node_ || position_ != other.position_;
}
// Accessors for the key/value the iterator is pointing at.
reference operator*() const {
- ABSL_HARDENING_ASSERT(node != nullptr);
- ABSL_HARDENING_ASSERT(node->start() <= position);
- ABSL_HARDENING_ASSERT(node->finish() > position);
- return node->value(position);
+ ABSL_HARDENING_ASSERT(node_ != nullptr);
+ ABSL_HARDENING_ASSERT(node_->start() <= position_);
+ ABSL_HARDENING_ASSERT(node_->finish() > position_);
+ assert_valid_generation();
+ return node_->value(position_);
}
pointer operator->() const { return &operator*(); }
@@ -1083,15 +1126,74 @@ struct btree_iterator {
friend class base_checker;
friend struct btree_access;
- const key_type &key() const { return node->key(position); }
- slot_type *slot() { return node->slot(position); }
+ // This SFINAE allows explicit conversions from const_iterator to
+ // iterator, but also avoids hiding the copy constructor.
+ // NOTE: the const_cast is safe because this constructor is only called by
+ // non-const methods and the container owns the nodes.
+ template <typename N, typename R, typename P,
+ absl::enable_if_t<
+ std::is_same<btree_iterator<N, R, P>, const_iterator>::value &&
+ std::is_same<btree_iterator, iterator>::value,
+ int> = 0>
+ explicit btree_iterator(const btree_iterator<N, R, P> other)
+ : node_(const_cast<node_type *>(other.node_)),
+ position_(other.position_) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ generation_ = other.generation_;
+#endif
+ }
+
+ // Increment/decrement the iterator.
+ void increment() {
+ assert_valid_generation();
+ if (node_->is_leaf() && ++position_ < node_->finish()) {
+ return;
+ }
+ increment_slow();
+ }
+ void increment_slow();
+
+ void decrement() {
+ assert_valid_generation();
+ if (node_->is_leaf() && --position_ >= node_->start()) {
+ return;
+ }
+ decrement_slow();
+ }
+ void decrement_slow();
+
+ // Updates the generation. For use internally right before we return an
+ // iterator to the user.
+ void update_generation() {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ if (node_ != nullptr) generation_ = node_->generation();
+#endif
+ }
+
+ const key_type &key() const { return node_->key(position_); }
+ slot_type *slot() { return node_->slot(position_); }
+
+ void assert_valid_generation() const {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ if (node_ != nullptr && node_->generation() != generation_) {
+ ABSL_INTERNAL_LOG(
+ FATAL,
+ "Attempting to use an invalidated iterator. The corresponding b-tree "
+ "container has been mutated since this iterator was constructed.");
+ }
+#endif
+ }
// The node in the tree the iterator is pointing at.
- Node *node;
+ Node *node_;
// The position within the node of the tree the iterator is pointing at.
// NOTE: this is an int rather than a field_type because iterators can point
// to invalid positions (such as -1) in certain circumstances.
- int position;
+ int position_;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ // Used to check that the iterator hasn't been invalidated.
+ uint32_t generation_;
+#endif
};
template <typename Params>
@@ -1106,6 +1208,9 @@ class btree {
struct alignas(node_type::Alignment()) EmptyNodeType : node_type {
using field_type = typename node_type::field_type;
node_type *parent;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ uint32_t generation = 0;
+#endif
field_type position = 0;
field_type start = 0;
field_type finish = 0;
@@ -1490,12 +1595,12 @@ class btree {
}
node_type *new_leaf_node(node_type *parent) {
node_type *n = allocate(node_type::LeafSize());
- n->init_leaf(parent, kNodeSlots);
+ n->init_leaf(kNodeSlots, parent);
return n;
}
node_type *new_leaf_root_node(const int max_count) {
node_type *n = allocate(node_type::LeafSize(max_count));
- n->init_leaf(/*parent=*/n, max_count);
+ n->init_leaf(max_count, /*parent=*/n);
return n;
}
@@ -1519,10 +1624,10 @@ class btree {
void try_shrink();
iterator internal_end(iterator iter) {
- return iter.node != nullptr ? iter : end();
+ return iter.node_ != nullptr ? iter : end();
}
const_iterator internal_end(const_iterator iter) const {
- return iter.node != nullptr ? iter : end();
+ return iter.node_ != nullptr ? iter : end();
}
// Emplaces a value into the btree immediately before iter. Requires that
@@ -1532,9 +1637,8 @@ class btree {
// Returns an iterator pointing to the first value >= the value "iter" is
// pointing at. Note that "iter" might be pointing to an invalid location such
- // as iter.position == iter.node->finish(). This routine simply moves iter up
- // in the tree to a valid location.
- // Requires: iter.node is non-null.
+ // as iter.position_ == iter.node_->finish(). This routine simply moves iter
+ // up in the tree to a valid location. Requires: iter.node_ is non-null.
template <typename IterType>
static IterType internal_last(IterType iter);
@@ -1570,7 +1674,7 @@ class btree {
if (node == nullptr || (node == root() && empty())) {
return node_stats(0, 0);
}
- if (node->leaf()) {
+ if (node->is_leaf()) {
return node_stats(1, 0);
}
node_stats res(0, 1);
@@ -1612,7 +1716,7 @@ inline void btree_node<P>::emplace_value(const size_type i,
value_init(i, alloc, std::forward<Args>(args)...);
set_finish(finish() + 1);
- if (!leaf() && finish() > i + 1) {
+ if (is_internal() && finish() > i + 1) {
for (field_type j = finish(); j > i + 1; --j) {
set_child(j, child(j - 1));
}
@@ -1630,7 +1734,7 @@ inline void btree_node<P>::remove_values(const field_type i,
const field_type src_i = i + to_erase;
transfer_n(orig_finish - src_i, i, src_i, this, alloc);
- if (!leaf()) {
+ if (is_internal()) {
// Delete all children between begin and end.
for (int j = 0; j < to_erase; ++j) {
clear_and_delete(child(i + j + 1), alloc);
@@ -1667,7 +1771,7 @@ void btree_node<P>::rebalance_right_to_left(const int to_move,
right->transfer_n(right->count() - to_move, right->start(),
right->start() + to_move, right, alloc);
- if (!leaf()) {
+ if (is_internal()) {
// Move the child pointers from the right to the left node.
for (int i = 0; i < to_move; ++i) {
init_child(finish() + i + 1, right->child(i));
@@ -1714,7 +1818,7 @@ void btree_node<P>::rebalance_left_to_right(const int to_move,
// 4) Move the new delimiting value to the parent from the left node.
parent()->transfer(position(), finish() - to_move, this, alloc);
- if (!leaf()) {
+ if (is_internal()) {
// Move the child pointers from the left to the right node.
for (int i = right->finish(); i >= right->start(); --i) {
right->init_child(i + to_move, right->child(i));
@@ -1760,7 +1864,7 @@ void btree_node<P>::split(const int insert_position, btree_node *dest,
value_destroy(finish(), alloc);
parent()->init_child(position() + 1, dest);
- if (!leaf()) {
+ if (is_internal()) {
for (int i = dest->start(), j = finish() + 1; i <= dest->finish();
++i, ++j) {
assert(child(j) != nullptr);
@@ -1781,7 +1885,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
// Move the values from the right to the left node.
transfer_n(src->count(), finish() + 1, src->start(), src, alloc);
- if (!leaf()) {
+ if (is_internal()) {
// Move the child pointers from the right to the left node.
for (int i = src->start(), j = finish() + 1; i <= src->finish(); ++i, ++j) {
init_child(j, src->child(i));
@@ -1799,7 +1903,7 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
template <typename P>
void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
- if (node->leaf()) {
+ if (node->is_leaf()) {
node->value_destroy_n(node->start(), node->count(), alloc);
deallocate(LeafSize(node->max_count()), node, alloc);
return;
@@ -1813,7 +1917,15 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
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();
+ while (node->is_internal()) node = node->start_child();
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ // When generations are enabled, we delete the leftmost leaf last in case it's
+ // the parent of the root and we need to check whether it's a leaf before we
+ // can update the root's generation.
+ // TODO(ezb): if we change btree_node::is_root to check a bool inside the node
+ // instead of checking whether the parent is a leaf, we can remove this logic.
+ btree_node *leftmost_leaf = node;
+#endif
// Use `int` because `pos` needs to be able to hold `kNodeSlots+1`, which
// isn't guaranteed to be a valid `field_type`.
int pos = node->position();
@@ -1823,14 +1935,17 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
assert(pos <= parent->finish());
do {
node = parent->child(pos);
- if (!node->leaf()) {
+ if (node->is_internal()) {
// Navigate to the leftmost leaf under node.
- while (!node->leaf()) node = node->start_child();
+ while (node->is_internal()) 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);
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ if (leftmost_leaf != node)
+#endif
+ deallocate(LeafSize(node->max_count()), node, alloc);
++pos;
} while (pos <= parent->finish());
@@ -1842,7 +1957,12 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
parent = node->parent();
node->value_destroy_n(node->start(), node->count(), alloc);
deallocate(InternalSize(), node, alloc);
- if (parent == delete_root_parent) return;
+ if (parent == delete_root_parent) {
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+ deallocate(LeafSize(leftmost_leaf->max_count()), leftmost_leaf, alloc);
+#endif
+ return;
+ }
++pos;
} while (pos > parent->finish());
}
@@ -1852,49 +1972,49 @@ void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
// btree_iterator methods
template <typename N, typename R, typename P>
void btree_iterator<N, R, P>::increment_slow() {
- if (node->leaf()) {
- assert(position >= node->finish());
+ if (node_->is_leaf()) {
+ assert(position_ >= node_->finish());
btree_iterator save(*this);
- while (position == node->finish() && !node->is_root()) {
- assert(node->parent()->child(node->position()) == node);
- position = node->position();
- node = node->parent();
+ while (position_ == node_->finish() && !node_->is_root()) {
+ assert(node_->parent()->child(node_->position()) == node_);
+ position_ = node_->position();
+ node_ = node_->parent();
}
// TODO(ezb): assert we aren't incrementing end() instead of handling.
- if (position == node->finish()) {
+ if (position_ == node_->finish()) {
*this = save;
}
} else {
- assert(position < node->finish());
- node = node->child(position + 1);
- while (!node->leaf()) {
- node = node->start_child();
+ assert(position_ < node_->finish());
+ node_ = node_->child(position_ + 1);
+ while (node_->is_internal()) {
+ node_ = node_->start_child();
}
- position = node->start();
+ position_ = node_->start();
}
}
template <typename N, typename R, typename P>
void btree_iterator<N, R, P>::decrement_slow() {
- if (node->leaf()) {
- assert(position <= -1);
+ if (node_->is_leaf()) {
+ assert(position_ <= -1);
btree_iterator save(*this);
- while (position < node->start() && !node->is_root()) {
- assert(node->parent()->child(node->position()) == node);
- position = node->position() - 1;
- node = node->parent();
+ while (position_ < node_->start() && !node_->is_root()) {
+ assert(node_->parent()->child(node_->position()) == node_);
+ position_ = node_->position() - 1;
+ node_ = node_->parent();
}
// TODO(ezb): assert we aren't decrementing begin() instead of handling.
- if (position < node->start()) {
+ if (position_ < node_->start()) {
*this = save;
}
} else {
- assert(position >= node->start());
- node = node->child(position);
- while (!node->leaf()) {
- node = node->child(node->finish());
+ assert(position_ >= node_->start());
+ node_ = node_->child(position_);
+ while (node_->is_internal()) {
+ node_ = node_->child(node_->finish());
}
- position = node->finish() - 1;
+ position_ = node_->finish() - 1;
}
}
@@ -2009,7 +2129,7 @@ auto btree<P>::insert_unique(const K &key, Args &&... args)
}
} else {
iterator last = internal_last(iter);
- if (last.node && !compare_keys(key, last.key())) {
+ if (last.node_ && !compare_keys(key, last.key())) {
// The key already exists in the tree, do nothing.
return {last, false};
}
@@ -2067,7 +2187,7 @@ auto btree<P>::insert_multi(const key_type &key, ValueType &&v) -> iterator {
}
iterator iter = internal_upper_bound(key);
- if (iter.node == nullptr) {
+ if (iter.node_ == nullptr) {
iter = end();
}
return internal_emplace(iter, std::forward<ValueType>(v));
@@ -2154,21 +2274,22 @@ auto btree<P>::operator=(btree &&other) noexcept -> btree & {
template <typename P>
auto btree<P>::erase(iterator iter) -> iterator {
bool internal_delete = false;
- if (!iter.node->leaf()) {
+ if (iter.node_->is_internal()) {
// Deletion of a value on an internal node. First, move the largest 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);
--iter;
- assert(iter.node->leaf());
- params_type::move(mutable_allocator(), iter.node->slot(iter.position),
- internal_iter.node->slot(internal_iter.position));
+ assert(iter.node_->is_leaf());
+ params_type::move(mutable_allocator(), iter.node_->slot(iter.position_),
+ internal_iter.node_->slot(internal_iter.position_));
internal_delete = true;
}
// Delete the key from the leaf.
- iter.node->remove_values(iter.position, /*to_erase=*/1, 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
@@ -2176,7 +2297,7 @@ auto btree<P>::erase(iterator iter) -> iterator {
// value is ++(++iter). If we erased from a leaf node (internal_delete ==
// false) then the next value is ++iter. Note that ++iter may point to an
// internal node and the value in the internal node may move to a leaf node
- // (iter.node) when rebalancing is performed at the leaf level.
+ // (iter.node_) when rebalancing is performed at the leaf level.
iterator res = rebalance_after_delete(iter);
@@ -2193,14 +2314,14 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
iterator res(iter);
bool first_iteration = true;
for (;;) {
- if (iter.node == root()) {
+ if (iter.node_ == root()) {
try_shrink();
if (empty()) {
return end();
}
break;
}
- if (iter.node->count() >= kMinNodeValues) {
+ if (iter.node_->count() >= kMinNodeValues) {
break;
}
bool merged = try_merge_or_rebalance(&iter);
@@ -2213,14 +2334,15 @@ auto btree<P>::rebalance_after_delete(iterator iter) -> iterator {
if (!merged) {
break;
}
- iter.position = iter.node->position();
- iter.node = iter.node->parent();
+ iter.position_ = iter.node_->position();
+ iter.node_ = iter.node_->parent();
}
+ res.update_generation();
// Adjust our return value. If we're pointing at the end of a node, advance
// the iterator.
- if (res.position == res.node->finish()) {
- res.position = res.node->finish() - 1;
+ if (res.position_ == res.node_->finish()) {
+ res.position_ = res.node_->finish() - 1;
++res;
}
@@ -2242,28 +2364,31 @@ auto btree<P>::erase_range(iterator begin, iterator end)
return {count, this->end()};
}
- if (begin.node == end.node) {
- assert(end.position > begin.position);
- begin.node->remove_values(begin.position, end.position - begin.position,
- mutable_allocator());
+ if (begin.node_ == end.node_) {
+ 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)};
}
const size_type target_size = size_ - count;
while (size_ > target_size) {
- if (begin.node->leaf()) {
+ if (begin.node_->is_leaf()) {
const size_type remaining_to_erase = size_ - target_size;
- const size_type remaining_in_node = begin.node->finish() - begin.position;
+ const size_type remaining_in_node =
+ begin.node_->finish() - begin.position_;
const size_type to_erase =
(std::min)(remaining_to_erase, remaining_in_node);
- begin.node->remove_values(begin.position, to_erase, mutable_allocator());
+ begin.node_->remove_values(begin.position_, to_erase,
+ mutable_allocator());
size_ -= to_erase;
begin = rebalance_after_delete(begin);
} else {
begin = erase(begin);
}
}
+ begin.update_generation();
return {count, begin};
}
@@ -2300,16 +2425,16 @@ void btree<P>::verify() const {
assert(leftmost() != nullptr);
assert(rightmost_ != nullptr);
assert(empty() || size() == internal_verify(root(), nullptr, nullptr));
- assert(leftmost() == (++const_iterator(root(), -1)).node);
- assert(rightmost_ == (--const_iterator(root(), root()->finish())).node);
- assert(leftmost()->leaf());
- assert(rightmost_->leaf());
+ assert(leftmost() == (++const_iterator(root(), -1)).node_);
+ assert(rightmost_ == (--const_iterator(root(), root()->finish())).node_);
+ assert(leftmost()->is_leaf());
+ assert(rightmost_->is_leaf());
}
template <typename P>
void btree<P>::rebalance_or_split(iterator *iter) {
- node_type *&node = iter->node;
- int &insert_position = iter->position;
+ node_type *&node = iter->node_;
+ int &insert_position = iter->position_;
assert(node->count() == node->max_count());
assert(kNodeSlots == node->max_count());
@@ -2384,16 +2509,17 @@ void btree<P>::rebalance_or_split(iterator *iter) {
// Create a new root node and set the current root node as the child of the
// new root.
parent = new_internal_node(parent);
+ parent->set_generation(root()->generation());
parent->init_child(parent->start(), root());
mutable_root() = parent;
// If the former root was a leaf node, then it's now the rightmost node.
- assert(!parent->start_child()->leaf() ||
+ assert(parent->start_child()->is_internal() ||
parent->start_child() == rightmost_);
}
// Split the node.
node_type *split_node;
- if (node->leaf()) {
+ if (node->is_leaf()) {
split_node = new_leaf_node(parent);
node->split(insert_position, split_node, mutable_allocator());
if (rightmost_ == node) rightmost_ = split_node;
@@ -2416,50 +2542,51 @@ void btree<P>::merge_nodes(node_type *left, node_type *right) {
template <typename P>
bool btree<P>::try_merge_or_rebalance(iterator *iter) {
- node_type *parent = iter->node->parent();
- if (iter->node->position() > parent->start()) {
+ node_type *parent = iter->node_->parent();
+ if (iter->node_->position() > parent->start()) {
// Try merging with our left sibling.
- node_type *left = parent->child(iter->node->position() - 1);
+ node_type *left = parent->child(iter->node_->position() - 1);
assert(left->max_count() == kNodeSlots);
- if (1U + left->count() + iter->node->count() <= kNodeSlots) {
- iter->position += 1 + left->count();
- merge_nodes(left, iter->node);
- iter->node = left;
+ if (1U + left->count() + iter->node_->count() <= kNodeSlots) {
+ iter->position_ += 1 + left->count();
+ merge_nodes(left, iter->node_);
+ iter->node_ = left;
return true;
}
}
- if (iter->node->position() < parent->finish()) {
+ if (iter->node_->position() < parent->finish()) {
// Try merging with our right sibling.
- node_type *right = parent->child(iter->node->position() + 1);
+ node_type *right = parent->child(iter->node_->position() + 1);
assert(right->max_count() == kNodeSlots);
- if (1U + iter->node->count() + right->count() <= kNodeSlots) {
- merge_nodes(iter->node, right);
+ if (1U + iter->node_->count() + right->count() <= kNodeSlots) {
+ merge_nodes(iter->node_, right);
return true;
}
// Try rebalancing with our right sibling. We don't perform rebalancing if
- // we deleted the first element from iter->node and the node is not
+ // we deleted the first element from iter->node_ and the node is not
// empty. This is a small optimization for the common pattern of deleting
// from the front of the tree.
if (right->count() > kMinNodeValues &&
- (iter->node->count() == 0 || iter->position > iter->node->start())) {
- int to_move = (right->count() - iter->node->count()) / 2;
+ (iter->node_->count() == 0 || iter->position_ > iter->node_->start())) {
+ int to_move = (right->count() - iter->node_->count()) / 2;
to_move = (std::min)(to_move, right->count() - 1);
- iter->node->rebalance_right_to_left(to_move, right, mutable_allocator());
+ iter->node_->rebalance_right_to_left(to_move, right, mutable_allocator());
return false;
}
}
- if (iter->node->position() > parent->start()) {
+ if (iter->node_->position() > parent->start()) {
// Try rebalancing with our left sibling. We don't perform rebalancing if
- // we deleted the last element from iter->node and the node is not
+ // we deleted the last element from iter->node_ and the node is not
// empty. This is a small optimization for the common pattern of deleting
// from the back of the tree.
- node_type *left = parent->child(iter->node->position() - 1);
+ node_type *left = parent->child(iter->node_->position() - 1);
if (left->count() > kMinNodeValues &&
- (iter->node->count() == 0 || iter->position < iter->node->finish())) {
- int to_move = (left->count() - iter->node->count()) / 2;
+ (iter->node_->count() == 0 ||
+ iter->position_ < iter->node_->finish())) {
+ int to_move = (left->count() - iter->node_->count()) / 2;
to_move = (std::min)(to_move, left->count() - 1);
- left->rebalance_left_to_right(to_move, iter->node, mutable_allocator());
- iter->position += to_move;
+ left->rebalance_left_to_right(to_move, iter->node_, mutable_allocator());
+ iter->position_ += to_move;
return false;
}
}
@@ -2473,7 +2600,7 @@ void btree<P>::try_shrink() {
return;
}
// Deleted the last item on the root node, shrink the height of the tree.
- if (orig_root->leaf()) {
+ if (orig_root->is_leaf()) {
assert(size() == 0);
mutable_root() = rightmost_ = EmptyNode();
} else {
@@ -2487,15 +2614,16 @@ void btree<P>::try_shrink() {
template <typename P>
template <typename IterType>
inline IterType btree<P>::internal_last(IterType iter) {
- assert(iter.node != nullptr);
- while (iter.position == iter.node->finish()) {
- iter.position = iter.node->position();
- iter.node = iter.node->parent();
- if (iter.node->leaf()) {
- iter.node = nullptr;
+ assert(iter.node_ != nullptr);
+ while (iter.position_ == iter.node_->finish()) {
+ iter.position_ = iter.node_->position();
+ iter.node_ = iter.node_->parent();
+ if (iter.node_->is_leaf()) {
+ iter.node_ = nullptr;
break;
}
}
+ iter.update_generation();
return iter;
}
@@ -2503,37 +2631,39 @@ template <typename P>
template <typename... Args>
inline auto btree<P>::internal_emplace(iterator iter, Args &&... args)
-> iterator {
- if (!iter.node->leaf()) {
+ if (iter.node_->is_internal()) {
// We can't insert on an internal node. Instead, we'll insert after the
// previous value which is guaranteed to be on a leaf node.
--iter;
- ++iter.position;
+ ++iter.position_;
}
- const field_type max_count = iter.node->max_count();
+ const field_type max_count = iter.node_->max_count();
allocator_type *alloc = mutable_allocator();
- if (iter.node->count() == max_count) {
+ if (iter.node_->count() == max_count) {
// Make room in the leaf for the new item.
if (max_count < kNodeSlots) {
// Insertion into the root where the root is smaller than the full node
// size. Simply grow the size of the root node.
- assert(iter.node == root());
- iter.node =
+ assert(iter.node_ == root());
+ iter.node_ =
new_leaf_root_node((std::min<int>)(kNodeSlots, 2 * max_count));
// Transfer the values from the old root to the new root.
node_type *old_root = root();
- node_type *new_root = iter.node;
+ node_type *new_root = iter.node_;
new_root->transfer_n(old_root->count(), new_root->start(),
old_root->start(), old_root, alloc);
new_root->set_finish(old_root->finish());
old_root->set_finish(old_root->start());
+ new_root->set_generation(old_root->generation());
node_type::clear_and_delete(old_root, alloc);
mutable_root() = rightmost_ = new_root;
} else {
rebalance_or_split(&iter);
}
}
- iter.node->emplace_value(iter.position, alloc, std::forward<Args>(args)...);
+ iter.node_->emplace_value(iter.position_, alloc, std::forward<Args>(args)...);
++size_;
+ iter.update_generation();
return iter;
}
@@ -2544,8 +2674,8 @@ inline auto btree<P>::internal_locate(const K &key) const
iterator iter(const_cast<node_type *>(root()));
for (;;) {
SearchResult<int, is_key_compare_to::value> res =
- iter.node->lower_bound(key, key_comp());
- iter.position = res.value;
+ iter.node_->lower_bound(key, key_comp());
+ iter.position_ = res.value;
if (res.IsEq()) {
return {iter, MatchKind::kEq};
}
@@ -2553,10 +2683,10 @@ inline auto btree<P>::internal_locate(const K &key) const
// down the tree if the keys are equal, but determining equality would
// require doing an extra comparison on each node on the way down, and we
// will need to go all the way to the leaf node in the expected case.
- if (iter.node->leaf()) {
+ if (iter.node_->is_leaf()) {
break;
}
- iter.node = iter.node->child(iter.position);
+ iter.node_ = iter.node_->child(iter.position_);
}
// Note: in the non-key-compare-to case, the key may actually be equivalent
// here (and the MatchKind::kNe is ignored).
@@ -2576,13 +2706,13 @@ auto btree<P>::internal_lower_bound(const K &key) const
SearchResult<int, is_key_compare_to::value> res;
bool seen_eq = false;
for (;;) {
- res = iter.node->lower_bound(key, key_comp());
- iter.position = res.value;
- if (iter.node->leaf()) {
+ res = iter.node_->lower_bound(key, key_comp());
+ iter.position_ = res.value;
+ if (iter.node_->is_leaf()) {
break;
}
seen_eq = seen_eq || res.IsEq();
- iter.node = iter.node->child(iter.position);
+ iter.node_ = iter.node_->child(iter.position_);
}
if (res.IsEq()) return {iter, MatchKind::kEq};
return {internal_last(iter), seen_eq ? MatchKind::kEq : MatchKind::kNe};
@@ -2593,11 +2723,11 @@ template <typename K>
auto btree<P>::internal_upper_bound(const K &key) const -> iterator {
iterator iter(const_cast<node_type *>(root()));
for (;;) {
- iter.position = iter.node->upper_bound(key, key_comp());
- if (iter.node->leaf()) {
+ iter.position_ = iter.node_->upper_bound(key, key_comp());
+ if (iter.node_->is_leaf()) {
break;
}
- iter.node = iter.node->child(iter.position);
+ iter.node_ = iter.node_->child(iter.position_);
}
return internal_last(iter);
}
@@ -2612,7 +2742,7 @@ auto btree<P>::internal_find(const K &key) const -> iterator {
}
} else {
const iterator iter = internal_last(res.value);
- if (iter.node != nullptr && !compare_keys(key, iter.key())) {
+ if (iter.node_ != nullptr && !compare_keys(key, iter.key())) {
return iter;
}
}
@@ -2634,7 +2764,7 @@ int btree<P>::internal_verify(const node_type *node, const key_type *lo,
assert(!compare_keys(node->key(i), node->key(i - 1)));
}
int count = node->count();
- if (!node->leaf()) {
+ if (node->is_internal()) {
for (int i = node->start(); i <= node->finish(); ++i) {
assert(node->child(i) != nullptr);
assert(node->child(i)->parent() == node);
@@ -2659,8 +2789,8 @@ struct btree_access {
++it;
continue;
}
- auto *node = it.node;
- if (!node->leaf()) {
+ auto *node = it.node_;
+ if (node->is_internal()) {
// Handle internal nodes normally.
it = container.erase(it);
continue;
@@ -2669,26 +2799,28 @@ struct btree_access {
// at once before doing rebalancing.
// The current position to transfer slots to.
- int to_pos = it.position;
- node->value_destroy(it.position, alloc);
- while (++it.position < node->finish()) {
+ int to_pos = it.position_;
+ node->value_destroy(it.position_, alloc);
+ while (++it.position_ < node->finish()) {
+ it.update_generation();
if (pred(*it)) {
- node->value_destroy(it.position, alloc);
+ node->value_destroy(it.position_, alloc);
} else {
- node->transfer(node->slot(to_pos++), node->slot(it.position),
- alloc);
+ node->transfer(node->slot(to_pos++), node->slot(it.position_), alloc);
}
}
const int num_deleted = node->finish() - to_pos;
tree.size_ -= num_deleted;
node->set_finish(to_pos);
- it.position = to_pos;
+ it.position_ = to_pos;
it = tree.rebalance_after_delete(it);
}
return initial_size - container.size();
}
};
+#undef ABSL_BTREE_ENABLE_GENERATIONS
+
} // namespace container_internal
ABSL_NAMESPACE_END
} // namespace absl
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index bae5c6e2..cc2e1793 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -537,6 +537,7 @@ class btree_multiset_container : public btree_container<Tree> {
using params_type = typename Tree::params_type;
using init_type = typename params_type::init_type;
using is_key_compare_to = typename params_type::is_key_compare_to;
+ friend class BtreeNodePeer;
template <class K>
using key_arg = typename super_type::template key_arg<K>;
@@ -668,6 +669,7 @@ template <typename Tree>
class btree_multimap_container : public btree_multiset_container<Tree> {
using super_type = btree_multiset_container<Tree>;
using params_type = typename Tree::params_type;
+ friend class BtreeNodePeer;
public:
using mapped_type = typename params_type::mapped_type;
diff --git a/absl/random/mocking_bit_gen.h b/absl/random/mocking_bit_gen.h
index 7b2b80eb..89fa5a47 100644
--- a/absl/random/mocking_bit_gen.h
+++ b/absl/random/mocking_bit_gen.h
@@ -87,7 +87,7 @@ class BitGenRef;
//
// ON_CALL(absl::MockUniform<int>(), Call(bitgen, testing::_, testing::_))
// .WillByDefault([] (int low, int high) {
-// return (low + high) / 2;
+// return low + (high - low) / 2;
// });
//
// EXPECT_EQ(absl::Uniform<int>(gen, 0, 10), 5);
diff --git a/absl/strings/BUILD.bazel b/absl/strings/BUILD.bazel
index 617577cd..129affec 100644
--- a/absl/strings/BUILD.bazel
+++ b/absl/strings/BUILD.bazel
@@ -271,7 +271,6 @@ cc_library(
"internal/cord_rep_btree.cc",
"internal/cord_rep_btree_navigator.cc",
"internal/cord_rep_btree_reader.cc",
- "internal/cord_rep_concat.cc",
"internal/cord_rep_consume.cc",
"internal/cord_rep_crc.cc",
"internal/cord_rep_ring.cc",
diff --git a/absl/strings/CMakeLists.txt b/absl/strings/CMakeLists.txt
index e73a1ea0..f31eef4d 100644
--- a/absl/strings/CMakeLists.txt
+++ b/absl/strings/CMakeLists.txt
@@ -568,7 +568,6 @@ absl_cc_library(
"internal/cord_rep_btree.cc"
"internal/cord_rep_btree_navigator.cc"
"internal/cord_rep_btree_reader.cc"
- "internal/cord_rep_concat.cc"
"internal/cord_rep_crc.cc"
"internal/cord_rep_consume.cc"
"internal/cord_rep_ring.cc"
diff --git a/absl/strings/cord.cc b/absl/strings/cord.cc
index 59722107..4ee722da 100644
--- a/absl/strings/cord.cc
+++ b/absl/strings/cord.cc
@@ -53,7 +53,6 @@ ABSL_NAMESPACE_BEGIN
using ::absl::cord_internal::CordRep;
using ::absl::cord_internal::CordRepBtree;
-using ::absl::cord_internal::CordRepConcat;
using ::absl::cord_internal::CordRepCrc;
using ::absl::cord_internal::CordRepExternal;
using ::absl::cord_internal::CordRepFlat;
@@ -66,53 +65,6 @@ using ::absl::cord_internal::kMinFlatLength;
using ::absl::cord_internal::kInlinedVectorSize;
using ::absl::cord_internal::kMaxBytesToCopy;
-constexpr uint64_t Fibonacci(unsigned char n, uint64_t a = 0, uint64_t b = 1) {
- return n == 0 ? a : Fibonacci(n - 1, b, a + b);
-}
-
-static_assert(Fibonacci(63) == 6557470319842,
- "Fibonacci values computed incorrectly");
-
-// Minimum length required for a given depth tree -- a tree is considered
-// balanced if
-// length(t) >= min_length[depth(t)]
-// The root node depth is allowed to become twice as large to reduce rebalancing
-// for larger strings (see IsRootBalanced).
-static constexpr uint64_t min_length[] = {
- Fibonacci(2), Fibonacci(3), Fibonacci(4), Fibonacci(5),
- Fibonacci(6), Fibonacci(7), Fibonacci(8), Fibonacci(9),
- Fibonacci(10), Fibonacci(11), Fibonacci(12), Fibonacci(13),
- Fibonacci(14), Fibonacci(15), Fibonacci(16), Fibonacci(17),
- Fibonacci(18), Fibonacci(19), Fibonacci(20), Fibonacci(21),
- Fibonacci(22), Fibonacci(23), Fibonacci(24), Fibonacci(25),
- Fibonacci(26), Fibonacci(27), Fibonacci(28), Fibonacci(29),
- Fibonacci(30), Fibonacci(31), Fibonacci(32), Fibonacci(33),
- Fibonacci(34), Fibonacci(35), Fibonacci(36), Fibonacci(37),
- Fibonacci(38), Fibonacci(39), Fibonacci(40), Fibonacci(41),
- Fibonacci(42), Fibonacci(43), Fibonacci(44), Fibonacci(45),
- Fibonacci(46), Fibonacci(47),
- 0xffffffffffffffffull, // Avoid overflow
-};
-
-static const int kMinLengthSize = ABSL_ARRAYSIZE(min_length);
-
-static inline constexpr bool btree_enabled() { return true; }
-
-static inline bool IsRootBalanced(CordRep* node) {
- if (!node->IsConcat()) {
- return true;
- } else if (node->concat()->depth() <= 15) {
- return true;
- } else if (node->concat()->depth() > kMinLengthSize) {
- return false;
- } else {
- // Allow depth to become twice as large as implied by fibonacci rule to
- // reduce rebalancing for larger strings.
- return (node->length >= min_length[node->concat()->depth() / 2]);
- }
-}
-
-static CordRep* Rebalance(CordRep* node);
static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
int indent = 0);
static bool VerifyNode(CordRep* root, CordRep* start_node,
@@ -134,24 +86,6 @@ static inline CordRep* VerifyTree(CordRep* node) {
return node;
}
-// Return the depth of a node
-static int Depth(const CordRep* rep) {
- if (rep->IsConcat()) {
- return rep->concat()->depth();
- } else {
- return 0;
- }
-}
-
-static void SetConcatChildren(CordRepConcat* concat, CordRep* left,
- CordRep* right) {
- concat->left = left;
- concat->right = right;
-
- concat->length = left->length + right->length;
- concat->set_depth(1 + std::max(Depth(left), Depth(right)));
-}
-
// Create a concatenation of the specified nodes.
// Does not change the refcounts of "left" and "right".
// The returned node has a refcount of 1.
@@ -167,42 +101,15 @@ static CordRep* RawConcat(CordRep* left, CordRep* right) {
CordRep::Unref(right);
return left;
}
-
- CordRepConcat* rep = new CordRepConcat();
- rep->tag = cord_internal::CONCAT;
- SetConcatChildren(rep, left, right);
-
- return rep;
+ ABSL_INTERNAL_LOG(FATAL, "CordRepConcat is no longer supported");
+ return nullptr;
}
static CordRep* Concat(CordRep* left, CordRep* right) {
CordRep* rep = RawConcat(left, right);
- if (rep != nullptr && !IsRootBalanced(rep)) {
- rep = Rebalance(rep);
- }
return VerifyTree(rep);
}
-// Make a balanced tree out of an array of leaf nodes.
-static CordRep* MakeBalancedTree(CordRep** reps, size_t n) {
- // Make repeated passes over the array, merging adjacent pairs
- // until we are left with just a single node.
- while (n > 1) {
- size_t dst = 0;
- for (size_t src = 0; src < n; src += 2) {
- if (src + 1 < n) {
- reps[dst] = Concat(reps[src], reps[src + 1]);
- } else {
- reps[dst] = reps[src];
- }
- dst++;
- }
- n = dst;
- }
-
- return reps[0];
-}
-
static CordRepFlat* CreateFlat(const char* data, size_t length,
size_t alloc_hint) {
CordRepFlat* flat = CordRepFlat::New(length + alloc_hint);
@@ -228,21 +135,7 @@ static CordRep* NewBtree(const char* data, size_t length, size_t alloc_hint) {
// The returned node has a refcount of 1.
static CordRep* NewTree(const char* data, size_t length, size_t alloc_hint) {
if (length == 0) return nullptr;
- if (btree_enabled()) {
- return NewBtree(data, length, alloc_hint);
- }
- absl::FixedArray<CordRep*> reps((length - 1) / kMaxFlatLength + 1);
- size_t n = 0;
- do {
- const size_t len = std::min(length, kMaxFlatLength);
- CordRepFlat* rep = CordRepFlat::New(len + alloc_hint);
- rep->length = len;
- memcpy(rep->Data(), data, len);
- reps[n++] = VerifyTree(rep);
- data += len;
- length -= len;
- } while (length != 0);
- return MakeBalancedTree(reps.data(), n);
+ return NewBtree(data, length, alloc_hint);
}
namespace cord_internal {
@@ -350,11 +243,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
assert(!is_tree());
if (!data_.is_empty()) {
CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
- if (btree_enabled()) {
- tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
- } else {
- tree = Concat(flat, tree);
- }
+ tree = CordRepBtree::Append(CordRepBtree::Create(flat), tree);
}
EmplaceTree(tree, method);
}
@@ -362,11 +251,7 @@ void Cord::InlineRep::AppendTreeToInlined(CordRep* tree,
void Cord::InlineRep::AppendTreeToTree(CordRep* tree, MethodIdentifier method) {
assert(is_tree());
const CordzUpdateScope scope(data_.cordz_info(), method);
- if (btree_enabled()) {
- tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
- } else {
- tree = Concat(cord_internal::RemoveCrcNode(data_.as_tree()), tree);
- }
+ tree = CordRepBtree::Append(ForceBtree(data_.as_tree()), tree);
SetTree(tree, scope);
}
@@ -386,11 +271,7 @@ void Cord::InlineRep::PrependTreeToInlined(CordRep* tree,
assert(!is_tree());
if (!data_.is_empty()) {
CordRepFlat* flat = MakeFlatWithExtraCapacity(0);
- if (btree_enabled()) {
- tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
- } else {
- tree = Concat(tree, flat);
- }
+ tree = CordRepBtree::Prepend(CordRepBtree::Create(flat), tree);
}
EmplaceTree(tree, method);
}
@@ -399,11 +280,7 @@ void Cord::InlineRep::PrependTreeToTree(CordRep* tree,
MethodIdentifier method) {
assert(is_tree());
const CordzUpdateScope scope(data_.cordz_info(), method);
- if (btree_enabled()) {
- tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
- } else {
- tree = Concat(tree, cord_internal::RemoveCrcNode(data_.as_tree()));
- }
+ tree = CordRepBtree::Prepend(ForceBtree(data_.as_tree()), tree);
SetTree(tree, scope);
}
@@ -433,12 +310,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
}
}
- // Search down the right-hand path for a non-full FLAT node.
CordRep* dst = root;
- while (dst->IsConcat() && dst->refcount.IsOne()) {
- dst = dst->concat()->right;
- }
-
if (!dst->IsFlat() || !dst->refcount.IsOne()) {
*region = nullptr;
*size = 0;
@@ -453,12 +325,7 @@ static inline bool PrepareAppendRegion(CordRep* root, char** region,
return false;
}
- size_t size_increase = std::min(capacity - in_use, max_length);
-
- // We need to update the length fields for all nodes, including the leaf node.
- for (CordRep* rep = root; rep != dst; rep = rep->concat()->right) {
- rep->length += size_increase;
- }
+ const size_t size_increase = std::min(capacity - in_use, max_length);
dst->length += size_increase;
*region = dst->flat()->Data() + in_use;
@@ -627,27 +494,11 @@ void Cord::InlineRep::AppendArray(absl::string_view src,
return;
}
- if (btree_enabled()) {
- // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
- rep = ForceBtree(rep);
- const size_t min_growth = std::max<size_t>(rep->length / 10, src.size());
- rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size());
- } else {
- // Use new block(s) for any remaining bytes that were not handled above.
- // Alloc extra memory only if the right child of the root of the new tree
- // is going to be a FLAT node, which will permit further inplace appends.
- size_t length = src.size();
- if (src.size() < kMaxFlatLength) {
- // The new length is either
- // - old size + 10%
- // - old_size + src.size()
- // This will cause a reasonable conservative step-up in size that is
- // still large enough to avoid excessive amounts of small fragments
- // being added.
- length = std::max<size_t>(rep->length / 10, src.size());
- }
- rep = Concat(rep, NewTree(src.data(), src.size(), length - src.size()));
- }
+ // TODO(b/192061034): keep legacy 10% growth rate: consider other rates.
+ rep = ForceBtree(rep);
+ const size_t min_growth = std::max<size_t>(rep->length / 10, src.size());
+ rep = CordRepBtree::Append(rep->btree(), src, min_growth - src.size());
+
CommitTree(root, rep, scope, method);
}
@@ -779,18 +630,6 @@ static CordRep* RemovePrefixFrom(CordRep* node, size_t n) {
absl::InlinedVector<CordRep*, kInlinedVectorSize> rhs_stack;
assert(!node->IsCrc());
- while (node->IsConcat()) {
- assert(n <= node->length);
- if (n < node->concat()->left->length) {
- // Push right to stack, descend left.
- rhs_stack.push_back(node->concat()->right);
- node = node->concat()->left;
- } else {
- // Drop left, descend right.
- n -= node->concat()->left->length;
- node = node->concat()->right;
- }
- }
assert(n <= node->length);
if (n == 0) {
@@ -822,19 +661,6 @@ static CordRep* RemoveSuffixFrom(CordRep* node, size_t n) {
bool inplace_ok = node->refcount.IsOne();
assert(!node->IsCrc());
- while (node->IsConcat()) {
- assert(n <= node->length);
- if (n < node->concat()->right->length) {
- // Push left to stack, descend right.
- lhs_stack.push_back(node->concat()->left);
- node = node->concat()->right;
- } else {
- // Drop right, descend left.
- n -= node->concat()->right->length;
- node = node->concat()->left;
- }
- inplace_ok = inplace_ok && node->refcount.IsOne();
- }
assert(n <= node->length);
if (n == 0) {
@@ -936,22 +762,12 @@ static CordRep* NewSubRange(CordRep* node, size_t pos, size_t n) {
results.push_back(Concat(left, right));
} else if (pos == 0 && n == node->length) {
results.push_back(CordRep::Ref(node));
- } else if (!node->IsConcat()) {
+ } else {
if (node->IsSubstring()) {
pos += node->substring()->start;
node = node->substring()->child;
}
results.push_back(NewSubstring(CordRep::Ref(node), pos, n));
- } else if (pos + n <= node->concat()->left->length) {
- todo.push_back(SubRange(node->concat()->left, pos, n));
- } else if (pos >= node->concat()->left->length) {
- pos -= node->concat()->left->length;
- todo.push_back(SubRange(node->concat()->right, pos, n));
- } else {
- size_t left_n = node->concat()->left->length - pos;
- todo.push_back(SubRange(nullptr, 0, 0)); // Concat()
- todo.push_back(SubRange(node->concat()->right, 0, n - left_n));
- todo.push_back(SubRange(node->concat()->left, pos, left_n));
}
} while (!todo.empty());
assert(results.size() == 1);
@@ -999,147 +815,6 @@ Cord Cord::Subcord(size_t pos, size_t new_size) const {
}
// --------------------------------------------------------------------
-// Balancing
-
-class CordForest {
- public:
- explicit CordForest(size_t length)
- : root_length_(length), trees_(kMinLengthSize, nullptr) {}
-
- void Build(CordRep* cord_root) {
- std::vector<CordRep*> pending = {cord_root};
- assert(cord_root->IsConcat());
-
- while (!pending.empty()) {
- CordRep* node = pending.back();
- pending.pop_back();
- CheckNode(node);
- if (ABSL_PREDICT_FALSE(!node->IsConcat())) {
- AddNode(node);
- continue;
- }
-
- CordRepConcat* concat_node = node->concat();
- if (concat_node->depth() >= kMinLengthSize ||
- concat_node->length < min_length[concat_node->depth()]) {
- pending.push_back(concat_node->right);
- pending.push_back(concat_node->left);
-
- if (concat_node->refcount.IsOne()) {
- concat_node->left = concat_freelist_;
- concat_freelist_ = concat_node;
- } else {
- CordRep::Ref(concat_node->right);
- CordRep::Ref(concat_node->left);
- CordRep::Unref(concat_node);
- }
- } else {
- AddNode(node);
- }
- }
- }
-
- CordRep* ConcatNodes() {
- CordRep* sum = nullptr;
- for (auto* node : trees_) {
- if (node == nullptr) continue;
-
- sum = PrependNode(node, sum);
- root_length_ -= node->length;
- if (root_length_ == 0) break;
- }
- ABSL_INTERNAL_CHECK(sum != nullptr, "Failed to locate sum node");
- return VerifyTree(sum);
- }
-
- private:
- CordRep* AppendNode(CordRep* node, CordRep* sum) {
- return (sum == nullptr) ? node : MakeConcat(sum, node);
- }
-
- CordRep* PrependNode(CordRep* node, CordRep* sum) {
- return (sum == nullptr) ? node : MakeConcat(node, sum);
- }
-
- void AddNode(CordRep* node) {
- CordRep* sum = nullptr;
-
- // Collect together everything with which we will merge with node
- int i = 0;
- for (; node->length > min_length[i + 1]; ++i) {
- auto& tree_at_i = trees_[i];
-
- if (tree_at_i == nullptr) continue;
- sum = PrependNode(tree_at_i, sum);
- tree_at_i = nullptr;
- }
-
- sum = AppendNode(node, sum);
-
- // Insert sum into appropriate place in the forest
- for (; sum->length >= min_length[i]; ++i) {
- auto& tree_at_i = trees_[i];
- if (tree_at_i == nullptr) continue;
-
- sum = MakeConcat(tree_at_i, sum);
- tree_at_i = nullptr;
- }
-
- // min_length[0] == 1, which means sum->length >= min_length[0]
- assert(i > 0);
- trees_[i - 1] = sum;
- }
-
- // Make concat node trying to resue existing CordRepConcat nodes we
- // already collected in the concat_freelist_.
- CordRep* MakeConcat(CordRep* left, CordRep* right) {
- if (concat_freelist_ == nullptr) return RawConcat(left, right);
-
- CordRepConcat* rep = concat_freelist_;
- if (concat_freelist_->left == nullptr) {
- concat_freelist_ = nullptr;
- } else {
- concat_freelist_ = concat_freelist_->left->concat();
- }
- SetConcatChildren(rep, left, right);
-
- return rep;
- }
-
- static void CheckNode(CordRep* node) {
- ABSL_INTERNAL_CHECK(node->length != 0u, "");
- if (node->IsConcat()) {
- ABSL_INTERNAL_CHECK(node->concat()->left != nullptr, "");
- ABSL_INTERNAL_CHECK(node->concat()->right != nullptr, "");
- ABSL_INTERNAL_CHECK(node->length == (node->concat()->left->length +
- node->concat()->right->length),
- "");
- }
- }
-
- size_t root_length_;
-
- // use an inlined vector instead of a flat array to get bounds checking
- absl::InlinedVector<CordRep*, kInlinedVectorSize> trees_;
-
- // List of concat nodes we can re-use for Cord balancing.
- CordRepConcat* concat_freelist_ = nullptr;
-};
-
-static CordRep* Rebalance(CordRep* node) {
- VerifyTree(node);
- assert(node->IsConcat());
-
- if (node->length == 0) {
- return nullptr;
- }
-
- CordForest forest(node->length);
- forest.Build(node);
- return forest.ConcatNodes();
-}
-
-// --------------------------------------------------------------------
// Comparators
namespace {
@@ -1203,11 +878,6 @@ inline absl::string_view Cord::InlineRep::FindFlatStartPiece() const {
return tree->Data(tree->begin());
}
- // Walk down the left branches until we hit a non-CONCAT node.
- while (node->IsConcat()) {
- node = node->concat()->left;
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1436,13 +1106,6 @@ Cord::ChunkIterator& Cord::ChunkIterator::AdvanceStack() {
CordRep* node = stack_of_right_children.back();
stack_of_right_children.pop_back();
- // Walk down the left branches until we hit a non-CONCAT node. Save the
- // right children to the stack for subsequent traversal.
- while (node->IsConcat()) {
- stack_of_right_children.push_back(node->concat()->right);
- node = node->concat()->left;
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1557,22 +1220,6 @@ Cord Cord::ChunkIterator::AdvanceAndReadBytes(size_t n) {
return subcord;
}
- // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
- // right children to the stack for subsequent traversal.
- while (node->IsConcat()) {
- if (node->concat()->left->length > n) {
- // Push right, descend left.
- stack_of_right_children.push_back(node->concat()->right);
- node = node->concat()->left;
- } else {
- // Read left, descend right.
- subnode = Concat(subnode, CordRep::Ref(node->concat()->left));
- n -= node->concat()->left->length;
- bytes_remaining_ -= node->concat()->left->length;
- node = node->concat()->right;
- }
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1630,21 +1277,6 @@ void Cord::ChunkIterator::AdvanceBytesSlowPath(size_t n) {
return;
}
- // Walk down the appropriate branches until we hit a non-CONCAT node. Save the
- // right children to the stack for subsequent traversal.
- while (node->IsConcat()) {
- if (node->concat()->left->length > n) {
- // Push right, descend left.
- stack_of_right_children.push_back(node->concat()->right);
- node = node->concat()->left;
- } else {
- // Skip left, descend right.
- n -= node->concat()->left->length;
- bytes_remaining_ -= node->concat()->left->length;
- node = node->concat()->right;
- }
- }
-
// Get the child node if we encounter a SUBSTRING.
size_t offset = 0;
size_t length = node->length;
@@ -1681,16 +1313,6 @@ char Cord::operator[](size_t i) const {
} else if (rep->IsExternal()) {
// Get the "i"th character from the external array.
return rep->external()->base[offset];
- } else if (rep->IsConcat()) {
- // Recursively branch to the side of the concatenation that the "i"th
- // character is on.
- size_t left_length = rep->concat()->left->length;
- if (offset < left_length) {
- rep = rep->concat()->left;
- } else {
- offset -= left_length;
- rep = rep->concat()->right;
- }
} else {
// This must be a substring a node, so bypass it to get to the child.
assert(rep->IsSubstring());
@@ -1772,43 +1394,13 @@ absl::string_view Cord::FlattenSlowPath() {
return;
}
- int stack_pos = 0;
- constexpr int stack_max = 128;
- // Stack of right branches for tree traversal
- absl::cord_internal::CordRep* stack[stack_max];
+ // This is a leaf node, so invoke our callback.
absl::cord_internal::CordRep* current_node = cord_internal::SkipCrcNode(rep);
- while (true) {
- if (current_node->IsConcat()) {
- if (stack_pos == stack_max) {
- // There's no more room on our stack array to add another right branch,
- // and the idea is to avoid allocations, so call this function
- // recursively to navigate this subtree further. (This is not something
- // we expect to happen in practice).
- ForEachChunkAux(current_node, callback);
-
- // Pop the next right branch and iterate.
- current_node = stack[--stack_pos];
- continue;
- } else {
- // Save the right branch for later traversal and continue down the left
- // branch.
- stack[stack_pos++] = current_node->concat()->right;
- current_node = current_node->concat()->left;
- continue;
- }
- }
- // This is a leaf node, so invoke our callback.
- absl::string_view chunk;
- bool success = GetFlatAux(current_node, &chunk);
- assert(success);
- if (success) {
- callback(chunk);
- }
- if (stack_pos == 0) {
- // end of traversal
- return;
- }
- current_node = stack[--stack_pos];
+ absl::string_view chunk;
+ bool success = GetFlatAux(current_node, &chunk);
+ assert(success);
+ if (success) {
+ callback(chunk);
}
}
@@ -1823,18 +1415,11 @@ static void DumpNode(CordRep* rep, bool include_data, std::ostream* os,
*os << " [";
if (include_data) *os << static_cast<void*>(rep);
*os << "]";
- *os << " " << (IsRootBalanced(rep) ? 'b' : 'u');
*os << " " << std::setw(indent) << "";
if (rep->IsCrc()) {
*os << "CRC crc=" << rep->crc()->crc << "\n";
indent += kIndentStep;
rep = rep->crc()->child;
- } else if (rep->IsConcat()) {
- *os << "CONCAT depth=" << Depth(rep) << "\n";
- indent += kIndentStep;
- indents.push_back(indent);
- stack.push_back(rep->concat()->right);
- rep = rep->concat()->left;
} else if (rep->IsSubstring()) {
*os << "SUBSTRING @ " << rep->substring()->start << "\n";
indent += kIndentStep;
@@ -1871,7 +1456,7 @@ static std::string ReportError(CordRep* root, CordRep* node) {
}
static bool VerifyNode(CordRep* root, CordRep* start_node,
- bool full_validation) {
+ bool /* full_validation */) {
absl::InlinedVector<CordRep*, 2> worklist;
worklist.push_back(start_node);
do {
@@ -1884,19 +1469,7 @@ static bool VerifyNode(CordRep* root, CordRep* start_node,
ABSL_INTERNAL_CHECK(!node->IsCrc(), ReportError(root, node));
}
- if (node->IsConcat()) {
- ABSL_INTERNAL_CHECK(node->concat()->left != nullptr,
- ReportError(root, node));
- ABSL_INTERNAL_CHECK(node->concat()->right != nullptr,
- ReportError(root, node));
- ABSL_INTERNAL_CHECK((node->length == node->concat()->left->length +
- node->concat()->right->length),
- ReportError(root, node));
- if (full_validation) {
- worklist.push_back(node->concat()->right);
- worklist.push_back(node->concat()->left);
- }
- } else if (node->IsFlat()) {
+ if (node->IsFlat()) {
ABSL_INTERNAL_CHECK(node->length <= node->flat()->Capacity(),
ReportError(root, node));
} else if (node->IsExternal()) {
@@ -1937,7 +1510,6 @@ uint8_t CordTestAccess::LengthToTag(size_t s) {
ABSL_INTERNAL_CHECK(s <= kMaxFlatLength, absl::StrCat("Invalid length ", s));
return cord_internal::AllocatedSizeToTag(s + cord_internal::kFlatOverhead);
}
-size_t CordTestAccess::SizeofCordRepConcat() { return sizeof(CordRepConcat); }
size_t CordTestAccess::SizeofCordRepExternal() {
return sizeof(CordRepExternal);
}
diff --git a/absl/strings/cord.h b/absl/strings/cord.h
index 49d51da2..7f34ef48 100644
--- a/absl/strings/cord.h
+++ b/absl/strings/cord.h
@@ -1553,7 +1553,6 @@ class CordTestAccess {
public:
static size_t FlatOverhead();
static size_t MaxFlatLength();
- static size_t SizeofCordRepConcat();
static size_t SizeofCordRepExternal();
static size_t SizeofCordRepSubstring();
static size_t FlatTagToLength(uint8_t tag);
diff --git a/absl/strings/cord_analysis.cc b/absl/strings/cord_analysis.cc
index c0d9ea79..3fa15b01 100644
--- a/absl/strings/cord_analysis.cc
+++ b/absl/strings/cord_analysis.cc
@@ -128,45 +128,6 @@ void AnalyzeDataEdge(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
raw_usage.Add(size, rep);
}
-// Computes the memory size of the provided Concat tree.
-template <Mode mode>
-void AnalyzeConcat(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
- absl::InlinedVector<CordRepRef<mode>, 47> pending;
-
- while (rep.rep != nullptr) {
- const CordRepConcat* concat = rep.rep->concat();
- CordRepRef<mode> left = rep.Child(concat->left);
- CordRepRef<mode> right = rep.Child(concat->right);
-
- raw_usage.Add(sizeof(CordRepConcat), rep);
-
- switch ((IsDataEdge(left.rep) ? 1 : 0) | (IsDataEdge(right.rep) ? 2 : 0)) {
- case 0: // neither left or right are data edges
- rep = left;
- pending.push_back(right);
- break;
- case 1: // only left is a data edge
- AnalyzeDataEdge(left, raw_usage);
- rep = right;
- break;
- case 2: // only right is a data edge
- AnalyzeDataEdge(right, raw_usage);
- rep = left;
- break;
- case 3: // left and right are data edges
- AnalyzeDataEdge(right, raw_usage);
- AnalyzeDataEdge(left, raw_usage);
- if (!pending.empty()) {
- rep = pending.back();
- pending.pop_back();
- } else {
- rep.rep = nullptr;
- }
- break;
- }
- }
-}
-
// Computes the memory size of the provided Ring tree.
template <Mode mode>
void AnalyzeRing(CordRepRef<mode> rep, RawUsage<mode>& raw_usage) {
@@ -211,8 +172,6 @@ size_t GetEstimatedUsage(const CordRep* rep) {
AnalyzeDataEdge(repref, raw_usage);
} else if (repref.rep->tag == BTREE) {
AnalyzeBtree(repref, raw_usage);
- } else if (repref.rep->IsConcat()) {
- AnalyzeConcat(repref, raw_usage);
} else if (repref.rep->tag == RING) {
AnalyzeRing(repref, raw_usage);
} else {
diff --git a/absl/strings/internal/cord_internal.cc b/absl/strings/internal/cord_internal.cc
index 75544191..06119350 100644
--- a/absl/strings/internal/cord_internal.cc
+++ b/absl/strings/internal/cord_internal.cc
@@ -36,53 +36,31 @@ ABSL_CONST_INIT std::atomic<bool> cord_btree_exhaustive_validation(false);
void CordRep::Destroy(CordRep* rep) {
assert(rep != nullptr);
- absl::InlinedVector<CordRep*, Constants::kInlinedVectorSize> pending;
while (true) {
assert(!rep->refcount.IsImmortal());
- if (rep->IsConcat()) {
- CordRepConcat* rep_concat = rep->concat();
- CordRep* right = rep_concat->right;
- if (!right->refcount.Decrement()) {
- pending.push_back(right);
- }
- CordRep* left = rep_concat->left;
- delete rep_concat;
- rep = nullptr;
- if (!left->refcount.Decrement()) {
- rep = left;
- continue;
- }
- } else if (rep->tag == BTREE) {
+ if (rep->tag == BTREE) {
CordRepBtree::Destroy(rep->btree());
- rep = nullptr;
+ return;
} else if (rep->tag == RING) {
CordRepRing::Destroy(rep->ring());
- rep = nullptr;
+ return;
} else if (rep->tag == EXTERNAL) {
CordRepExternal::Delete(rep);
- rep = nullptr;
+ return;
} else if (rep->tag == SUBSTRING) {
CordRepSubstring* rep_substring = rep->substring();
- CordRep* child = rep_substring->child;
+ rep = rep_substring->child;
delete rep_substring;
- rep = nullptr;
- if (!child->refcount.Decrement()) {
- rep = child;
- continue;
+ if (rep->refcount.Decrement()) {
+ return;
}
} else if (rep->tag == CRC) {
CordRepCrc::Destroy(rep->crc());
- rep = nullptr;
+ return;
} else {
+ assert(rep->IsFlat());
CordRepFlat::Delete(rep);
- rep = nullptr;
- }
-
- if (!pending.empty()) {
- rep = pending.back();
- pending.pop_back();
- } else {
- break;
+ return;
}
}
}
diff --git a/absl/strings/internal/cord_internal.h b/absl/strings/internal/cord_internal.h
index b9ecbba6..8db6aa6d 100644
--- a/absl/strings/internal/cord_internal.h
+++ b/absl/strings/internal/cord_internal.h
@@ -171,7 +171,7 @@ class CordRepBtree;
// Various representations that we allow
enum CordRepKind {
- CONCAT = 0,
+ UNUSED_0 = 0,
SUBSTRING = 1,
CRC = 2,
BTREE = 3,
@@ -239,7 +239,6 @@ struct CordRep {
// Returns true if this instance's tag matches the requested type.
constexpr bool IsRing() const { return tag == RING; }
- constexpr bool IsConcat() const { return tag == CONCAT; }
constexpr bool IsSubstring() const { return tag == SUBSTRING; }
constexpr bool IsCrc() const { return tag == CRC; }
constexpr bool IsExternal() const { return tag == EXTERNAL; }
@@ -248,8 +247,6 @@ struct CordRep {
inline CordRepRing* ring();
inline const CordRepRing* ring() const;
- inline CordRepConcat* concat();
- inline const CordRepConcat* concat() const;
inline CordRepSubstring* substring();
inline const CordRepSubstring* substring() const;
inline CordRepCrc* crc();
@@ -276,21 +273,6 @@ struct CordRep {
static inline void Unref(CordRep* rep);
};
-struct CordRepConcat : public CordRep {
- CordRep* left;
- CordRep* right;
-
- uint8_t depth() const { return storage[0]; }
- void set_depth(uint8_t depth) { storage[0] = depth; }
-
- // Extracts the right-most flat in the provided concat tree if the entire path
- // to that flat is not shared, and the flat has the requested extra capacity.
- // Returns the (potentially new) top level tree node and the extracted flat,
- // or {tree, nullptr} if no flat was extracted.
- static ExtractResult ExtractAppendBuffer(CordRepConcat* tree,
- size_t extra_capacity);
-};
-
struct CordRepSubstring : public CordRep {
size_t start; // Starting offset of substring in child
CordRep* child;
@@ -569,16 +551,6 @@ class InlineData {
static_assert(sizeof(InlineData) == kMaxInline + 1, "");
-inline CordRepConcat* CordRep::concat() {
- assert(IsConcat());
- return static_cast<CordRepConcat*>(this);
-}
-
-inline const CordRepConcat* CordRep::concat() const {
- assert(IsConcat());
- return static_cast<const CordRepConcat*>(this);
-}
-
inline CordRepSubstring* CordRep::substring() {
assert(IsSubstring());
return static_cast<CordRepSubstring*>(this);
diff --git a/absl/strings/internal/cord_rep_concat.cc b/absl/strings/internal/cord_rep_concat.cc
deleted file mode 100644
index 3457b55c..00000000
--- a/absl/strings/internal/cord_rep_concat.cc
+++ /dev/null
@@ -1,63 +0,0 @@
-// Copyright 2021 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 <cstdint>
-
-#include "absl/base/config.h"
-#include "absl/container/inlined_vector.h"
-#include "absl/strings/internal/cord_internal.h"
-#include "absl/strings/internal/cord_rep_flat.h"
-
-namespace absl {
-ABSL_NAMESPACE_BEGIN
-namespace cord_internal {
-
-CordRepConcat::ExtractResult CordRepConcat::ExtractAppendBuffer(
- CordRepConcat* tree, size_t extra_capacity) {
- absl::InlinedVector<CordRepConcat*, kInlinedVectorSize> stack;
- CordRepConcat* concat = tree;
- CordRep* rep = concat->right;
-
- // Dive down the tree, making sure no edges are shared
- while (concat->refcount.IsOne() && rep->IsConcat()) {
- stack.push_back(concat);
- concat = rep->concat();
- rep = concat->right;
- }
- // Validate we ended on a non shared flat.
- if (concat->refcount.IsOne() && rep->IsFlat() &&
- rep->refcount.IsOne()) {
- // Verify it has at least the requested extra capacity
- CordRepFlat* flat = rep->flat();
- size_t remaining = flat->Capacity() - flat->length;
- if (extra_capacity > remaining) return {tree, nullptr};
-
- // Check if we have a parent to adjust, or if we must return the left node.
- rep = concat->left;
- if (!stack.empty()) {
- stack.back()->right = rep;
- for (CordRepConcat* parent : stack) {
- parent->length -= flat->length;
- }
- rep = tree;
- }
- delete concat;
- return {rep, flat};
- }
- return {tree, nullptr};
-}
-
-} // namespace cord_internal
-ABSL_NAMESPACE_END
-} // namespace absl
diff --git a/absl/strings/internal/cord_rep_consume.cc b/absl/strings/internal/cord_rep_consume.cc
index 253339be..20a55797 100644
--- a/absl/strings/internal/cord_rep_consume.cc
+++ b/absl/strings/internal/cord_rep_consume.cc
@@ -40,88 +40,21 @@ CordRep* ClipSubstring(CordRepSubstring* substring) {
return child;
}
-// Unrefs the provided `concat`, and returns `{concat->left, concat->right}`
-// Adds or assumes a reference on `concat->left` and `concat->right`.
-// Returns an array of 2 elements containing the left and right nodes.
-std::array<CordRep*, 2> ClipConcat(CordRepConcat* concat) {
- std::array<CordRep*, 2> result{concat->left, concat->right};
- if (concat->refcount.IsOne()) {
- delete concat;
- } else {
- CordRep::Ref(result[0]);
- CordRep::Ref(result[1]);
- CordRep::Unref(concat);
- }
- return result;
-}
+} // namespace
-void Consume(bool forward, CordRep* rep, ConsumeFn consume_fn) {
+void Consume(CordRep* rep, ConsumeFn consume_fn) {
size_t offset = 0;
size_t length = rep->length;
- struct Entry {
- CordRep* rep;
- size_t offset;
- size_t length;
- };
- absl::InlinedVector<Entry, 40> stack;
-
- for (;;) {
- if (rep->IsConcat()) {
- std::array<CordRep*, 2> res = ClipConcat(rep->concat());
- CordRep* left = res[0];
- CordRep* right = res[1];
-
- if (left->length <= offset) {
- // Don't need left node
- offset -= left->length;
- CordRep::Unref(left);
- rep = right;
- continue;
- }
- size_t length_left = left->length - offset;
- if (length_left >= length) {
- // Don't need right node
- CordRep::Unref(right);
- rep = left;
- continue;
- }
-
- // Need both nodes
- size_t length_right = length - length_left;
- if (forward) {
- stack.push_back({right, 0, length_right});
- rep = left;
- length = length_left;
- } else {
- stack.push_back({left, offset, length_left});
- rep = right;
- offset = 0;
- length = length_right;
- }
- } else if (rep->tag == SUBSTRING) {
- offset += rep->substring()->start;
- rep = ClipSubstring(rep->substring());
- } else {
- consume_fn(rep, offset, length);
- if (stack.empty()) return;
-
- rep = stack.back().rep;
- offset = stack.back().offset;
- length = stack.back().length;
- stack.pop_back();
- }
+ if (rep->tag == SUBSTRING) {
+ offset += rep->substring()->start;
+ rep = ClipSubstring(rep->substring());
}
-}
-
-} // namespace
-
-void Consume(CordRep* rep, ConsumeFn consume_fn) {
- return Consume(true, rep, std::move(consume_fn));
+ consume_fn(rep, offset, length);
}
void ReverseConsume(CordRep* rep, ConsumeFn consume_fn) {
- return Consume(false, rep, std::move(consume_fn));
+ return Consume(rep, std::move(consume_fn));
}
} // namespace cord_internal
diff --git a/absl/strings/internal/cord_rep_flat.h b/absl/strings/internal/cord_rep_flat.h
index ae8b3a2a..e3e27fcd 100644
--- a/absl/strings/internal/cord_rep_flat.h
+++ b/absl/strings/internal/cord_rep_flat.h
@@ -73,9 +73,11 @@ static_assert(AllocatedSizeToTagUnchecked(kMinFlatSize) == FLAT, "");
static_assert(AllocatedSizeToTagUnchecked(kMaxLargeFlatSize) == MAX_FLAT_TAG,
"");
-// Helper functions for rounded div, and rounding to exact sizes.
-constexpr size_t DivUp(size_t n, size_t m) { return (n + m - 1) / m; }
-constexpr size_t RoundUp(size_t n, size_t m) { return DivUp(n, m) * m; }
+// RoundUp logically performs `((n + m - 1) / m) * m` to round up to the nearest
+// multiple of `m`, optimized for the invariant that `m` is a power of 2.
+constexpr size_t RoundUp(size_t n, size_t m) {
+ return (n + m - 1) & (0 - m);
+}
// Returns the size to the nearest equal or larger value that can be
// expressed exactly as a tag value.
diff --git a/absl/strings/internal/cord_rep_test_util.h b/absl/strings/internal/cord_rep_test_util.h
index 692d7db5..18a0a195 100644
--- a/absl/strings/internal/cord_rep_test_util.h
+++ b/absl/strings/internal/cord_rep_test_util.h
@@ -114,9 +114,6 @@ inline void CordVisitReps(cord_internal::CordRep* rep, Fn&& fn) {
for (cord_internal::CordRep* edge : rep->btree()->Edges()) {
CordVisitReps(edge, fn);
}
- } else if (rep->IsConcat()) {
- CordVisitReps(rep->concat()->left, fn);
- CordVisitReps(rep->concat()->right, fn);
}
}
diff --git a/absl/strings/internal/cordz_info.cc b/absl/strings/internal/cordz_info.cc
index 24605260..c891d0ed 100644
--- a/absl/strings/internal/cordz_info.cc
+++ b/absl/strings/internal/cordz_info.cc
@@ -98,8 +98,6 @@ class CordRepAnalyzer {
AnalyzeRing(repref);
} else if (repref.rep->tag == BTREE) {
AnalyzeBtree(repref);
- } else if (repref.rep->IsConcat()) {
- AnalyzeConcat(repref);
} else {
// We should have either a concat, btree, or ring node if not null.
assert(false);
@@ -141,14 +139,6 @@ class CordRepAnalyzer {
}
};
- // Returns `rr` if `rr.rep` is not null and a CONCAT type.
- // Asserts that `rr.rep` is a concat node or null.
- static RepRef AssertConcat(RepRef repref) {
- const CordRep* rep = repref.rep;
- assert(rep == nullptr || rep->IsConcat());
- return (rep != nullptr && rep->IsConcat()) ? repref : RepRef{nullptr, 0};
- }
-
// Counts a flat of the provide allocated size
void CountFlat(size_t size) {
statistics_.node_count++;
@@ -201,34 +191,6 @@ class CordRepAnalyzer {
return rep;
}
- // Analyzes the provided concat node in a flattened recursive way.
- void AnalyzeConcat(RepRef rep) {
- absl::InlinedVector<RepRef, 47> pending;
-
- while (rep.rep != nullptr) {
- const CordRepConcat* concat = rep.rep->concat();
- RepRef left = rep.Child(concat->left);
- RepRef right = rep.Child(concat->right);
-
- statistics_.node_count++;
- statistics_.node_counts.concat++;
- memory_usage_.Add(sizeof(CordRepConcat), rep.refcount);
-
- right = AssertConcat(CountLinearReps(right, memory_usage_));
- rep = AssertConcat(CountLinearReps(left, memory_usage_));
- if (rep.rep != nullptr) {
- if (right.rep != nullptr) {
- pending.push_back(right);
- }
- } else if (right.rep != nullptr) {
- rep = right;
- } else if (!pending.empty()) {
- rep = pending.back();
- pending.pop_back();
- }
- }
- }
-
// Analyzes the provided ring.
void AnalyzeRing(RepRef rep) {
statistics_.node_count++;
diff --git a/absl/strings/internal/cordz_info_statistics_test.cc b/absl/strings/internal/cordz_info_statistics_test.cc
index 40f93dd3..476c38d2 100644
--- a/absl/strings/internal/cordz_info_statistics_test.cc
+++ b/absl/strings/internal/cordz_info_statistics_test.cc
@@ -148,10 +148,6 @@ double FairShareImpl(CordRep* rep, size_t ref) {
rep->ring()->ForEach([&](CordRepRing::index_type i) {
self += FairShareImpl(rep->ring()->entry_child(i), 1);
});
- } else if (rep->IsConcat()) {
- self = SizeOf(rep->concat());
- children = FairShareImpl(rep->concat()->left, ref) +
- FairShareImpl(rep->concat()->right, ref);
} else {
assert(false);
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-19 15:45:39 +0000