about summary refs log tree commit diff
path: root/library/alloc/src/collections
AgeCommit message (Collapse)AuthorLines
2020-12-13Auto merge of #79987 - ssomers:btree_cleanup_4, r=Mark-Simulacrumbors-0/+2
BTreeMap: detect bulk_steal's count-1 underflow in release builds too r? `@Mark-Simulacrum`
2020-12-13Auto merge of #79376 - ssomers:btree_choose_parent_kv, r=Mark-Simulacrumbors-12/+14
BTreeMap: clarify comments and panics around choose_parent_kv Fixes a lie in recent code: `unreachable!("empty non-root node")` should shout "empty internal node", but it might as well be good and keep quiet r? `@Mark-Simulacrum`
2020-12-13fix typoJustus K-1/+1
2020-12-13BTreeMap: more expressive local variables in mergeStein Somers-28/+27
2020-12-13BTreeMap: declare clear_parent_link directly on the root it needsStein Somers-10/+11
2020-12-13fix panic if converting ZST Vec to VecDequeJustus K-2/+6
2020-12-13Auto merge of #79994 - JohnTitor:rollup-43wl2uj, r=JohnTitorbors-62/+0
Rollup of 12 pull requests Successful merges: - #79360 (std::iter: document iteration over `&T` and `&mut T`) - #79398 (Link loop/for keyword) - #79834 (Remove deprecated linked_list_extras methods.) - #79845 (Fix rustup support in default_build_triple for python3) - #79940 (fix more clippy::complexity findings) - #79942 (Add post-init hook for static memory for miri.) - #79954 (Fix building compiler docs with stage 0) - #79963 (Fix typo in `DebruijnIndex` documentation) - #79970 (Misc rustbuild improvements when the LLVM backend isn't used) - #79973 (rustdoc light theme: Fix CSS for selected buttons) - #79984 (Remove an unused dependency that made `rustdoc` crash) - #79985 (Fixes submit event of the search input) Failed merges: r? `@ghost` `@rustbot` modify labels: rollup
2020-12-13Rollup merge of #79834 - m-ou-se:bye-linked-list-extras, r=Mark-SimulacrumYuki Okushi-62/+0
Remove deprecated linked_list_extras methods. https://github.com/rust-lang/rust/issues/27794#issuecomment-667524201: > I'd say give it about 2 weeks then remove them. It's been 18 weeks. Time to remove them. :) Closes #27794.
2020-12-13BTreeMap: capture a recurring use pattern as replace_kvStein Somers-8/+10
2020-12-13BTreeMap: detect bulk_steal's count-1 underflow in release builds tooStein Somers-0/+2
2020-12-12BTreeMap: clarify comments and panics surrounding choose_parent_kvStein Somers-12/+14
2020-12-08Remove deprecated linked_list_extras methods.Mara Bos-62/+0
2020-12-08fix unsoundness in `make_contiguous`Bastian Kauschke-5/+27
2020-12-07Removed spurious linebreak from new documentationChai T. Rex-1/+1
2020-12-07Improved documentation for HashMap/BTreeMap Entry's .or_insert_with_key methodChai T. Rex-3/+6
2020-12-05Auto merge of #78373 - matthewjasper:drop-on-into, r=pnkfelixbors-1/+1
Don't leak return value after panic in drop Closes #47949
2020-12-04Avoid leaking block expression valuesMatthew Jasper-1/+1
2020-12-04 Rename `AllocRef` to `Allocator` and `(de)alloc` to `(de)allocate`Tim Diekmann-5/+5
2020-12-01Update rustc version that or_insert_with_key landedChai T. Rex-1/+1
2020-11-28BTreeMap: try to enhance various comments & local identifiersStein Somers-89/+118
2020-11-24Rollup merge of #79358 - ssomers:btree_public_comments, r=Mark-SimulacrumJonas Schievink-4/+6
BTreeMap/BTreeSet: make public doc more consistent Tweaks #72876 and #73667 and propagate them to `BTreeSet`.
2020-11-24Rollup merge of #79354 - ssomers:btree_bereave_BoxedNode, r=Mark-SimulacrumJonas Schievink-38/+12
BTreeMap: cut out the ceremony around BoxedNode The opposite direction of #79093. r? ``@Mark-Simulacrum``
2020-11-23BTreeMap/BTreeSet: make public doc more consistentStein Somers-4/+6
2020-11-23BTreeMap: cut out the ceremony around BoxedNodeStein Somers-38/+12
2020-11-23doc typooliver-2/+2
plus a small edit for clarity
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
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-28 06:17:54 +0000