diff options
Diffstat (limited to 'absl/container/internal/btree.h')
-rw-r--r-- | absl/container/internal/btree.h | 76 |
1 files changed, 20 insertions, 56 deletions
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h index d986f81e85e5..adf49f81c571 100644 --- a/absl/container/internal/btree.h +++ b/absl/container/internal/btree.h @@ -776,9 +776,6 @@ class btree_node { // delimiting key in the parent node onto itself. void merge(btree_node *src, allocator_type *alloc); - // Swaps the contents of `this` and `other`. - void swap(btree_node *other, allocator_type *alloc); - // Node allocation/deletion routines. void init_leaf(btree_node *parent, int max_count) { set_parent(parent); @@ -820,6 +817,14 @@ class btree_node { absl::container_internal::SanitizerPoisonObject(slot(i)); } + // Transfers value from slot `src_i` in `src` to slot `dest_i` in `this`. + void transfer(const size_type dest_i, const size_type src_i, btree_node *src, + allocator_type *alloc) { + absl::container_internal::SanitizerUnpoisonObject(slot(dest_i)); + params_type::transfer(alloc, slot(dest_i), src->slot(src_i)); + absl::container_internal::SanitizerPoisonObject(src->slot(src_i)); + } + // Move n values starting at value i in this node into the values starting at // value j in dest_node. void uninitialized_move_n(const size_type n, const size_type i, @@ -1752,54 +1757,6 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) { parent()->remove_value(position(), alloc); } -template <typename P> -void btree_node<P>::swap(btree_node *other, allocator_type *alloc) { - using std::swap; - assert(leaf() == other->leaf()); - - // Determine which is the smaller/larger node. - btree_node *smaller = this, *larger = other; - if (smaller->count() > larger->count()) { - swap(smaller, larger); - } - - // Swap the values. - for (slot_type *a = smaller->start_slot(), *b = larger->start_slot(), - *end = smaller->finish_slot(); - a != end; ++a, ++b) { - params_type::swap(alloc, a, b); - } - - // Move values that can't be swapped. - const size_type to_move = larger->count() - smaller->count(); - larger->uninitialized_move_n(to_move, smaller->finish(), smaller->finish(), - smaller, alloc); - larger->value_destroy_n(smaller->finish(), to_move, alloc); - - if (!leaf()) { - // Swap the child pointers. - std::swap_ranges(&smaller->mutable_child(smaller->start()), - &smaller->mutable_child(smaller->finish() + 1), - &larger->mutable_child(larger->start())); - // Update swapped children's parent pointers. - int i = smaller->start(); - int j = larger->start(); - for (; i <= smaller->finish(); ++i, ++j) { - smaller->child(i)->set_parent(smaller); - larger->child(j)->set_parent(larger); - } - // Move the child pointers that couldn't be swapped. - for (; j <= larger->finish(); ++i, ++j) { - smaller->init_child(i, larger->child(j)); - larger->clear_child(j); - } - } - - // Swap the `finish`s. - // TODO(ezb): with floating storage, will also need to swap starts. - swap(mutable_finish(), other->mutable_finish()); -} - //// // btree_iterator methods template <typename N, typename R, typename P> @@ -2492,6 +2449,7 @@ inline auto btree<P>::internal_emplace(iterator iter, Args &&... args) ++iter.position; } const int max_count = iter.node->max_count(); + allocator_type *alloc = mutable_allocator(); if (iter.node->count() == max_count) { // Make room in the leaf for the new item. if (max_count < kNodeValues) { @@ -2500,15 +2458,21 @@ inline auto btree<P>::internal_emplace(iterator iter, Args &&... args) assert(iter.node == root()); iter.node = new_leaf_root_node((std::min<int>)(kNodeValues, 2 * max_count)); - iter.node->swap(root(), mutable_allocator()); - delete_leaf_node(root()); - mutable_root() = rightmost_ = iter.node; + // Transfer the values from the old root to the new root. + node_type *old_root = root(); + node_type *new_root = iter.node; + for (int i = old_root->start(), f = old_root->finish(); i < f; ++i) { + new_root->transfer(i, i, old_root, alloc); + } + new_root->set_finish(old_root->finish()); + old_root->set_finish(old_root->start()); + delete_leaf_node(old_root); + mutable_root() = rightmost_ = new_root; } else { rebalance_or_split(&iter); } } - iter.node->emplace_value(iter.position, mutable_allocator(), - std::forward<Args>(args)...); + iter.node->emplace_value(iter.position, alloc, std::forward<Args>(args)...); ++size_; return iter; } |