]> git.lizzy.rs Git - rust.git/commit - src/tools/miri
Rollup merge of #66648 - crgl:btree-clone-from, r=Amanieu
authorDylan DPC <dylan.dpc@gmail.com>
Thu, 30 Jan 2020 00:46:38 +0000 (01:46 +0100)
committerGitHub <noreply@github.com>
Thu, 30 Jan 2020 00:46:38 +0000 (01:46 +0100)
commit12c9562486224afb083cbe04d846c3f02cffe8c2
treebea4c517ba60a1b8f93ee9080694a125fcd9cbdf
parent9ed29b6ff6aa2e048b09c27af8f62ee3040bdb37
parent6c3e477d134511094ab301fc15c504cc79804e41
Rollup merge of #66648 - crgl:btree-clone-from, r=Amanieu

Implement clone_from for BTreeMap and BTreeSet

See #28481. This results in up to 90% speedups on simple data types when `self` and `other` are the same size, and is generally comparable or faster. Some concerns:

1. This implementation requires an `Ord` bound on the `Clone` implementation for `BTreeMap` and `BTreeSet`. Since these structs can only be created externally for keys with `Ord` implemented, this should be fine? If not, there's certainly a less safe way to do this.
2. Changing `next_unchecked` on `RangeMut` to return mutable key references allows for replacing the entire overlapping portion of both maps without changing the external interface in any way. However, if `clone_from` fails it can leave the `BTreeMap` in an invalid state, which might be unacceptable.

~This probably needs an FCP since it changes a trait bound, but (as far as I know?) that change cannot break any external code.~
src/liballoc/collections/btree/map.rs
src/liballoc/collections/btree/set.rs
src/liballoc/tests/btree/map.rs