use std::{mem, ptr};
use std::hint::unreachable_unchecked;
use std::pin::Pin;
use std::ptr::NonNull;
use smallvec::SmallVec;
use super::*;
use rle::AppendRle;
impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> ContentTreeRaw<E, I, IE, LE> {
unsafe fn insert_internal<F>(mut items: &[E], cursor: &mut UnsafeCursor<E, I, IE, LE>, flush_marker: &mut I::Update, notify: &mut F)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>)
{
if items.is_empty() { return; }
assert!(items.len() <= 3);
let mut node = &mut *cursor.node.as_ptr();
let remainder = if cursor.offset == usize::MAX {
debug_assert_eq!(cursor.idx, 0);
debug_assert_eq!(node.num_entries, 0);
cursor.offset = 0;
None
} else if cursor.offset == 0 && cursor.idx > 0 {
cursor.idx -= 1;
cursor.offset = node.data[cursor.idx].len(); None
} else {
if cursor.offset == node.data[cursor.idx].len() || cursor.offset == 0 {
None
} else {
let entry: &mut E = &mut node.data[cursor.idx];
let remainder = entry.truncate(cursor.offset);
I::decrement_marker(flush_marker, &remainder);
Some(remainder)
}
};
let mut trailing_offset = 0;
if cursor.offset != 0 {
debug_assert_eq!(cursor.offset, node.data[cursor.idx].len());
let mut items_idx = 0;
let cur_entry: &mut E = &mut node.data[cursor.idx];
while items_idx < items.len() { let next = items[items_idx];
if cur_entry.can_append(&next) {
I::increment_marker(flush_marker, &next);
notify(next, cursor.node);
cur_entry.append(next);
cursor.offset = cur_entry.len();
items_idx += 1;
} else { break; }
}
if items_idx == items.len() && remainder.is_none() {
return; }
items = &items[items_idx..];
cursor.offset = 0;
cursor.idx += 1;
if remainder.is_none() && !items.is_empty() && cursor.idx < node.len_entries() {
let mut end_idx = items.len() - 1;
let cur_entry = &mut node.data[cursor.idx];
loop {
let next = items[end_idx];
if next.can_append(cur_entry) {
I::increment_marker(flush_marker, &next);
notify(next, cursor.node);
trailing_offset += next.len();
cur_entry.prepend(next);
} else { break; }
if end_idx == 0 {
cursor.offset = trailing_offset;
return; } else { end_idx -= 1; }
}
items = &items[..=end_idx];
}
}
debug_assert_eq!(cursor.offset, 0);
let space_needed = items.len() + remainder.is_some() as usize;
let num_filled = node.len_entries();
debug_assert!(space_needed > 0);
assert!(space_needed <= LE / 2);
let remainder_moved = if num_filled + space_needed > LE {
node.flush_metric_update(flush_marker);
if cursor.idx < LE / 2 {
node.split_at(cursor.idx, 0, notify);
node.num_entries += space_needed as u8;
false
} else {
let new_node_ptr = node.split_at(cursor.idx, space_needed, notify);
cursor.node = new_node_ptr;
cursor.idx = 0;
node = &mut *cursor.node.as_ptr();
true
}
} else {
if num_filled > cursor.idx {
node.data[..].copy_within(cursor.idx..num_filled, cursor.idx + space_needed);
}
node.num_entries += space_needed as u8;
false
};
let remainder_idx = cursor.idx + items.len();
if !items.is_empty() {
for e in items {
I::increment_marker(flush_marker, e);
notify(*e, cursor.node);
}
node.data[cursor.idx..cursor.idx + items.len()].copy_from_slice(items);
cursor.idx += items.len() - 1;
cursor.offset = items[items.len() - 1].len();
if trailing_offset > 0 {
cursor.move_forward_by_offset(trailing_offset, Some(flush_marker));
}
}
if let Some(e) = remainder {
I::increment_marker(flush_marker, &e);
if remainder_moved {
notify(e, cursor.node);
}
node.data[remainder_idx] = e;
}
}
pub unsafe fn unsafe_insert_notify<F>(cursor: &mut UnsafeCursor<E, I, IE, LE>, new_entry: E, mut notify: F)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
let mut marker = I::Update::default();
Self::insert_internal(&[new_entry], cursor, &mut marker, &mut notify);
cursor.get_node_mut().flush_metric_update(&mut marker);
}
#[inline(always)]
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>>)
{
unsafe { Self::unsafe_insert_notify(&mut self.unsafe_cursor_at_start(), new_entry, notify) }
}
#[inline(always)]
pub fn insert_at_start(self: &mut Pin<Box<Self>>, new_entry: E) {
self.insert_at_start_notify(new_entry, null_notify);
}
#[inline(always)]
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>>)
{
unsafe { Self::unsafe_insert_notify(&mut self.unsafe_cursor_at_end(), new_entry, notify) }
}
#[inline(always)]
pub fn push(self: &mut Pin<Box<Self>>, new_entry: E)
{
self.push_notify(new_entry, null_notify);
}
#[allow(clippy::len_zero)]
unsafe fn replace_entry<F>(cursor: &mut UnsafeCursor<E, I, IE, LE>, items: &[E], flush_marker: &mut I::Update, notify: &mut F)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
assert!(items.len() >= 1 && items.len() <= 3);
let mut items_idx = 0;
let node = cursor.node.as_mut();
debug_assert!(cursor.idx < node.len_entries());
if cursor.idx >= 1 {
let elem = &mut node.data[cursor.idx - 1];
loop { let item = &items[items_idx];
if elem.can_append(item) {
I::increment_marker(flush_marker, item);
elem.append(*item);
items_idx += 1;
if items_idx >= items.len() { break; }
} else { break; }
}
}
let entry = &mut node.data[cursor.idx];
I::decrement_marker(flush_marker, entry);
if items_idx >= items.len() {
node.splice_out(cursor.idx);
if cursor.idx >= node.len_entries() {
debug_assert!(node.len_entries() >= 1);
cursor.idx -= 1;
cursor.offset = node.data[cursor.idx].len();
} else {
cursor.offset = 0;
}
} else {
*entry = items[items_idx];
I::increment_marker(flush_marker, entry);
cursor.offset = entry.len();
Self::insert_internal(&items[items_idx + 1..], cursor, flush_marker, notify);
}
if cfg!(debug_assertions) {
let node = cursor.get_node_mut();
debug_assert!(cursor.idx < node.len_entries());
}
}
pub unsafe fn unsafe_replace_entry_notify<N>(cursor: &mut UnsafeCursor<E, I, IE, LE>, items: &[E], mut notify: N)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
let mut flush_marker = I::Update::default();
Self::replace_entry(cursor, items, &mut flush_marker, &mut notify);
cursor.get_node_mut().flush_metric_update(&mut flush_marker);
}
#[inline]
unsafe fn replace_entry_simple<F>(cursor: &mut UnsafeCursor<E, I, IE, LE>, new_item: E, flush_marker: &mut I::Update, notify: &mut F)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
notify(new_item, cursor.node);
cursor.offset = new_item.len();
let entry = cursor.get_raw_entry_mut();
I::decrement_marker(flush_marker, entry);
*entry = new_item;
I::increment_marker(flush_marker, entry);
}
pub unsafe fn unsafe_replace_entry_simple_notify<N>(cursor: &mut UnsafeCursor<E, I, IE, LE>, new_item: E, mut notify: N)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
let mut flush_marker = I::Update::default();
Self::replace_entry_simple(cursor, new_item, &mut flush_marker, &mut notify);
cursor.get_node_mut().flush_metric_update(&mut flush_marker);
}
unsafe fn unsafe_mutate_entry_internal<MapFn, N, R>(
map_fn: MapFn,
cursor: &mut UnsafeCursor<E, I, IE, LE>,
replace_max: usize,
flush_marker: &mut I::Update,
notify: &mut N
) -> (usize, R)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>), MapFn: FnOnce(&mut E) -> R
{
let node = cursor.get_node_mut();
debug_assert!(cursor.idx < node.len_entries());
let mut entry: E = node.data[cursor.idx];
let mut entry_len = entry.len();
assert!(cursor.offset < entry_len);
let a = if cursor.offset > 0 {
entry_len -= cursor.offset;
Some(entry.truncate_keeping_right(cursor.offset))
} else { None };
let (c, replaced_here) = if replace_max < entry_len {
(Some(entry.truncate(replace_max)), replace_max)
} else { (None, entry_len) };
let return_val = map_fn(&mut entry);
match (a, c) {
(Some(a), Some(c)) => {
let c_len = c.len();
Self::replace_entry(cursor, &[a, entry, c], flush_marker, notify);
cursor.move_back_by_offset(c_len, Some(flush_marker));
},
(Some(a), None) => {
Self::replace_entry(cursor, &[a, entry], flush_marker, notify);
},
(None, Some(c)) => {
let c_len = c.len();
Self::replace_entry(cursor, &[entry, c], flush_marker, notify);
cursor.move_back_by_offset(c_len, Some(flush_marker));
},
(None, None) => {
I::decrement_marker(flush_marker, &node.data[cursor.idx]);
node.data[cursor.idx] = entry;
cursor.offset = replaced_here;
I::increment_marker(flush_marker, &entry);
notify(entry, cursor.node);
}
}
(replaced_here, return_val)
}
pub unsafe fn unsafe_mutate_single_entry_notify<MapFn, R, N>(
map_fn: MapFn,
cursor: &mut UnsafeCursor<E, I, IE, LE>,
replace_max: usize,
mut notify: N
) -> (usize, R)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>), MapFn: FnOnce(&mut E) -> R {
let mut flush_marker = I::Update::default();
let (amt_modified, ret) = Self::unsafe_mutate_entry_internal(map_fn, cursor, replace_max, &mut flush_marker, &mut notify);
cursor.get_node_mut().flush_metric_update(&mut flush_marker);
(amt_modified, ret)
}
pub unsafe fn unsafe_mutate_entries_notify<MapFn, N>(
map_fn: MapFn,
cursor: &mut UnsafeCursor<E, I, IE, LE>,
replace_len: usize,
mut notify: N
)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>), MapFn: Fn(&mut E) {
let mut flush_marker = I::Update::default();
let mut remaining = replace_len;
while remaining > 0 {
cursor.roll_to_next_entry_marker(&mut flush_marker);
let (consumed_here, _) = Self::unsafe_mutate_entry_internal(&map_fn, cursor, remaining, &mut flush_marker, &mut notify);
assert!(consumed_here > 0, "Could not mutate past end of list");
remaining -= consumed_here;
}
cursor.get_node_mut().flush_metric_update(&mut flush_marker);
}
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>>) {
let mut flush_marker = I::Update::default();
Self::replace_range_internal(cursor, new_entry.len(), new_entry, &mut flush_marker, notify);
cursor.get_node_mut().flush_metric_update(&mut flush_marker);
}
unsafe fn replace_range_internal<N>(cursor: &mut UnsafeCursor<E, I, IE, LE>, mut replaced_len: usize, new_entry: E, flush_marker: &mut I::Update, mut notify: N)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
let node = cursor.node.as_mut();
if cursor.idx >= node.len_entries() {
cursor.roll_to_next_entry();
Self::insert_internal(&[new_entry], cursor, flush_marker, &mut notify);
return;
}
let entry = &mut node.data[cursor.idx];
let entry_len = entry.len();
if cursor.offset == entry_len && entry.can_append(&new_entry) {
assert!(cursor.offset > 0);
notify(new_entry, cursor.node);
I::increment_marker(flush_marker, &new_entry);
entry.append(new_entry);
cursor.offset += new_entry.len();
Self::delete_internal(cursor, replaced_len, flush_marker, &mut notify);
return;
}
if !cursor.roll_to_next_entry() { debug_assert_eq!(*flush_marker, I::Update::default());
Self::insert_internal(&[new_entry], cursor, flush_marker, &mut notify);
return;
}
let mut node = cursor.node.as_mut();
let mut entry = &mut node.data[cursor.idx];
let mut entry_len = entry.len();
if cursor.offset > 0 {
if cursor.offset + replaced_len < entry_len {
let mut a = *entry;
a.truncate(cursor.offset);
let mut c = *entry;
c.truncate_keeping_right(cursor.offset + replaced_len);
let c_len = c.len();
Self::replace_entry(cursor, &[a, new_entry, c], flush_marker, &mut notify);
cursor.move_back_by_offset(c_len, Some(flush_marker));
return;
} else {
let removed = entry.truncate(cursor.offset);
I::decrement_marker(flush_marker, &removed);
replaced_len -= entry_len - cursor.offset;
debug_assert_eq!(entry_len - cursor.offset, removed.len());
if replaced_len == 0 || !cursor.next_entry_marker(Some(flush_marker)) {
Self::insert_internal(&[new_entry], cursor, flush_marker, &mut notify);
return;
}
node = cursor.node.as_mut();
entry = &mut node.data[cursor.idx];
entry_len = entry.len();
}
}
debug_assert_eq!(cursor.offset, 0);
if replaced_len >= entry_len {
I::decrement_marker(flush_marker, entry);
I::increment_marker(flush_marker, &new_entry);
notify(new_entry, cursor.node);
cursor.offset = new_entry.len();
*cursor.get_raw_entry_mut() = new_entry;
if replaced_len > entry_len {
cursor.next_entry_marker(Some(flush_marker));
Self::delete_internal(cursor, replaced_len - entry_len, flush_marker, &mut notify);
} } else { let mut remainder = *entry;
let remainder = remainder.truncate(replaced_len);
let rem_len = remainder.len();
Self::replace_entry(cursor, &[new_entry, remainder], flush_marker, &mut notify);
cursor.move_back_by_offset(rem_len, Some(flush_marker));
}
}
unsafe fn delete_entry_range(cursor: &mut UnsafeCursor<E, I, IE, LE>, mut del_items: usize, flush_marker: &mut I::Update) -> (bool, usize) {
debug_assert_eq!(cursor.offset, 0);
debug_assert!(del_items > 0);
let mut node = cursor.get_node_mut();
if cursor.idx >= node.num_entries as usize {
node.flush_metric_update(flush_marker);
if !cursor.traverse_forward() { return (false, 0); }
node = cursor.get_node_mut();
}
if cursor.idx >= LE { unreachable_unchecked(); }
let start_range = cursor.idx;
let mut end_range = cursor.idx;
let len_entries = node.len_entries();
while end_range < len_entries && del_items > 0 {
let entry = node.data[end_range];
let entry_len = entry.len();
if entry_len <= del_items {
I::decrement_marker(flush_marker, &entry);
del_items -= entry_len;
end_range += 1;
} else {
break;
}
}
if start_range == 0 && end_range == len_entries && !node.has_root_as_parent() {
node.flush_metric_update(flush_marker);
let node = cursor.node;
let has_next = cursor.traverse_forward();
if !has_next {
cursor.traverse_backwards();
del_items = 0; }
NodeLeaf::remove(node);
(has_next, del_items)
} else if end_range > start_range {
let len_entries = node.len_entries();
let tail_count = len_entries - end_range;
if tail_count > 0 {
node.data.copy_within(end_range..len_entries, start_range);
}
node.num_entries = (start_range + tail_count) as u8;
debug_assert!(node.num_entries > 0 || node.parent.is_root());
node.data[start_range + tail_count..].fill(E::default());
(true, del_items)
} else {
(false, del_items)
}
}
unsafe fn delete_internal<N>(cursor: &mut UnsafeCursor<E, I, IE, LE>, mut del_items: usize, flush_marker: &mut I::Update, notify: &mut N)
where N: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
if del_items == 0 { return; }
if cursor.offset > 0 {
let node = cursor.node.as_mut();
let entry = &mut node.data[cursor.idx];
let entry_len = entry.len();
let remaining_len = entry_len - cursor.offset;
if remaining_len > 0 {
if remaining_len <= del_items {
I::decrement_marker(flush_marker, &entry.truncate(cursor.offset));
del_items -= remaining_len;
if del_items == 0 { return; }
} else { let mut remainder = entry.truncate(cursor.offset);
I::decrement_marker(flush_marker, &remainder);
remainder.truncate_keeping_right(del_items);
let mut c2 = cursor.clone();
Self::insert_internal(&[remainder], &mut c2, flush_marker, notify);
c2.get_node_mut().flush_metric_update(flush_marker);
return;
}
}
if !cursor.next_entry_marker(Some(flush_marker)) { return; }
}
debug_assert!(del_items > 0);
debug_assert_eq!(cursor.offset, 0);
while del_items > 0 {
let (iterate, num) = Self::delete_entry_range(cursor, del_items, flush_marker);
del_items = num;
if !iterate { break; }
}
let node = cursor.node.as_mut();
if del_items > 0 {
debug_assert!(cursor.idx < node.len_entries());
debug_assert!(node.data[cursor.idx].len() > del_items);
let trimmed = node.data[cursor.idx].truncate_keeping_right(del_items);
I::decrement_marker(flush_marker, &trimmed);
} else if cursor.idx >= node.len_entries() {
debug_assert_eq!(cursor.offset, 0);
if cursor.idx == 0 {
cursor.offset = usize::MAX;
debug_assert!(node.parent.is_root());
} else {
cursor.idx -= 1;
cursor.offset = node.data[cursor.idx].len();
}
}
}
pub unsafe fn unsafe_delete_notify<F>(cursor: &mut UnsafeCursor<E, I, IE, LE>, del_items: usize, mut notify: F)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>)
{
let mut marker = I::Update::default();
Self::delete_internal(cursor, del_items, &mut marker, &mut notify);
cursor.get_node_mut().flush_metric_update(&mut marker);
}
pub fn delete_at_start_notify<F>(self: &mut Pin<Box<Self>>, del_items: usize, mut notify: F)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>)
{
let mut marker = I::Update::default();
let mut cursor = self.unsafe_cursor_at_start();
unsafe {
Self::delete_internal(&mut cursor, del_items, &mut marker, &mut notify);
cursor.get_node_mut().flush_metric_update(&mut marker);
}
}
pub fn delete_at_start(self: &mut Pin<Box<Self>>, del_items: usize) {
self.delete_at_start_notify(del_items, null_notify);
}
}
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>>, mut cursor: UnsafeCursor<E, I, IE, LE>, deleted_len: usize, mut notify: F) -> DeleteResult<E>
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>)
{
if cfg!(debug_assertions) {
}
let mut result: DeleteResult<E> = SmallVec::default();
let mut flush_marker = I::Update::default();
let mut delete_remaining = deleted_len;
cursor.roll_to_next_entry();
while delete_remaining > 0 {
while cursor.get_raw_entry().is_deactivated() {
Self::next_entry_or_panic(&mut cursor, &mut flush_marker);
}
delete_remaining -= Self::unsafe_mutate_entry_internal(|e| {
result.push_rle(*e);
e.mark_deactivated();
}, &mut cursor, delete_remaining, &mut flush_marker, &mut notify).0;
}
cursor.compress_node();
cursor.get_node_mut().flush_metric_update(&mut flush_marker);
if cfg!(debug_assertions) {
}
result
}
unsafe fn set_enabled<F>(cursor: &mut UnsafeCursor<E, I, IE, LE>, max_len: usize, want_enabled: bool, notify: F) -> (usize, bool)
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>) {
cursor.roll_to_next_entry();
let entry = cursor.get_raw_entry();
if entry.is_activated() != want_enabled {
let (amt_modified, _) = Self::unsafe_mutate_single_entry_notify(|e| {
if want_enabled { e.mark_activated(); } else { e.mark_deactivated(); }
}, cursor, max_len, notify);
(amt_modified, true)
} else {
(max_len.min(entry.len() - cursor.offset), false)
}
}
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>>)
{
Self::set_enabled(cursor, max_deleted_len, false, notify)
}
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>>)
{
Self::set_enabled(cursor, max_len, true, notify)
}
}
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>>)
{
let mut cursor = self.unsafe_cursor_at_offset_pos(pos, true);
unsafe { Self::unsafe_insert_notify(&mut cursor, new_entry, notify); }
}
pub fn insert_at_offset(self: &mut Pin<Box<Self>>, pos: usize, new_entry: E) {
let mut cursor = self.unsafe_cursor_at_offset_pos(pos, true);
unsafe { Self::unsafe_insert_notify(&mut cursor, new_entry, null_notify); }
}
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>>)
{
let mut cursor = self.unsafe_cursor_at_offset_pos(offset, true);
unsafe { Self::unsafe_replace_range_notify(&mut cursor, new_entry, notify); }
}
pub fn replace_range_at_offset(self: &mut Pin<Box<Self>>, offset: usize, new_entry: E) {
let mut cursor = self.unsafe_cursor_at_offset_pos(offset, true);
unsafe { Self::unsafe_replace_range_notify(&mut cursor, new_entry, null_notify); }
}
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>>)
{
let mut cursor = self.unsafe_cursor_at_offset_pos(pos, false);
unsafe { Self::unsafe_delete_notify(&mut cursor, del_items, notify); }
}
pub fn delete_at_offset(self: &mut Pin<Box<Self>>, pos: usize, del_items: usize) {
let mut cursor = self.unsafe_cursor_at_offset_pos(pos, false);
unsafe { Self::unsafe_delete_notify(&mut cursor, del_items, null_notify); }
}
}
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>>)
{
let mut cursor = self.unsafe_cursor_at_content_pos(pos, true);
unsafe { Self::unsafe_insert_notify(&mut cursor, new_entry, notify); }
}
pub fn insert_at_content(self: &mut Pin<Box<Self>>, pos: usize, new_entry: E) {
let mut cursor = self.unsafe_cursor_at_content_pos(pos, true);
unsafe { Self::unsafe_insert_notify(&mut cursor, new_entry, null_notify); }
}
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>>)
{
let mut cursor = self.unsafe_cursor_at_content_pos(pos, true);
unsafe { Self::unsafe_replace_range_notify(&mut cursor, new_entry, notify); }
}
pub fn replace_range_at_content(self: &mut Pin<Box<Self>>, pos: usize, new_entry: E) {
let mut cursor = self.unsafe_cursor_at_content_pos(pos, true);
unsafe { Self::unsafe_replace_range_notify(&mut cursor, new_entry, null_notify); }
}
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>>)
{
let mut cursor = self.unsafe_cursor_at_content_pos(pos, false);
unsafe { Self::unsafe_delete_notify(&mut cursor, del_items, notify); }
}
pub fn delete_at_content(self: &mut Pin<Box<Self>>, pos: usize, del_items: usize) {
let mut cursor = self.unsafe_cursor_at_content_pos(pos, false);
unsafe { Self::unsafe_delete_notify(&mut cursor, del_items, null_notify); }
}
}
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>>)
{
let cursor = self.unsafe_cursor_at_content_pos(offset, false);
unsafe { self.local_deactivate_notify(cursor, deleted_len, notify) }
}
}
impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> NodeLeaf<E, I, IE, LE> {
fn split_at<F>(&mut self, idx: usize, padding: usize, notify: &mut F) -> NonNull<NodeLeaf<E, I, IE, LE>>
where F: FnMut(E, NonNull<NodeLeaf<E, I, IE, LE>>)
{
unsafe {
let mut new_node = Self::new(self.next); let new_filled_len = self.len_entries() - idx;
let new_len = new_filled_len + padding;
debug_assert!(new_len <= LE);
if new_filled_len > 0 {
ptr::copy_nonoverlapping(&self.data[idx], &mut new_node.data[padding], new_filled_len);
}
new_node.num_entries = new_len as u8;
let mut stolen_length = I::Value::default();
for e in &mut self.data[idx..self.num_entries as usize] {
I::increment_offset(&mut stolen_length, e);
*e = E::default();
}
self.num_entries = idx as u8;
let mut new_node_boxed = Box::pin(new_node);
let new_leaf_ptr = NonNull::new_unchecked(new_node_boxed.as_mut().get_unchecked_mut());
self.next = Some(new_leaf_ptr);
for e in &new_node_boxed.as_ref().data[padding..new_len] {
notify(*e, new_leaf_ptr);
}
insert_after(self.parent, Node::Leaf(new_node_boxed), NodePtr::Leaf(NonNull::new_unchecked(self)), stolen_length);
new_leaf_ptr
}
}
unsafe fn remove(self_ptr: NonNull<NodeLeaf<E, I, IE, LE>>) {
let leaf = self_ptr.as_ref();
debug_assert!(!leaf.has_root_as_parent());
if let Some(mut prev) = leaf.prev_leaf() {
prev.as_mut().next = leaf.next;
}
NodeInternal::remove_leaf(leaf.parent.unwrap_internal(), self_ptr);
}
}
impl<E: ContentTraits, I: TreeMetrics<E>, const IE: usize, const LE: usize> NodeInternal<E, I, IE, LE> {
unsafe fn slice_out(&mut self, child: NodePtr<E, I, IE, LE>) -> Node<E, I, IE, LE> {
if self.children[1].is_none() {
debug_assert_eq!(self.find_child(child).unwrap(), 0);
self.children[0].take().unwrap()
} else {
let idx = self.find_child(child).unwrap();
let num_children = self.count_children();
let removed = self.children[idx].take().unwrap();
let count = num_children - idx - 1;
if count > 0 {
ptr::copy(
&self.children[idx + 1],
&mut self.children[idx],
count
);
self.metrics.copy_within(idx + 1..num_children, idx);
}
std::mem::forget(self.children[num_children - 1].take());
removed
}
}
unsafe fn remove_leaf(mut self_ptr: NonNull<NodeInternal<E, I, IE, LE>>, child: NonNull<NodeLeaf<E, I, IE, LE>>) {
let spare = self_ptr.as_mut().slice_out(NodePtr::Leaf(child));
Self::ripple_delete(self_ptr, spare);
}
unsafe fn ripple_delete(mut self_ptr: NonNull<NodeInternal<E, I, IE, LE>>, mut spare_leaf: Node<E, I, IE, LE>) {
debug_assert!(spare_leaf.is_leaf());
let self_ref = self_ptr.as_mut();
if self_ref.children[0].is_none() {
match self_ref.parent {
ParentPtr::Root(mut root) => {
let mut root = root.as_mut();
spare_leaf.set_parent(root.to_parent_ptr());
spare_leaf.unwrap_leaf_mut().get_unchecked_mut().clear_all();
root.root = spare_leaf;
}
ParentPtr::Internal(mut parent) => {
parent.as_mut().slice_out(NodePtr::Internal(self_ptr));
Self::ripple_delete(parent, spare_leaf);
}
}
}
}
}
unsafe fn insert_after<E: ContentTraits, I: TreeMetrics<E>, const INT_ENTRIES: usize, const LEAF_ENTRIES: usize>(
mut parent: ParentPtr<E, I, INT_ENTRIES, LEAF_ENTRIES>,
mut inserted_leaf_node: Node<E, I, INT_ENTRIES, LEAF_ENTRIES>,
mut insert_after: NodePtr<E, I, INT_ENTRIES, LEAF_ENTRIES>,
mut stolen_length: I::Value) {
loop {
if let ParentPtr::Internal(mut n) = parent {
let parent_ref = n.as_ref();
let count = parent_ref.count_children();
if count < INT_ENTRIES {
inserted_leaf_node.set_parent(ParentPtr::Internal(n));
let old_idx = parent_ref.find_child(insert_after).unwrap();
let new_idx = old_idx + 1;
let parent_ref = n.as_mut();
parent_ref.metrics[old_idx] -= stolen_length;
parent_ref.splice_in(new_idx, stolen_length, inserted_leaf_node);
return;
}
}
match parent {
ParentPtr::Root(mut r) => {
let new_root = Node::Internal(NodeInternal::new_with_parent(ParentPtr::Root(r)));
let mut old_root = mem::replace(&mut r.as_mut().root, new_root);
let root = r.as_mut();
let mut count = root.count;
let mut new_internal_root = root.root.unwrap_internal_mut();
let parent_ptr = new_internal_root.as_ref().to_parent_ptr();
old_root.set_parent(parent_ptr);
inserted_leaf_node.set_parent(parent_ptr);
count -= stolen_length;
new_internal_root.as_mut().set_entry(0, count, Some(old_root));
new_internal_root.as_mut().set_entry(1, stolen_length, Some(inserted_leaf_node));
return;
},
ParentPtr::Internal(mut n) => {
let left_sibling = n.as_ref();
parent = left_sibling.parent; debug_assert!(left_sibling.count_children() == INT_ENTRIES);
let mut right_sibling_box = Node::Internal(NodeInternal::new_with_parent(parent));
let mut right_sibling = right_sibling_box.unwrap_internal_mut();
let old_idx = left_sibling.find_child(insert_after).unwrap();
let left_sibling = n.as_mut();
left_sibling.metrics[old_idx] -= stolen_length;
let mut new_stolen_length = I::Value::default();
if old_idx < INT_ENTRIES /2 {
for i in 0..INT_ENTRIES /2 {
let ii = i + INT_ENTRIES /2;
let c = mem::take(&mut left_sibling.metrics[ii]);
let e = mem::take(&mut left_sibling.children[ii]);
if let Some(mut e) = e {
e.set_parent(right_sibling.as_ref().to_parent_ptr());
new_stolen_length += c;
right_sibling.as_mut().set_entry(i, c, Some(e));
}
}
let new_idx = old_idx + 1;
inserted_leaf_node.set_parent(ParentPtr::Internal(NonNull::new_unchecked(left_sibling)));
left_sibling.splice_in(new_idx, stolen_length, inserted_leaf_node);
} else {
let new_idx = old_idx - INT_ENTRIES /2 + 1;
inserted_leaf_node.set_parent(right_sibling.as_ref().to_parent_ptr());
let mut new_entry = (stolen_length, Some(inserted_leaf_node));
new_stolen_length = stolen_length;
let mut src = INT_ENTRIES /2;
for dest in 0..=INT_ENTRIES /2 {
if dest == new_idx {
right_sibling.as_mut().set_entry(dest, mem::take(&mut new_entry.0), mem::take(&mut new_entry.1));
} else {
let c = mem::take(&mut left_sibling.metrics[src]);
let e = mem::take(&mut left_sibling.children[src]);
if let Some(mut e) = e {
e.set_parent(right_sibling.as_ref().to_parent_ptr());
new_stolen_length += c;
right_sibling.as_mut().set_entry(dest, c, Some(e));
src += 1;
} else { break; }
}
}
debug_assert!(new_entry.1.is_none());
}
insert_after = NodePtr::Internal(n);
inserted_leaf_node = right_sibling_box;
stolen_length = new_stolen_length;
},
};
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::testrange::TestRange;
#[test]
fn splice_insert_test() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
let entry = TestRange {
id: 1000,
len: 100,
is_activated: true
};
tree.insert_at_content(15, entry);
tree.check();
let entry = TestRange {
id: 1100,
len: 20,
is_activated: true
};
tree.insert_at_content(15, entry);
tree.check();
assert_eq!(tree.raw_iter().collect::<Vec<TestRange>>(), vec![
TestRange { id: 1000, len: 15, is_activated: true },
TestRange { id: 1100, len: 20, is_activated: true },
TestRange { id: 1015, len: 85, is_activated: true },
]);
}
#[test]
fn delete_collapses() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
let entry = TestRange {
id: 1000,
len: 100,
is_activated: true,
};
tree.insert_at_content(0, entry);
assert_eq!(tree.count_entries(), 1);
tree.local_deactivate_at_content_notify(50, 1, null_notify);
assert_eq!(tree.count_entries(), 3);
tree.local_deactivate_at_content_notify(50, 1, null_notify);
assert_eq!(tree.raw_iter().collect::<Vec<TestRange>>(), vec![
TestRange { id: 1000, len: 50, is_activated: true },
TestRange { id: 1050, len: 2, is_activated: false },
TestRange { id: 1052, len: 48, is_activated: true },
]);
}
#[test]
fn backspace_collapses() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
let entry = TestRange {
id: 1000,
len: 100,
is_activated: true,
};
tree.insert_at_content_notify(0, entry, null_notify);
assert_eq!(tree.count_entries(), 1);
tree.local_deactivate_at_content_notify(99, 1, null_notify);
assert_eq!(tree.count_entries(), 2);
tree.local_deactivate_at_content_notify(98, 1, null_notify);
assert_eq!(tree.count_entries(), 2);
assert_eq!(tree.raw_iter().collect::<Vec<TestRange>>(), vec![
TestRange { id: 1000, len: 98, is_activated: true },
TestRange { id: 1098, len: 2, is_activated: false },
]);
tree.check();
}
#[test]
fn delete_single_item() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
tree.insert_at_start(TestRange { id: 0, len: 10, is_activated: true });
tree.delete_at_start(10);
assert_eq!(tree.len(), 0);
tree.check();
}
#[test]
fn delete_all_items() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
let num = DEFAULT_LE + 1;
for i in 0..num {
tree.insert_at_start_notify(TestRange { id: i as _, len: 10, is_activated: true }, null_notify);
}
assert!(!tree.root.is_leaf());
tree.delete_at_start_notify(10 * num, null_notify);
assert_eq!(tree.len(), 0);
tree.check();
}
#[test]
fn delete_past_end() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
tree.insert_at_start_notify(TestRange { id: 10 as _, len: 10, is_activated: true }, null_notify);
tree.delete_at_content_notify(10, 100, null_notify);
assert_eq!(tree.raw_iter().collect::<Vec<TestRange>>(), vec![
TestRange { id: 10, len: 10, is_activated: true },
]);
}
#[test]
fn push_into_empty() {
let mut tree = ContentTreeRaw::<TestRange, ContentMetrics, DEFAULT_IE, DEFAULT_LE>::new();
tree.push(TestRange { id: 0, len: 10, is_activated: true });
}
#[test]
fn mutation_wrappers() {
let mut tree = ContentTreeRaw::<TestRange, FullMetricsU32, DEFAULT_IE, DEFAULT_LE>::new();
tree.insert_at_content(0, TestRange { id: 0, len: 10, is_activated: true });
assert_eq!(tree.offset_len(), 10);
assert_eq!(tree.content_len(), 10);
tree.replace_range_at_content(3, TestRange { id: 100, len: 3, is_activated: false });
assert_eq!(tree.offset_len(), 10);
assert_eq!(tree.content_len(), 7);
assert_eq!(tree.at_content(4), Some((7, true)));
assert_eq!(tree.at_offset(4), Some((101, false)));
tree.delete_at_offset(5, 3);
assert_eq!(tree.offset_len(), 7);
assert_eq!(tree.content_len(), 5);
tree.delete_at_content(0, 1);
assert_eq!(tree.offset_len(), 6);
assert_eq!(tree.content_len(), 4);
}
#[test]
fn mutate_range() {
let mut tree = ContentTreeRaw::<TestRange, FullMetricsU32, DEFAULT_IE, DEFAULT_LE>::new();
tree.push(TestRange { id: 0, len: 10, is_activated: true });
unsafe {
let mut cursor = tree.unsafe_cursor_at_offset_pos(5, false);
ContentTreeRaw::unsafe_mutate_entries_notify(|r| {
assert_eq!(r, &TestRange { id: 5, len: 2, is_activated: true });
r.len = 1;
}, &mut cursor, 2, null_notify);
}
unsafe {
let mut cursor = tree.unsafe_cursor_at_offset_pos(5, false);
ContentTreeRaw::unsafe_mutate_entries_notify(|r| {
assert_eq!(r.len, 1);
assert!(r.id == 5 || r.id == 7);
r.len += 1;
}, &mut cursor, 2, null_notify);
}
assert_eq!(tree.raw_iter().collect::<Vec<TestRange>>(), vec![
TestRange { id: 0, len: 9, is_activated: true },
TestRange { id: 8, len: 2, is_activated: true },
]);
}
}