-
Notifications
You must be signed in to change notification settings - Fork 13.2k
Commit 8ee9693
committed
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);
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>;
}
```1 parent 4f3da90 commit 8ee9693Copy full SHA for 8ee9693
0 commit comments