summary refs log tree commit diff
path: root/src/liballoc/collections
AgeCommit message (Collapse)AuthorLines
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-07Rollup merge of #69773 - matthiaskrgr:typos, r=petrochenkovMazdak Farrokhzad-5/+5
fix various typos
2020-03-06Don't redundantly repeat field names (clippy::redundant_field_names)Matthias Krüger-1/+1
2020-03-06fix various typosMatthias Krüger-5/+5
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-29simplify boolean expressionsMatthias Krüger-2/+2
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-112/+195
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-20Rollup merge of #68705 - BijanT:ll_remove, r=Mark-SimulacrumDylan DPC-0/+46
Add LinkedList::remove() LinkedList::remove() removes the element at the specified index and returns it. I added this because I think having a remove function would be useful to have, and similar functions are in other containers, like Vec and HashMap. I'm not sure if adding a feature like this requires an RFC or not, so I'm sorry if this PR is premature.
2020-02-19Add LinkedList::remove()Bijan Tabatabai-0/+46
LinkedList::remove() removes the element at the specified index and returns it. Signed-off-by: Bijan Tabatabai <bijan311@yahoo.com>
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-21Rollup merge of #67686 - ssomers:keys_start_slasher, r=Mark-SimulacrumMazdak Farrokhzad-65/+24
Simplify NodeHeader by avoiding slices in BTreeMaps with shared roots Simplify a complicated piece of code that creates slices of keys in node leaves.
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-19FormatJonas Schievink-2/+5
2020-01-19Move VecDeque Drain iterator to new fileJonas Schievink-121/+131
2020-01-19Avoid leak in DrainFilter when a drop panicsJonas Schievink-1/+15
2020-01-19Fix leak in VecDeque::drain when drop panicsJonas Schievink-34/+48
2020-01-19Fix leak in btree_map::IntoIter when drop panicsJonas Schievink-1/+16
2020-01-19Fix `VecDeque::truncate` leak on drop panicJonas Schievink-1/+16
2020-01-19Fix `binary_heap::DrainSorted` drop leak on panicsJonas Schievink-2/+14
2020-01-14Update APIs according to RFC change suggestions.Charles Lew-18/+85
2020-01-12Address review comments.Charles Lew-2/+33
2020-01-12Address review comments.Charles Lew-83/+161
2020-01-12Implement Cursor for linked lists. (RFC 2570).Charles Lew-24/+531
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-5/+5
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-27 06:09:49 +0000