Struct content_tree::ContentTreeRaw

pub struct ContentTreeRaw<E: ContentTraits, I: TreeIndex<E>, const INT_ENTRIES: usize, const LEAF_ENTRIES: usize> { /* fields omitted */ }

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.raw_iter().collect::<Vec<TestRange>>(), vec![
    TestRange { id: 0, len: 150, is_activated: true }
]);

Implementations

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

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

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

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::IndexValue) -> usize,
    G: Fn(E) -> usize, 

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 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 next_entry_or_panic(
    cursor: &mut UnsafeCursor<E, I, IE, LE>,
    marker: &mut I::IndexUpdate
)

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: TreeIndex<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE>

pub unsafe fn 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.

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: TreeIndex<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_mutate_entry_notify<MapFn, N>(
    map_fn: MapFn,
    cursor: &mut UnsafeCursor<E, I, IE, LE>,
    replace_max: usize,
    flush_marker: &mut I::IndexUpdate,
    notify: &mut N
) -> usize where
    N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>),
    MapFn: FnOnce(&mut E), 

Replace as much of the current entry from cursor onwards as we can

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: TreeIndex<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: 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: 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: TreeIndex<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::IndexValue) -> 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::IndexValue) -> usize,
    G: Fn(E) -> usize, 

Trait Implementations

impl<E: Debug + ContentTraits, I: Debug + TreeIndex<E>, const INT_ENTRIES: usize, const LEAF_ENTRIES: usize> Debug for ContentTreeRaw<E, I, INT_ENTRIES, LEAF_ENTRIES> where
    I::IndexValue: Debug, 

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

Formats the value using the given formatter.