void btree::rebalance_or_split()

in absl/container/internal/btree.h [2297:2396]

• 73 lines of code
• 17 McCabe index (conditional complexity)

void btree<P>::rebalance_or_split(iterator *iter) {
  node_type *&node = iter->node;
  int &insert_position = iter->position;
  assert(node->count() == node->max_count());
  assert(kNodeSlots == node->max_count());

  // First try to make room on the node by rebalancing.
  node_type *parent = node->parent();
  if (node != root()) {
    if (node->position() > parent->start()) {
      // Try rebalancing with our left sibling.
      node_type *left = parent->child(node->position() - 1);
      assert(left->max_count() == kNodeSlots);
      if (left->count() < kNodeSlots) {
        // We bias rebalancing based on the position being inserted. If we're
        // inserting at the end of the right node then we bias rebalancing to
        // fill up the left node.
        int to_move = (kNodeSlots - left->count()) /
                      (1 + (insert_position < static_cast<int>(kNodeSlots)));
        to_move = (std::max)(1, to_move);

        if (insert_position - to_move >= node->start() ||
            left->count() + to_move < static_cast<int>(kNodeSlots)) {
          left->rebalance_right_to_left(to_move, node, mutable_allocator());

          assert(node->max_count() - node->count() == to_move);
          insert_position = insert_position - to_move;
          if (insert_position < node->start()) {
            insert_position = insert_position + left->count() + 1;
            node = left;
          }

          assert(node->count() < node->max_count());
          return;
        }
      }
    }

    if (node->position() < parent->finish()) {
      // Try rebalancing with our right sibling.
      node_type *right = parent->child(node->position() + 1);
      assert(right->max_count() == kNodeSlots);
      if (right->count() < kNodeSlots) {
        // We bias rebalancing based on the position being inserted. If we're
        // inserting at the beginning of the left node then we bias rebalancing
        // to fill up the right node.
        int to_move = (static_cast<int>(kNodeSlots) - right->count()) /
                      (1 + (insert_position > node->start()));
        to_move = (std::max)(1, to_move);

        if (insert_position <= node->finish() - to_move ||
            right->count() + to_move < static_cast<int>(kNodeSlots)) {
          node->rebalance_left_to_right(to_move, right, mutable_allocator());

          if (insert_position > node->finish()) {
            insert_position = insert_position - node->count() - 1;
            node = right;
          }

          assert(node->count() < node->max_count());
          return;
        }
      }
    }

    // Rebalancing failed, make sure there is room on the parent node for a new
    // value.
    assert(parent->max_count() == kNodeSlots);
    if (parent->count() == kNodeSlots) {
      iterator parent_iter(node->parent(), node->position());
      rebalance_or_split(&parent_iter);
    }
  } else {
    // Rebalancing not possible because this is the root node.
    // Create a new root node and set the current root node as the child of the
    // new root.
    parent = new_internal_node(parent);
    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() ||
           parent->start_child() == rightmost_);
  }

  // Split the node.
  node_type *split_node;
  if (node->leaf()) {
    split_node = new_leaf_node(parent);
    node->split(insert_position, split_node, mutable_allocator());
    if (rightmost_ == node) rightmost_ = split_node;
  } else {
    split_node = new_internal_node(parent);
    node->split(insert_position, split_node, mutable_allocator());
  }

  if (insert_position > node->finish()) {
    insert_position = insert_position - node->count() - 1;
    node = split_node;
  }
}