content_tree/
safe_cursor.rs

1#![allow(clippy::needless_lifetimes)] // Clippy doesn't understand the need for some lifetimes below
2
3use std::cmp::Ordering;
4use std::marker::PhantomData;
5use std::ops::{Deref, AddAssign, DerefMut};
6use rle::Searchable;
7
8use super::*;
9
10/// This file provides the safe implementation methods for cursors.
11
12impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Cursor<'a, E, I, IE, LE> {
13    #[inline(always)]
14    pub unsafe fn unchecked_from_raw(_tree: &'a ContentTreeRaw<E, I, IE, LE>, cursor: UnsafeCursor<E, I, IE, LE>) -> Self {
15        Cursor {
16            inner: cursor,
17            marker: PhantomData,
18        }
19    }
20
21    // TODO: Implement from_raw as well, where we walk up the tree to check the root.
22}
23
24impl<R, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> SafeCursor<R, E, I, IE, LE> {
25    // pub fn old_count_pos(&self) -> I::IndexValue {
26    //     unsafe { self.inner.old_count_pos() }
27    // }
28
29    pub fn count_pos_raw<Out, F, G, H>(&self, offset_to_num: F, entry_len: G, entry_len_at: H) -> Out
30        where Out: AddAssign + Default, F: Fn(I::Value) -> Out, G: Fn(&E) -> Out, H: Fn(&E, usize) -> Out
31    {
32        unsafe { self.inner.count_pos_raw(offset_to_num, entry_len, entry_len_at) }
33    }
34}
35
36impl<R, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> From<SafeCursor<R, E, I, IE, LE>> for UnsafeCursor<E, I, IE, LE> {
37    #[inline(always)]
38    fn from(c: SafeCursor<R, E, I, IE, LE>) -> Self {
39        c.inner
40    }
41}
42
43
44impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Deref for Cursor<'a, E, I, IE, LE> {
45    type Target = UnsafeCursor<E, I, IE, LE>;
46
47    #[inline(always)]
48    fn deref(&self) -> &Self::Target {
49        &self.inner
50    }
51}
52
53impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> DerefMut for Cursor<'a, E, I, IE, LE> {
54    #[inline(always)]
55    fn deref_mut(&mut self) -> &mut Self::Target {
56        &mut self.inner
57    }
58}
59
60impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Deref for MutCursor<'a, E, I, IE, LE> {
61    type Target = Cursor<'a, E, I, IE, LE>;
62
63    #[inline(always)]
64    fn deref(&self) -> &Self::Target {
65        unsafe { std::mem::transmute(self) }
66    }
67}
68
69impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> DerefMut for MutCursor<'a, E, I, IE, LE> {
70    #[inline(always)]
71    fn deref_mut(&mut self) -> &mut Self::Target {
72        unsafe { std::mem::transmute(self) }
73    }
74}
75
76
77impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Iterator for Cursor<'a, E, I, IE, LE> {
78    type Item = E;
79
80    fn next(&mut self) -> Option<Self::Item> {
81        // When the cursor is past the end, idx is an invalid value.
82        if self.inner.idx == usize::MAX {
83            return None;
84        }
85
86        // The cursor is at the end of the current element. Its a bit dirty doing this twice but
87        // This will happen for a fresh cursor in an empty document, or when iterating using a
88        // cursor made by some other means.
89        if self.inner.idx >= unsafe { self.inner.node.as_ref() }.len_entries() {
90            let has_next = self.inner.next_entry();
91            if !has_next {
92                self.inner.idx = usize::MAX;
93                return None;
94            }
95        }
96
97        let current = *self.inner.get_raw_entry();
98        // Move the cursor forward preemptively for the next call to next().
99        let has_next = self.inner.next_entry();
100        if !has_next {
101            self.inner.idx = usize::MAX;
102        }
103        Some(current)
104    }
105}
106
107impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> MutCursor<'a, E, I, IE, LE> {
108    pub unsafe fn unchecked_from_raw(_tree: &mut Pin<Box<ContentTreeRaw<E, I, IE, LE>>>, cursor: UnsafeCursor<E, I, IE, LE>) -> Self {
109        // TODO: Check that this is free.
110        Self {
111            inner: cursor,
112            marker: PhantomData,
113        }
114    }
115
116    #[inline(always)]
117    pub fn insert_notify<F>(&mut self, new_entry: E, notify: F)
118        where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
119
120        unsafe {
121            ContentTreeRaw::unsafe_insert_notify(&mut self.inner, new_entry, notify);
122        }
123    }
124
125    #[inline(always)]
126    pub fn insert(&mut self, new_entry: E) {
127        unsafe {
128            ContentTreeRaw::unsafe_insert_notify(&mut self.inner, new_entry, null_notify);
129        }
130    }
131
132    #[inline(always)]
133    pub fn replace_range_notify<N>(&mut self, new_entry: E, notify: N)
134        where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
135        unsafe {
136            ContentTreeRaw::unsafe_replace_range_notify(&mut self.inner, new_entry, notify);
137        }
138    }
139
140    #[inline(always)]
141    pub fn replace_range(&mut self, new_entry: E) {
142        unsafe {
143            ContentTreeRaw::unsafe_replace_range_notify(&mut self.inner, new_entry, null_notify);
144        }
145    }
146
147    #[inline(always)]
148    pub fn delete_notify<F>(&mut self, del_items: usize, notify: F)
149        where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
150        unsafe {
151            ContentTreeRaw::unsafe_delete_notify(&mut self.inner, del_items, notify);
152        }
153    }
154
155    #[inline(always)]
156    pub fn delete(&mut self, del_items: usize) {
157        unsafe {
158            ContentTreeRaw::unsafe_delete_notify(&mut self.inner, del_items, null_notify);
159        }
160    }
161
162    /// Replace the current entry with the items passed via items[]. Items.len must be <= 3. The
163    /// cursor offset is ignored. This is a fancy method - use sparingly.
164    #[inline(always)]
165    pub fn replace_entry(&mut self, items: &[E]) {
166        unsafe {
167            ContentTreeRaw::unsafe_replace_entry_notify(&mut self.inner, items, null_notify);
168        }
169    }
170
171    pub fn replace_entry_simple(&mut self, new_item: E) {
172        unsafe {
173            ContentTreeRaw::unsafe_replace_entry_simple_notify(&mut self.inner, new_item, null_notify);
174        }
175    }
176
177    /// Mutate a single entry in-place. The entry to be modified is whatever is at this cursor, and
178    /// up to replace_max size.
179    ///
180    /// The function will be modified by the (passed) map_fn.
181    ///
182    /// Returns a tuple of (actual length replaced, map_fn return value).
183    pub fn mutate_single_entry_notify<MapFn, R, N>(&mut self, replace_max: usize, notify: N, map_fn: MapFn) -> (usize, R)
184    where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>), MapFn: FnOnce(&mut E) -> R {
185        unsafe {
186            ContentTreeRaw::unsafe_mutate_single_entry_notify(map_fn, self, replace_max, notify)
187        }
188    }
189}
190
191impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE> {
192    #[inline(always)]
193    pub fn cursor_at_start(&self) -> Cursor<E, I, IE, LE> {
194        unsafe {
195            Cursor::unchecked_from_raw(self, self.unsafe_cursor_at_start())
196        }
197    }
198
199    #[inline(always)]
200    pub fn cursor_at_end(&self) -> Cursor<E, I, IE, LE> {
201        unsafe {
202            Cursor::unchecked_from_raw(self, self.unsafe_cursor_at_end())
203        }
204    }
205
206    #[inline(always)]
207    pub fn cursor_at_query<F, G>(&self, raw_pos: usize, stick_end: bool, offset_to_num: F, entry_to_num: G) -> Cursor<E, I, IE, LE>
208    where F: Fn(I::Value) -> usize, G: Fn(E) -> usize {
209        unsafe {
210            Cursor::unchecked_from_raw(self, self.unsafe_cursor_at_query(raw_pos, stick_end, offset_to_num, entry_to_num))
211        }
212    }
213
214    // And the mut variants...
215    #[inline(always)]
216    pub fn mut_cursor_at_start<'a>(self: &'a mut Pin<Box<Self>>) -> MutCursor<'a, E, I, IE, LE> {
217        unsafe {
218            MutCursor::unchecked_from_raw(self, self.unsafe_cursor_at_start())
219        }
220    }
221
222    #[inline(always)]
223    pub fn mut_cursor_at_end<'a>(self: &'a mut Pin<Box<Self>>) -> MutCursor<'a, E, I, IE, LE> {
224        unsafe {
225            MutCursor::unchecked_from_raw(self, self.unsafe_cursor_at_end())
226        }
227    }
228
229    #[inline(always)]
230    pub fn mut_cursor_at_query<'a, F, G>(self: &'a mut Pin<Box<Self>>, raw_pos: usize, stick_end: bool, offset_to_num: F, entry_to_num: G) -> MutCursor<'a, E, I, IE, LE>
231        where F: Fn(I::Value) -> usize, G: Fn(E) -> usize {
232        unsafe {
233            MutCursor::unchecked_from_raw(self, self.unsafe_cursor_at_query(raw_pos, stick_end, offset_to_num, entry_to_num))
234        }
235    }
236}
237
238impl<R, E: ContentTraits + ContentLength, I: FindContent<E>, const IE: usize, const LE: usize> SafeCursor<R, E, I, IE, LE> {
239    pub fn count_content_pos(&self) -> usize {
240        unsafe { self.inner.unsafe_count_content_pos() }
241        // I::index_to_content(self.old_count_pos())
242    }
243}
244
245impl<R, E: ContentTraits, I: FindOffset<E>, const IE: usize, const LE: usize> SafeCursor<R, E, I, IE, LE> {
246    pub fn count_offset_pos(&self) -> usize {
247        unsafe { self.inner.unsafe_count_offset_pos() }
248        // I::index_to_offset(self.old_count_pos())
249    }
250}
251
252impl<R, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> PartialEq for SafeCursor<R, E, I, IE, LE> {
253    fn eq(&self, other: &Self) -> bool {
254        self.inner.eq(&other.inner)
255    }
256}
257
258impl<R, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Eq for SafeCursor<R, E, I, IE, LE> {}
259
260
261/// NOTE: This comparator will panic when cursors from different range trees are compared.
262///
263/// Also beware: A cursor pointing to the end of a leaf entry will be considered less than a cursor
264/// pointing to the subsequent entry in the next leaf.
265impl<R, E: ContentTraits + Eq, I: TreeMetrics<E>, const IE: usize, const LE: usize> Ord for SafeCursor<R, E, I, IE, LE> {
266    fn cmp(&self, other: &Self) -> Ordering {
267        unsafe { self.inner.unsafe_cmp(&other.inner) }
268    }
269}
270
271impl<R, E: ContentTraits + Eq, I: TreeMetrics<E>, const IE: usize, const LE: usize> PartialOrd<SafeCursor<R, E, I, IE, LE>> for SafeCursor<R, E, I, IE, LE> {
272    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
273        Some(self.cmp(other))
274    }
275}
276
277impl<R, E: ContentTraits + Searchable, I: TreeMetrics<E>, const IE: usize, const LE: usize> SafeCursor<R, E, I, IE, LE> {
278    pub fn get_item(&self) -> Option<E::Item> {
279        unsafe { self.inner.unsafe_get_item() }
280    }
281}
content_tree/safe_cursor.rs

content_tree/
safe_cursor.rs
