about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2020-10-03BTreeMap: comment why drain_filter's size_hint is somewhat pessimistictidStein Somers-0/+4
2020-10-03BTreeMap: refactoring around edges, missed spotsStein Somers-7/+7
2020-10-03Rollup merge of #75377 - canova:map_debug_impl, r=dtolnayJonas Schievink-7/+51
Fix Debug implementations of some of the HashMap and BTreeMap iterator types HashMap's `ValuesMut`, BTreeMaps `ValuesMut`, IntoValues and `IntoKeys` structs were printing both keys and values on their Debug implementations. But they are iterators over either keys or values. Irrelevant values should not be visible. With this PR, they only show relevant fields. This fixes #75297. [Here's an example code.](https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=0c79356ed860e347a0c1a205616f93b7) This prints this on nightly: ``` ValuesMut { inner: IterMut { range: [(1, "hello"), (2, "goodbye")], length: 2 } } IntoKeys { inner: [(1, "hello"), (2, "goodbye")] } IntoValues { inner: [(1, "hello"), (2, "goodbye")] } [(2, "goodbye"), (1, "hello")] ``` After the patch this example prints these instead: ``` ["hello", "goodbye"] ["hello", "goodbye"] [1, 2] ["hello", "goodbye"] ``` I didn't add test cases for them, since I couldn't see any tests for Debug implementations anywhere. But please let me know if I should add it to a specific place. r? @dtolnay
2020-10-02BTreeMap: document DrainFilterInner betterStein Somers-2/+6
2020-10-01BTreeMap: use Unique::from to avoid a cast where type information existsStein Somers-1/+1
2020-10-01BTreeMap: admit the existence of leaf edges in commentsStein Somers-22/+12
2020-09-30Rollup merge of #77233 - ssomers:btree_size_matters, r=Mark-SimulacrumJonas Schievink-0/+9
BTreeMap: keep an eye out on the size of the main components r? @Mark-Simulacrum
2020-09-27Use relative links instead of intra-doc linksJoshua Nelson-1/+1
Previously, `BTreeMap` tried to link to `crate::collections`, intending for the link to go to `std/collections/index.html`. But `BTreeMap` is defined in `alloc`, so after the fix in the previous commit, the links instead went to `alloc/collections/index.html`, which has almost no information. This changes it to link to `index.html`, which only works when viewing from `std::collections::BTreeMap`, the most common place to visit the docs. Fixing it to work from anywhere would require the docs for `std::collections` to be duplicated in `alloc::collections`, which in turn would require HashMap to be `alloc` for intra-doc links to work (https://github.com/rust-lang/rust/issues/74481).
2020-09-26BTreeMap: keep an eye out on the size of the main componentsStein Somers-0/+9
2020-09-25Rollup merge of #77005 - ssomers:btree_cleanup_3, r=Mark-SimulacrumJonas Schievink-110/+99
BtreeMap: refactoring around edges Parts chipped off a more daring effort, that the btree benchmarks judge to be performance-neutral. r? @Mark-Simulacrum
2020-09-25BTreeMap: various tweaksStein Somers-61/+50
2020-09-25BTreeMap: introduce edge methods similar to those of keys and valuesStein Somers-24/+34
2020-09-25BTreeMap: refactor correct_childrens_parent_linksStein Somers-26/+16
2020-09-23Use Self in allocAlexis Bourget-2/+2
2020-09-21Rollup merge of #76983 - ssomers:btree_extra_test, r=Mark-SimulacrumRalf Jung-6/+25
BTreeMap: extra testing & fixed comments r? @Mark-Simulacrum
2020-09-21Auto merge of #75974 - SkiFire13:peekmut-opt-sift, r=LukasKalbertodtbors-2/+4
Avoid useless sift_down when std::collections::binary_heap::PeekMut is never mutably dereferenced If `deref_mut` is never called then it's not possible for the element to be mutated without internal mutability, meaning there's no need to call `sift_down`. This could be a little improvement in cases where you want to mutate the biggest element of the heap only if it satisfies a certain predicate that needs only read access to the element.
2020-09-20BTreeMap: extra testing unveiling mistakes in future PRStein Somers-6/+25
2020-09-20Rollup merge of #76926 - ssomers:btree_cleanup_1, r=Mark-SimulacrumRalf Jung-7/+7
BTreeMap: code readability tweaks Gathered over the past months r? @Mark-Simulacrum
2020-09-20Rollup merge of #76877 - denisvasilik:intra-doc-links-alloc-vec-deque, r=jyn514Ralf Jung-23/+28
Move to intra-doc links in collections/vec_deque.rs and collections/vec_deque/drain.rs Helps with #75080. @rustbot modify labels: T-doc, A-intra-doc-links
2020-09-20Rollup merge of #76876 - denisvasilik:intra-doc-links-alloc, r=jyn514Ralf Jung-12/+8
Move to intra-doc links in collections/btree/map.rs and collections/linked_list.rs Helps with #75080. @rustbot modify labels: T-doc, A-intra-doc-links
2020-09-20Rollup merge of #76875 - denisvasilik:intra-doc-links-alloc-binary-heap, ↵Ralf Jung-20/+14
r=jyn514 Move to intra-doc links in library/alloc/src/collections/binary_heap.rs Helps with #75080. @rustbot modify labels: T-doc, A-intra-doc-links
2020-09-20Rollup merge of #76722 - ssomers:btree_send_sync, r=Mark-SimulacrumRalf Jung-0/+143
Test and fix Send and Sync traits of BTreeMap artefacts Fixes #76686. I'm not quite sure what all this implies. E.g. comparing with the definitions for `NodeRef` in node.rs, maybe an extra bound `T: 'a` is useful for something. The test compiles on stable/beta (apart from `drain_filter`) so I bet `Sync` is equally desirable. r? @Mark-Simulacrum
2020-09-20Fix time complexity in BinaryHeap::peek_mut docsGiacomo Stevanato-1/+2
2020-09-20Set sift=true only when PeekMut yields a mutable referenceGiacomo Stevanato-1/+2
2020-09-19Use intra-doc linksDenis Vasilik-12/+8
2020-09-19Auto merge of #76929 - ssomers:btree_cleanup_2, r=Mark-Simulacrumbors-20/+22
BTreeMap: wrap node's raw parent pointer in NonNull Now that the other `*const` (root) is gone, seemed like a small step forward. r? `@Mark-Simulacrum`
2020-09-19BTreeMap: wrap node's raw parent pointer in NonNullStein Somers-20/+22
2020-09-19BTreeMap: code readability tweaksStein Somers-7/+7
2020-09-19Use `T::BITS` instead of `size_of::<T> * 8`.Mara Bos-2/+2
2020-09-18Rename method to `assert_len`dylni-1/+1
2020-09-18Move `slice::check_range` to `RangeBounds`dylni-1/+1
2020-09-18Update library/alloc/src/collections/binary_heap.rsDenis Vasilik-1/+1
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
2020-09-18Update library/alloc/src/collections/binary_heap.rsDenis Vasilik-1/+1
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
2020-09-18Update library/alloc/src/collections/binary_heap.rsDenis Vasilik-1/+1
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
2020-09-18Update library/alloc/src/collections/binary_heap.rsDenis Vasilik-1/+1
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
2020-09-18Use intra-doc linksDenis Vasilik-2/+1
2020-09-18Move to intra-doc linksDenis Vasilik-21/+27
2020-09-18Use intra-doc linksDenis Vasilik-16/+10
2020-09-18Auto merge of #76790 - ssomers:btree_slice_slasher_returns, r=Mark-Simulacrumbors-16/+29
BTreeMap: avoid slices even more Epilogue to #73971: it seems the compiler is unable to realize that creating a slice and `get_unchecked`-ing one element is a simple fetch. So try to spell it out for the only remaining but often invoked case. Also, the previous code doesn't seem fair game to me, using `get_unchecked` to reach beyond the end of a slice. Although the local function `slice_insert` also does that. r? `@Mark-Simulacrum`
2020-09-16Rollup merge of #76662 - RalfJung:lib-test-miri, r=Mark-SimulacrumRalf Jung-5/+1
Fix liballoc test suite for Miri Mostly, fix the regression introduced by https://github.com/rust-lang/rust/pull/75207 that caused slices (i.e., references) to be created to invalid memory or memory that has aliasing pointers that we want to keep valid. @dylni this changes the type of `check_range` to only require the length, not the full reference to the slice, which indeed is all the information this function requires. Also reduce the size of a test introduced in https://github.com/rust-lang/rust/pull/70793 to make it not take 3 minutes in Miri. This makes https://github.com/RalfJung/miri-test-libstd work again.
2020-09-16Rollup merge of #76534 - notriddle:doc-comments, r=jyn514Ralf Jung-0/+4
Add doc comments for From impls https://github.com/rust-lang/rust/issues/51430
2020-09-16BTreeMap: avoid slices even moreStein Somers-16/+29
2020-09-15fix slice::check_range aliasing problemsRalf Jung-5/+1
2020-09-15Test and fix Sync & Send traits of BTreeMap artefactsStein Somers-0/+143
2020-09-13Rollup merge of #76527 - fusion-engineering-forks:cleanup-uninit, ↵Jonas Schievink-3/+3
r=jonas-schievink Remove internal and unstable MaybeUninit::UNINIT. Looks like it is no longer necessary, as `uninit_array()` can be used instead in the few cases where it was needed. (I wanted to just add `#[doc(hidden)]` to remove clutter from the documentation, but looks like it can just be removed entirely.)
2020-09-10Auto merge of #74437 - ssomers:btree_no_root_in_noderef, r=Mark-Simulacrumbors-117/+163
BTreeMap: move up reference to map's root from NodeRef Since the introduction of `NodeRef` years ago, it also contained a mutable reference to the owner of the root node of the tree (somewhat disguised as *const). Its intent is to be used only when the rest of the `NodeRef` is no longer needed. Moving this to where it's actually used, thought me 2 things: - Some sort of "postponed mutable reference" is required in most places that it is/was used, and that's exactly where we also need to store a reference to the length (number of elements) of the tree, for the same reason. The length reference can be a normal reference, because the tree code does not care about tree length (just length per node). - It's downright obfuscation in `from_sorted_iter` (transplanted to #75329) - It's one of the reasons for the scary notice on `reborrow_mut`, the other one being addressed in #73971. This does repeat the raw pointer code in a few places, but it could be bundled up with the length reference. r? `@Mark-Simulacrum`
2020-09-09Rollup merge of #76543 - ssomers:btree_cleanup_4, r=Mark-SimulacrumTyler Mandry-0/+3
Document btree's unwrap_unchecked #74693's second wind
2020-09-10Document btree's unwrap_uncheckedStein Somers-0/+3
2020-09-09Rollup merge of #76504 - Flying-Toast:master, r=lcnrTyler Mandry-1/+1
Capitalize safety comments
2020-09-09Rollup merge of #76481 - moonheart08:vec_deque_constify, r=sfacklerTyler Mandry-6/+2
Convert repetitive target_pointer_width checks to const solution. Simply a quick code tidying change. Not sure if more needs to be said.
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-25 14:41:12 +0000