]> git.lizzy.rs Git - rust.git/commit
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)
commit562581c2db7ae9294e16f84deeef1dcdaae18152
tree656cd9d2677908d494525f12a4c2547206b80aed
parenta00e24d76a9ac03b146d3bf89e2161b2466c6551
parent36831b3ccbc4104c6b559cbd341dbd7ee6251ec7
Rollup merge of #105641 - Amanieu:btree_cursor, r=m-ou-se

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.