Repository: rust-lang/rust
File: library/alloc/src/collections/btree/map.rs (Rust)

Code before:
            return;
        }

        // We can just swap `self` and `other` if `self` is empty.
        if self.is_empty() {
            mem::swap(self, &mut other);
            return;
        }

        let mut other_iter = other.into_iter();
        let (first_other_key, first_other_val) = other_iter.next().unwrap();

        // find the first gap that has the smallest key greater than the first key from other
        let mut self_cursor = self.lower_bound_mut(Bound::Included(&first_other_key));

        if let Some((self_key, self_val)) = self_cursor.peek_next() {
            match K::cmp(&first_other_key, self_key) {
                Ordering::Equal => {
                    // SAFETY: We read in self_val's and hand it over to our conflict function
                    // which will always return a value that we can use to overwrite what's
                    // in self_val
                    unsafe {
                        let val = ptr::read(self_val);
                        let next_val = (conflict)(self_key, val, first_other_val);
                        ptr::write(self_val, next_val);
                    }
                }
                Ordering::Less =>
                // SAFETY: we know our other_key's ordering is less than self_key,
                // so inserting before will guarantee sorted order
                unsafe {
                    self_cursor.insert_before_unchecked(first_other_key, first_other_val);
                },
                Ordering::Greater => {
                    unreachable!("cursor's peek_next would return None in this case");
                }
            }
        } else {
            // SAFETY: if we reach here, that means our cursor has reached
            // the end of self BTreeMap, (other_key is greater than all the
            // previous self BTreeMap keys) so we just insert other_key here
            // at the end of the CursorMut
            unsafe {
                self_cursor.insert_after_unchecked(first_other_key, first_other_val);
            }
        }

        for (other_key, other_val) in other_iter {
            if self_cursor.peek_next().is_some() {
                loop {
                    let self_entry = self_cursor.peek_next();

Review comment (performance):
this should really be a method of `Cursor*`, you need a handler for when `conflict` panics that removes the entry without dropping whatever you `ptr::read` from.
something like:
```rust
impl<K, V> CursorMut<'a, K, V> {
    /// call `f` with the next entry's key and value, replacing the next entry's value with the returned value. if `f` unwinds, the next entry is removed.
    /// equivalent to a more efficient version of:
    /// ```rust
    /// if let Some((k, v)) = self.remove_next() {
    ///     let v = f(&k, v);
    ///     // Safety: key is unmodified
    ///     unsafe { self.insert_after_unchecked(k, v) };
    /// }
    /// ```
    pub(super) fn with_next(&mut self, f: impl FnOnce(&K, V) -> V) {
        struct RemoveNextOnDrop<'a, 'b, K, V> {
            cursor: &'a mut CursorMut<'b, K, V>,
            forget_next: bool,
        }
        impl<K, V> Drop for RemoveNextOnDrop<'_, '_, K, V> {
            fn drop(&mut self) {
                if self.forget_next {
                    // call an equivalent to CursorMut::remove_next()
                    // except that instead of returning `V`, it never moves or drops it.
                    self.0.forget_next_value();
                }
            }
        }
        let mut remove_next_on_drop = RemoveNextOnDrop {
            cursor: self,
            forget_next: false, // we don't know that we have a next value yet
        };
        if let Some((k, v_mut)) = remove_next_on_drop.cursor.peek_next() {
            remove_next_on_drop.forget_next = true;
            // Safety: we move the V out of the next entry,
            // we marked the entry's value to be forgotten
            // when remove_next_on_drop is dropped that
            // way we avoid returning to the caller leaving
            // a moved-out invalid value if `f` unwinds.
            let v = unsafe { std::ptr::read(v_mut) };
            let v = f(k, v);
            // Safety: move the V back into the next entry
            unsafe { std::ptr::write(v_mut, v) };
            remove_next_on_drop.forget_next = false;
        }
    }
}
```

The equivalent `CursorMutKey` method should instead have `f` be `impl FnOnce(K, V) -> (K, V)` and needs to forget both the key and value since they were both `ptr::read`, and not just the value.

Code after:
        }

        // We can just swap `self` and `other` if `self` is empty.
        if self.is_empty() {
            mem::swap(self, &mut other);
            return;
        }

        let mut other_iter = other.into_iter();
        let (first_other_key, first_other_val) = other_iter.next().unwrap();

        // find the first gap that has the smallest key greater than or equal to
        // the first key from other
        let mut self_cursor = self.lower_bound_mut(Bound::Included(&first_other_key));

        if let Some((self_key, _)) = self_cursor.peek_next() {
            match K::cmp(self_key, &first_other_key) {
                Ordering::Equal => {
                    // if `f` unwinds, the next entry is already removed leaving
                    // the tree in valid state.
                    // FIXME: Once `MaybeDangling` is implemented, we can optimize
                    // this through using a drop handler and transmutating CursorMutKey<K, V>
                    // to CursorMutKey<ManuallyDrop<K>, ManuallyDrop<V>> (see PR #152418)
                    if let Some((k, v)) = self_cursor.remove_next() {
                        // SAFETY: we remove the K, V out of the next entry,
                        // apply 'f' to get a new (K, V), and insert it back
                        // into the next entry that the cursor is pointing at
                        let v = conflict(&k, v, first_other_val);
                        unsafe { self_cursor.insert_after_unchecked(k, v) };
                    }
                }
                Ordering::Greater =>
                // SAFETY: we know our other_key's ordering is less than self_key,
                // so inserting before will guarantee sorted order
                unsafe {
                    self_cursor.insert_before_unchecked(first_other_key, first_other_val);
                },
                Ordering::Less => {
                    unreachable!("Cursor's peek_next should return None.");
                }
            }
        } else {
            // SAFETY: reaching here means our cursor is at the end
            // self BTreeMap so we just insert other_key here
            unsafe {
                self_cursor.insert_before_unchecked(first_other_key, first_other_val);
            }
        }

        for (other_key, other_val) in other_iter {
            loop {