1 files 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();
 			}
 		}
 	}