D7794: rust-nodemap: generic NodeTreeVisitor
gracinet (Georges Racinet)
phabricator at mercurial-scm.org
Mon Jan 6 19:26:13 UTC 2020
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.
REVISION SUMMARY
This iterator will help avoid code duplication when we'll
implement `insert()`, in which we will need to
traverse the node tree, and to remember the visited blocks.
The iterator converts the three variants of `Element` into the
boolean `leaf` and `Option<Revision>` instead of just emitting the
variant it's seen. The motivation is to avoid a dead match arm
in the future `insert()`.
REPOSITORY
rHG Mercurial
BRANCH
default
REVISION DETAIL
https://phab.mercurial-scm.org/D7794
AFFECTED FILES
rust/hg-core/src/revlog/nodemap.rs
CHANGE DETAILS
diff --git a/rust/hg-core/src/revlog/nodemap.rs b/rust/hg-core/src/revlog/nodemap.rs
--- a/rust/hg-core/src/revlog/nodemap.rs
+++ b/rust/hg-core/src/revlog/nodemap.rs
@@ -222,17 +222,58 @@
&self,
prefix: NodePrefixRef<'p>,
) -> Result<Option<Revision>, NodeMapError> {
- let mut visit = self.len() - 1;
- for i in 0..prefix.len() {
- let nybble = prefix.get_nybble(i);
- match self[visit].read(nybble) {
- Element::None => return Ok(None),
- Element::Rev(r) => return Ok(Some(r)),
- Element::Block(idx) => visit = idx,
+ for (leaf, _, _, opt) in self.visit(prefix) {
+ if leaf {
+ return Ok(opt);
}
}
Err(NodeMapError::MultipleResults)
}
+
+ fn visit<'n, 'p>(
+ &'n self,
+ prefix: NodePrefixRef<'p>,
+ ) -> NodeTreeVisitor<'n, 'p> {
+ NodeTreeVisitor {
+ nt: self,
+ prefix: prefix,
+ visit: self.len() - 1,
+ nybble_idx: 0,
+ done: false,
+ }
+ }
+}
+
+struct NodeTreeVisitor<'n, 'p> {
+ nt: &'n NodeTree,
+ prefix: NodePrefixRef<'p>,
+ visit: usize,
+ nybble_idx: usize,
+ done: bool,
+}
+
+impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
+ type Item = (bool, usize, u8, Option<Revision>);
+
+ fn next(&mut self) -> Option<Self::Item> {
+ if self.done || self.nybble_idx >= self.prefix.len() {
+ return None;
+ }
+
+ let nybble = self.prefix.get_nybble(self.nybble_idx);
+ let visit = self.visit;
+ let (leaf, opt) = match self.nt[visit].read(nybble) {
+ Element::None => (true, None),
+ Element::Rev(r) => (true, Some(r)),
+ Element::Block(idx) => {
+ self.visit = idx;
+ (false, None)
+ }
+ };
+ self.nybble_idx += 1;
+ self.done = leaf;
+ Some((leaf, visit, nybble, opt))
+ }
}
impl From<Vec<Block>> for NodeTree {
To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
More information about the Mercurial-devel
mailing list