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

Code before:
                            break;
                        }
                        Ordering::Greater => {
                            // advance the cursor forward
                            self_cursor.next();
                        }
                    }
                } else {
                    // SAFETY: reaching here means our cursor is at the end
                    // self BTreeMap so we just insert other_key here
                    unsafe {
                        self_cursor.insert_after_unchecked(other_key, other_val);
                    }
                    self_cursor.next();
                    break;
                }
            }
        }
    }

    /// Constructs a double-ended iterator over a sub-range of elements in the map.
    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
    /// yield elements from min (inclusive) to max (exclusive).
    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
    /// range from 4 to 10.
    ///
    /// # Panics
    ///
    /// Panics if range `start > end`.
    /// Panics if range `start == end` and both bounds are `Excluded`.
    ///
    /// # Examples
    ///
    /// ```
    /// use std::collections::BTreeMap;
    /// use std::ops::Bound::Included;
    ///
    /// let mut map = BTreeMap::new();
    /// map.insert(3, "a");
    /// map.insert(5, "b");
    /// map.insert(8, "c");
    /// for (&key, &value) in map.range((Included(&4), Included(&8))) {
    ///     println!("{key}: {value}");
    /// }
    /// assert_eq!(Some((&5, &"b")), map.range(4..).next());
    /// ```
    #[stable(feature = "btree_range", since = "1.17.0")]
    pub fn range<T: ?Sized, R>(&self, range: R) -> Range<'_, K, V>
    where
        T: Ord,

Review comment (performance):
```suggestion
                            // FIXME: instead of doing a linear search here,
                            // this can be optimized to search the tree by starting
                            // from self_cursor and going towards the root and then
                            // back down to the proper node -- that should probably
                            // be a new method on Cursor*.
                            self_cursor.next();
```

Code after:
                            // 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, other_val);
                                unsafe { self_cursor.insert_after_unchecked(k, v) };
                            }
                            break;
                        }
                        Ordering::Greater => {
                            // SAFETY: we know our self_key's ordering is greater than other_key,
                            // so inserting before will guarantee sorted order
                            unsafe {
                                self_cursor.insert_before_unchecked(other_key, other_val);
                            }
                            break;
                        }
                        Ordering::Less => {
                            // FIXME: instead of doing a linear search here,
                            // this can be optimized to search the tree by starting
                            // from self_cursor and going towards the root and then
                            // back down to the proper node -- that should probably
                            // be a new method on Cursor*.
                            self_cursor.next();
                        }
                    }
                } else {
                    // FIXME: If we get here, that means all of other's keys are greater than
                    // self's keys. For performance, this should really do a bulk insertion of items
                    // from other_iter into the end of self `BTreeMap`. Maybe this should be
                    // a method for Cursor*?

                    // 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(other_key, other_val);
                    }
                    break;
                }
            }
        }
    }

    /// Constructs a double-ended iterator over a sub-range of elements in the map.
    /// The simplest way is to use the range syntax `min..max`, thus `range(min..max)` will
    /// yield elements from min (inclusive) to max (exclusive).
    /// The range may also be entered as `(Bound<T>, Bound<T>)`, so for example
    /// `range((Excluded(4), Included(10)))` will yield a left-exclusive, right-inclusive
    /// range from 4 to 10.