about summary refs log tree commit diff
path: root/src/liballoc/collections/vec_deque.rs
AgeCommit message (Collapse)AuthorLines
2019-07-03Fix the links in Vec(Deque)-from-Vec(Deque)Scott McMurray-0/+6
Ok, I can't use `std` in doc-links, only in doc-tests. Try 7...
2019-07-02When possible without changing semantics, implement Iterator::last in terms ↵Kyle Huey-0/+10
of DoubleEndedIterator::next_back for types in liballoc and libcore. Provided that the iterator has finite length and does not trigger user-provided code, this is safe. What follows is a full list of the DoubleEndedIterators in liballoc/libcore and whether this optimization is safe, and if not, why not. src/liballoc/boxed.rs Box: Pass through to avoid defeating optimization of the underlying DoubleIterator implementation. This has no correctness impact. src/liballoc/collections/binary_heap.rs Iter: Pass through to avoid defeating optimizations on slice::Iter IntoIter: Not safe, changes Drop order Drain: Not safe, changes Drop order src/liballoc/collections/btree/map.rs Iter: Safe to call next_back, invokes no user defined code. IterMut: ditto IntoIter: Not safe, changes Drop order Keys: Safe to call next_back, invokes no user defined code. Values: ditto ValuesMut: ditto Range: ditto RangeMut: ditto src/liballoc/collections/btree/set.rs Iter: Safe to call next_back, invokes no user defined code. IntoIter: Not safe, changes Drop order Range: Safe to call next_back, invokes no user defined code. src/liballoc/collections/linked_list.rs Iter: Safe to call next_back, invokes no user defined code. IterMut: ditto IntoIter: Not safe, changes Drop order src/liballoc/collections/vec_deque.rs Iter: Safe to call next_back, invokes no user defined code. IterMut: ditto IntoIter: Not safe, changes Drop order Drain: ditto src/liballoc/string.rs Drain: Safe because return type is a primitive (char) src/liballoc/vec.rs IntoIter: Not safe, changes Drop order Drain: ditto Splice: ditto src/libcore/ascii.rs EscapeDefault: Safe because return type is a primitive (u8) src/libcore/iter/adapters/chain.rs Chain: Not safe, invokes user defined code (Iterator impl) src/libcore/iter/adapters/flatten.rs FlatMap: Not safe, invokes user defined code (Iterator impl) Flatten: ditto FlattenCompat: ditto src/libcore/iter/adapters/mod.rs Rev: Not safe, invokes user defined code (Iterator impl) Copied: ditto Cloned: Not safe, invokes user defined code (Iterator impl and T::clone) Map: Not safe, invokes user defined code (Iterator impl + closure) Filter: ditto FilterMap: ditto Enumerate: Not safe, invokes user defined code (Iterator impl) Skip: ditto Fuse: ditto Inspect: ditto src/libcore/iter/adapters/zip.rs Zip: Not safe, invokes user defined code (Iterator impl) src/libcore/iter/range.rs ops::Range: Not safe, changes Drop order, but ALREADY HAS SPECIALIZATION ops::RangeInclusive: ditto src/libcore/iter/sources.rs Repeat: Not safe, calling last should iloop. Empty: No point, iterator is at most one item long. Once: ditto OnceWith: ditto src/libcore/option.rs Item: No point, iterator is at most one item long. Iter: ditto IterMut: ditto IntoIter: ditto src/libcore/result.rs Iter: No point, iterator is at most one item long IterMut: ditto IntoIter: ditto src/libcore/slice/mod.rs Split: Not safe, invokes user defined closure SplitMut: ditto RSplit: ditto RSplitMut: ditto Windows: Safe, already has specialization Chunks: ditto ChunksMut: ditto ChunksExact: ditto ChunksExactMut: ditto RChunks: ditto RChunksMut: ditto RChunksExact: ditto RChunksExactMut: ditto src/libcore/str/mod.rs Chars: Safe, already has specialization CharIndices: ditto Bytes: ditto Lines: Safe to call next_back, invokes no user defined code. LinesAny: Deprecated Everything that is generic over P: Pattern: Not safe because Pattern invokes user defined code. SplitWhitespace: Safe to call next_back, invokes no user defined code. SplitAsciiWhitespace: ditto
2019-06-11Remove the questionably-useful exampleScott McMurray-22/+0
2019-06-08Add hyperlinks to Vec and VecDequeScott McMurray-2/+2
Let's try the auto-linking instead, since the relative ones don't work.
2019-06-08Apply suggestions from code reviewscottmcm-1/+1
Co-Authored-By: Joe ST <joe@fbstj.net>
2019-06-08Put the docs on the methods instead of the implsScott McMurray-53/+53
Since simulacrum suggested (on Discord) they're better there.
2019-06-08Apply suggestions from code reviewscottmcm-10/+10
Co-Authored-By: Mazdak Farrokhzad <twingoow@gmail.com>
2019-06-08Add some Vec <-> VecDeque documentationScott McMurray-0/+53
These are more than just `.into_iter().collect()`, so talk about some of their nuances.
2019-05-19Rollup merge of #60678 - DutchGhost:master, r=scottmcmMazdak Farrokhzad-6/+2
Stabilize vecdeque_rotate This PR stabilizes the vecdeque_rotate feature. r? @scottmcm Closes https://github.com/rust-lang/rust/issues/56686
2019-05-10Add examples of ordered retainJosh Stone-0/+14
2019-05-09supposed to be 1.36.0Dodo-2/+2
2019-05-09make vecdeque_rotate stableDodo-6/+2
2019-04-29Document the order of {Vec,VecDeque,String}::retainJosh Stone-2/+2
It's natural for `retain` to work in order from beginning to end, but this wasn't actually documented to be the case. If we actually promise this, then the caller can do useful things like track the index of each element being tested, as [discussed in the forum][1]. This is now documented for `Vec`, `VecDeque`, and `String`. [1]: https://users.rust-lang.org/t/vec-retain-by-index/27697 `HashMap` and `HashSet` also have `retain`, and the `hashbrown` implementation does happen to use a plain `iter()` order too, but it's not certain that this should always be the case for these types.
2019-04-27Rename .cap() methods to .capacity()Matthias Geier-17/+17
... but leave the old names in there for backwards compatibility.
2019-04-26Use "capacity" as parameter name in with_capacity() methodsMatthias Geier-4/+4
Closes #60271.
2019-04-25ignore-tidy-filelength on all files with greater than 3000 linesvarkor-0/+2
2019-04-19move variable down to where it is usedRalf Jung-5/+5
2019-04-18make liballoc internal test suite mostly pass in MiriRalf Jung-1/+10
2019-04-05Use for_each to extend collectionsJosh Stone-3/+1
This updates the `Extend` implementations to use `for_each` for many collections: `BinaryHeap`, `BTreeMap`, `BTreeSet`, `LinkedList`, `Path`, `TokenStream`, `VecDeque`, and `Wtf8Buf`. Folding with `for_each` enables better performance than a `for`-loop for some iterators, especially if they can just forward to internal iterators, like `Chain` and `FlatMap` do.
2019-02-22Rollup merge of #58064 - llogiq:vec-deque-try-rfold, r=scottmcmMazdak Farrokhzad-5/+46
override `VecDeque::try_rfold`, also update iterator This keeps the slice based iteration and updates the iterator state after each slice. It also uses a loop to reduce the amount of code. This uses unsafe code, so some thorough review would be appreciated. Cc @RalfJung
2019-02-20Rollup merge of #58553 - scottmcm:more-ihle, r=Centrilkennytm-3/+3
Use more impl header lifetime elision Inspired by seeing explicit lifetimes on these two: - https://doc.rust-lang.org/nightly/std/slice/struct.Iter.html#impl-FusedIterator - https://doc.rust-lang.org/nightly/std/primitive.u32.html#impl-Not And a follow-up to https://github.com/rust-lang/rust/pull/54687, that started using IHLE in libcore. Most of the changes in here fall into two big categories: - Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop`, `Debug`, and `Clone`) - Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`) I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations [where the flipped one cannot elide the lifetime](https://internals.rust-lang.org/t/impl-type-parameter-aliases/9403/2?u=scottmcm). I also removed two lifetimes that turned out to be completely unused; see https://github.com/rust-lang/rust/issues/41960#issuecomment-464557423
2019-02-18override `VecDeque::try_rfold`, also update iteratorAndre Bogus-5/+46
This keeps the slice based iteration and updates the iterator state after each slice. It also uses a loop to reduce the amount of code. This uses unsafe code, so some thorough review would be appreciated.
2019-02-17Use more impl header lifetime elisionScott McMurray-3/+3
There are two big categories of changes in here - Removing lifetimes from common traits that can essentially never user a lifetime from an input (particularly `Drop` & `Debug`) - Forwarding impls that are only possible because the lifetime doesn't matter (like `impl<R: Read + ?Sized> Read for &mut R`) I omitted things that seemed like they could be more controversial, like the handful of iterators that have a `Item: 'static` despite the iterator having a lifetime or the `PartialEq` implementations where the flipped one cannot elide the lifetime.
2019-02-10libs: doc commentsAlexander Regueiro-4/+4
2019-02-10tests: doc commentsAlexander Regueiro-2/+2
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-19/+13
2019-02-02liballoc: fix some idiom lints.Mazdak Farrokhzad-8/+8
2019-02-02liballoc: elide some lifetimes.Mazdak Farrokhzad-21/+21
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-20/+23
2019-02-02liballoc: cargo check passes on 2018Mazdak Farrokhzad-3/+3
2019-01-30override `VecDeque`'s `Iter::try_fold`Andre Bogus-1/+9
2018-12-25Remove licensesMark Rousskov-10/+0
2018-12-23Rollup merge of #57002 - scottmcm:stabilize-resize_with, r=rkruppekennytm-3/+1
Stabilize Vec(Deque)::resize_with Closes #41758
2018-12-19Stabilize Vec(Deque)::resize_withScott McMurray-3/+1
Closes #41758
2018-12-15Add a note about why the unsafe is soundScott McMurray-0/+10
2018-12-15Add unstable VecDeque::rotate_{left|right}Scott McMurray-0/+102
2018-12-13Auto merge of #56161 - RalfJung:vecdeque-stacked-borrows, r=SimonSapinbors-1/+4
VecDeque: fix for stacked borrows `VecDeque` violates a version of stacked borrows where creating a shared reference is not enough to make a location *mutably accessible* from raw pointers (and I think that is the version we want). There are two problems: * Creating a `NonNull<T>` from `&mut T` goes through `&T` (inferred for a `_`), then `*const T`, then `NonNull<T>`. That means in this stricter version of Stacked Borrows, we cannot actually write to such a `NonNull` because it was created from a shared reference! This PR fixes that by going from `&mut T` to `*mut T` to `*const T`. * `VecDeque::drain` creates the `Drain` struct by *first* creating a `NonNull` from `self` (which is an `&mut VecDeque`), and *then* calling `self.buffer_as_mut_slice()`. The latter reborrows `self`, asserting that `self` is currently the unique pointer to access this `VecDeque`, and hence invalidating the `NonNull` that was created earlier. This PR fixes that by instead using `self.buffer_as_slice()`, which only performs read accesses and creates only shared references, meaning the raw pointer (`NonNull`) remains valid. It is possible that other methods on `VecDeque` do something similar, miri's test coverage of `VecDeque` is sparse to say the least. Cc @nikomatsakis @Gankro
2018-12-07Drain only needs a shared referenceRalf Jung-7/+5
2018-12-07VecDeque::drain: make sure the 'drain' raw pointer is actually still usableRalf Jung-2/+7
2018-12-04Replace usages of `..i + 1` ranges with `..=i`.Corey Farwell-9/+9
2018-12-03Rollup merge of #56432 - ordovicia:shrink-to-issue, r=Centrilkennytm-1/+1
Update issue number of `shrink_to` methods to point the tracking issue Tracking issue: #56431
2018-12-02Update issue number of `shrink_to` methods to point the tracking issueHidehito Yabuuchi-1/+1
2018-11-30Move VecDeque::resize_with out of the impl<T:Clone> blockScott McMurray-33/+27
2018-11-17Add VecDeque::resize_withScott McMurray-1/+39
2018-10-28msp430: fix compilation of liballocJorge Aparicio-0/+2
2018-10-05Revert "Slightly refactor VecDeque implementation"Alex Crichton-3/+3
This reverts commit 6ce76acae455a32113116cd2f95f8076388fc2d3.
2018-10-05Revert "Optimize VecDeque::append"Alex Crichton-27/+2
This reverts commit 11e488b64fed181820280d494d4fcc157ee1adc5.
2018-10-05Revert "Add docs and debug asserts"Alex Crichton-23/+11
This reverts commit 1a1a7f6167edf18b8a0ab488e651f7748cc2e9d3.
2018-10-05Revert "Fix tidy"Alex Crichton-2/+1
This reverts commit 1908892d3f60008f265dfc25ac46db387c0ad6a0.
2018-10-05Revert "Add another assert"Alex Crichton-4/+0
This reverts commit 21d2a6c9868541ec9829ced9a5bae936b18741c5.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-24 02:36:58 +0000