From 9fc107d2540f914b8019876d07f80388f90285c6 Mon Sep 17 00:00:00 2001
From: edef <edef@unfathomable.blue>
Date: Wed, 4 May 2022 00:09:01 +0000
Subject: ripple/fossil/mount: back memtree with a single Vec

A single linear array does everything we need here, since we don't
actually use the cheap writes the BTreeMaps would permit us, and we
save ourselves the hassle of maintaining two parallel lookup structures.

Change-Id: I418b0aaa7a3191fab3195f36f2c68ac0f5f0382b
---
 ripple/fossil/src/bin/mount.rs | 104 ++++++++++++++++++++++-------------------
 1 file changed, 55 insertions(+), 49 deletions(-)

diff --git a/ripple/fossil/src/bin/mount.rs b/ripple/fossil/src/bin/mount.rs
index 9e0e8aa..ee46b8e 100644
--- a/ripple/fossil/src/bin/mount.rs
+++ b/ripple/fossil/src/bin/mount.rs
@@ -204,7 +204,7 @@ impl fuser::Filesystem for Filesystem {
 					None => reply.error(ENOENT),
 					Some(entry) => {
 						let ino = parent + entry.index as u64 + 1;
-						reply.entry(&Duration::ZERO, &file_attr(ino, entry.node), 0);
+						reply.entry(&Duration::ZERO, &file_attr(ino, entry.node()), 0);
 					}
 				}
 			}
@@ -394,12 +394,12 @@ impl fuser::Filesystem for Filesystem {
 				];
 
 				for entry in dir.iter() {
-					let kind = match entry.node {
+					let kind = match entry.node() {
 						memtree::Node::Directory(_) => fuser::FileType::Directory,
 						memtree::Node::File(_) => fuser::FileType::RegularFile,
 						memtree::Node::Link { .. } => fuser::FileType::Symlink,
 					};
-					children.push((ino + entry.index as u64 + 1, kind, entry.name));
+					children.push((ino + entry.index as u64 + 1, kind, &entry.name));
 				}
 
 				for (offset, &(ino, kind, name)) in
@@ -765,39 +765,46 @@ mod memtree {
 
 	#[derive(Default)]
 	pub struct Directory {
-		by_index: BTreeMap<u32, NodeBuf>,
-		by_name: BTreeMap<String, u32>,
+		children: Vec<DirectoryEntry>,
 		size: u32,
 	}
 
-	pub struct DirectoryEntry<'a> {
-		pub name: &'a str,
+	pub struct DirectoryEntry {
+		pub name: String,
 		pub index: u32,
-		pub node: Node<'a>,
+		node: NodeBuf,
+	}
+
+	impl DirectoryEntry {
+		/// Get the directory entry's node.
+		#[must_use]
+		pub fn node(&self) -> Node {
+			self.node.as_ref()
+		}
 	}
 
 	impl Directory {
-		pub fn iter(&self) -> impl Iterator<Item = DirectoryEntry> {
-			let by_name = self.by_name.iter();
-			let by_index = self.by_index.iter();
-
-			by_name.zip(by_index).map(|((name, &idx), (&idy, node))| {
-				assert_eq!(idx, idy);
-				DirectoryEntry {
-					name: &name,
-					index: idx,
-					node: node.as_ref(),
-				}
-			})
+		pub fn iter(&self) -> impl Iterator<Item = &DirectoryEntry> {
+			self.children.iter()
 		}
 
-		pub fn lookup<'a>(&self, name: &'a str) -> Option<DirectoryEntry> {
-			let (name, &index) = self.by_name.get_key_value(name)?;
-			Some(DirectoryEntry {
-				name,
-				index,
-				node: self.by_index[&index].as_ref(),
-			})
+		pub fn lookup<'a>(&self, name: &'a str) -> Option<&DirectoryEntry> {
+			let idx = self
+				.children
+				.binary_search_by_key(&name, |e| &e.name)
+				.ok()?;
+			Some(&self.children[idx])
+		}
+
+		fn by_max_index(&self, max_index: u32) -> Option<&DirectoryEntry> {
+			let pos = match self.children.binary_search_by_key(&max_index, |e| e.index) {
+				// exact match
+				Ok(n) => n,
+				// if the position is 0, then we're *empty*
+				// if the position is n, then the parent node is at n-1
+				Err(n) => n.checked_sub(1)?,
+			};
+			Some(&self.children[pos])
 		}
 
 		/// Get the directory's size.
@@ -821,7 +828,7 @@ mod memtree {
 	impl fmt::Debug for DirectoryMembers<'_> {
 		fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 			f.debug_map()
-				.entries(self.0.iter().map(|e| ((e.name, e.index), e.node)))
+				.entries(self.0.iter().map(|e| ((&e.name, e.index), &e.node)))
 				.finish()
 		}
 	}
@@ -867,28 +874,27 @@ mod memtree {
 
 	impl Directory {
 		fn from_children(children: BTreeMap<String, NodeBuf>) -> Directory {
-			let mut d = Directory::default();
-			for (name, child) in children {
-				let index = d.size;
-				let size = match child {
-					NodeBuf::Directory(Directory { size, .. }) => {
-						size.checked_add(1).expect("overflow")
-					}
-					NodeBuf::File(_) | NodeBuf::Link { .. } => 1,
-				};
+			let mut size: u32 = 0;
+			let children = children
+				.into_iter()
+				.map(|(name, node)| {
+					let index = size;
+					let node_size = match node {
+						NodeBuf::Directory(Directory { size, .. }) => {
+							size.checked_add(1).expect("overflow")
+						}
+						NodeBuf::File(_) | NodeBuf::Link { .. } => 1,
+					};
+					size = size.checked_add(node_size).expect("overflow");
 
-				d.size = index.checked_add(size).expect("overflow");
-				d.by_name.insert(name, index);
-				d.by_index.insert(index, child);
-			}
-			d
+					DirectoryEntry { name, index, node }
+				})
+				.collect();
+			Directory { children, size }
 		}
 
 		pub fn len(&self) -> usize {
-			let len = self.by_index.len();
-			let lem = self.by_name.len();
-			debug_assert_eq!(len, lem);
-			len
+			self.children.len()
 		}
 	}
 
@@ -909,9 +915,9 @@ mod memtree {
 					}
 				};
 
-				let (&child_index, child) = d.by_index.range(..=index).next_back()?;
-				root = child.as_ref();
-				index = index.checked_sub(child_index).unwrap();
+				let child = d.by_max_index(index)?;
+				root = child.node();
+				index = index.checked_sub(child.index).unwrap();
 			}
 		}
 	}
-- 
cgit 1.4.1