changeset 44185:a19331456d48

rust-nodemap: mutable NodeTree data structure Thanks to the previously indexing abstraction, the only difference in the lookup algorithm is that we don't need the special case for an empty NodeTree any more. We've considered making the mutable root an `Option<Block>`, but that leads to unpleasant checks and `unwrap()` unless we abstract it as typestate patterns (`NodeTree<Immutable>` and `NodeTree<Mutated>`) which seem exaggerated in that case. The initial copy of the root block is a very minor performance penalty, given that it typically occurs just once per transaction. Differential Revision: https://phab.mercurial-scm.org/D7793
author Georges Racinet <georges.racinet@octobus.net>
date Fri, 27 Dec 2019 15:11:43 +0100
parents 220d4d2e3185
children 796d05f3fa84
files rust/hg-core/src/revlog/nodemap.rs
diffstat 1 files changed, 72 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/rust/hg-core/src/revlog/nodemap.rs	Thu Dec 26 15:47:14 2019 +0100
+++ b/rust/hg-core/src/revlog/nodemap.rs	Fri Dec 27 15:11:43 2019 +0100
@@ -191,16 +191,31 @@
     }
 }
 
-/// A 16-radix tree with the root block at the end
+/// A mutable 16-radix tree with the root block logically at the end
+///
+/// Because of the append only nature of our node trees, we need to
+/// keep the original untouched and store new blocks separately.
+///
+/// The mutable root `Block` is kept apart so that we don't have to rebump
+/// it on each insertion.
 pub struct NodeTree {
     readonly: Box<dyn Deref<Target = [Block]> + Send>,
+    growable: Vec<Block>,
+    root: Block,
 }
 
 impl Index<usize> for NodeTree {
     type Output = Block;
 
     fn index(&self, i: usize) -> &Block {
-        &self.readonly[i]
+        let ro_len = self.readonly.len();
+        if i < ro_len {
+            &self.readonly[i]
+        } else if i == ro_len + self.growable.len() {
+            &self.root
+        } else {
+            &self.growable[i - ro_len]
+        }
     }
 }
 
@@ -222,12 +237,32 @@
 }
 
 impl NodeTree {
-    fn len(&self) -> usize {
-        self.readonly.len()
+    /// Initiate a NodeTree from an immutable slice-like of `Block`
+    ///
+    /// We keep `readonly` and clone its root block if it isn't empty.
+    fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
+        let root = readonly
+            .last()
+            .map(|b| b.clone())
+            .unwrap_or_else(|| Block::new());
+        NodeTree {
+            readonly: readonly,
+            growable: Vec::new(),
+            root: root,
+        }
     }
 
+    /// Total number of blocks
+    fn len(&self) -> usize {
+        self.readonly.len() + self.growable.len() + 1
+    }
+
+    /// Implemented for completeness
+    ///
+    /// A `NodeTree` always has at least the mutable root block.
+    #[allow(dead_code)]
     fn is_empty(&self) -> bool {
-        self.len() == 0
+        false
     }
 
     /// Main working method for `NodeTree` searches
@@ -237,9 +272,6 @@
         &self,
         prefix: NodePrefixRef<'p>,
     ) -> Result<Option<Revision>, NodeMapError> {
-        if self.is_empty() {
-            return Ok(None);
-        }
         let mut visit = self.len() - 1;
         for i in 0..prefix.len() {
             let nybble = prefix.get_nybble(i);
@@ -255,16 +287,18 @@
 
 impl From<Vec<Block>> for NodeTree {
     fn from(vec: Vec<Block>) -> Self {
-        NodeTree {
-            readonly: Box::new(vec),
-        }
+        Self::new(Box::new(vec))
     }
 }
 
 impl fmt::Debug for NodeTree {
     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-        let blocks: &[Block] = &*self.readonly;
-        write!(f, "readonly: {:?}", blocks)
+        let readonly: &[Block] = &*self.readonly;
+        write!(
+            f,
+            "readonly: {:?}, growable: {:?}, root: {:?}",
+            readonly, self.growable, self.root
+        )
     }
 }
 
@@ -365,7 +399,9 @@
         assert_eq!(
             format!("{:?}", nt),
             "readonly: \
-             [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}]"
+             [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \
+             growable: [], \
+             root: {0: Block(1), 1: Rev(1)}",
         );
     }
 
@@ -374,7 +410,7 @@
         let mut idx: TestIndex = HashMap::new();
         pad_insert(&mut idx, 1, "1234deadcafe");
 
-        let nt = NodeTree::from(vec![block![1: Rev(1)]]);
+        let nt = NodeTree::from(vec![block! {1: Rev(1)}]);
         assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
         assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
         assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
@@ -401,4 +437,25 @@
         assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
         assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
     }
+
+    #[test]
+    fn test_mutated_find() -> Result<(), NodeMapError> {
+        let mut idx = TestIndex::new();
+        pad_insert(&mut idx, 9, "012");
+        pad_insert(&mut idx, 0, "00a");
+        pad_insert(&mut idx, 2, "cafe");
+        pad_insert(&mut idx, 3, "15");
+        pad_insert(&mut idx, 1, "10");
+
+        let nt = NodeTree {
+            readonly: sample_nodetree().readonly,
+            growable: vec![block![0: Rev(1), 5: Rev(3)]],
+            root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
+        };
+        assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
+        assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
+        assert_eq!(nt.find_hex(&idx, "00")?, Some(0));
+        assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
+        Ok(())
+    }
 }