about summary refs log tree commit diff
path: root/library/alloc/src/collections/btree/map/tests.rs
AgeCommit message (Collapse)AuthorLines
2025-05-27Unit test for Range parameter of `BTreeMap::extract_if`Sidney Cammeresi-0/+24
2025-05-27Update tests with Range parameter to `BTreeMap::extract_if` etc.Sidney Cammeresi-25/+25
2024-11-04btree: don't leak value if destructor of key panicsLukas Markeffsky-0/+48
2024-10-25library: consistently use American spelling for 'behavior'Ralf Jung-1/+1
2024-09-22Reformat using the new identifier sorting from rustfmtMichael Goulet-1/+1
2024-07-29Reformat `use` declarations.Nicholas Nethercote-5/+7
The previous commit updated `rustfmt.toml` appropriately. This commit is the outcome of running `x fmt --all` with the new formatting options.
2024-07-06Mark format! with must_use hintlukas-9/+9
2024-01-25Rollup merge of #118208 - Amanieu:btree_cursor2, r=dtolnayMatthias Krüger-48/+87
Rewrite the BTreeMap cursor API using gaps Tracking issue: #107540 Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use. This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning. The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation. API summary: ```rust impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn next(&mut self) -> Option<(&'a K, &'a V)>; fn prev(&mut self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&K, &mut V)>; fn prev(&mut self) -> Option<(&K, &mut V)>; fn peek_next(&mut self) -> Option<(&K, &mut V)>; fn peek_prev(&mut self) -> Option<(&K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct CursorMutKey<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&mut K, &mut V)>; fn prev(&mut self) -> Option<(&mut K, &mut V)>; fn peek_next(&mut self) -> Option<(&mut K, &mut V)>; fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn insert_before(&mut self, key: K, value: V) -> Result<(), UnorderedKeyError>; fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct UnorderedKeyError; ```
2023-12-10remove redundant importssurechen-6/+1
detects redundant imports that can be eliminated. for #117772 : In order to facilitate review and modification, split the checking code and removing redundant imports code into two PR.
2023-11-23Add UnorderedKeyErrorAmanieu d'Antras-21/+13
2023-11-23Rewrite the BTreeMap cursor API using gapsAmanieu d'Antras-34/+81
Tracking issue: #107540 Currently, a `Cursor` points to a single element in the tree, and allows moving to the next or previous element while mutating the tree. However this was found to be confusing and hard to use. This PR completely refactors cursors to instead point to a gap between two elements in the tree. This eliminates the need for a "ghost" element that exists after the last element and before the first one. Additionally, `upper_bound` and `lower_bound` now have a much clearer meaning. The ability to mutate keys is also factored out into a separate `CursorMutKey` type which is unsafe to create. This makes the API easier to use since it avoids duplicated versions of each method with and without key mutation. API summary: ```rust impl<K, V> BTreeMap<K, V> { fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V> where K: Borrow<Q> + Ord, Q: Ord; } struct Cursor<'a, K: 'a, V: 'a>; impl<'a, K, V> Cursor<'a, K, V> { fn next(&mut self) -> Option<(&'a K, &'a V)>; fn prev(&mut self) -> Option<(&'a K, &'a V)>; fn peek_next(&self) -> Option<(&'a K, &'a V)>; fn peek_prev(&self) -> Option<(&'a K, &'a V)>; } struct CursorMut<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&K, &mut V)>; fn prev(&mut self) -> Option<(&K, &mut V)>; fn peek_next(&mut self) -> Option<(&K, &mut V)>; fn peek_prev(&mut self) -> Option<(&K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } struct CursorMutKey<'a, K: 'a, V: 'a>; impl<'a, K, V> CursorMut<'a, K, V> { fn next(&mut self) -> Option<(&mut K, &mut V)>; fn prev(&mut self) -> Option<(&mut K, &mut V)>; fn peek_next(&mut self) -> Option<(&mut K, &mut V)>; fn peek_prev(&mut self) -> Option<(&mut K, &mut V)>; unsafe fn insert_after_unchecked(&mut self, key: K, value: V); unsafe fn insert_before_unchecked(&mut self, key: K, value: V); fn insert_after(&mut self, key: K, value: V); fn insert_before(&mut self, key: K, value: V); fn remove_next(&mut self) -> Option<(K, V)>; fn remove_prev(&mut self) -> Option<(K, V)>; fn as_cursor(&self) -> Cursor<'_, K, V>; unsafe fn with_mutable_key(self) -> CursorMutKey<'a, K, V, A>; } ```
2023-06-14s/drain_filter/extract_if/ for Vec, Btree{Map,Set} and LinkedListThe 8472-28/+28
2023-06-14remove drain-on-drop behavior from BTree{Set,Map}::DrainFilter and add ↵The 8472-18/+21
#[must_use]
2023-06-13ignore core, alloc and test tests that require unwinding on panic=abortPietro Albini-0/+9
2023-05-04btree_map: `Cursor{,Mut}::peek_prev` must agreeJubilee Young-0/+19
Our `Cursor::peek_prev` and `CursorMut::peek_prev` must agree on how to behave when they are called on the "null element".
2023-04-14Rollup merge of #110244 - kadiwa4:unnecessary_imports, r=JohnTitorMatthias Krüger-2/+1
Remove some unneeded imports / qualified paths Continuation of #105537.
2023-04-12remove some unneeded importsKaDiWa-2/+1
2023-04-12Fix btree `CursorMut::insert_after` checkmarc0246-0/+64
2023-02-01BTreeMap: Add Cursor and CursorMutAmanieu d'Antras-0/+49
2022-12-28Rollup merge of #94145 - ssomers:binary_heap_tests, r=jyn514fee1-dead-3/+3
Test leaking of BinaryHeap Drain iterators Add test cases about forgetting the `BinaryHeap::Drain` iterator, and slightly fortifies some other test cases. Consists of separate commits that I don't think are relevant on their own (but I'll happily turn these into more PRs if desired).
2022-06-23Fix BTreeSet's range API panic message, documenttnballo-0/+33
2022-06-16btree: avoid forcing the allocator to be a referenceRalf Jung-5/+1
2022-06-14BTreeMap: Add alloc paramJacob Hughes-1/+5
2022-05-02Share testing utilities with non-btree test casesStein Somers-3/+3
2022-04-15chore: formattingKeita Nonaka-11/+9
2022-04-15test: add try_insert() test cases for BTreeSetKeita Nonaka-0/+15
2022-04-15test: add get_key_value() test cases for BTreeSetKeita Nonaka-0/+24
2022-04-14test: add pop_first() pop_last() test cases for BTreeSetKeita Nonaka-9/+77
2022-03-20Auto merge of #92962 - frank-king:btree_entry_no_insert, r=Amanieubors-7/+38
BTreeMap::entry: Avoid allocating if no insertion This PR allows the `VacantEntry` to borrow from an empty tree with no root, and to lazily allocate a new root node when the user calls `.insert(value)`.
2022-03-10Use implicit capture syntax in format_argsT-O-R-U-S-1/+1
This updates the standard library's documentation to use the new syntax. The documentation is worthwhile to update as it should be more idiomatic (particularly for features like this, which are nice for users to get acquainted with). The general codebase is likely more hassle than benefit to update: it'll hurt git blame, and generally updates can be done by folks updating the code if (and when) that makes things more readable with the new format. A few places in the compiler and library code are updated (mostly just due to already having been done when this commit was first authored).
2022-03-09BTreeMap::entry: Avoid allocating if no insertionFrank King-7/+38
2022-02-20BTree: simplify test codeStein Somers-108/+89
2022-01-09eplace usages of vec![].into_iter with [].into_iterLucas Kent-2/+2
2021-12-10BTree: rename compile-time assertions to match library/alloc/testsStein Somers-3/+3
2021-10-15Add #[must_use] to remaining alloc functionsJohn Kugelman-13/+13
2021-10-10Add #[must_use] to conversions that move selfJohn Kugelman-10/+10
2021-10-03Auto merge of #88086 - ssomers:btree_clone_testing, r=dtolnaybors-24/+31
BTree: toughen panicky test of clone() Test did not cover the second half of `clone_subtree` and why this clones key & value first.
2021-08-18BTree: remove Ord bound from newGary Guo-1/+7
2021-08-16BTree: toughen panicky test of clone()Stein Somers-24/+31
2021-08-13Moved ui testDeadbeef-7/+0
2021-06-30impl From<[(K, V); N]> for std::collectionsbstrie-0/+7
2021-03-18BTree: no longer search arrays twice to check OrdStein Somers-2/+0
2021-03-03Fix ui-full-deps suiteRyan Levick-4/+4
2021-02-21BTreeMap: correct tests for alternative choices of BStein Somers-2/+3
2021-02-09BTreeMap: share panicky test code & test panic during clear, cloneStein Somers-127/+152
2021-02-09BTreeMap/BTreeSet: separate off code supporting testsStein Somers-4/+2
2021-02-06BTreeMap: remove Ord bound where it is absent elsewhereStein Somers-2/+15
2021-02-06Rollup merge of #81610 - ssomers:btree_emphasize_ord_bound, r=dtolnayMara Bos-0/+28
BTreeMap: make Ord bound explicit, compile-test its absence Most `BTreeMap` and `BTreeSet` members are subject to an `Ord` bound but a fair number of methods are not. To better convey and perhaps later tune the `Ord` bound, make it stand out in individual `where` clauses, instead of once far away at the beginning of an `impl` block. This PR does not introduce or remove any bounds. Also adds compilation test cases checking that the bound doesn't creep in unintended on the historically unbounded methods.
2021-02-04Revert "Avoid leaking block expression values"Felix S. Klock II-1/+1
This reverts commit 4fef39113a514bb270f5661a82fdba17d3e41dbb.
2021-02-02BTreeMap: make Ord bound explicit, compile-test its absenceStein Somers-0/+28
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-24 06:01:22 +0000