about summary refs log tree commit diff
path: root/src/liballoc/collections/linked_list.rs
AgeCommit message (Collapse)AuthorLines
2020-07-27mv std libs to library/mark-1904/+0
2020-07-19Use italics for O notationpierwill-10/+10
Co-authored-by: Guillaume Gomez <guillaume1.gomez@gmail.com>
2020-06-19`#[deny(unsafe_op_in_unsafe_fn)]` in liballocLeSeulArtichaut-11/+25
2020-05-29Add Extend::{extend_one,extend_reserve}Josh Stone-0/+10
This adds new optional methods on `Extend`: `extend_one` add a single element to the collection, and `extend_reserve` pre-allocates space for the predicted number of incoming elements. These are used in `Iterator` for `partition` and `unzip` as they shuffle elements one-at-a-time into their respective collections.
2020-05-04whoopsmain()-1/+1
2020-05-04Add remove_current_as_list to LinkedList's CursorMutmain()-0/+25
The `remove_current` method only returns the inner `T` and deallocates the list node. This is unnecessary for move operations, where the element is going to be linked back into this (or even a different) `LinkedList`. The `remove_current_as_list` method avoids this by returning the unlinked list node as a new single-element `LinkedList` structure .
2020-04-26fix more clippy warningsMatthias Krüger-1/+1
clippy::{redundant_pattern_matching, clone_on_copy, iter_cloned_collect, option_as_ref_deref, match_ref_pats}
2020-04-25Rollup merge of #71548 - crlf0710:cursor_bounds, r=AmanieuDylan DPC-0/+12
Add missing Send and Sync impls for linked list Cursor and CursorMut. Someone pointed out these to me, and i think it's indeed reasonable to add those impl. r? @Amanieu
2020-04-25Rollup merge of #71168 - SimonSapin:into_raw_non_null, r=AmanieuDylan DPC-9/+7
Deprecate `{Box,Rc,Arc}::into_raw_non_null` Per ongoing FCP at https://github.com/rust-lang/rust/issues/47336#issuecomment-586589016 See also https://github.com/rust-lang/rust/issues/47336#issuecomment-614054164
2020-04-25Use the correct bound for `Cursor` `Send`Charles Lew-1/+1
Co-Authored-By: Amanieu d'Antras <amanieu@gmail.com>
2020-04-25Add missing Send and Sync bounds for linked list Cursor and CursorMut.Charles Lew-0/+12
2020-04-17Rollup merge of #71167 - RalfJung:big-o, r=shepmasterDylan DPC-10/+10
big-O notation: parenthesis for function calls, explicit multiplication I saw `O(n m log n)` in the docs and found that really hard to parse. In particular, I don't think we should use blank space as syntax for *both* multiplication and function calls, that is just confusing. This PR makes both multiplication and function calls explicit using Rust-like syntax. If you prefer, I can also leave one of them implicit, but I believe explicit is better here. While I was at it I also added backticks consistently.
2020-04-17Implement `Clone` for `liballoc::collections::linked_list::Cursor`.Charles Lew-0/+8
2020-04-15Deprecate `Box::into_raw_non_null`Simon Sapin-9/+7
Per https://github.com/rust-lang/rust/issues/47336#issuecomment-586589016
2020-04-15big-O notation: parenthesis, multiplication and backticksRalf Jung-10/+10
2020-03-12remove lifetimes that can be elided (clippy::needless_lifetimes)Matthias Krüger-1/+1
2020-03-07Rollup merge of #69773 - matthiaskrgr:typos, r=petrochenkovMazdak Farrokhzad-3/+3
fix various typos
2020-03-06Don't redundantly repeat field names (clippy::redundant_field_names)Matthias Krüger-1/+1
2020-03-06fix various typosMatthias Krüger-3/+3
2020-02-26Auto merge of #67290 - jonas-schievink:leak-audit, r=KodrAusbors-1/+18
Audit liballoc for leaks in `Drop` impls when user destructor panics Inspired by https://github.com/rust-lang/rust/pull/67243 and https://github.com/rust-lang/rust/pull/67235, this audits and hopefully fixes the remaining `Drop` impls in liballoc for resource leaks in the presence of panics in destructors called by the affected `Drop` impl. This does not touch `Hash{Map,Set}` since they live in hashbrown. They have similar issues though. r? @KodrAus
2020-02-19Add LinkedList::remove()Bijan Tabatabai-0/+46
LinkedList::remove() removes the element at the specified index and returns it. Signed-off-by: Bijan Tabatabai <bijan311@yahoo.com>
2020-01-19FormatJonas Schievink-2/+5
2020-01-19Avoid leak in DrainFilter when a drop panicsJonas Schievink-1/+15
2020-01-14Update APIs according to RFC change suggestions.Charles Lew-10/+33
2020-01-12Address review comments.Charles Lew-2/+24
2020-01-12Address review comments.Charles Lew-78/+155
2020-01-12Implement Cursor for linked lists. (RFC 2570).Charles Lew-24/+433
2019-12-26Remove redundant link textsMatthew Kraai-1/+1
2019-12-22Format the worldMark Rousskov-72/+38
2019-12-18Propagate cfg bootstrapMark Rousskov-4/+1
2019-12-13Require stable/unstable annotations for the constness of all stable ↵Oliver Scherer-0/+4
functions with a `const` modifier
2019-12-12LinkedList: drop remaining items when drop panicsJonas Schievink-1/+15
2019-11-07Rollup merge of #66117 - olegnn:fixed_linked_list_marker, r=RalfJungYuki Okushi-1/+1
Fixed PhantomData markers in Arc and Rc Include owned internal structs in `PhantomData` markers in `Arc` (`PhantomData<T>` => `PhantomData<ArcInner<T>>`) and `Rc` (`PhantomData<T>` => `PhantomData<RcBox<T>>`).
2019-11-05Reverted PhantomData in LinkedList, fixed PhantomData markers in Rc and ArcOleg Nosov-2/+2
2019-11-05LinkedList: PhantomData<Box<Node<T>>> => PhantomData<T>Oleg Nosov-3/+3
2019-10-31docs: improve disclaimer regarding LinkedListTshepang Lekhonkhobe-7/+7
2019-10-02Use zipped iterators in clone_from for LinkedListCharles Gleason-2/+2
2019-10-01Implement Clone::clone_from for LinkedListCharles Gleason-0/+13
2019-08-18Constify LinkedList new functionGrayJack-1/+1
2019-08-02liballoc: Unconfigure tests during normal buildVadim Petrochenkov-270/+3
Remove additional libcore-like restrictions from liballoc, turns out the testing works ok if the tests are a part of liballoc itself.
2019-07-18Fix clippy::clone_on_copy warningsMateusz Mikuła-4/+4
2019-07-04Rollup merge of #62316 - khuey:efficient_last, r=sfacklerMazdak Farrokhzad-0/+10
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-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-07-01Convert more usages overChris Gregory-1/+1
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
2019-04-19fix LinkedList invalidating mutable referencesRalf Jung-11/+37
2019-04-18make liballoc internal test suite mostly pass in MiriRalf Jung-0/+2
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-17Use more impl header lifetime elisionScott McMurray-4/+4
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-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-10/+11
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-03 06:38:22 +0000