about summary refs log tree commit diff
path: root/src/liballoc/collections/btree
AgeCommit message (Collapse)AuthorLines
2020-04-05Rollup merge of #70795 - Amanieu:btree_remove_tracking, r=Mark-SimulacrumDylan DPC-49/+64
Keep track of position when deleting from a BTreeMap This improves the performance of drain_filter and is needed for future Cursor support for BTreeMap. cc @ssomers r? @Mark-Simulacrum
2020-04-05Apply review feedbackAmanieu d'Antras-15/+10
2020-04-05Keep track of position when deleting from a BTreeMapAmanieu d'Antras-39/+59
This improves the performance of drain_filter and is needed for future Cursor support for BTreeMap.
2020-04-04use ManuallyDrop instead of forget inside collectionsTrevor Spiteri-8/+8
This commit changes some usage of mem::forget into mem::ManuallyDrop in some Vec, VecDeque, BTreeMap and Box methods. Before the commit, the generated IR for some of the methods was longer, and even after optimization, some unwinding artifacts were still present.
2020-04-02Auto merge of #70362 - TimDiekmann:alloc-overhaul, r=Amanieubors-4/+5
Overhaul of the `AllocRef` trait to match allocator-wg's latest consens; Take 2 GitHub won't let me reopen #69889 so I make a new PR. In addition to #69889 this fixes the unsoundness of `RawVec::into_box` when using allocators supporting overallocating. Also it uses `MemoryBlock` in `AllocRef` to unify `_in_place` methods by passing `&mut MemoryBlock`. Additionally, `RawVec` now checks for `size_of::<T>()` again and ignore every ZST. The internal capacity of `RawVec` isn't used by ZSTs anymore, as `into_box` now requires a length to be specified. r? @Amanieu fixes rust-lang/wg-allocators#38 fixes rust-lang/wg-allocators#41 fixes rust-lang/wg-allocators#44 fixes rust-lang/wg-allocators#51
2020-03-29BTreeMap/BTreeSet: implement and test drain_filterStein Somers-13/+298
2020-03-26Remove alignment from `MemoryBlock`Tim Diekmann-8/+4
2020-03-26Fix issues from review and unsoundness of `RawVec::into_box`Tim Diekmann-7/+12
2020-03-22remove redundant closures (clippy::redundant_closure)Matthias Krüger-2/+2
2020-03-20Simplify ensure_root_is_owned callersMark Rousskov-15/+13
This makes ensure_root_is_owned return a reference to the (now guaranteed to exist) root, allowing callers to operate on it without going through another unwrap. Unfortunately this is only rarely useful as it's frequently the case that both the length and the root need to be accessed and field-level borrows in methods don't yet exist.
2020-03-20Drop NodeHeader type from BTree codeMark Rousskov-41/+5
We no longer have a separate header because the shared root is gone; all code can work solely with leafs now.
2020-03-20Make functions dependent only on shared root avoidance safeMark Rousskov-58/+58
2020-03-20Remove shared root code and assertions from BTree nodesMark Rousskov-59/+8
2020-03-20Replace shared root with optional rootMark Rousskov-77/+112
This simplifies the node manipulation, as we can (in later commits) always know when traversing nodes that we are not in a shared root.
2020-03-08Rollup merge of #69668 - ssomers:btreemap_even_more_comments, r=Mark-SimulacrumMazdak Farrokhzad-14/+19
More documentation and simplification of BTreeMap's internals Salvage the documentation and simplification from #67980, without changing the type locked down by debuginfo. r? @rkruppe
2020-03-08Rollup merge of #69776 - ssomers:fix69769, r=Mark-SimulacrumMazdak Farrokhzad-1/+10
Fix & test leak of some BTreeMap nodes on panic during `into_iter` Fixes #69769
2020-03-06fix various typosMatthias Krüger-1/+1
2020-03-06Fix & test leak of some BTreeMap nodes on panic during `into_iter`Stein Somers-1/+10
2020-03-04Documentation and slight simplification of BTreeMap's internalsStein Somers-14/+19
2020-03-03Simplify conditions like x + 1 <= y to x < yMatthias Krüger-1/+1
2020-02-28Auto merge of #68827 - ssomers:btree_navigation_revisited, r=Mark-Simulacrumbors-150/+148
BTreeMap navigation done safer & faster It turns out that there was a faster way to do the tree navigation code bundled in #67073, by moving from edge to KV and from KV to next edge separately. It extracts most of the code as safe functions, and contains the duplication of handles within the short wrapper functions. This somehow hits a sweet spot in the compiler because it reports boosts all over the board: ``` >cargo benchcmp pre3.txt posz4.txt --threshold 5 name pre3.txt ns/iter posz4.txt ns/iter diff ns/iter diff % speedup btree::map::first_and_last_0 40 37 -3 -7.50% x 1.08 btree::map::first_and_last_100 58 44 -14 -24.14% x 1.32 btree::map::iter_1000 8,920 3,419 -5,501 -61.67% x 2.61 btree::map::iter_100000 1,069,290 411,615 -657,675 -61.51% x 2.60 btree::map::iter_20 169 58 -111 -65.68% x 2.91 btree::map::iter_mut_1000 8,701 3,303 -5,398 -62.04% x 2.63 btree::map::iter_mut_100000 1,034,560 405,975 -628,585 -60.76% x 2.55 btree::map::iter_mut_20 165 58 -107 -64.85% x 2.84 btree::set::clone_100 1,831 1,562 -269 -14.69% x 1.17 btree::set::clone_100_and_clear 1,831 1,565 -266 -14.53% x 1.17 btree::set::clone_100_and_into_iter 1,917 1,541 -376 -19.61% x 1.24 btree::set::clone_100_and_pop_all 2,609 2,441 -168 -6.44% x 1.07 btree::set::clone_100_and_remove_all 4,598 3,927 -671 -14.59% x 1.17 btree::set::clone_100_and_remove_half 2,765 2,551 -214 -7.74% x 1.08 btree::set::clone_10k 191,610 164,616 -26,994 -14.09% x 1.16 btree::set::clone_10k_and_clear 192,003 164,616 -27,387 -14.26% x 1.17 btree::set::clone_10k_and_into_iter 200,037 163,010 -37,027 -18.51% x 1.23 btree::set::clone_10k_and_pop_all 267,023 250,913 -16,110 -6.03% x 1.06 btree::set::clone_10k_and_remove_all 536,230 464,100 -72,130 -13.45% x 1.16 btree::set::clone_10k_and_remove_half 453,350 430,545 -22,805 -5.03% x 1.05 btree::set::difference_random_100_vs_100 1,787 801 -986 -55.18% x 2.23 btree::set::difference_random_100_vs_10k 2,978 2,696 -282 -9.47% x 1.10 btree::set::difference_random_10k_vs_100 111,075 54,734 -56,341 -50.72% x 2.03 btree::set::difference_random_10k_vs_10k 246,380 175,980 -70,400 -28.57% x 1.40 btree::set::difference_staggered_100_vs_100 1,789 951 -838 -46.84% x 1.88 btree::set::difference_staggered_100_vs_10k 2,798 2,606 -192 -6.86% x 1.07 btree::set::difference_staggered_10k_vs_10k 176,452 97,401 -79,051 -44.80% x 1.81 btree::set::intersection_100_neg_vs_10k_pos 34 32 -2 -5.88% x 1.06 btree::set::intersection_100_pos_vs_100_neg 30 27 -3 -10.00% x 1.11 btree::set::intersection_random_100_vs_100 1,537 613 -924 -60.12% x 2.51 btree::set::intersection_random_100_vs_10k 2,793 2,649 -144 -5.16% x 1.05 btree::set::intersection_random_10k_vs_10k 222,127 147,166 -74,961 -33.75% x 1.51 btree::set::intersection_staggered_100_vs_100 1,447 622 -825 -57.01% x 2.33 btree::set::intersection_staggered_100_vs_10k 2,606 2,382 -224 -8.60% x 1.09 btree::set::intersection_staggered_10k_vs_10k 143,620 58,790 -84,830 -59.07% x 2.44 btree::set::is_subset_100_vs_100 1,349 488 -861 -63.83% x 2.76 btree::set::is_subset_100_vs_10k 1,720 1,428 -292 -16.98% x 1.20 btree::set::is_subset_10k_vs_10k 135,984 48,527 -87,457 -64.31% x 2.80 ``` The `first_and_last` ones are noise (they don't do iteration), the others seem genuine. As always, approved by Miri. Also, a separate commit with some more benchmarks of mutable behaviour (which also benefit). r? @cuviper
2020-02-28Make implementation of navigation simpler, safer and fasterStein Somers-150/+148
2020-02-28Fix and test implementation of BTreeMap's first_entry, last_entry, ↵Stein Somers-10/+14
pop_first, pop_last
2020-02-26Auto merge of #67290 - jonas-schievink:leak-audit, r=KodrAusbors-1/+16
Audit liballoc for leaks in `Drop` impls when user destructor panics Inspired by https://github.com/rust-lang/rust/pull/67243 and https://github.com/rust-lang/rust/pull/67235, this audits and hopefully fixes the remaining `Drop` impls in liballoc for resource leaks in the presence of panics in destructors called by the affected `Drop` impl. This does not touch `Hash{Map,Set}` since they live in hashbrown. They have similar issues though. r? @KodrAus
2020-02-16Fix comments outdated during #66648Stein Somers-5/+4
2020-02-09Rollup merge of #68834 - ssomers:btree_first_last_fix68829, r=KodrAusDylan DPC-10/+14
Fix and test implementation of BTreeMap's first/last_entry, pop_first/last Properly implement and test `first_entry` & `last_entry` to fix problem report #68829
2020-02-07Lift range_search up one level of abstractionStein Somers-42/+45
2020-02-04Fix and test implementation of BTreeMap's first_entry, last_entry, ↵Stein Somers-10/+14
pop_first, pop_last
2020-01-31Bundle and document 6 BTreeMap navigation algorithmsStein Somers-236/+314
2020-01-30Rollup merge of #68468 - ssomers:btreemap_prefer_middle, r=Mark-SimulacrumDylan DPC-119/+132
BTreeMap: tag and explain unsafe internal functions or assert preconditions #68418 concluded that it's not desirable to tag all internal functions with preconditions as being unsafe. This PR does it to some functions, documents why, and elsewhere enforces the preconditions with asserts.
2020-01-30Rollup merge of #66648 - crgl:btree-clone-from, r=AmanieuDylan DPC-9/+86
Implement clone_from for BTreeMap and BTreeSet See #28481. This results in up to 90% speedups on simple data types when `self` and `other` are the same size, and is generally comparable or faster. Some concerns: 1. This implementation requires an `Ord` bound on the `Clone` implementation for `BTreeMap` and `BTreeSet`. Since these structs can only be created externally for keys with `Ord` implemented, this should be fine? If not, there's certainly a less safe way to do this. 2. Changing `next_unchecked` on `RangeMut` to return mutable key references allows for replacing the entire overlapping portion of both maps without changing the external interface in any way. However, if `clone_from` fails it can leave the `BTreeMap` in an invalid state, which might be unacceptable. ~This probably needs an FCP since it changes a trait bound, but (as far as I know?) that change cannot break any external code.~
2020-01-29BTreeMap: tag and explain unsafe internal functions or assert preconditionsStein Somers-119/+132
Co-Authored-By: Mark Rousskov <mark.simulacrum@gmail.com>
2020-01-29Rollup merge of #68378 - billyrieger:btreemap-remove-entry, r=KodrAusYuki Okushi-1/+30
Add BTreeMap::remove_entry Implements https://github.com/rust-lang/rust/issues/66714.
2020-01-28Reformat truncation section of clone_fromCharles Gleason-10/+10
2020-01-28Add private is_empty method to RangeMutCharles Gleason-3/+7
2020-01-28Format safety comment as per tidyCharles Gleason-1/+1
Co-Authored-By: Ashley Mannix <ashleymannix@live.com.au>
2020-01-28Add BTreeMap::remove_entryBilly Rieger-1/+30
Mainly for API parity with HashMap. - Add BTreeMap::remove_entry - Rewrite BTreeMap::remove to use remove_entry - Use btreemap_remove_entry feature in doc comment
2020-01-27Rename `Alloc` to `AllocRef`Tim Diekmann-1/+1
2020-01-21Declare unsafe functions that can no longer handle shared rootsStein Somers-6/+6
2020-01-21trade in outdated comments for correct onesStein Somers-2/+2
2020-01-19Fix leak in btree_map::IntoIter when drop panicsJonas Schievink-1/+16
2020-01-10Simplify NodeHeader by avoiding slices in BTreeMaps with shared rootsStein Somers-60/+19
2020-01-09Apply suggestions from code reviewStein Somers-1/+2
Co-Authored-By: Ralf Jung <post@ralfj.de>
2020-01-09Simplify into_key_slice_mut and document bits and bobsStein Somers-13/+20
2020-01-04Tweak and extend internal documentation, including debug asserts.Stein Somers-15/+39
Co-Authored-By: Robin Kruppe <robin.kruppe@gmail.com>
2019-12-28Auto merge of #67459 - ssomers:#67438, r=RalfJungbors-24/+30
prune ill-conceived BTreeMap iter_mut assertion and test its mutability Proposal to deal with #67438 (and I'm more sure now that this is the right thing to do). Passes testing with miri.
2019-12-26prune ill-conceived BTreeMap iter_mut assertion and test moreStein Somers-24/+30
2019-12-26Remove redundant link textsMatthew Kraai-2/+2
2019-12-23Implement clone_from for BTree collectionsCharles Gleason-1/+66
2019-12-23Make RangeMut::next_unchecked() output a mutable key referenceCharles Gleason-7/+15
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-01 02:36:51 +0000