]> git.lizzy.rs Git - rust.git/commitdiff
Rollup merge of #105641 - Amanieu:btree_cursor, r=m-ou-se
authorMatthias Krüger <matthias.krueger@famsik.de>
Wed, 8 Feb 2023 17:32:41 +0000 (18:32 +0100)
committerGitHub <noreply@github.com>
Wed, 8 Feb 2023 17:32:41 +0000 (18:32 +0100)
Implement cursors for BTreeMap

See the ACP for an overview of the API: https://github.com/rust-lang/libs-team/issues/141

The implementation is split into 2 commits:
- The first changes the internal insertion functions to return a handle to the newly inserted element. The lifetimes involved are a bit hairy since we need a mutable handle to both the `BTreeMap` itself (which holds the root) and the nodes allocated in memory. I have tested that this passes the standard library testsuite under miri.
- The second commit implements the cursor API itself. This is more straightforward to follow but still involves some unsafe code to deal with simultaneous mutable borrows of the tree root and the node that is currently being iterated.


Trivial merge