summaryrefslogtreecommitdiff
path: root/absl/container/internal
diff options
context:
space:
mode:
Diffstat (limited to 'absl/container/internal')
-rw-r--r--absl/container/internal/btree.h562
-rw-r--r--absl/container/internal/btree_container.h2
2 files changed, 349 insertions, 215 deletions
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;