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

Code before:
    #[unstable(feature = "btree_merge", issue = "152152")]
    pub fn merge(&mut self, mut other: Self, mut conflict: impl FnMut(&K, V, V) -> V)
    where
        K: Ord,
        A: Clone,
    {
        // Do we have to append anything at all?
        if other.is_empty() {
            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 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(&first_other_key, self_key) {
                Ordering::Equal => {
                    self_cursor.with_next(|self_key, self_val| {
                        conflict(self_key, self_val, first_other_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 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 {

Review comment (performance):
Is this comparison is flipped from what lower_bound_mut uses (`self_key <=> first_other_key`)? I haven't looked at its impl but that would be somewhat intuitive to me. It seems likely that reusing the direction is good for optimizations to maybe be able to merge the comparison (in cases where it's expensive, e.g., strings)?

It would also make it easier to read the code after reading the docs on lower_bound_mut, since those say "greater than or equal to" whereas here we have "less than or equal to" due to the flipped order.

Code after:
    pub fn merge(&mut self, mut other: Self, mut conflict: impl FnMut(&K, V, V) -> V)
    where
        K: Ord,
        A: Clone,
    {
        // Do we have to append anything at all?
        if other.is_empty() {
            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 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