about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
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
2020-08-19BTreeMap: introduce marker::ValMut and reserve marker::Mut for unique accessStein Somers-171/+319
2020-08-18BTreeMap: check some invariants, avoid recursion in depth first searchStein Somers-41/+302
2020-08-16Replace ad hoc implementations with `slice::check_range`dylni-26/+11
2020-08-15Auto merge of #75488 - ssomers:btree_revert_75257, r=Mark-Simulacrumbors-49/+20
Revert the fundamental changes in #74762 and #75257 Before possibly going over to #75487. Also contains some added and fixed comments. r? @Mark-Simulacrum
2020-08-14Rollup merge of #75531 - ssomers:btree_tests_migration, r=Mark-SimulacrumTyler Mandry-0/+2173
Migrate unit tests of btree collections to their native breeding ground There's one BTreeSet test case that I couldn't easily convince to come along, maybe because it truly is an integration test. But leaving it in place would mean git wouldn't see the move so I also moved it to a new file. r? @Mark-Simulacrum
2020-08-14Rollup merge of #75519 - ssomers:btree_splitpoint_cleanup, r=Mark-SimulacrumTyler Mandry-31/+36
BTreeMap: refactor splitpoint and move testing over to unit test r? @Mark-Simulacrum
2020-08-14Rollup merge of #75195 - ssomers:btree_split_up_into_kv_mut, r=Mark-SimulacrumTyler Mandry-9/+19
BTreeMap: purge innocent use of into_kv_mut Replace the use of `into_kv_mut` into more precise calls. This makes more sense if you know that the single remaining use of `into_kv_mut` is in fact evil and can be trialled in court (#75200) and sent to a correction facility (#73971). No real performance difference reported (but functions that might benefit a tiny constant bit like `BTreeMap::get_mut` aren't benchmarked): ``` benchcmp old new --threshold 5 name old ns/iter new ns/iter diff ns/iter diff % speedup btree::map::clone_fat_100 63,073 59,256 -3,817 -6.05% x 1.06 btree::map::iter_100 3,514 3,235 -279 -7.94% x 1.09 ```
2020-08-14Move btree unit test to their native, privileged locationStein Somers-0/+2173
2020-08-14BTreeMap: refactor splitpoint and move testing over to unit testStein Somers-31/+36
2020-08-14BTreeMap: refactor splitpoint and move testing over to unit testStein Somers-31/+36
2020-08-14Auto merge of #74777 - ssomers:btree_cleanup_7, r=Mark-Simulacrumbors-20/+16
Stop BTreeMap casts from reborrowing Down in btree/node.rs, the interface and use of `cast_unchecked` look a bit shady. It's really just there for inverting `forget_type` which does not borrow. By borrowing we can't write the same `cast_unchecked` in the same way at the Handle level. No change in undefined behaviour or performance.
2020-08-13Reverts the fundamental changes in #74762 and #75257Stein Somers-49/+20
2020-08-13Stop BTreeMap casts from reborrowingStein Somers-20/+16
2020-08-12Somewhat complicated way to respect BTreeMap's node length invariantStein Somers-16/+65
2020-08-11BTreeMap: purge innocent use of into_kv_mutStein Somers-9/+19
2020-08-10Manually implement Debug for BTreeMap::ValuesMut structNazım Can Altınova-1/+24
Deriving debug prints all the values including keys. But ValuesMut struct should only print the values.
2020-08-10Manually implement Debug for BTreeMap::{IntoKeys,IntoValues} structsNazım Can Altınova-6/+27
2020-08-09BTreeMap: better distinguish the root holder from the root nodeStein Somers-42/+51
2020-08-08Auto merge of #75163 - canova:map_into_keys_values, r=dtolnaybors-0/+148
Implement `into_keys` and `into_values` for associative maps This PR implements `into_keys` and `into_values` for HashMap and BTreeMap types. They are implemented as unstable, under `map_into_keys_values` feature. Fixes #55214. r? @dtolnay
2020-08-08Update the tracking issue number of map_into_keys_valuesNazım Can Altınova-12/+12
2020-08-08Remove min/max values from IntoValues Iterator implementationNazım Can Altınova-8/+0
2020-08-08Auto merge of #75257 - ssomers:btree_74762_again, r=Mark-Simulacrumbors-32/+25
BTreeMap: better way to postpone root access in DrainFilter A slightly more elegant (in my opinion) adaptation of #74762. Benchmarks seem irrationally pleased to: ``` benchcmp old new --threshold 5 name old ns/iter new ns/iter diff ns/iter diff % speedup btree::map::clone_fat_100_and_remove_all 215,182 185,052 -30,130 -14.00% x 1.16 btree::map::clone_fat_100_and_remove_half 139,667 127,945 -11,722 -8.39% x 1.09 btree::map::clone_fat_val_100_and_remove_all 96,755 81,279 -15,476 -16.00% x 1.19 btree::map::clone_fat_val_100_and_remove_half 64,678 56,911 -7,767 -12.01% x 1.14 btree::map::find_rand_100 18 17 -1 -5.56% x 1.06 btree::map::first_and_last_0 33 35 2 6.06% x 0.94 btree::map::first_and_last_100 40 54 14 35.00% x 0.74 btree::map::insert_rand_100 45 42 -3 -6.67% x 1.07 btree::map::insert_rand_10_000 45 41 -4 -8.89% x 1.10 btree::map::iter_0 2,010 1,759 -251 -12.49% x 1.14 btree::map::iter_100 3,514 2,764 -750 -21.34% x 1.27 btree::map::iter_10k 4,018 3,768 -250 -6.22% x 1.07 btree::map::range_unbounded_unbounded 37,269 28,929 -8,340 -22.38% x 1.29 btree::map::range_unbounded_vs_iter 31,518 28,814 -2,704 -8.58% x 1.09 ``` r? @Mark-Simulacrum
2020-08-07Auto merge of #75071 - ssomers:btree_cleanup_5, r=Mark-Simulacrumbors-53/+51
BTreeMap: enforce the panic rule imposed by `replace` Also, reveal the unsafe parts in the closures fed to it. r? @Mark-Simulacrum
2020-08-07BTreeMap: enforce the panic rule imposed by `replace`Stein Somers-53/+51
2020-08-07BTreeMap: better way to postpone root access in DrainFilterStein Somers-32/+25
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 03:48:27 +0000