about summary refs log tree commit diff
path: root/src/libcollections
AgeCommit message (Collapse)AuthorLines
2014-07-07librustc (RFC #34): Implement the new `Index` and `IndexMut` traits.Patrick Walton-15/+49
This will break code that used the old `Index` trait. Change this code to use the new `Index` traits. For reference, here are their signatures: pub trait Index<Index,Result> { fn index<'a>(&'a self, index: &Index) -> &'a Result; } pub trait IndexMut<Index,Result> { fn index_mut<'a>(&'a mut self, index: &Index) -> &'a mut Result; } Closes #6515. [breaking-change]
2014-07-07collections: merge unsafe_push_all_clone and push_allErick Tryzelaar-29/+14
2014-07-07collections: minimize code that's in unsafe blocksErick Tryzelaar-22/+22
This changes Vec::from_slice to call unsafe_push_all_clone directly to avoid doing an unnecessary reserve_additional call
2014-07-07collections: flesh out the Vec::clone_from benchmarks to cover reuseErick Tryzelaar-30/+93
2014-07-07Add example for str replace() and MaybeOwnedJason Thompson-0/+47
- for 3 implementations of into_maybe_owned() - is_slice() - is_owned()
2014-07-06auto merge of #15465 : SimonSapin/rust/patch-4, r=alexcrichtonbors-1/+1
`Vec::push_all` with a length 1 slice seems to have significant overhead compared to `Vec::push`. ``` test new_push_byte ... bench: 6985 ns/iter (+/- 487) = 17 MB/s test old_push_byte ... bench: 19335 ns/iter (+/- 1368) = 6 MB/s ``` ```rust extern crate test; use test::Bencher; static TEXT: &'static str = "\ Unicode est un standard informatique qui permet des échanges \ de textes dans différentes langues, à un niveau mondial."; #[bench] fn old_push_byte(bencher: &mut Bencher) { bencher.bytes = TEXT.len() as u64; bencher.iter(|| { let mut new = String::new(); for b in TEXT.bytes() { unsafe { new.as_mut_vec().push_all([b]) } } }) } #[bench] fn new_push_byte(bencher: &mut Bencher) { bencher.bytes = TEXT.len() as u64; bencher.iter(|| { let mut new = String::new(); for b in TEXT.bytes() { unsafe { new.as_mut_vec().push(b) } } }) } ```
2014-07-05collections: Optimize Vec when cloning from a sliceErick Tryzelaar-31/+44
llvm is currently not able to conver `Vec::extend` into a memcpy for `Copy` types, which results in methods like `Vec::push_all` to run twice as slow as it should be running. This patch takes the unsafe `Vec::clone` optimization to speed up all the operations that are cloning a slice into a `Vec`. before: test vec::tests::bench_clone_from_0000_0000 ... bench: 12 ns/iter (+/- 2) test vec::tests::bench_clone_from_0000_0010 ... bench: 125 ns/iter (+/- 4) = 80 MB/s test vec::tests::bench_clone_from_0000_0100 ... bench: 360 ns/iter (+/- 33) = 277 MB/s test vec::tests::bench_clone_from_0000_1000 ... bench: 2601 ns/iter (+/- 175) = 384 MB/s test vec::tests::bench_clone_from_0010_0000 ... bench: 12 ns/iter (+/- 2) test vec::tests::bench_clone_from_0010_0010 ... bench: 125 ns/iter (+/- 10) = 80 MB/s test vec::tests::bench_clone_from_0010_0100 ... bench: 361 ns/iter (+/- 28) = 277 MB/s test vec::tests::bench_clone_from_0100_0010 ... bench: 131 ns/iter (+/- 13) = 76 MB/s test vec::tests::bench_clone_from_0100_0100 ... bench: 360 ns/iter (+/- 9) = 277 MB/s test vec::tests::bench_clone_from_0100_1000 ... bench: 2575 ns/iter (+/- 168) = 388 MB/s test vec::tests::bench_clone_from_1000_0100 ... bench: 356 ns/iter (+/- 20) = 280 MB/s test vec::tests::bench_clone_from_1000_1000 ... bench: 2605 ns/iter (+/- 167) = 383 MB/s test vec::tests::bench_from_slice_0000 ... bench: 11 ns/iter (+/- 0) test vec::tests::bench_from_slice_0010 ... bench: 115 ns/iter (+/- 5) = 86 MB/s test vec::tests::bench_from_slice_0100 ... bench: 309 ns/iter (+/- 170) = 323 MB/s test vec::tests::bench_from_slice_1000 ... bench: 2065 ns/iter (+/- 198) = 484 MB/s test vec::tests::bench_push_all_0000_0000 ... bench: 7 ns/iter (+/- 0) test vec::tests::bench_push_all_0000_0010 ... bench: 79 ns/iter (+/- 7) = 126 MB/s test vec::tests::bench_push_all_0000_0100 ... bench: 342 ns/iter (+/- 18) = 292 MB/s test vec::tests::bench_push_all_0000_1000 ... bench: 2873 ns/iter (+/- 75) = 348 MB/s test vec::tests::bench_push_all_0010_0010 ... bench: 154 ns/iter (+/- 8) = 64 MB/s test vec::tests::bench_push_all_0100_0100 ... bench: 518 ns/iter (+/- 18) = 193 MB/s test vec::tests::bench_push_all_1000_1000 ... bench: 4490 ns/iter (+/- 223) = 222 MB/s after: test vec::tests::bench_clone_from_0000_0000 ... bench: 12 ns/iter (+/- 1) test vec::tests::bench_clone_from_0000_0010 ... bench: 123 ns/iter (+/- 5) = 81 MB/s test vec::tests::bench_clone_from_0000_0100 ... bench: 367 ns/iter (+/- 23) = 272 MB/s test vec::tests::bench_clone_from_0000_1000 ... bench: 2618 ns/iter (+/- 252) = 381 MB/s test vec::tests::bench_clone_from_0010_0000 ... bench: 12 ns/iter (+/- 1) test vec::tests::bench_clone_from_0010_0010 ... bench: 124 ns/iter (+/- 7) = 80 MB/s test vec::tests::bench_clone_from_0010_0100 ... bench: 369 ns/iter (+/- 34) = 271 MB/s test vec::tests::bench_clone_from_0100_0010 ... bench: 123 ns/iter (+/- 6) = 81 MB/s test vec::tests::bench_clone_from_0100_0100 ... bench: 371 ns/iter (+/- 25) = 269 MB/s test vec::tests::bench_clone_from_0100_1000 ... bench: 2713 ns/iter (+/- 532) = 368 MB/s test vec::tests::bench_clone_from_1000_0100 ... bench: 369 ns/iter (+/- 14) = 271 MB/s test vec::tests::bench_clone_from_1000_1000 ... bench: 2611 ns/iter (+/- 194) = 382 MB/s test vec::tests::bench_from_slice_0000 ... bench: 7 ns/iter (+/- 0) test vec::tests::bench_from_slice_0010 ... bench: 108 ns/iter (+/- 4) = 92 MB/s test vec::tests::bench_from_slice_0100 ... bench: 235 ns/iter (+/- 24) = 425 MB/s test vec::tests::bench_from_slice_1000 ... bench: 1318 ns/iter (+/- 96) = 758 MB/s test vec::tests::bench_push_all_0000_0000 ... bench: 7 ns/iter (+/- 0) test vec::tests::bench_push_all_0000_0010 ... bench: 70 ns/iter (+/- 4) = 142 MB/s test vec::tests::bench_push_all_0000_0100 ... bench: 176 ns/iter (+/- 16) = 568 MB/s test vec::tests::bench_push_all_0000_1000 ... bench: 1125 ns/iter (+/- 94) = 888 MB/s test vec::tests::bench_push_all_0010_0010 ... bench: 159 ns/iter (+/- 15) = 62 MB/s test vec::tests::bench_push_all_0100_0100 ... bench: 363 ns/iter (+/- 12) = 275 MB/s test vec::tests::bench_push_all_1000_1000 ... bench: 2860 ns/iter (+/- 415) = 349 MB/s
2014-07-05collections: flesh out Vec benchmarksErick Tryzelaar-54/+364
2014-07-06Optimize String::push_byte()Simon Sapin-1/+1
``` test new_push_byte ... bench: 6985 ns/iter (+/- 487) = 17 MB/s test old_push_byte ... bench: 19335 ns/iter (+/- 1368) = 6 MB/s ``` ```rust extern crate test; use test::Bencher; static TEXT: &'static str = "\ Unicode est un standard informatique qui permet des échanges \ de textes dans différentes langues, à un niveau mondial."; #[bench] fn old_push_byte(bencher: &mut Bencher) { bencher.bytes = TEXT.len() as u64; bencher.iter(|| { let mut new = String::new(); for b in TEXT.bytes() { unsafe { new.as_mut_vec().push_all([b]) } } }) } #[bench] fn new_push_byte(bencher: &mut Bencher) { bencher.bytes = TEXT.len() as u64; bencher.iter(|| { let mut new = String::new(); for b in TEXT.bytes() { unsafe { new.as_mut_vec().push(b) } } }) } ```
2014-07-05Add #[crate_name] attributes as necessaryAlex Crichton-1/+3
2014-07-05libcore: Fix Items iterator for zero sized types.Luqman Aden-6/+4
2014-07-05auto merge of #15284 : apoelstra/rust/bitv-methods, r=cmrbors-642/+689
The types `Bitv` and `BitvSet` are badly out of date. This PR: - cleans up the code (primarily, simplifies `Bitv` and implements `BitvSet` in terms of `Bitv`) - implements several new traits for `Bitv` - adds new functionality to `Bitv` and `BitvSet` - replaces internal iterators with external ones - updates documentation - minor bug fixes This is a significantly souped-up version of PR #15139 and is the result of the discussion there.
2014-07-04librustc: Don't create &[T] slices with NULL as the ptr.Luqman Aden-17/+14
2014-07-04auto merge of #15343 : alexcrichton/rust/0.11.0-release, r=brsonbors-2/+2
2014-07-03collections: Fix conditional when reserving extra vec spaceErick Tryzelaar-1/+1
2014-07-03collections: grow should use the overflow-checked reserve_additionalErick Tryzelaar-2/+1
2014-07-03Add examples for StrVector methodsJason Thompson-1/+19
- examples for connect and concat - also fixed extra word in existing docs
2014-07-02collections::bitv: clean up and unit test `BitvSet::is_subset`Andrew Poelstra-55/+36
2014-07-02collections::bitv: change constructors for `Bitv` and `BitvSet`Andrew Poelstra-69/+81
`Bitv::new` has been renamed `Bitv::with_capacity`. The new function `Bitv::new` now creates a `Bitv` with no elements. The new function `BitvSet::with_capacity` creates a `BitvSet` with a specified capacity.
2014-07-02collections::bitv: Implement several methods for `Bitv` and `BitvSet`Andrew Poelstra-41/+295
On Bitv: - Add .push() and .pop() which take and return bool, respectively - Add .truncate() which truncates a Bitv to a specific length - Add .grow() which grows a Bitv by a specific length - Add .reserve() which grows the underlying storage to be able to hold a specified number of bits without resizing - Implement FromIterator<Vec<bool>> - Implement Extendable<bool> - Implement Collection - Implement Mutable - Remove .from_bools() since FromIterator<Vec<bool>> now accomplishes this. - Remove .assign() since Clone::clone_from() accomplishes this. On BitvSet: - Add .reserve() which grows the underlying storage to be able to hold a specified number of bits without resizing - Add .get_ref() and .get_mut_ref() to return references to the underlying Bitv
2014-07-02collections::bitv: Add documentation and #[inline]'sAndrew Poelstra-2/+26
Add documentation to methods on BitvSet that were missing them. Also make sure #[inline] is on all methods that are (a) one-liners or (b) private methods whose only purpose is code deduplication.
2014-07-02collections::bitv: replace internal iterators with external onesAndrew Poelstra-54/+88
2014-07-02collections::bitv: remove some ancient interfacesAndrew Poelstra-24/+3
Removes the following methods from `Bitv`: - `to_vec`: translates a `Bitv` into a bulky `Vec<uint>` of 0's and 1's replace with: `bitv.iter().map(|b| if b {1} else {0}).collect()` - `to_bools`: translates a `Bitv` into a `Vec<bool>` replace with: `bitv.iter().collect()` - `ones`: internal iterator over all 1 bits in a `Bitv` replace with: `BitvSet::from_bitv(bitv).iter().advance(fn)` These methods had specific functionality which can be replicated more generally by the modern iterator system. (Also `to_vec` was not even unit tested!)
2014-07-02collections::bitv: correct use of Vec<T>::growAndrew Poelstra-2/+11
The argument passed to Vec::grow is the number of elements to grow the vector by, not the target number of elements. The old `Bitv` code did the wrong thing, allocating more memory than it needed to.
2014-07-02collections::bitv: ensure correct masking behaviourAndrew Poelstra-83/+87
The internal masking behaviour for `Bitv` is now defined as: - Any entirely words in self.storage must be all zeroes. - Any partially used words may have anything at all in their unused bits. This means: - When decreasing self.nbits, care must be taken that any no-longer-used words are zeroed out. - When increasing self.nbits, care must be taken that any newly-unmasked bits are set to their correct values. - When reading words, care should be taken that the values of unused bits are not used. (Preferably, use `Bitv::mask_words` which zeroes them out for you.) The old behaviour was that every unused bit was always set to zero. The problem with this is that unused bits are almost never read, so forgetting to do this will result in very subtle and hard-to-track down bugs. This way the responsibility for masking falls on the places which might cause unused bits to be read: for now, this is only `Bitv::mask_words` and `BitvSet::insert`.
2014-07-02collections::bitv: Remove SmallBitv/BigBitv dichotomyAndrew Poelstra-397/+106
The old `Bitv` structure had two variations: one represented by a vector of uints, and another represented by a single uint for bit vectors containing fewer than uint::BITS bits. The purpose of this is to avoid the indirection of using a Vec, but the speedup is only available to users who (a) are storing less than uints::BITS bits (b) know this when they create the vector (since `Bitv`s cannot be resized) (c) don't know this at compile time (else they could use uint directly) Giving such specific users a (questionable) speed benefit at the cost of adding explicit checks to almost every single bit call, frequently writing the same method twice and making iteration much much more difficult, does not seem like a worthwhile tradeoff to me. Also, rustc does not use Bitv anywhere, only through BitvSet, which does not have this optimization. For reference, here is some speed data from before and after this PR: BEFORE: test bitv::tests::bench_bitv_big ... bench: 4 ns/iter (+/- 1) test bitv::tests::bench_bitv_big_iter ... bench: 4858 ns/iter (+/- 22) test bitv::tests::bench_bitv_big_union ... bench: 507 ns/iter (+/- 35) test bitv::tests::bench_bitv_set_big ... bench: 6 ns/iter (+/- 1) test bitv::tests::bench_bitv_set_small ... bench: 6 ns/iter (+/- 0) test bitv::tests::bench_bitv_small ... bench: 5 ns/iter (+/- 1) test bitv::tests::bench_bitvset_iter ... bench: 12930 ns/iter (+/- 662) test bitv::tests::bench_btv_small_iter ... bench: 39 ns/iter (+/- 1) test bitv::tests::bench_uint_small ... bench: 4 ns/iter (+/- 1) AFTER: test bitv::tests::bench_bitv_big ... bench: 5 ns/iter (+/- 1) test bitv::tests::bench_bitv_big_iter ... bench: 5004 ns/iter (+/- 102) test bitv::tests::bench_bitv_big_union ... bench: 356 ns/iter (+/- 26) test bitv::tests::bench_bitv_set_big ... bench: 6 ns/iter (+/- 0) test bitv::tests::bench_bitv_set_small ... bench: 6 ns/iter (+/- 1) test bitv::tests::bench_bitv_small ... bench: 4 ns/iter (+/- 1) test bitv::tests::bench_bitvset_iter ... bench: 12918 ns/iter (+/- 621) test bitv::tests::bench_btv_small_iter ... bench: 50 ns/iter (+/- 5) test bitv::tests::bench_uint_small ... bench: 4 ns/iter (+/- 1)
2014-07-02collections::bitv: implement BitvSet directly as a BitvAndrew Poelstra-102/+143
2014-07-02Merge remote-tracking branch 'origin/master' into 0.11.0-releaseAlex Crichton-103/+124
Conflicts: src/libstd/lib.rs
2014-07-01rustc: Remove `&str` indexing from the language.Brian Anderson-3/+3
Being able to index into the bytes of a string encourages poor UTF-8 hygiene. To get a view of `&[u8]` from either a `String` or `&str` slice, use the `as_bytes()` method. Closes #12710. [breaking-change]
2014-07-01Add examples for from_utf8_owned, from_char, from_chars, from_byteJason Thompson-2/+28
2014-07-01auto merge of #15271 : jasonthompson/rust/docs/str, r=huonwbors-0/+8
I'm working on adding examples to the API documentation. Should future pull requests include examples for more than one function? Or is this about the right size for a pull request?
2014-06-30auto merge of #14613 : schmee/rust/utf16-iterator, r=huonwbors-12/+9
Closes #14358. ~~The tests are not yet moved to `utf16_iter`, so this probably won't compile. I'm submitting this PR anyway so it can be reviewed and since it was mentioned in #14611.~~ EDIT: Tests now use `utf16_iter`. This deprecates `.to_utf16`. `x.to_utf16()` should be replaced by either `x.utf16_iter().collect::<Vec<u16>>()` (the type annotation may be optional), or just `x.utf16_iter()` directly, if it can be used in an iterator context. [breaking-change] cc @huonw
2014-06-30Add `utf16_units`John Schmidt-12/+9
This deprecates `.to_utf16`. `x.to_utf16()` should be replaced by either `x.utf16_units().collect::<Vec<u16>>()` (the type annotation may be optional), or just `x.utf16_units()` directly, if it can be used in an iterator context. Closes #14358 [breaking-change]
2014-06-30add example for from_byte() documenationJason Thompson-0/+8
2014-06-30auto merge of #15030 : sfackler/rust/partial-cmp, r=huonwbors-45/+26
I ended up altering the semantics of Json's PartialOrd implementation. It used to be the case that Null < Null, but I can't think of any reason for an ordering other than the default one so I just switched it over to using the derived implementation. This also fixes broken `PartialOrd` implementations for `Vec` and `TreeMap`. # Note This isn't ready to merge yet since libcore tests are broken as you end up with 2 versions of `Option`. The rest should be reviewable though. RFC: 0028-partial-cmp
2014-06-29Implement RFC#28: Add PartialOrd::partial_cmpSteven Fackler-45/+26
I ended up altering the semantics of Json's PartialOrd implementation. It used to be the case that Null < Null, but I can't think of any reason for an ordering other than the default one so I just switched it over to using the derived implementation. This also fixes broken `PartialOrd` implementations for `Vec` and `TreeMap`. RFC: 0028-partial-cmp
2014-06-30auto merge of #15256 : erickt/rust/optimizations, r=alexcrichtonbors-2/+0
The bug #11084 causes `option::collect` and `result::collect` about twice as slower as it should because llvm is having some trouble optimizing away the scan closure. This gets rid of it so now those functions perform equivalent to a hand written version. This also adds an impl of `Default` for `Rc` along the way.
2014-06-29collections: minor cleanupErick Tryzelaar-2/+0
2014-06-29librustc: Remove the fallback to `int` for integers and `f64` forPatrick Walton-22/+22
floating point numbers for real. This will break code that looks like: let mut x = 0; while ... { x += 1; } println!("{}", x); Change that code to: let mut x = 0i; while ... { x += 1; } println!("{}", x); Closes #15201. [breaking-change]
2014-06-28auto merge of #15208 : alexcrichton/rust/snapshots, r=pcwaltonbors-19/+27
This change registers new snapshots, allowing `*T` to be removed from the language. This is a large breaking change, and it is recommended that if compiler errors are seen that any FFI calls are audited to determine whether they should be actually taking `*mut T`.
2014-06-28Rename all raw pointers as necessaryAlex Crichton-19/+27
2014-06-28Add remark and an example about the bounds of `Vec::insert`Tobias Bucher-1/+4
2014-06-27Update to 0.11.0 0.11.0Alex Crichton-2/+2
2014-06-24librustc: Remove cross borrowing from mutable `Box`es to `&mut`.Patrick Walton-6/+6
This will break code like: fn f(x: &mut int) {} let mut a = box 1i; f(a); Change it to: fn f(x: &mut int) {} let mut a = box 1i; f(&mut *a); RFC 33; issue #10504. [breaking-change]
2014-06-24core: Add stability attributes to CloneBrian Anderson-0/+1
The following are tagged 'unstable' - core::clone - Clone - Clone::clone - impl Clone for Arc - impl Clone for arc::Weak - impl Clone for Rc - impl Clone for rc::Weak - impl Clone for Vec - impl Clone for Cell - impl Clone for RefCell - impl Clone for small tuples The following are tagged 'experimental' - Clone::clone_from - may not provide enough utility - impls for various extern "Rust" fns - may not handle lifetimes correctly See https://github.com/rust-lang/rust/wiki/Meeting-API-review-2014-06-23#clone
2014-06-24librustc: Remove the fallback to `int` from typechecking.Niko Matsakis-429/+431
This breaks a fair amount of code. The typical patterns are: * `for _ in range(0, 10)`: change to `for _ in range(0u, 10)`; * `println!("{}", 3)`: change to `println!("{}", 3i)`; * `[1, 2, 3].len()`: change to `[1i, 2, 3].len()`. RFC #30. Closes #6023. [breaking-change]
2014-06-24std: Bring back half of Add on StringAlex Crichton-0/+17
This adds an implementation of Add for String where the rhs is <S: Str>. The other half of adding strings is where the lhs is <S: Str>, but coherence and the libcore separation currently prevent that.
2014-06-22Register new snapshotsAlex Crichton-1/+0
2014-06-21collections: fix running `make check-stage1-collections`Erick Tryzelaar-0/+3
2014-06-21std: micro-optimize Vec constructors and add benchmarksErick Tryzelaar-0/+115
Generally speaking, inlining doesn't really help out with constructing vectors, except for when we construct a zero-sized vector. This patch allows llvm to optimize this case away in a lot of cases, which shaves off 4-8ns. It's not much, but it might help in some inner loop somewhere. before: running 12 tests test bench_extend_0 ... bench: 123 ns/iter (+/- 6) test bench_extend_5 ... bench: 323 ns/iter (+/- 11) test bench_from_fn_0 ... bench: 7 ns/iter (+/- 0) test bench_from_fn_5 ... bench: 49 ns/iter (+/- 6) test bench_from_iter_0 ... bench: 11 ns/iter (+/- 0) test bench_from_iter_5 ... bench: 176 ns/iter (+/- 11) test bench_from_slice_0 ... bench: 8 ns/iter (+/- 1) test bench_from_slice_5 ... bench: 73 ns/iter (+/- 5) test bench_new ... bench: 0 ns/iter (+/- 0) test bench_with_capacity_0 ... bench: 6 ns/iter (+/- 1) test bench_with_capacity_100 ... bench: 41 ns/iter (+/- 3) test bench_with_capacity_5 ... bench: 40 ns/iter (+/- 2) after: test bench_extend_0 ... bench: 123 ns/iter (+/- 7) test bench_extend_5 ... bench: 339 ns/iter (+/- 27) test bench_from_fn_0 ... bench: 7 ns/iter (+/- 0) test bench_from_fn_5 ... bench: 54 ns/iter (+/- 4) test bench_from_iter_0 ... bench: 11 ns/iter (+/- 1) test bench_from_iter_5 ... bench: 182 ns/iter (+/- 16) test bench_from_slice_0 ... bench: 4 ns/iter (+/- 0) test bench_from_slice_5 ... bench: 62 ns/iter (+/- 3) test bench_new ... bench: 0 ns/iter (+/- 0) test bench_with_capacity_0 ... bench: 0 ns/iter (+/- 0) test bench_with_capacity_100 ... bench: 41 ns/iter (+/- 1) test bench_with_capacity_5 ... bench: 41 ns/iter (+/- 3)
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-13 20:47:10 +0000