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