about summary refs log tree commit diff
path: root/src/liballoc/collections/btree
AgeCommit message (Collapse)AuthorLines
2019-10-23proposal for access to BTreeMap/BTreeSet first/last, #62924Stein Somers-11/+214
2019-10-18BTreeSet symmetric_difference & union optimized, cleanedStein Somers-120/+119
2019-10-01Rollup merge of #64912 - lzutao:unneeded-main-doc, r=jonas-schievinkMazdak Farrokhzad-2/+0
Remove unneeded `fn main` blocks from docs ## [No whitespace diff](https://github.com/rust-lang/rust/pull/64912/files?w=1)
2019-10-01BTreeSet intersection, difference & is_subnet optimizationsStein Somers-75/+155
2019-10-01Remove unneeded `fn main` blocks from docsLzu Tao-2/+0
2019-09-27Stabilize map_get_key_value featureLzu Tao-2/+1
2019-09-16Improve BTreeSet::Intersection::size_hintpcpthm-22/+22
The commented invariant that an iterator is smaller than other iterator was violated after next is called and two iterators are consumed at different rates.
2019-08-14Handle cfg(bootstrap) throughoutMark Rousskov-3/+3
2019-07-28Rollup merge of #62806 - mati865:clippy, r=TimNNMazdak Farrokhzad-3/+3
Fix few Clippy warnings
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-18Fix clippy::len_zero warningsMateusz Mikuła-3/+3
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/+35
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/+35
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-2/+2
2019-07-01Remove needless lifetimesJeremy Stucki-5/+5
2019-05-22Revert "Add implementations of last in terms of next_back on a bunch of ↵Steven Fackler-55/+0
DoubleEndedIterators." This reverts commit 3e86cf36b5114f201868bf459934fe346a76a2d4.
2019-04-19Add implementations of last in terms of next_back on a bunch of ↵Kyle Huey-0/+55
DoubleEndedIterators. r?Manishearth
2019-04-05Use for_each to extend collectionsJosh Stone-4/+4
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-03-29improve worst-case performance of BTreeSet difference and intersectionStein Somers-65/+233
2019-03-26adjust MaybeUninit API to discussionsRalf Jung-5/+5
uninitialized -> uninit into_initialized -> assume_init read_initialized -> read set -> write
2019-02-22Rollup merge of #58431 - RalfJung:btree, r=Mark-SimulacrumMazdak Farrokhzad-15/+42
fix overlapping references in BTree This fixes two kinds of overlapping references in BTree (both found by running the BTree test suite in Miri). In `into_slices_mut`, we did `k.into_key_slice_mut()` followed by `self.into_val_slice_mut()` (where `k` is a copy of `self`). Calling `into_val_slice_mut` calls `self.len()`, which creates a shared reference to `NodeHeader`, which unfortunately (due to padding) overlaps with the mutable reference returned by `into_key_slice_mut`. Hence the key slice got (partially) invalidated. The fix is to avoid creating an `&NodeHeader` after the first slice got created. In the iterators, we used to first create the references that will be returned, and then perform the walk on the tree. Walking the tree creates references (such as `&mut InternalNode`) that overlap with all of the keys and values stored in a pointer; in particular, they overlap with the references the iterator will later return. This is fixed by reordering the operations of walking the tree and obtaining the inner references. The test suite still passes (and it passes in Miri now!), but there is a lot of code here that I do not understand...
2019-02-20Rollup merge of #58553 - scottmcm:more-ihle, r=Centrilkennytm-20/+20
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-17Use more impl header lifetime elisionScott McMurray-20/+20
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-14split MaybeUninit into several features, expand docs a bitRalf Jung-2/+2
2019-02-13fix invalidating references in BTree iteratorsRalf Jung-13/+21
2019-02-13fix overlapping mutable and shared references in BTreeMap's into_slices_mutRalf Jung-3/+22
2019-02-10libs: doc commentsAlexander Regueiro-5/+5
2019-02-10tests: doc commentsAlexander Regueiro-3/+3
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-42/+26
2019-02-02liballoc: fix some idiom lints.Mazdak Farrokhzad-35/+35
2019-02-02liballoc: elide some lifetimes.Mazdak Farrokhzad-38/+37
2019-02-02liballoc: apply uniform_paths.Mazdak Farrokhzad-2/+3
2019-02-02liballoc: prefer imports of borrow from libcore.Mazdak Farrokhzad-9/+7
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-33/+42
2019-02-02liballoc: cargo check passes on 2018Mazdak Farrokhzad-6/+6
2019-01-28rename first_mut_ptr -> first_ptr_mutRalf Jung-5/+5
2019-01-28add macro for creating uninitialized arrayRalf Jung-9/+3
2019-01-28avoid some raw ptr casts in BTreeMapRalf Jung-7/+10
2019-01-28avoid mem::uninitialized in BTreeMapRalf Jung-9/+16
2018-12-28Auto merge of #55519 - fhartwig:hashmap-index-example, r=Centrilbors-0/+3
Add example of using the indexing operator to HashMap docs Fixes #52575
2018-12-25Remove licensesMark Rousskov-50/+0
2018-12-11TypoAlexis Beingessner-1/+1
Co-Authored-By: RalfJung <post@ralfj.de>
2018-12-09avoid as_leaf_mut asserting exclusive accessRalf Jung-30/+33
2018-12-09fix BTree creating shared references that are not entirely in-boundsRalf Jung-29/+86
2018-12-07Various minor/cosmetic improvements to codeAlexander Regueiro-6/+6
2018-12-07Fix broken doc testCorey Farwell-1/+1
2018-12-05Fix typo in variable nameCorey Farwell-1/+1
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-26 05:13:13 +0000