BTreeMap/BTreeSet: add drain and split_off_range methods #81075
Conversation
|
Is there a chance we can split this up into more commits? Reviewing a diff in a couple thousand lines is going to be quite challenging. It would be good to document any design decisions or otherwise guide my review, too. |
|
I can split off a few refactorings of existing functions, to open up for new use, but they seemed a bit pointless on their own (apart from one thing that I actually postponed). |
|
I don't really know what you postponed, but I will likely not be able to effectively review this diff without at least some guidance as to where to start or the overall vision in adding these methods. |
|
The item I postponed is that |
|
The overall vision in adding these methods is to not copy any existing functionality, but break it up in order to reuse parts. I'll feed those refactings in a few separate PRs now. |
|
|
|
|
ssomers
force-pushed the
ssomers:btree_drain
branch
3 times, most recently
from
4e62119
to
d111d91
|
|
|
|
ssomers
force-pushed the
ssomers:btree_drain
branch
2 times, most recently
from
ad80c11
to
24ec3f4
BTreeMap: gather and decompose reusable tree fixing functions This is kind of pushing it as a standalone refactor, probably only useful for rust-lang#81075 (or similar). r? `@Mark-Simulacrum`
…rk-Simulacrum BTreeMap: gather and decompose reusable tree fixing functions This is kind of pushing it as a standalone refactor, probably only useful for rust-lang#81075 (or similar). r? `@Mark-Simulacrum`
|
|
|
|
|
|
…rk-Simulacrum BTreeMap: gather and decompose reusable tree fixing functions This is kind of pushing it as a standalone refactor, probably only useful for rust-lang#81075 (or similar). r? `@Mark-Simulacrum`
…rk-Simulacrum BTreeMap: gather and decompose reusable tree fixing functions This is kind of pushing it as a standalone refactor, probably only useful for rust-lang#81075 (or similar). r? `@Mark-Simulacrum`
…rk-Simulacrum BTreeMap: gather and decompose reusable tree fixing functions This is kind of pushing it as a standalone refactor, probably only useful for rust-lang#81075 (or similar). r? `@Mark-Simulacrum`
|
|
…rk-Simulacrum BTreeMap: split up range_search into two stages `range_search` expects the caller to pass the same root twice and starts searching a node for both bounds of a range. It's not very clear that in the early iterations, it searches twice in the same node. This PR splits that search up in an initial `find_leaf_edges_spanning_range` that postpones aliasing until the last second, and a second phase for continuing the search for the range in the each subtree independently (`find_lower_bound_edge` & `find_upper_bound_edge`), which greatly helps for use in rust-lang#81075. It also moves those functions over to the search module. r? `@Mark-Simulacrum`
|
@rustbot label: -S-waiting-on-author +S-waiting-on-review |
Implements #81074
r? @Mark-Simulacrum