summary refs log tree commit diff
path: root/library/alloc/src/collections/btree/node.rs
AgeCommit message (Collapse)AuthorLines
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
2021-01-10BTreeMap: tougher checks on code using raw into_kv_pointersStein Somers-81/+88
2021-01-08BTreeMap: tougher checks on most uses of copy_nonoverlappingStein Somers-26/+32
2020-12-26BTreeMap: rename the area access methodsStein Somers-50/+48
2020-12-25BTreeMap: declare exclusive access to arrays when copying from themStein Somers-64/+17
2020-12-24BTreeMap: avoid implicit use of node length in flightStein Somers-97/+81
2020-12-17BTreeMap: relax the explicit borrow rule to make code shorter and saferStein Somers-105/+107
2020-12-17Rollup merge of #80006 - ssomers:btree_cleanup_6, r=Mark-SimulacrumGuillaume Gomez-28/+27
BTreeMap: more expressive local variables in merge r? ```````@Mark-Simulacrum```````
2020-12-13Auto merge of #80005 - ssomers:btree_cleanup_3, r=Mark-Simulacrumbors-10/+11
BTreeMap: declare clear_parent_link directly on the root it needs r? `@Mark-Simulacrum`
2020-12-13Auto merge of #79987 - ssomers:btree_cleanup_4, r=Mark-Simulacrumbors-0/+2
BTreeMap: detect bulk_steal's count-1 underflow in release builds too r? `@Mark-Simulacrum`
2020-12-13Auto merge of #79376 - ssomers:btree_choose_parent_kv, r=Mark-Simulacrumbors-6/+8
BTreeMap: clarify comments and panics around choose_parent_kv Fixes a lie in recent code: `unreachable!("empty non-root node")` should shout "empty internal node", but it might as well be good and keep quiet r? `@Mark-Simulacrum`
2020-12-13BTreeMap: more expressive local variables in mergeStein Somers-28/+27
2020-12-13BTreeMap: declare clear_parent_link directly on the root it needsStein Somers-10/+11
2020-12-13BTreeMap: capture a recurring use pattern as replace_kvStein Somers-4/+8
generated by cgit-pink 1.4.1-3-g733a5 (git 2.37.1) at 2026-03-01 22:06:29 +0000