diff options
| -rw-r--r-- | ripple/fossil/src/bin/mount.rs | 104 |
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(); } } } |