Struct ContentTreeRaw

pub struct ContentTreeRaw<E: ContentTraits, I: TreeMetrics<E>, const INT_ENTRIES: usize = DEFAULT_IE, const LEAF_ENTRIES: usize = DEFAULT_LE> { /* private fields */ }

A ContentTree is an efficient packed list of RLE entries, allowing for arbitrary inserts and deletes anywhere in the range.

use content_tree::ContentTree;
use content_tree::testrange::TestRange;

let mut tree = ContentTree::new();
tree.push(TestRange { id: 0, len: 100, is_activated: true });
tree.push(TestRange { id: 100, len: 50, is_activated: true });

assert_eq!(tree.iter().collect::<Vec<TestRange>>(), vec![
    TestRange { id: 0, len: 150, is_activated: true }
]);

Implementations

impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn new() -> Pin<Box<Self>>

pub fn len(&self) -> I::Value

pub fn unsafe_cursor_at_query<F, G>( &self, raw_pos: usize, stick_end: bool, offset_to_num: F, entry_to_num: G, ) -> UnsafeCursor<E, I, IE, LE>

where F: Fn(I::Value) -> usize, G: Fn(E) -> usize,

WARNING: This method doesn’t actually figure out the cursor position at the item. The offset stored in the cursor contains the final offset. For cursor_at_offset this will be correct, or any time the content size corresponds to offset size.

pub fn unsafe_cursor_at_start(&self) -> UnsafeCursor<E, I, IE, LE>

pub fn unsafe_cursor_at_end(&self) -> UnsafeCursor<E, I, IE, LE>

pub fn next_entry_or_panic( cursor: &mut UnsafeCursor<E, I, IE, LE>, marker: &mut I::Update, )

pub fn check(&self)

pub fn print_ptr_tree(&self)

pub fn print_stats(&self, name: &str, detailed: bool)

pub fn count_entries(&self) -> usize

pub fn count_nodes(&self) -> (usize, usize)

pub fn count_total_memory(&self) -> usize

impl<E: ContentTraits + Searchable, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub unsafe fn unsafe_cursor_before_item( loc: E::Item, ptr: NonNull<NodeLeaf<E, I, IE, LE>>, ) -> UnsafeCursor<E, I, IE, LE>

Returns a cursor right before the named location, referenced by the pointer.

pub fn cursor_before_item( &self, loc: E::Item, ptr: NonNull<NodeLeaf<E, I, IE, LE>>, ) -> Cursor<'_, E, I, IE, LE>

pub fn mut_cursor_before_item<'a>( self: &'a mut Pin<Box<Self>>, loc: E::Item, ptr: NonNull<NodeLeaf<E, I, IE, LE>>, ) -> MutCursor<'a, E, I, IE, LE>

impl<E: ContentTraits + ContentLength, I: FindContent<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn content_len(&self) -> usize

pub fn unsafe_cursor_at_content_pos( &self, pos: usize, stick_end: bool, ) -> UnsafeCursor<E, I, IE, LE>

pub fn cursor_at_content_pos( &self, pos: usize, stick_end: bool, ) -> Cursor<'_, E, I, IE, LE>

pub fn mut_cursor_at_content_pos<'a>( self: &'a mut Pin<Box<Self>>, pos: usize, stick_end: bool, ) -> MutCursor<'a, E, I, IE, LE>

impl<E: ContentTraits, I: FindOffset<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn offset_len(&self) -> usize

pub fn unsafe_cursor_at_offset_pos( &self, pos: usize, stick_end: bool, ) -> UnsafeCursor<E, I, IE, LE>

pub fn cursor_at_offset_pos( &self, pos: usize, stick_end: bool, ) -> Cursor<'_, E, I, IE, LE>

pub fn mut_cursor_at_offset_pos<'a>( self: &'a mut Pin<Box<Self>>, pos: usize, stick_end: bool, ) -> MutCursor<'a, E, I, IE, LE>

impl<E: ContentTraits + Searchable, I: FindOffset<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn at_offset(&self, pos: usize) -> Option<E::Item>

impl<E: ContentTraits + ContentLength + Searchable, I: FindContent<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn at_content(&self, pos: usize) -> Option<E::Item>

impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

This file contains the core code for content-tree’s mutation operations.

pub unsafe fn unsafe_insert_notify<F>( cursor: &mut UnsafeCursor<E, I, IE, LE>, new_entry: E, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn insert_at_start_notify<F>( self: &mut Pin<Box<Self>>, new_entry: E, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn insert_at_start(self: &mut Pin<Box<Self>>, new_entry: E)

pub fn push_notify<F>(self: &mut Pin<Box<Self>>, new_entry: E, notify: F)

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn push(self: &mut Pin<Box<Self>>, new_entry: E)

Push a new entry to the end of the tree. The new entry will be merged with the existing last entry if possible.

pub unsafe fn unsafe_replace_entry_notify<N>( cursor: &mut UnsafeCursor<E, I, IE, LE>, items: &[E], notify: N, )

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

Replace the current entry with the items passed via items[]. Items.len must be <= 3. The cursor offset is ignored. This is a fancy method - use sparingly.

pub unsafe fn unsafe_replace_entry_simple_notify<N>( cursor: &mut UnsafeCursor<E, I, IE, LE>, new_item: E, notify: N, )

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub unsafe fn unsafe_mutate_single_entry_notify<MapFn, R, N>( map_fn: MapFn, cursor: &mut UnsafeCursor<E, I, IE, LE>, replace_max: usize, notify: N, ) -> (usize, R)

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>), MapFn: FnOnce(&mut E) -> R,

pub unsafe fn unsafe_mutate_entries_notify<MapFn, N>( map_fn: MapFn, cursor: &mut UnsafeCursor<E, I, IE, LE>, replace_len: usize, notify: N, )

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>), MapFn: Fn(&mut E),

pub unsafe fn unsafe_replace_range_notify<N>( cursor: &mut UnsafeCursor<E, I, IE, LE>, new_entry: E, notify: N, )

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

Replace the range from cursor..cursor + replaced_len with new_entry.

pub unsafe fn unsafe_delete_notify<F>( cursor: &mut UnsafeCursor<E, I, IE, LE>, del_items: usize, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

Delete the specified number of items from the b-tree at the cursor. Cursor may be modified to point to the start of the next item.

pub fn delete_at_start_notify<F>( self: &mut Pin<Box<Self>>, del_items: usize, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn delete_at_start(self: &mut Pin<Box<Self>>, del_items: usize)

impl<E: ContentTraits + Toggleable, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub unsafe fn local_deactivate_notify<F>( self: &mut Pin<Box<Self>>, cursor: UnsafeCursor<E, I, IE, LE>, deleted_len: usize, notify: F, ) -> DeleteResult<E>

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub unsafe fn unsafe_remote_deactivate_notify<F>( cursor: &mut UnsafeCursor<E, I, IE, LE>, max_deleted_len: usize, notify: F, ) -> (usize, bool)

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

Deactivate up to max_deleted_len from the marker tree, at the location specified by cursor. We will always process at least one item. Consumers of this API should call this in a loop.

If the entry is already marked as deleted, unlike local_deactivate, this method does nothing. local_deactivate will skip over deleted items and delete something else.

Returns the number of items we tried to deactivate, and whether we were successful. (eg (1, true) means we marked 1 item for deletion. (2, false) means we skipped past 2 items which were already deactivated.

TODO: It might be cleaner to make the caller check for deleted items if we return 0.

TODO: Consider returning / mutating the cursor. Subsequent items will probably be in this node. It would be marginally faster to find a cursor using a hint, and subsequent deletes in the txn we’re applying will usually be in this node (usually the next item in this node).

pub unsafe fn unsafe_remote_reactivate_notify<F>( cursor: &mut UnsafeCursor<E, I, IE, LE>, max_len: usize, notify: F, ) -> (usize, bool)

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

impl<E: ContentTraits, I: FindOffset<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn insert_at_offset_notify<F>( self: &mut Pin<Box<Self>>, pos: usize, new_entry: E, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn insert_at_offset(self: &mut Pin<Box<Self>>, pos: usize, new_entry: E)

pub fn replace_range_at_offset_notify<N>( self: &mut Pin<Box<Self>>, offset: usize, new_entry: E, notify: N, )

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn replace_range_at_offset( self: &mut Pin<Box<Self>>, offset: usize, new_entry: E, )

pub fn delete_at_offset_notify<F>( self: &mut Pin<Box<Self>>, pos: usize, del_items: usize, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn delete_at_offset(self: &mut Pin<Box<Self>>, pos: usize, del_items: usize)

impl<E: ContentTraits + ContentLength, I: FindContent<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn insert_at_content_notify<F>( self: &mut Pin<Box<Self>>, pos: usize, new_entry: E, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn insert_at_content(self: &mut Pin<Box<Self>>, pos: usize, new_entry: E)

pub fn replace_range_at_content_notify<N>( self: &mut Pin<Box<Self>>, pos: usize, new_entry: E, notify: N, )

where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn replace_range_at_content( self: &mut Pin<Box<Self>>, pos: usize, new_entry: E, )

pub fn delete_at_content_notify<F>( self: &mut Pin<Box<Self>>, pos: usize, del_items: usize, notify: F, )

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

pub fn delete_at_content( self: &mut Pin<Box<Self>>, pos: usize, del_items: usize, )

impl<E: ContentTraits + ContentLength + Toggleable, I: FindContent<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn local_deactivate_at_content_notify<F>( self: &mut Pin<Box<Self>>, offset: usize, deleted_len: usize, notify: F, ) -> DeleteResult<E>

where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),

impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn cursor_at_start(&self) -> Cursor<'_, E, I, IE, LE>

pub fn cursor_at_end(&self) -> Cursor<'_, E, I, IE, LE>

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>

where F: Fn(I::Value) -> usize, G: Fn(E) -> usize,

pub fn mut_cursor_at_start<'a>( self: &'a mut Pin<Box<Self>>, ) -> MutCursor<'a, E, I, IE, LE>

pub fn mut_cursor_at_end<'a>( self: &'a mut Pin<Box<Self>>, ) -> MutCursor<'a, E, I, IE, LE>

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>

where F: Fn(I::Value) -> usize, G: Fn(E) -> usize,

impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub fn raw_iter(&self) -> Cursor<'_, E, I, IE, LE>

Iterate through all the items “raw” - which is to say, without merging anything.

This is different from iter() because in some editing situations the tree will not be perfectly flattened. That is, it may be possible to merge some items in the tree. This iterator method will not merge anything, and instead just iterate through all items as they are stored.

Whether specific items are merged or not is an implementation detail, and should not be relied upon by your application. If you expect all mergable items to be merged, use iter().

pub fn iter(&self) -> MergeIter<Cursor<'_, E, I, IE, LE>>

Iterate through all entries in the content tree. This iterator will yield all entries merged according to the methods in SplitableSpan.

pub fn item_iter(&self) -> ItemIterator<'_, E, I, IE, LE>

pub fn node_iter(&self) -> NodeIter<'_, E, I, IE, LE>

Trait Implementations

impl<'a, E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Cursors for &'a ContentTreeRaw<E, I, IE, LE>

type UnsafeCursor = UnsafeCursor<E, I, IE, LE>

type Cursor = SafeCursor<&'a ContentTreeRaw<E, I, IE, LE>, E, I, IE, LE>

type MutCursor = SafeCursor<&'a mut ContentTreeRaw<E, I, IE, LE>, E, I, IE, LE>

impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> Debug for ContentTreeRaw<E, I, IE, LE>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<E: ContentTraits + PartialEq, I: TreeMetrics<E>, const IE: usize, const LE: usize> PartialEq for ContentTreeRaw<E, I, IE, LE>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<E: ContentTraits + PartialEq, I: TreeMetrics<E>, const IE: usize, const LE: usize> Eq for ContentTreeRaw<E, I, IE, LE>