diff options
Diffstat (limited to 'absl/container/internal/btree.h')
| -rw-r--r-- | absl/container/internal/btree.h | 562 |
1 files changed, 347 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 |