]> git.lizzy.rs Git - rust.git/commit
Implement `append` for b-trees.
authorJohannes Oertel <johannes.oertel@uni-due.de>
Thu, 24 Mar 2016 14:39:46 +0000 (15:39 +0100)
committerJohannes Oertel <johannes.oertel@uni-due.de>
Fri, 22 Apr 2016 10:30:43 +0000 (12:30 +0200)
commit241a3e4689d3004daf9e1d36cec2235cbd301fbf
tree2271c120af812b64ca3beab24c2c19ce98f53398
parent887e9471783ff3f5edc920a85b6110486dc063c0
Implement `append` for b-trees.

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`.
src/libcollections/btree/map.rs
src/libcollections/btree/node.rs
src/libcollections/btree/set.rs
src/libcollectionstest/btree/map.rs
src/libcollectionstest/btree/set.rs
src/libcollectionstest/lib.rs
src/libstd/collections/mod.rs