about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
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.
2020-09-10BTreeMap: pull the map's root out of NodeRefStein Somers-117/+163
2020-09-09Add documentation for `impl<T> From<BinaryHeap<T>> for Vec<T>`Michael Howell-0/+4
2020-09-09Remove internal and unstable MaybeUninit::UNINIT.Mara Bos-3/+3
Looks like it is no longer necessary, as uninit_array() can be used instead in the few cases where it was needed.
2020-09-09BTreeMap: avoid aliasing by avoiding slicesStein Somers-167/+203
2020-09-09make as_leaf return a raw pointer, to reduce aliasing assumptionsRalf Jung-7/+12
2020-09-08Capitalize safety commentsFlying-Toast-1/+1
2020-09-08Update library/alloc/src/collections/vec_deque.rs Braden Nelson-1/+1
Replace lshift with multiply Co-authored-by: Mara Bos <m-ou.se@m-ou.se>
2020-09-08Convert MAXIMUM_ZST_CAPACITY to be calculated in amoonheart08-6/+2
const instead of multiple target_pointer_width checks.
2020-09-05rename MaybeUninit slice methodsRalf Jung-11/+15
first_ptr -> slice_as_ptr first_ptr_mut -> slice_as_mut_ptr slice_get_ref -> slice_assume_init_ref slice_get_mut -> slice_assume_init_mut
2020-09-04Auto merge of #75200 - ssomers:btree_valmut, r=Mark-Simulacrumbors-171/+319
BTreeMap: introduce marker::ValMut and reserve Mut for unique access The mutable BTreeMap iterators (apart from `DrainFilter`) are double-ended, meaning they have to rely on a front and a back handle that each represent a reference into the tree. Reserve a type category `marker::ValMut` for them, so that we guarantee that they cannot reach operations on handles with borrow type `marker::Mut`and that these operations can assume unique access to the tree. Including #75195, benchmarks report no genuine change: ``` benchcmp old new --threshold 5 name old ns/iter new ns/iter diff ns/iter diff % speedup btree::map::iter_100 3,333 3,023 -310 -9.30% x 1.10 btree::map::range_unbounded_vs_iter 36,624 31,569 -5,055 -13.80% x 1.16 ``` r? @Mark-Simulacrum
2020-09-04Auto merge of #75207 - dylni:add-slice-check-range, r=KodrAusbors-26/+13
Add `slice::check_range` This method is useful for [`RangeBounds`] parameters. It's even been [rewritten](https://github.com/rust-lang/rust/blob/22ee68dc586440f96b76b32fbd6087507c6afdb9/src/librustc_data_structures/sorted_map.rs#L214) [many](https://github.com/rust-lang/rust/blob/22ee68dc586440f96b76b32fbd6087507c6afdb9/library/alloc/src/vec.rs#L1299) [times](https://github.com/rust-lang/rust/blob/22ee68dc586440f96b76b32fbd6087507c6afdb9/library/core/src/slice/mod.rs#L2441) in the standard library, sometimes assuming that the bounds won't be [`usize::MAX`]. For example, [`Vec::drain`] creates an empty iterator when [`usize::MAX`] is used as an inclusive end bound: ```rust assert!(vec![1].drain(..=usize::max_value()).eq(iter::empty())); ``` If this PR is merged, I'll create another to use it for those methods. [`RangeBounds`]: https://doc.rust-lang.org/std/ops/trait.RangeBounds.html [`usize::MAX`]: https://doc.rust-lang.org/std/primitive.usize.html#associatedconstant.MAX [`Vec::drain`]: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.drain
2020-09-03generalize in-place collect to types of same size and alignmentThe8472-2/+4
2020-09-03pacify tidyThe8472-3/+3
2020-09-03mark as_inner as unsafe and update commentsThe8472-1/+1
2020-09-03avoid exposing that binary heap's IntoIter is backed by vec::IntoIter, use a ↵The8472-3/+9
private trait instead
2020-09-03hide binary_heap::IntoIter internals behind impl TraitThe8472-1/+1
2020-09-03mark SourceIter as unsafe, document invariantsThe8472-1/+1
2020-09-03in-place collect for Vec. Box<[]> and BinaryHeap IntoIter and some adaptersThe8472-1/+14
2020-09-02Same typos in vec_dequeAnton-2/+2
2020-09-01Will land in 1.48, not 1.47Jon Gjengset-1/+1
2020-09-01Merge branch 'master' into stabilize-vecdeque-make_contiguousJon Gjengset-387/+3021
2020-08-24Add more information to safety commentdylni-1/+3
2020-08-23Prefer https link for wikipedia URLsLzu Tao-3/+3
2020-08-21Apply suggestions from code reviewLeSeulArtichaut-6/+2
Co-authored-by: Joshua Nelson <joshua@yottadb.com>
2020-08-21Use intra-doc-links in `alloc`LeSeulArtichaut-7/+4
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-13 12:50:40 +0000