about summary refs log tree commit diff
path: root/src/liballoc/collections
AgeCommit message (Collapse)AuthorLines
2019-08-22Fix formatting.Tomasz Różański-1/+1
2019-08-22Fix a typo.Tomasz Różański-1/+1
2019-08-18Auto merge of #63045 - Rosto75:master, r=jonas-schievinkbors-43/+43
Change the placement of two functions. Right now, the order is as follows: `pop_front()` `push_front()` `push_back()` `pop_back()` `swap_remove_back()` `swap_remove_front()` I believe it would be more natural, and easier to follow, if we place `pop_back()` right after the `pop_front()`, and `swap_remove_back()` after the `swap_remove_front()` like this: `pop_front()` `pop_back()` `push_front()` `push_back()` `swap_remove_front()` `swap_remove_back()` The rest of the documentation (at least in this module) adheres to the same logic, where the 'front' function always precedes its 'back' equivalent.
2019-08-16Add the Layout of the failed allocation to TryReserveError::AllocErrorSimon Sapin-11/+14
… and add a separately-unstable field to force non-exhaustive matching (`#[non_exhaustive]` is no implemented yet on enum variants) so that we have the option to later expose the allocator’s error value. CC https://github.com/rust-lang/wg-allocators/issues/23
2019-08-16Rename CollectionAllocError to TryReserveErrorSimon Sapin-13/+13
2019-08-14Auto merge of #63534 - Mark-Simulacrum:stage0-bump, r=Centrilbors-3/+3
Bump to 1.39 r? @Centril
2019-08-14Handle cfg(bootstrap) throughoutMark Rousskov-3/+3
2019-08-12Apply suggestions from code reviewObserver42-2/+2
Co-Authored-By: Mazdak Farrokhzad <twingoow@gmail.com>
2019-08-12Document From trait for BinaryHeapObserver42-0/+3
2019-08-02Remove some more `cfg(test)`sVadim Petrochenkov-1/+0
2019-08-02liballoc: Unconfigure tests during normal buildVadim Petrochenkov-656/+650
Remove additional libcore-like restrictions from liballoc, turns out the testing works ok if the tests are a part of liballoc itself.
2019-07-28Rollup merge of #63061 - Centril:constantly-improving, r=scottmcmMazdak Farrokhzad-26/+14
In which we constantly improve the Vec(Deque) array PartialEq impls Use the same approach as in https://github.com/rust-lang/rust/pull/62435 as sanctioned by https://github.com/rust-lang/rust/issues/61415#issuecomment-504155110. r? @scottmcm
2019-07-28Rollup merge of #62806 - mati865:clippy, r=TimNNMazdak Farrokhzad-7/+7
Fix few Clippy warnings
2019-07-28Use const generics for some VecDeque impls.Mazdak Farrokhzad-26/+14
2019-07-27Change the placement of two functions.Tomasz Różański-43/+43
Right now, the order is as follows: `pop_front()` `push_front()` `push_back()` `pop_back()` `swap_remove_back()` `swap_remove_front()` I believe it would be more natural, and easier to follow, if we place `pop_back()` right after the `pop_front()`, and `swap_remove_back()` after the `swap_remove_front()` like this: `pop_front()` `pop_back()` `push_front()` `push_back()` `swap_remove_front()` `swap_remove_back()` The rest of the documentation (at least in this module) adheres to the same logic, where the 'front' function always precedes its 'back' equivalent.
2019-07-25Auto merge of #60340 - mgeier:cap-vs-capacity, r=alexcrichtonbors-17/+17
Rename .cap() methods to .capacity() As mentioned in #60316, there are a few `.cap()` methods, which seem out-of-place because such methods are called `.capacity()` in the rest of the code. This PR renames them to `.capacity()` but leaves `RawVec::cap()` in there for backwards compatibility. I didn't try to mark the old version as "deprecated", because I guess this would cause too much noise.
2019-07-22Rollup merge of #62858 - Rosto75:master, r=jonas-schievinkMazdak Farrokhzad-4/+4
Change wrong variable name. r? @steveklabnik
2019-07-21Change wrong variable name.Tomasz Różański-4/+4
2019-07-19use const array repeat expressions for uninit_arrayRalf Jung-3/+3
2019-07-18Rollup merge of #61926 - scottmcm:vec-vecdeque, r=Mark-SimulacrumMark Rousskov-0/+6
Fix hyperlinks in From impls between Vec and VecDeque I'd been trying to link them, but apparently actually just added brackets: <https://doc.rust-lang.org/nightly/std/collections/struct.VecDeque.html#impl-From%3CVec%3CT%3E%3E> ~~This reverts commit 5168f5d220d0b30d322f254f51142931a9054056.~~ ~~(I'd previously tried to make relative links, but those failed linkcheck because the types are exported at different levels. So just skip the links -- they're already linked in the function signature anyway.)~~ This makes the links now work.
2019-07-18Fix clippy::len_zero warningsMateusz Mikuła-3/+3
2019-07-18Fix clippy::clone_on_copy warningsMateusz Mikuła-4/+4
2019-07-05Rollup merge of #62123 - jeremystucki:needless_lifetimes_std, r=alexcrichtonMazdak Farrokhzad-5/+5
Remove needless lifetimes (std) Split from #62039
2019-07-04Rollup merge of #62316 - khuey:efficient_last, r=sfacklerMazdak Farrokhzad-0/+60
When possible without changing semantics, implement Iterator::last in terms 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 This is attempt 2 of #60130. r? @sfackler
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/+60
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-07-01Convert more usages overChris Gregory-3/+3
2019-07-01Remove needless lifetimesJeremy Stucki-5/+5
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-22Revert "Add implementations of last in terms of next_back on a bunch of ↵Steven Fackler-70/+0
DoubleEndedIterators." This reverts commit 3e86cf36b5114f201868bf459934fe346a76a2d4.
2019-05-20Rollup merge of #60952 - dtolnay:heap, r=AmanieuMazdak Farrokhzad-0/+43
Document BinaryHeap time complexity I went into some detail on the time complexity of `push` because it is relevant for using BinaryHeap efficiently -- specifically that you should avoid pushing many elements in ascending order when possible. r? @Amanieu Closes #47976. Closes #59698.
2019-05-18Document BinaryHeap time complexityDavid Tolnay-0/+43
I went into some detail on the time complexity of `push` because it is relevant for using BinaryHeap efficiently -- specifically that you should avoid pushing many elements in ascending order when possible.
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-14Rollup merge of #60130 - khuey:efficient_last, r=sfacklerMazdak Farrokhzad-0/+70
Add implementations of last in terms of next_back on a bunch of DoubleEndedIterators Provided a `DoubleEndedIterator` has finite length, `Iterator::last` is equivalent to `DoubleEndedIterator::next_back`. But searching forwards through the iterator when it's unnecessary is obviously not good for performance. I ran into this on one of the collection iterators. I tried adding appropriate overloads for a bunch of the iterator adapters like filter, map, etc, but I ran into a lot of type inference failures after doing so. The other interesting case is what to do with `Repeat`. Do we consider it part of the contract that `Iterator::last` will loop forever on it? The docs do say that the iterator will be evaluated until it returns None. This is also relevant for the adapters, it's trivially easy to observe whether a `Map` adapter invoked its closure a zillion times or just once for the last element.
2019-05-12Auto merge of #60396 - cuviper:ordered-retain, r=scottmcmbors-2/+16
Document the order of {Vec,VecDeque,String}::retain 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. r? @scottmcm
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-05-01BinaryHeap: add min-heap exampleAlexey Shmalko-0/+24
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-19Add implementations of last in terms of next_back on a bunch of ↵Kyle Huey-0/+70
DoubleEndedIterators. r?Manishearth
2019-04-19Auto merge of #60072 - RalfJung:linked-list, r=shepmasterbors-11/+37
fix LinkedList invalidating mutable references The test `test_insert_prev` failed in Miri due to what I consider a bug in `LinkedList`: in various places, `NonNull::as_mut` got called to modify the `prev`/`next` pointers of existing nodes. In particular, the unstable `insert_next` has to modify the `next` pointer of the node that was last handed out by the iterator; to this end it creates a mutable reference to the *entire node* that overlaps with the mutable reference to the node's content that was handed out by the iterator! Thus, the next use if said mutable reference is UB. In code: ```rust loop { match it.next() { // mutable reference handed to us None => break, Some(elt) => { it.insert_next(*elt + 1); // this invalidates `elt` because it creates an overlapping mutable reference match it.peek_next() { Some(x) => assert_eq!(*x, *elt + 2), // this use of `elt` now is a use of an invalid pointer None => assert_eq!(8, *elt), } } } } ``` This PR fixes that by using `as_ptr` instead of `as_mut`. This avoids invalidating the mutable reference that was handed to the user. I did this in all methods called by iterators, just to be sure. Cc @Gankro
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 17:58:05 +0000