summary refs log tree commit diff
path: root/src/libcollections/btree/node.rs
AgeCommit message (Collapse)AuthorLines
2015-02-18rollup merge of #22286: nikomatsakis/variance-4bAlex Crichton-32/+52
Conflicts: src/librustc/middle/infer/combine.rs src/librustc_typeck/check/wf.rs
2015-02-18Stabilize std::borrowAaron Turon-4/+5
This commit stabilizes `std::borrow`, making the following modifications to catch up the API with language changes: * It renames `BorrowFrom` to `Borrow`, as was originally intended (but blocked for technical reasons), and reorders the parameters accordingly. * It moves the type parameter of `ToOwned` to an associated type. This is somewhat less flexible, in that each borrowed type must have a unique owned type, but leads to a significant simplification for `Cow`. Flexibility can be regained by using newtyped slices, which is advisable for other reasons anyway. * It removes the owned type parameter from `Cow`, making the type much less verbose. * Deprecates the `is_owned` and `is_borrowed` predicates in favor of direct matching. The above API changes are relatively minor; the basic functionality remains the same, and essentially the whole module is now marked `#[stable]`. [breaking-change]
2015-02-18Fallout: port btree to use Unique, some markers.Niko Matsakis-32/+52
2015-02-11Add core::marker::PhantomData.Felix S. Klock II-8/+8
Port `core::ptr::Unique` to have `PhantomData`. Add `PhantomData` to `TypedArena` and `Vec` as well. As a drive-by, switch `ptr::Unique` from a tuple-struct to a struct with fields.
2015-02-06Rollup merge of #21969 - Gankro:collections-cleanup, r=alexcrichtonManish Goregaokar-61/+61
This is 99% burning ints to the ground, but I also got rid of useless annotations or made code more \"idiomatic\" as I went along. Mostly changes in tests.
2015-02-05misc collections code cleanupAlexis-61/+61
2015-02-04Fix for misspelled comments.Joseph Crail-1/+1
The spelling corrections were made in both documentation comments and regular comments.
2015-02-02`for x in xs.iter()` -> `for x in &xs`Jorge Aparicio-3/+3
2015-01-30fix falloutJorge Aparicio-4/+4
2015-01-29`for x in range(a, b)` -> `for x in a..b`Jorge Aparicio-1/+1
sed -i 's/in range(\([^,]*\), *\([^()]*\))/in \1\.\.\2/g' **/*.rs
2015-01-25Merge remote-tracking branch 'rust-lang/master'Brian Anderson-11/+10
Conflicts: mk/tests.mk src/liballoc/arc.rs src/liballoc/boxed.rs src/liballoc/rc.rs src/libcollections/bit.rs src/libcollections/btree/map.rs src/libcollections/btree/set.rs src/libcollections/dlist.rs src/libcollections/ring_buf.rs src/libcollections/slice.rs src/libcollections/str.rs src/libcollections/string.rs src/libcollections/vec.rs src/libcollections/vec_map.rs src/libcore/any.rs src/libcore/array.rs src/libcore/borrow.rs src/libcore/error.rs src/libcore/fmt/mod.rs src/libcore/iter.rs src/libcore/marker.rs src/libcore/ops.rs src/libcore/result.rs src/libcore/slice.rs src/libcore/str/mod.rs src/libregex/lib.rs src/libregex/re.rs src/librustc/lint/builtin.rs src/libstd/collections/hash/map.rs src/libstd/collections/hash/set.rs src/libstd/sync/mpsc/mod.rs src/libstd/sync/mutex.rs src/libstd/sync/poison.rs src/libstd/sync/rwlock.rs src/libsyntax/feature_gate.rs src/libsyntax/test.rs
2015-01-23grandfathered -> rust1Brian Anderson-1/+1
2015-01-21Add 'feature' and 'since' to stability attributesBrian Anderson-1/+1
2015-01-21Fallout from stabilization.Aaron Turon-11/+10
2015-01-21Rollup merge of #21375 - petrochenkov:ssbsl, r=alexcrichtonBarosl LEE-3/+3
After PR #19766 added implicit coersions `*mut T -> *const T`, the explicit casts can be removed. (The number of such casts turned out to be relatively small).
2015-01-19Implement range and range_mut for BTreePiotr Czarnecki-75/+215
Simplify BTree's iterators, too.
2015-01-17Remove unnecessary explicit conversions to *const Twe-3/+3
2015-01-07Merge pull request #20674 from jbcrail/fix-misspelled-commentsbors-2/+2
Fix misspelled comments. Reviewed-by: steveklabnik
2015-01-06Fix misspelled comments.Joseph Crail-2/+2
I cleaned up comments prior to the 1.0 alpha release.
2015-01-06rollup merge of #20593: nikomatsakis/unused-tps-in-implAlex Crichton-1/+2
Conflicts: src/libcollections/lib.rs src/librustc/lib.rs src/libserialize/lib.rs src/libstd/lib.rs
2015-01-06core: split into fmt::Show and fmt::StringSean McArthur-1/+1
fmt::Show is for debugging, and can and should be implemented for all public types. This trait is used with `{:?}` syntax. There still exists #[derive(Show)]. fmt::String is for types that faithfully be represented as a String. Because of this, there is no way to derive fmt::String, all implementations must be purposeful. It is used by the default format syntax, `{}`. This will break most instances of `{}`, since that now requires the type to impl fmt::String. In most cases, replacing `{}` with `{:?}` is the correct fix. Types that were being printed specifically for users should receive a fmt::String implementation to fix this. Part of #20013 [breaking-change]
2015-01-06Fix fallout in libs. For the most part I just tagged impls as ↵Niko Matsakis-1/+2
`#[old_impl_check]`.
2015-01-06FalloutNick Cameron-2/+2
2015-01-03sed -i -s 's/#\[deriving(/#\[derive(/g' **/*.rsJorge Aparicio-1/+1
2015-01-03collections: fix falloutJorge Aparicio-9/+11
2015-01-02rollup merge of #20410: japaric/assoc-typesAlex Crichton-16/+32
Conflicts: src/liballoc/lib.rs src/libcollections/lib.rs src/libcollections/slice.rs src/libcore/ops.rs src/libcore/prelude.rs src/libcore/ptr.rs src/librustc/middle/traits/project.rs src/libstd/c_str.rs src/libstd/io/mem.rs src/libstd/io/mod.rs src/libstd/lib.rs src/libstd/path/posix.rs src/libstd/path/windows.rs src/libstd/prelude.rs src/libstd/rt/exclusive.rs src/libsyntax/lib.rs src/test/compile-fail/issue-18566.rs src/test/run-pass/deref-mut-on-ref.rs src/test/run-pass/deref-on-ref.rs src/test/run-pass/dst-deref-mut.rs src/test/run-pass/dst-deref.rs src/test/run-pass/fixup-deref-mut.rs src/test/run-pass/issue-13264.rs src/test/run-pass/overloaded-autoderef-indexing.rs
2015-01-02core: use assoc types in `Deref[Mut]`Jorge Aparicio-16/+32
2015-01-02std: Stabilize the prelude moduleAlex Crichton-2/+4
This commit is an implementation of [RFC 503][rfc] which is a stabilization story for the prelude. Most of the RFC was directly applied, removing reexports. Some reexports are kept around, however: * `range` remains until range syntax has landed to reduce churn. * `Path` and `GenericPath` remain until path reform lands. This is done to prevent many imports of `GenericPath` which will soon be removed. * All `io` traits remain until I/O reform lands so imports can be rewritten all at once to `std::io::prelude::*`. This is a breaking change because many prelude reexports have been removed, and the RFC can be consulted for the exact list of removed reexports, as well as to find the locations of where to import them. [rfc]: https://github.com/rust-lang/rfcs/blob/master/text/0503-prelude-stabilization.md [breaking-change] Closes #20068
2014-12-31Test fixes and rebase conflictsAlex Crichton-4/+4
2014-12-30rollup merge of #20061: aturon/stab-2-vec-sliceAlex Crichton-33/+33
Conflicts: src/libcollections/slice.rs src/libcollections/vec.rs src/libstd/sys/windows/os.rs
2014-12-30Fallout from stabilizationAaron Turon-33/+33
2014-12-29collections: use Unique in btree::NodeSean McArthur-15/+16
2014-12-22Renaming of the Iter types as in RFC #344Florian Wilkens-6/+6
libcore: slice::Items -> slice::Iter, slice::MutItems -> slice::IterMut libcollections: *::Items -> *::Iter, *::MoveItems -> *::IntoIter, *::MutItems -> *::IterMut This is of course a [breaking-change].
2014-12-21rollup merge of #20070: aturon/stab-2-cloneAlex Crichton-0/+1
This patch marks `clone` stable, as well as the `Clone` trait, but leaves `clone_from` unstable. The latter will be decided by the beta. The patch also marks most manual implementations of `Clone` as stable, except where the APIs are otherwise deprecated or where there is uncertainty about providing `Clone`. r? @alexcrichton
2014-12-20Stabilize cloneAaron Turon-0/+1
This patch marks `clone` stable, as well as the `Clone` trait, but leaves `clone_from` unstable. The latter will be decided by the beta. The patch also marks most manual implementations of `Clone` as stable, except where the APIs are otherwise deprecated or where there is uncertainty about providing `Clone`.
2014-12-20Fix more import_shadowing fallout in collections.Eduard Burtescu-29/+36
2014-12-17rollup merge of #19832: japaric/no-nocopyAlex Crichton-4/+0
r? @aturon / @alexcrichton
2014-12-15Remove internal uses of `marker::NoCopy`Jorge Aparicio-4/+0
2014-12-12Make BTree's Handle system more generic and more powerful, removing some ↵Jonathan S-174/+141
runtine checks in favor of newly gained static safety
2014-12-12Slimmify BTree by replacing its internal Node type, which previously…held ↵Jonathan S-300/+1199
three separately allocated `Vec`s, with a manually allocated buffer. Additionally, restructure the node and stack interfaces to be safer and require fewer bounds checks. Before: test btree::map::bench::find_rand_100 ... bench: 35 ns/iter (+/- 2) test btree::map::bench::find_rand_10_000 ... bench: 88 ns/iter (+/- 3) test btree::map::bench::find_seq_100 ... bench: 36 ns/iter (+/- 1) test btree::map::bench::find_seq_10_000 ... bench: 62 ns/iter (+/- 0) test btree::map::bench::insert_rand_100 ... bench: 157 ns/iter (+/- 8) test btree::map::bench::insert_rand_10_000 ... bench: 413 ns/iter (+/- 8) test btree::map::bench::insert_seq_100 ... bench: 272 ns/iter (+/- 10) test btree::map::bench::insert_seq_10_000 ... bench: 369 ns/iter (+/- 19) test btree::map::bench::iter_1000 ... bench: 19049 ns/iter (+/- 740) test btree::map::bench::iter_100000 ... bench: 1916737 ns/iter (+/- 102250) test btree::map::bench::iter_20 ... bench: 424 ns/iter (+/- 40) After: test btree::map::bench::find_rand_100 ... bench: 9 ns/iter (+/- 1) test btree::map::bench::find_rand_10_000 ... bench: 8 ns/iter (+/- 0) test btree::map::bench::find_seq_100 ... bench: 7 ns/iter (+/- 0) test btree::map::bench::find_seq_10_000 ... bench: 8 ns/iter (+/- 0) test btree::map::bench::insert_rand_100 ... bench: 136 ns/iter (+/- 5) test btree::map::bench::insert_rand_10_000 ... bench: 380 ns/iter (+/- 34) test btree::map::bench::insert_seq_100 ... bench: 255 ns/iter (+/- 8) test btree::map::bench::insert_seq_10_000 ... bench: 364 ns/iter (+/- 10) test btree::map::bench::iter_1000 ... bench: 19112 ns/iter (+/- 837) test btree::map::bench::iter_100000 ... bench: 1911961 ns/iter (+/- 33069) test btree::map::bench::iter_20 ... bench: 453 ns/iter (+/- 37)
2014-12-06libcollections: remove unnecessary `as_mut_slice()` callsJorge Aparicio-8/+8
2014-12-06libcollections: remove unnecessary `as_slice()` callsJorge Aparicio-8/+8
2014-11-18rollup merge of #19008: alex/collections-typosJakub Bukaj-1/+1
2014-11-17libcollections: generalize BTree* to use BorrowFromAaron Turon-5/+6
Generalizes the BTree-based collections to use the new BorrowFrom infrastructure for more flexible lookups and removals.
2014-11-17Switch to purely namespaced enumsSteven Fackler-0/+4
This breaks code that referred to variant names in the same namespace as their enum. Reexport the variants in the old location or alter code to refer to the new locations: ``` pub enum Foo { A, B } fn main() { let a = A; } ``` => ``` pub use self::Foo::{A, B}; pub enum Foo { A, B } fn main() { let a = A; } ``` or ``` pub enum Foo { A, B } fn main() { let a = Foo::A; } ``` [breaking-change]
2014-11-16Fixed several typos in libcollectionsAlex Gaynor-1/+1
2014-11-01collections: Remove all collections traitsAlex Crichton-1/+0
As part of the collections reform RFC, this commit removes all collections traits in favor of inherent methods on collections themselves. All methods should continue to be available on all collections. This is a breaking change with all of the collections traits being removed and no longer being in the prelude. In order to update old code you should move the trait implementations to inherent implementations directly on the type itself. Note that some traits had default methods which will also need to be implemented to maintain backwards compatibility. [breaking-change] cc #18424
2014-10-29Rename fail! to panic!Steve Klabnik-1/+1
https://github.com/rust-lang/rfcs/pull/221 The current terminology of "task failure" often causes problems when writing or speaking about code. You often want to talk about the possibility of an operation that returns a Result "failing", but cannot because of the ambiguity with task failure. Instead, you have to speak of "the failing case" or "when the operation does not succeed" or other circumlocutions. Likewise, we use a "Failure" header in rustdoc to describe when operations may fail the task, but it would often be helpful to separate out a section describing the "Err-producing" case. We have been steadily moving away from task failure and toward Result as an error-handling mechanism, so we should optimize our terminology accordingly: Result-producing functions should be easy to describe. To update your code, rename any call to `fail!` to `panic!` instead. Assuming you have not created your own macro named `panic!`, this will work on UNIX based systems: grep -lZR 'fail!' . | xargs -0 -l sed -i -e 's/fail!/panic!/g' You can of course also do this by hand. [breaking-change]
2014-10-25Fix spelling mistakes in comments.Joseph Crail-9/+9
2014-09-27complete btree rewriteAlexis Beingessner-0/+552
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]
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-08 18:14:28 +0000