]> git.lizzy.rs Git - rust.git/commit
Auto merge of #32466 - jooert:btree_append, r=apasel422
authorbors <bors@rust-lang.org>
Sat, 23 Apr 2016 00:54:30 +0000 (17:54 -0700)
committerbors <bors@rust-lang.org>
Sat, 23 Apr 2016 00:54:30 +0000 (17:54 -0700)
commit66ff163081685aa48bc59033eb5280052963a750
tree78384c49fd9e157f4867d440773415f33923d18d
parentaf000a7bbffcaf5e75ff97b245fa5a413062acc1
parent241a3e4689d3004daf9e1d36cec2235cbd301fbf
Auto merge of #32466 - jooert:btree_append, r=apasel422

Implement `append` for b-trees.

I have finally found time to revive #26227, this time only with an `append` implementation.

The algorithm implemented here is linear in the size of the two b-trees. It firsts creates
a `MergeIter` from the two b-trees and then builds a new b-tree by pushing
key-value pairs from the `MergeIter` into nodes at the right heights.

Three functions for stealing have been added to the implementation of `Handle` as
well as a getter for the height of a `NodeRef`.

The docs have been updated with performance information about `BTreeMap::append` and
the remark about B has been removed now that it is the same for all instances of `BTreeMap`.

cc @gereeter @Gankro @apasel422