complete btree rewrite

Replaces BTree with BTreeMap and BTreeSet, which are completely new implementations.
BTreeMap's internal Node representation is particularly inefficient at the moment to
make this first implementation easy to reason about and fairly safe. Both collections
are also currently missing some of the tooling specific to sorted collections, which
is planned as future work pending reform of these APIs. General implementation issues
are discussed with TODOs internally

Perf results on x86_64 Linux:

test treemap::bench::find_rand_100                         ... bench:        76 ns/iter (+/- 4)
test treemap::bench::find_rand_10_000                      ... bench:       163 ns/iter (+/- 6)
test treemap::bench::find_seq_100                          ... bench:        77 ns/iter (+/- 3)
test treemap::bench::find_seq_10_000                       ... bench:       115 ns/iter (+/- 1)
test treemap::bench::insert_rand_100                       ... bench:       111 ns/iter (+/- 1)
test treemap::bench::insert_rand_10_000                    ... bench:       996 ns/iter (+/- 18)
test treemap::bench::insert_seq_100                        ... bench:       486 ns/iter (+/- 20)
test treemap::bench::insert_seq_10_000                     ... bench:       800 ns/iter (+/- 15)

test btree::map::bench::find_rand_100                      ... bench:        74 ns/iter (+/- 4)
test btree::map::bench::find_rand_10_000                   ... bench:       153 ns/iter (+/- 5)
test btree::map::bench::find_seq_100                       ... bench:        82 ns/iter (+/- 1)
test btree::map::bench::find_seq_10_000                    ... bench:       108 ns/iter (+/- 0)
test btree::map::bench::insert_rand_100                    ... bench:       220 ns/iter (+/- 1)
test btree::map::bench::insert_rand_10_000                 ... bench:       620 ns/iter (+/- 16)
test btree::map::bench::insert_seq_100                     ... bench:       411 ns/iter (+/- 12)
test btree::map::bench::insert_seq_10_000                  ... bench:       534 ns/iter (+/- 14)

BTreeMap still has a lot of room for optimization, but it's already beating out TreeMap on most access patterns.

[breaking-change]

1 files changed, 1 insertions, 1 deletions

diff --git a/src/libstd/collections/mod.rs b/src/libstd/collections/mod.rs
index d98d490a84b..324c0295971 100644
--- a/src/libstd/collections/mod.rs
+++ b/src/libstd/collections/mod.rs
@@ -16,7 +16,7 @@
 
 pub use core_collections::{Collection, Mutable, Map, MutableMap};
 pub use core_collections::{Set, MutableSet, Deque, MutableSeq};
-pub use core_collections::{Bitv, BitvSet, BTree, DList, EnumSet};
+pub use core_collections::{Bitv, BitvSet, BTreeMap, BTreeSet, DList, EnumSet};
 pub use core_collections::{PriorityQueue, RingBuf, SmallIntMap};
 pub use core_collections::{TreeMap, TreeSet, TrieMap, TrieSet};
 pub use core_collections::{bitv, btree, dlist, enum_set};