aboutsummaryrefslogtreecommitdiffstats
path: root/src/rope.rs
diff options
context:
space:
mode:
Diffstat (limited to 'src/rope.rs')
-rw-r--r--src/rope.rs114
1 files changed, 72 insertions, 42 deletions
diff --git a/src/rope.rs b/src/rope.rs
index 930c88a..62c6a89 100644
--- a/src/rope.rs
+++ b/src/rope.rs
@@ -56,33 +56,39 @@ impl Rope {
}
}
- fn leaf(buf: &[u8]) -> Rope {
- if buf.len() > MAX_NODE_SIZE {
- panic!("buffer too long for leaf!");
- }
- if buf.is_empty() {
- return Rope(Node::Leaf(Leaf {
- unsafe_buf: None,
- start: 0,
- end: 0,
- lines: 0,
- }));
+ fn empty() -> Rope {
+ Rope(Node::Leaf(Leaf {
+ unsafe_buf: None,
+ start: 0,
+ end: 0,
+ lines: 0,
+ }))
+ }
+
+ fn from_slice(buf: Rc<[u8]>, start: usize, end: usize) -> Rope {
+ if buf.len() > MAX_NODE_SIZE || start > buf.len() || end > buf.len() || start > end {
+ panic!("Invalid leaf!");
}
let mut lines = 0;
- for &b in buf.iter() {
+ for &b in buf[start..end].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"),
+ unsafe_buf: Some(buf),
+ start: u16::try_from(start).expect("buffer too long"),
+ end: u16::try_from(end).expect("buffer too long"),
lines,
}))
}
- fn branch(children: &[Rope]) -> Rope {
+ fn leaf(buf: Rc<[u8]>) -> Rope {
+ let n = buf.len();
+ Rope::from_slice(buf, 0, n)
+ }
+
+ fn branch(children: Rc<[Rope]>) -> Rope {
let mut len = 0;
let mut lines = 0;
for c in children.iter() {
@@ -90,7 +96,7 @@ impl Rope {
lines += c.lines();
}
Rope(Node::Branch(Branch {
- children: Rc::from(children),
+ children,
len,
lines,
}))
@@ -99,18 +105,20 @@ impl Rope {
fn concat_height(&self, self_height: usize, other: &Rope, other_height: usize) -> Insert {
if let (Rope(Node::Leaf(l)), Rope(Node::Leaf(r))) = (self, other) {
if self.len() + other.len() <= MAX_NODE_SIZE {
- let mut buf = vec![0; self.len() + other.len()];
- buf[..self.len()].copy_from_slice(l.bytes());
- buf[self.len()..].copy_from_slice(r.bytes());
- return Insert::Node(Rope::leaf(&buf));
+ let mut buf: Rc<[u8]> = Rc::from(vec![0; self.len() + other.len()]);
+ let buf_m = Rc::get_mut(&mut buf)
+ .expect("r was just created, so there can't be any other references");
+ buf_m[..self.len()].copy_from_slice(l.bytes());
+ buf_m[self.len()..].copy_from_slice(r.bytes());
+ return Insert::Node(Rope::leaf(buf));
}
if self.len() < MAX_NODE_SIZE / 2 || other.len() < MAX_NODE_SIZE / 2 {
let mut buf = vec![0; self.len() + other.len()];
buf[..self.len()].copy_from_slice(l.bytes());
buf[self.len()..].copy_from_slice(r.bytes());
return Insert::Split(
- Rope::leaf(&buf[..buf.len() / 2]),
- Rope::leaf(&buf[buf.len() / 2..]),
+ Rope::leaf(Rc::from(&buf[..buf.len() / 2])),
+ Rope::leaf(Rc::from(&buf[buf.len() / 2..])),
);
}
return Insert::Split(self.clone(), other.clone());
@@ -128,21 +136,29 @@ impl Rope {
other_height,
) {
Insert::Node(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));
+ if b.children.len() == 2 {
+ return Insert::Node(Rope::branch(Rc::new([
+ b.children[0].clone(),
+ new_child,
+ ])));
+ }
+ return Insert::Node(Rope::branch(Rc::new([
+ b.children[0].clone(),
+ b.children[1].clone(),
+ new_child,
+ ])));
}
Insert::Split(child1, child2) => {
if b.children.len() == 2 {
- return Insert::Node(Rope::branch(&[
+ return Insert::Node(Rope::branch(Rc::new([
b.children[0].clone(),
child1,
child2,
- ]));
+ ])));
}
return Insert::Split(
- Rope::branch(&[b.children[0].clone(), b.children[1].clone()]),
- Rope::branch(&[child1, child2]),
+ Rope::branch(Rc::new([b.children[0].clone(), b.children[1].clone()])),
+ Rope::branch(Rc::new([child1, child2])),
);
}
}
@@ -152,17 +168,26 @@ impl Rope {
};
match self.concat_height(self_height, &b.children[0], other_height - 1) {
Insert::Node(new_child) => {
- let mut new_children = b.children.to_vec();
- new_children[0] = new_child;
- Insert::Node(Rope::branch(&new_children))
+ if b.children.len() == 2 {
+ return Insert::Node(Rope::branch(Rc::new([new_child, b.children[1].clone()])));
+ }
+ Insert::Node(Rope::branch(Rc::new([
+ new_child,
+ b.children[1].clone(),
+ b.children[2].clone(),
+ ])))
}
Insert::Split(child1, child2) => {
if b.children.len() == 2 {
- return Insert::Node(Rope::branch(&[child1, child2, b.children[1].clone()]));
+ return Insert::Node(Rope::branch(Rc::new([
+ child1,
+ child2,
+ b.children[1].clone(),
+ ])));
}
Insert::Split(
- Rope::branch(&[child1, child2]),
- Rope::branch(&[b.children[1].clone(), b.children[2].clone()]),
+ Rope::branch(Rc::new([child1, child2])),
+ Rope::branch(Rc::new([b.children[1].clone(), b.children[2].clone()])),
)
}
}
@@ -184,24 +209,29 @@ impl Rope {
}
match self.concat_height(self.height(), other, other.height()) {
Insert::Node(r) => r,
- Insert::Split(l, r) => Rope::branch(&[l, r]),
+ Insert::Split(l, r) => Rope::branch(Rc::new([l, r])),
}
}
pub fn read(r: &mut dyn Read) -> Result<Rope, std::io::Error> {
- let mut buf = vec![0; MAX_NODE_SIZE];
- let mut rope = Rope::leaf(&[]);
+ let mut rope = Rope::empty();
loop {
- let n = r.read(&mut buf)?;
+ let mut buf = Rc::new([0; MAX_NODE_SIZE]);
+ let buf_m = Rc::get_mut(&mut buf)
+ .expect("buf was just created, so there should be no other references");
+ let n = r.read(buf_m)?;
if n == 0 {
break;
}
- rope = rope.concat(&Rope::leaf(&buf[..n]));
+ rope = rope.concat(&Rope::from_slice(buf, 0, n));
}
Ok(rope)
}
pub fn new(buf: &[u8]) -> Rope {
+ if buf.len() <= MAX_NODE_SIZE {
+ return Rope::leaf(Rc::from(buf));
+ }
let mut buf = buf;
Rope::read(&mut buf).expect("reading from a slice should never fail")
}
@@ -333,7 +363,7 @@ impl Rope {
}))
}
Rope(Node::Branch(b)) => {
- let mut s = Rope::new(&[]);
+ let mut s = Rope::empty();
let mut start = start;
let mut end = end;
for c in b.children.iter() {
generated by cgit v1.3.1 (git 2.54.0) at 2026-09-04 13:26:23 +0000