From a41476ac28083a2d8a54161d4177b3ee5c028525 Mon Sep 17 00:00:00 2001 From: Rose Hogenson Date: Fri, 12 Jan 2024 21:03:25 -0800 Subject: Start tuning the performance of rope. --- src/lib.rs | 2 ++ src/main.rs | 10 +++---- src/rope.rs | 99 ++++++++++++++++++++++++++++++------------------------------- 3 files changed, 54 insertions(+), 57 deletions(-) create mode 100644 src/lib.rs (limited to 'src') diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..a382743 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,2 @@ +pub mod rope; +pub mod term; diff --git a/src/main.rs b/src/main.rs index b40d9b1..5b9d2f5 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,14 +1,12 @@ -mod rope; -mod term; - -use rope::Rope; +use edit::rope::Rope; +use edit::term; +use edit::term::Key; +use edit::term::Reader; use std::error::Error; use std::ffi::{OsStr, OsString}; use std::fs::File; use std::io::{stderr, stdout, Write}; use std::path::{Path, PathBuf}; -use term::Key; -use term::Reader; fn open(file: &Path) -> Result { let mut f = File::open(file)?; diff --git a/src/rope.rs b/src/rope.rs index 8bda5af..930c88a 100644 --- a/src/rope.rs +++ b/src/rope.rs @@ -9,10 +9,11 @@ enum Insert { } #[derive(Debug, Clone)] -pub struct Leaf { +struct Leaf { unsafe_buf: Option>, start: u16, end: u16, + lines: u16, } impl Leaf { @@ -25,23 +26,16 @@ impl Leaf { } #[derive(Debug, Clone)] -pub struct Branch { - unsafe_children: [Rope; 3], +struct Branch { + children: Rc<[Rope]>, len: usize, lines: usize, - n_children: u8, -} - -impl Branch { - fn children(&self) -> &[Rope] { - &self.unsafe_children[..usize::from(self.n_children)] - } } #[derive(Debug, Clone)] enum Node { Leaf(Leaf), - Branch(Rc), + Branch(Branch), } #[derive(Debug, Clone)] @@ -57,15 +51,7 @@ impl Rope { pub fn lines(&self) -> usize { match self { - Rope(Node::Leaf(l)) => { - let mut lines = 0; - for &b in l.bytes().iter() { - if b == b'\n' { - lines += 1; - } - } - lines - } + Rope(Node::Leaf(l)) => usize::from(l.lines), Rope(Node::Branch(b)) => b.lines, } } @@ -79,12 +65,20 @@ impl Rope { unsafe_buf: None, start: 0, end: 0, + lines: 0, })); } + let mut lines = 0; + for &b in buf.iter() { + if b == b'\n' { + lines += 1; + } + } Rope(Node::Leaf(Leaf { unsafe_buf: Some(Rc::from(buf)), start: 0, end: u16::try_from(buf.len()).expect("buf.len() <= MAX_NODE_SIZE"), + lines, })) } @@ -95,17 +89,11 @@ impl Rope { len += c.len(); lines += c.lines(); } - let mut child_array = [Rope::leaf(&[]), Rope::leaf(&[]), Rope::leaf(&[])]; - for (i, c) in children.iter().enumerate() { - child_array[i] = c.clone(); - } - Rope(Node::Branch(Rc::new(Branch { - unsafe_children: child_array, + Rope(Node::Branch(Branch { + children: Rc::from(children), len, lines, - n_children: u8::try_from(children.len()) - .expect("there should only ever be 2 or 3 children"), - }))) + })) } fn concat_height(&self, self_height: usize, other: &Rope, other_height: usize) -> Insert { @@ -134,26 +122,26 @@ impl Rope { let Rope(Node::Branch(b)) = self else { panic!("self_height is at least 1, so it's a branch"); }; - match b.children()[b.children().len() - 1].concat_height( + match b.children[b.children.len() - 1].concat_height( self_height - 1, other, other_height, ) { Insert::Node(new_child) => { - let mut new_children = b.children().to_vec(); - new_children[b.children().len() - 1] = new_child; + let mut new_children = b.children.to_vec(); + new_children[b.children.len() - 1] = new_child; return Insert::Node(Rope::branch(&new_children)); } Insert::Split(child1, child2) => { - if b.children().len() == 2 { + if b.children.len() == 2 { return Insert::Node(Rope::branch(&[ - b.children()[0].clone(), + b.children[0].clone(), child1, child2, ])); } return Insert::Split( - Rope::branch(&[b.children()[0].clone(), b.children()[1].clone()]), + Rope::branch(&[b.children[0].clone(), b.children[1].clone()]), Rope::branch(&[child1, child2]), ); } @@ -162,19 +150,19 @@ impl Rope { let Rope(Node::Branch(b)) = other else { panic!("other_height is at least 1, so it's a branch"); }; - match self.concat_height(self_height, &b.children()[0], other_height - 1) { + match self.concat_height(self_height, &b.children[0], other_height - 1) { Insert::Node(new_child) => { - let mut new_children = b.children().to_vec(); + let mut new_children = b.children.to_vec(); new_children[0] = new_child; Insert::Node(Rope::branch(&new_children)) } Insert::Split(child1, child2) => { - if b.children().len() == 2 { - return Insert::Node(Rope::branch(&[child1, child2, b.children()[1].clone()])); + if b.children.len() == 2 { + return Insert::Node(Rope::branch(&[child1, child2, b.children[1].clone()])); } Insert::Split( Rope::branch(&[child1, child2]), - Rope::branch(&[b.children()[1].clone(), b.children()[2].clone()]), + Rope::branch(&[b.children[1].clone(), b.children[2].clone()]), ) } } @@ -183,7 +171,7 @@ impl Rope { fn height(&self) -> usize { match self { Rope(Node::Leaf(_)) => 0, - Rope(Node::Branch(b)) => 1 + b.children()[0].height(), + Rope(Node::Branch(b)) => 1 + b.children[0].height(), } } @@ -225,7 +213,7 @@ impl Rope { } Rope(Node::Branch(b)) => { let mut i = i; - for c in b.children().iter() { + for c in b.children.iter() { if i < c.len() { return c.is_char_boundary(i); } @@ -271,7 +259,7 @@ impl Rope { Rope(Node::Branch(b)) => { let mut n = n; let mut offset = 0; - for c in b.children().iter() { + for c in b.children.iter() { if n < c.lines() { return offset + c.line_end(n); } @@ -304,7 +292,7 @@ impl Rope { Ok(()) } Rope(Node::Branch(b)) => { - for c in b.children().iter() { + for c in b.children.iter() { c.print(w)?; } Ok(()) @@ -330,16 +318,25 @@ impl Rope { return self.clone(); } match self { - Rope(Node::Leaf(l)) => Rope(Node::Leaf(Leaf { - unsafe_buf: l.unsafe_buf.clone(), - start: l.start + u16::try_from(start).expect("start <= self.len()"), - end: l.start + u16::try_from(end).expect("end <= self.len()"), - })), + Rope(Node::Leaf(l)) => { + let mut lines = 0; + for &b in l.bytes()[start..end].iter() { + if b == b'\n' { + lines += 1; + } + } + Rope(Node::Leaf(Leaf { + unsafe_buf: l.unsafe_buf.clone(), + start: l.start + u16::try_from(start).expect("start <= self.len()"), + end: l.start + u16::try_from(end).expect("end <= self.len()"), + lines, + })) + } Rope(Node::Branch(b)) => { let mut s = Rope::new(&[]); let mut start = start; let mut end = end; - for c in b.children().iter() { + for c in b.children.iter() { if start >= c.len() { start -= c.len(); end -= c.len(); @@ -365,7 +362,7 @@ impl Rope { Rope(Node::Leaf(l)) => l.bytes()[i], Rope(Node::Branch(b)) => { let mut i = i; - for c in b.children().iter() { + for c in b.children.iter() { if i < c.len() { return c.byte(i); } -- cgit v1.3.1