about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2020-11-22Rollup merge of #79297 - ssomers:btree_post_redux, r=Mark-SimulacrumMara Bos-14/+14
BTreeMap: swap the names of NodeRef::new and Root::new_leaf #78104 preserved the name of Root::new_leaf to minimize changes, but the resulting names are confusing. r? `@Mark-Simulacrum`
2020-11-22Rollup merge of #79295 - ssomers:btree_fix_78903, r=Mark-SimulacrumMara Bos-16/+15
BTreeMap: fix minor testing mistakes in #78903 Mostly a duplicate test case r? `@Mark-Simulacrum`
2020-11-22Rollup merge of #79267 - ssomers:btree_namespaces, r=Mark-SimulacrumMara Bos-35/+33
BTreeMap: address namespace conflicts Fix an annoyance popping up whenever synchronizing the test cases with a version capable of miri-track-raw-pointers. r? `@Mark-Simulacrum`
2020-11-22BTreeMap: swap the names of NodeRef::new and Root::new_leafStein Somers-14/+14
2020-11-22BTreeMap: fix minor testing mistakes in #78903Stein Somers-16/+15
2020-11-21More consistently use spaces after commas in lists in docsCarol (Nichols || Goulding)-6/+6
2020-11-21BTreeMap: address namespace conflictsStein Somers-35/+33
2020-11-18BTreeMap: reuse NodeRef as Root, keep BoxedNode for edges only, ban UniqueStein Somers-141/+132
2020-11-16Rollup merge of #78903 - ssomers:btree_order_chaos_testing, r=Mark-SimulacrumMara Bos-26/+201
BTreeMap: test chaotic ordering & other bits & bobs r? `@Mark-Simulacrum`
2020-11-16Rollup merge of #77691 - exrook:rename-layouterr, r=KodrAusMara Bos-3/+3
Rename/Deprecate LayoutErr in favor of LayoutError Implements rust-lang/wg-allocators#73. This patch renames LayoutErr to LayoutError, and uses a type alias to support users using the old name. The new name will be instantly stable in release 1.49 (current nightly), the type alias will become deprecated in release 1.51 (so that when the current nightly is 1.51, 1.49 will be stable). This is the only error type in `std` that ends in `Err` rather than `Error`, if this PR lands all stdlib error types will end in `Error` :smiling_face_with_three_hearts:
2020-11-16Auto merge of #78631 - ssomers:btree-alias_for_underfull, r=Mark-Simulacrumbors-203/+320
BTreeMap: fix pointer provenance rules in underfullness Continuing on #78480, and for readability, and possibly for performance: avoid aliasing when handling underfull nodes, and consolidate the code doing that. In particular: - Avoid the rather explicit aliasing for internal nodes in `remove_kv_tracking`. - Climb down to the root to handle underfull nodes using a reborrowed handle, rather than one copied with `ptr::read`, before resuming on the leaf level. - Integrate the code tracking leaf edge position into the functions performing changes, rather than bolting it on. r? `@Mark-Simulacrum`
2020-11-15Rollup merge of #79026 - mbrubeck:btree_retain, r=m-ou-seJonas Schievink-0/+70
Implement BTreeMap::retain and BTreeSet::retain Adds new methods `BTreeMap::retain` and `BTreeSet::retain`. These are implemented on top of `drain_filter` (#70530). The API of these methods is identical to `HashMap::retain` and `HashSet::retain`, which were implemented in #39560 and stabilized in #36648. The docs and tests are also copied from HashMap/HashSet. The new methods are unstable, behind the `btree_retain` feature gate, with tracking issue #79025. See also rust-lang/rfcs#1338.
2020-11-15stabilize deque_rangeSpyros Roum-6/+2
2020-11-13Add BTreeMap::retain and BTreeSet::retainMatt Brubeck-0/+70
2020-11-13refactor: vec_deque ignore-tidy-filelengthC-472/+514
commit c547d5fabcd756515afa7263ee5304965bb4c497 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 11:22:23 2020 +0000 test: updating ui/hygiene/panic-location.rs expected commit 2af03769c4ffdbbbad75197a1ad0df8c599186be Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 10:43:30 2020 +0000 fix: documentation unresolved link commit c4b0df361ce27d7392d8016229f2e0265af32086 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:58:31 2020 +0000 style: compiling with Rust's style guidelines commit bdd2de5f3c09b49a18e3293f2457fcab25557c96 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:56:31 2020 +0000 refactor: removing ignore-tidy-filelength commit fcc4b3bc41f57244c65ebb8e4efe4cbc9460b5a9 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:51:35 2020 +0000 refactor: moving trait RingSlices to ring_slices.rs commit 2f0cc539c06d8841baf7f675168f68ca7c21e68e Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:46:09 2020 +0000 refactor: moving struct PairSlices to pair_slices.rs commit a55d3ef1dab4c3d85962b3a601ff8d1f7497faf2 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:31:45 2020 +0000 refactor: moving struct Iter to iter.rs commit 76ab33a12442a03726f36f606b4e0fe70f8f246b Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:24:32 2020 +0000 refactor: moving struct IntoIter into into_iter.rs commit abe0d9eea2933881858c3b1bc09df67cedc5ada5 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 02:19:07 2020 +0000 refactor: moving struct IterMut into iter_mut.rs commit 70ebd6420335e1895e2afa2763a0148897963e24 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 01:49:15 2020 +0000 refactor: moved macros into macros.rs commit b08dd2add994b04ae851aa065800bd8bd6326134 Author: C <DeveloperC@protonmail.com> Date: Sat Oct 31 01:05:36 2020 +0000 refactor: moving vec_deque.rs to vec_deque/mod.rs
2020-11-12Rollup merge of #78857 - SkiFire13:bheap-opt, r=KodrAusMara Bos-13/+19
Improve BinaryHeap performance By changing the condition in the loops from `child < end` to `child < end - 1` we're guaranteed that `right = child + 1 < end` and since finding the index of the biggest sibling can be done with an arithmetic operation we can remove a branch from the loop body. The case where there's no right child, i.e. `child == end - 1` is instead handled outside the loop, after it ends; note that if the loops ends early we can use `return` instead of `break` since the check `child == end - 1` will surely fail. I've also removed a call to `<[T]>::swap` that was hiding a bound check that [wasn't being optimized by LLVM](https://godbolt.org/z/zrhdGM). A quick benchmarks on my pc shows that the gains are pretty significant: |name |before ns/iter |after ns/iter |diff ns/iter |diff % |speedup | |---------------------|----------------|---------------|--------------|----------|--------| |find_smallest_1000 | 352,565 | 260,098 | -92,467 | -26.23% | x 1.36 | |from_vec | 676,795 | 473,934 | -202,861 | -29.97% | x 1.43 | |into_sorted_vec | 469,511 | 304,275 | -165,236 | -35.19% | x 1.54 | |pop | 483,198 | 373,778 | -109,420 | -22.64% | x 1.29 | The other 2 benchmarks for `BinaryHeap` (`peek_mut_deref_mut` and `push`) weren't impacted and as such didn't show any significant change.
2020-11-12BTreeMap: test chaotic ordering & other bits & bobsStein Somers-26/+201
2020-11-12BTreeMap: avoid aliasing while handling underfull nodesStein Somers-203/+320
2020-11-11Rollup merge of #78417 - ssomers:btree_chop_up_2, r=Mark-SimulacrumJonas Schievink-114/+176
BTreeMap: split off most code of append To complete #78056, move the last single-purpose pieces of code out of map.rs into a separate module. Also, tweaked documentation and safeness - I doubt think this code would be safe if the iterators passed in wouldn't be as sorted as the method says they should be - and bounds on MergeIterInner. r? ```@Mark-Simulacrum```
2020-11-09Added SAFETY comment as requestGiacomo Stevanato-0/+4
2020-11-09BTreeMap: fix pointer provenance rules, make borrowing explicitStein Somers-247/+327
2020-11-09Rollup merge of #78476 - RalfJung:btree-alias, r=Mark-SimulacrumDylan DPC-4/+8
fix some incorrect aliasing in the BTree This line is wrong: ``` ptr::copy(slice.as_ptr().add(idx), slice.as_mut_ptr().add(idx + 1), slice.len() - idx); ``` When `slice.as_mut_ptr()` is called, that creates a mutable reference to the entire slice, which invalidates the raw pointer previously returned by `slice.as_ptr()`. (Miri currently misses this because raw pointers are not tracked properly.) Cc ````````@ssomers````````
2020-11-09Rollup merge of #78437 - ssomers:btree_no_ord_at_node_level, r=Mark-SimulacrumDylan DPC-41/+22
BTreeMap: stop mistaking node for an orderly place A second mistake in #77612 was to ignore the node module's rightful comment "this module doesn't care whether the entries are sorted". And there's a much simpler way to visit the keys in order, if you check this separately from a single pass checking everything. r? ````````@Mark-Simulacrum````````
2020-11-08BTreeMap: split off most code of append, slightly improve interfacesStein Somers-114/+176
2020-11-07Remove useless bound checks from into_sorted_vecGiacomo Stevanato-1/+4
2020-11-07Remove useless branches from sift_down_range loopGiacomo Stevanato-6/+6
2020-11-07Remove branches from sift_down_to_bottom loopGiacomo Stevanato-6/+5
2020-11-07Rollup merge of #78538 - ssomers:btree_testing_rng, r=Mark-SimulacrumYuki Okushi-0/+3
BTreeMap: document a curious assumption in test cases r? ```@Mark-Simulacrum```
2020-11-01Rollup merge of #78602 - RalfJung:raw-ptr-aliasing-issues, r=m-ou-seMara Bos-2/+3
fix various aliasing issues in the standard library This fixes various cases where the standard library either used raw pointers after they were already invalidated by using the original reference again, or created raw pointers for one element of a slice and used it to access neighboring elements.
2020-10-31fix aliasing issue in binary_heapRalf Jung-2/+3
2020-10-30Constantify more BTreeMap and BTreeSet functionsBenoît du Garreau-4/+22
- BTreeMap::len - BTreeMap::is_empty - BTreeSet::len - BTreeSet::is_empty
2020-10-29BTreeMap: document a curious assumption in test casesStein Somers-0/+3
2020-10-28fix some incorrect aliasing in the BTreeRalf Jung-4/+8
2020-10-27BTreeMap: stop mistaking node for an orderly placeStein Somers-41/+22
2020-10-27Auto merge of #78359 - ssomers:btree_cleanup_mem, r=Mark-Simulacrumbors-40/+42
BTreeMap: move generic support functions out of navigate.rs A preparatory step chipped off #78104, useful in general (if at all). r? `@Mark-Simulacrum`
2020-10-26Auto merge of #77187 - TimDiekmann:box-alloc, r=Amanieubors-1/+1
Support custom allocators in `Box` r? `@Amanieu` This pull request requires a crater run. ### Prior work: - #71873 - #58457 - [`alloc-wg`](https://github.com/TimDiekmann/alloc-wg)-crate Currently blocked on: - ~#77118~ - ~https://github.com/rust-lang/chalk/issues/615 (#77515)~
2020-10-26BTreeMap: move generic functions out of navigate.rsStein Somers-40/+42
2020-10-25Auto merge of #78015 - ssomers:btree_merge_mergers, r=Mark-Simulacrumbors-97/+111
btree: merge the implementations of MergeIter Also remove the gratuitous Copy bounds. Same benchmark performance. r? `@Mark-Simulacrum`
2020-10-25Merge remote-tracking branch 'upstream/master' into box-allocTim Diekmann-824/+1012
2020-10-24BTreeMap: stop mistaking node::MIN_LEN as a node level constraintStein Somers-55/+55
2020-10-22BTreeMap/Set: merge the implementations of MergeIterStein Somers-97/+111
2020-10-21Rollup merge of #78056 - ssomers:btree_chop_up_1, r=dtolnayYuki Okushi-222/+239
BTreeMap: split off most code of remove and split_off Putting map.rs on a diet, in addition to #77851. r? @dtolnay
2020-10-20BTreeMap: less sharing, more similarity between leaf and internal nodesStein Somers-45/+36
2020-10-20BTreeMap: reuse BoxedNode instances directly instead of their contentsStein Somers-7/+3
2020-10-20Rollup merge of #77612 - ssomers:btree_cleanup_2, r=Mark-SimulacrumYuki Okushi-79/+115
BTreeMap: test invariants more thoroughly and more readably r? @Mark-Simulacrum
2020-10-19BTreeMap: test invariants more thoroughly and more readablyStein Somers-79/+115
2020-10-18Stabilize or_insert_with_keyChai T. Rex-2/+1
2020-10-18Auto merge of #76885 - dylni:move-slice-check-range-to-range-bounds, r=KodrAusbors-1/+1
Move `slice::check_range` to `RangeBounds` Since this method doesn't take a slice anymore (#76662), it makes more sense to define it on `RangeBounds`. Questions: - Should the new method be `assert_len` or `assert_length`?
2020-10-18BTreeMap: split off most code of remove and split_offStein Somers-222/+239
2020-10-18Rollup merge of #77851 - exrook:split-btreemap, r=dtolnayYuki Okushi-468/+480
BTreeMap: refactor Entry out of map.rs into its own file btree/map.rs is approaching the 3000 line mark, splitting out the entry code buys about 500 lines of headroom. I've created this PR because the changes I've made in #77438 will push `map.rs` over the 3000 line limit and cause tidy to complain. I picked `Entry` to factor out because it feels less tightly coupled to the rest of `BTreeMap` than the various iterator implementations. Related: #60302
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-07-12 23:52:04 +0000