about summary refs log tree commit diff
path: root/library/alloc/src/collections/btree/node.rs
AgeCommit message (Collapse)AuthorLines
2025-09-25Rollup merge of #146859 - cammeresi:btree-alloc-20250920, r=joboetMatthias Krüger-2/+10
BTreeMap: Don't leak allocators when initializing nodes Memory was allocated via `Box::leak` and thence intended to be tracked and deallocated manually, but the allocator was also leaked, not tracked, and never dropped. Now it is dropped immediately. According to my reading of the `Allocator` trait, if a copy of the allocator remains live, then its allocations must remain live. Since the B-tree has a copy of the allocator that will only be dropped after the nodes, it's safe to not store the allocator in each node (which would be a much more intrusive change). Fixes: rust-lang/rust#106203
2025-09-24BTreeMap: Don't leak allocators when initializing nodesSidney Cammeresi-2/+10
Memory was allocated via `Box::leak` and thence intended to be tracked and deallocated manually, but the allocator was also leaked, not tracked, and never dropped. Now it is dropped immediately. According to my reading of the `Allocator` trait, if a copy of the allocator remains live, then its allocations must remain live. Since the B-tree has a copy of the allocator that will only be dropped after the nodes, it's safe to not store the allocator in each node (which would be a much more intrusive change).
2025-09-21btree InternalNode::new safety commentsMarijn Schouten-2/+3
2025-09-19btree: safety comments for init and newMarijn Schouten-1/+7
2025-01-29btree/node.rs: pop_internal_level: does not invalidate other handlesBart Jacobs-0/+3
2025-01-28btree/node.rs: remove incorrect comment from pop_internal_level docsBart Jacobs-3/+0
2025-01-20alloc: add `#![warn(unreachable_pub)]`Urgau-97/+112
2025-01-11Add inherent versions of MaybeUninit methods for slicesltdk-3/+1
2024-11-26Rollup merge of #133042 - cuviper:btreemap-insert_entry, r=AmanieuMichael Goulet-1/+1
btree: add `{Entry,VacantEntry}::insert_entry` This matches the recently-stabilized methods on `HashMap` entries. I've reused tracking issue #65225 for now, but we may want to split it.
2024-11-14btree: add `{Entry,VacantEntry}::insert_entry`Josh Stone-1/+1
This matches the recently-stabilized methods on `HashMap` entries. I've reused tracking issue #65225 for now, but we may want to split it.
2024-11-04btree: don't leak value if destructor of key panicsLukas Markeffsky-2/+16
2024-10-23"innermost", "outermost", "leftmost", and "rightmost" don't need hyphensJosh Triplett-2/+2
These are all standard dictionary words and don't require hyphenation.
2024-09-25Use `&raw` in the standard libraryJosh Stone-5/+5
Since the stabilization in #127679 has reached stage0, 1.82-beta, we can start using `&raw` freely, and even the soft-deprecated `ptr::addr_of!` and `ptr::addr_of_mut!` can stop allowing the unstable feature. I intentionally did not change any documentation or tests, but the rest of those macro uses are all now using `&raw const` or `&raw mut` in the standard library.
2023-11-23Rewrite the BTreeMap cursor API using gapsAmanieu d'Antras-5/+24
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-02-01BTreeMap: Add Cursor and CursorMutAmanieu d'Antras-1/+9
2023-02-01BTreeMap: Change internal insert function to return a handleAmanieu d'Antras-18/+76
This is a prerequisite for cursor support for `BTreeMap`.
2022-12-28fix documenting private items of standard libraryLukas Markeffsky-11/+17
2022-10-05Fix overconstrained Send impls in btree internalsDavid Tolnay-3/+3
2022-08-26Rollup merge of #95005 - ssomers:btree_static_assert, r=thomccGuillaume Gomez-7/+9
BTree: evaluate static type-related check at compile time `assert`s like the ones replaced here would only go off when you run the right test cases, if the code were ever incorrectly changed such that rhey would trigger. But [inspired on a nice forum question](https://users.rust-lang.org/t/compile-time-const-generic-parameter-check/69202), they can be checked at compile time.
2022-06-16btree: avoid forcing the allocator to be a referenceRalf Jung-32/+37
2022-06-14BTreeMap: Add alloc paramJacob Hughes-38/+61
2022-03-16BTree: evaluate static type-related check at compile timeStein Somers-7/+9
2022-03-09BTreeMap::entry: Avoid allocating if no insertionFrank King-4/+5
2022-03-07BTree: remove dead data needlessly complicating insertStein Somers-37/+16
2021-08-17BTree: refine some commentsStein Somers-2/+2
2021-08-02BTree: merge the complication introduced by #81486 and #86031Stein Somers-2/+6
2021-07-29Fix may not to appropriate might not or must notAli Malik-2/+2
2021-06-25Fix a few misspellings.Eric Huss-1/+1
2021-05-07BTree: no longer copy keys and values before dropping themStein Somers-3/+36
2021-04-28Minor grammar tweaks for readabilityBen-Lichtman-4/+4
2021-03-03BTree: move blocks around in node.rsStein Somers-167/+165
2021-03-03Rollup merge of #82439 - ssomers:btree_fix_unsafety, r=Mark-SimulacrumYuki Okushi-16/+15
BTree: fix untrue safety Fix needless and missing `unsafe` tags. r? ````@Mark-Simulacrum````
2021-03-01Auto merge of #82440 - ssomers:btree_fix_casts, r=Mark-Simulacrumbors-8/+10
BTree: no longer define impossible casts Casts to leaf to internal only make sense when the original has a chance of being the thing it's cast to. r? `@Mark-Simulacrum`
2021-02-23BTree: fix untrue safetyStein Somers-16/+15
2021-02-23BTree: no longer define impossible castsStein Somers-8/+10
2021-02-23BTree: split off reusable components from range_searchStein Somers-10/+0
2021-02-14Rollup merge of #81919 - ssomers:btree_cleanup_comments, r=Mark-SimulacrumDylan DPC-1/+1
BTreeMap: fix internal comments Salvaged from #81372 r? `@Mark-Simulacrum`
2021-02-12Use raw ref macros as in #80886Stein Somers-3/+3
2021-02-12Initialize BTree nodes directly in the heapJosh Stone-18/+30
2021-02-09BTreeMap: fix internal commentsStein Somers-1/+1
2021-01-30Rollup merge of #80886 - RalfJung:stable-raw-ref-macros, r=m-ou-seYuki Okushi-2/+2
Stabilize raw ref macros This stabilizes `raw_ref_macros` (https://github.com/rust-lang/rust/issues/73394), which is possible now that https://github.com/rust-lang/rust/issues/74355 is fixed. However, as I already said in https://github.com/rust-lang/rust/issues/73394#issuecomment-751342185, I am not particularly happy with the current names of the macros. So I propose we also change them, which means I am proposing to stabilize the following in `core::ptr`: ```rust pub macro const_addr_of($e:expr) { &raw const $e } pub macro mut_addr_of($e:expr) { &raw mut $e } ``` The macro name change means we need another round of FCP. Cc `````@rust-lang/libs````` Fixes #73394
2021-01-29rename raw_const/mut -> const/mut_addr_of, and stabilize themRalf Jung-2/+2
2021-01-26BTreeMap: stop tree from being owned by non-root nodeStein Somers-14/+49
2021-01-20BTreeMap: bring back the key slice for immutable lookupStein Somers-25/+18
2021-01-18BTreeMap: prefer bulk_steal functions over specialized onesStein Somers-117/+4
2021-01-18Auto merge of #81090 - ssomers:btree_drainy_refactor_2, r=Mark-Simulacrumbors-24/+52
BTreeMap: offer merge in variants with more clarity r? `@Mark-Simulacrum`
2021-01-17Rollup merge of #81082 - ssomers:btree_cleanup_comments, r=Mark-SimulacrumMara Bos-4/+7
BTreeMap: clean up a few more comments And mark `pop` as unsafe. r? ```@Mark-Simulacrum```
2021-01-16BTreeMap: offer merge in variants with more clarityStein Somers-24/+52
2021-01-16BTreeMap: expose new_internal function and sanitize from_new_internalStein Somers-9/+12
2021-01-16BTreeMap: clean up a few more commentsStein Somers-4/+7
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-02-24 07:34:18 +0000