about summary refs log tree commit diff
path: root/src/liballoc/tests/btree
AgeCommit message (Collapse)AuthorLines
2020-07-27mv std libs to library/mark-2156/+0
2020-07-24Rollup merge of #74677 - ssomers:btree_cleanup_2, r=AmanieuYuki Okushi-12/+46
Remove needless unsafety from BTreeMap::drain_filter Remove one piece of unsafe code in the iteration over the iterator returned by BTreeMap::drain_filter. - Changes an explicitly unspecified part of the API: when the user-supplied predicate (or some of BTreeMap's code) panicked, and the caller tries to use the iterator again, we no longer offer the same key/value pair to the predicate again but pretend the iterator has finished. Note that Miri does not find UB in the test case added here with the unsafe code (or without). - Makes the code a little easier on the eyes. - Makes the code a little harder on the CPU: ``` benchcmp c0 c2 --threshold 3 name c0 ns/iter c2 ns/iter diff ns/iter diff % speedup btree::set::clone_100_and_drain_all 2,794 2,900 106 3.79% x 0.96 btree::set::clone_100_and_drain_half 2,604 2,964 360 13.82% x 0.88 btree::set::clone_10k_and_drain_half 287,770 322,755 34,985 12.16% x 0.89 ``` r? @Amanieu
2020-07-23BTreeMap::drain_filter: replace needless unsafety and testStein Somers-12/+46
2020-07-22More BTreeMap test cases, some exposing undefined behaviourStein Somers-0/+80
2020-07-02disable BTree min_max test in Miri for nowRalf Jung-0/+1
2020-06-26Shortcuts for min/max on ordinary BTreeMap/BTreeSet iteratorsStein Somers-0/+66
2020-04-23liballoc: more compact way to adjust test sizes for MiriRalf Jung-36/+18
2020-04-06Use usize::MAX as assoc const in liballocLinus Färnstrand-1/+1
2020-04-01Rollup merge of #68770 - ssomers:btree_drain_filter, r=AmanieuDylan DPC-1/+339
BTreeMap/BTreeSet: implement drain_filter Provide an implementation of drain_filter for BTreeMap and BTreeSet. Should be optimal when the predicate picks only elements in leaf nodes with at least MIN_LEN remaining elements, which is a common case, at least when draining only a fraction of the map/set, and also when the predicate picks elements stored in internal nodes where the right subtree can easily let go of a replacement element. The first commit adds benchmarks with an external, naive implementation. to compare how much this claimed optimality-in-some-cases is actually worth.
2020-03-30fix BTreeMap test compilation with MiriRalf Jung-1/+1
2020-03-29BTreeMap/BTreeSet: implement and test drain_filterStein Somers-1/+339
2020-03-28BTreeMap testing: introduce symbolic constants and refer to height consistently.Stein Somers-41/+49
2020-03-20Update test commentary for shared root removalMark Rousskov-9/+2
2020-03-06Fix & test leak of some BTreeMap nodes on panic during `into_iter`Stein Somers-1/+25
2020-02-26Auto merge of #67290 - jonas-schievink:leak-audit, r=KodrAusbors-0/+28
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-16Lighten tests, in particular for Miri, yet test and explain moreStein Somers-20/+32
2020-02-04Fix and test implementation of BTreeMap's first_entry, last_entry, ↵Stein Somers-11/+21
pop_first, pop_last
2020-01-30Rollup merge of #66648 - crgl:btree-clone-from, r=AmanieuDylan DPC-0/+20
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-28Include empty BTreeMap in clone_from testsCharles Gleason-2/+2
2020-01-19Fix leak in btree_map::IntoIter when drop panicsJonas Schievink-0/+28
2019-12-31More thorough testing of BTreeMap::rangeStein Somers-31/+150
2019-12-26prune ill-conceived BTreeMap iter_mut assertion and test moreStein Somers-1/+122
2019-12-23Add test for BTreeMap::clone_fromCharles Gleason-0/+20
2019-12-22Format the worldMark Rousskov-55/+53
2019-11-29Format liballoc with rustfmtDavid Tolnay-6/+1
2019-10-23proposal for access to BTreeMap/BTreeSet first/last, #62924Stein Somers-0/+73
2019-10-18BTreeSet symmetric_difference & union optimized, cleanedStein Somers-1/+25
2019-10-01BTreeSet intersection, difference & is_subnet optimizationsStein Somers-18/+92
2019-09-16Improve BTreeSet::Intersection::size_hintpcpthm-0/+11
The commented invariant that an iterator is smaller than other iterator was violated after next is called and two iterators are consumed at different rates.
2019-08-09Rollup merge of #63407 - RalfJung:miri-test-sizes, r=CentrilMazdak Farrokhzad-0/+27
reduce some test sizes in Miri
2019-08-09reduce some test sizes in MiriRalf Jung-0/+27
2019-08-09Merge pull request #1 from rust-lang/masterSayan Nandan-5/+61
Merge recent changes into master
2019-08-09Improve tests for liballoc/btree/setSayan Nandan-2/+2
2019-05-17Use iter() for iterating arrays by sliceJosh Stone-2/+2
These `into_iter()` calls will change from iterating references to values if we ever get `IntoIterator` for arrays, which may break the code using that iterator. Calling `iter()` is future proof.
2019-03-29improve worst-case performance of BTreeSet difference and intersectionStein Somers-0/+61
2019-03-10we can now skip should_panic tests with the libtest harnessRalf Jung-5/+0
2019-02-13miri: test with slightly larger BTreesRalf Jung-8/+10
2019-02-13review failures in btree, stringRalf Jung-2/+28
2019-02-09Rollup merge of #58275 - RalfJung:miri-test-libcore, r=Mark-SimulacrumMazdak Farrokhzad-0/+2
libcore, liballoc: disable tests in Miri I am going to run the libcore and liballoc unit test suites in Miri. Not all tests pass. This PR disables a whole bunch of tests when running in Miri, to get us to a baseline from which I can investigate failures. Cc @SimonSapin @alexcrichton
2019-02-07disable tests in MiriRalf Jung-0/+2
2019-02-03liballoc: revert nested imports style changes.Mazdak Farrokhzad-10/+8
2019-02-02liballoc: adjust abolute imports + more import fixes.Mazdak Farrokhzad-1/+1
2019-02-02liballoc: refactor & fix some imports.Mazdak Farrokhzad-9/+13
2018-12-25Remove licensesMark Rousskov-30/+0
2018-12-04Replace usages of `..i + 1` ranges with `..=i`.Corey Farwell-2/+2
2018-07-25Add missing dynTatsuyuki Ishi-1/+1
2018-03-29Move alloc::Bound to {core,std}::opsSimon Sapin-1/+1
The stable reexport `std::collections::Bound` is now deprecated. Another deprecated reexport could be added in `alloc`, but that crate is unstable.
2017-09-22Add support for `..=` syntaxAlex Burka-14/+14
Add ..= to the parser Add ..= to libproc_macro Add ..= to ICH Highlight ..= in rustdoc Update impl Debug for RangeInclusive to ..= Replace `...` to `..=` in range docs Make the dotdoteq warning point to the ... Add warning for ... in expressions Updated more tests to the ..= syntax Updated even more tests to the ..= syntax Updated the inclusive_range entry in unstable book
2017-06-13Merge crate `collections` into `alloc`Murarth-0/+1060
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-20 10:51:02 +0000