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 @@ -148,16 +148,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 + Send>, + growable: Vec, + root: Block, } impl Index 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] + } } } @@ -179,8 +194,24 @@ } impl NodeTree { + /// 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 + 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.readonly.len() + self.growable.len() + 1 } /// Main working method for `NodeTree` searches @@ -191,11 +222,7 @@ &self, prefix: NodePrefixRef<'p>, ) -> Result, NodeMapError> { - let len = self.len(); - if len == 0 { - return Ok(None); - } - let mut visit = len - 1; + let mut visit = self.len() - 1; for i in 0..prefix.len() { let nybble = prefix.get_nybble(i); match self[visit].read(nybble) { @@ -210,16 +237,18 @@ impl From> for NodeTree { fn from(vec: Vec) -> 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 + ) } } @@ -320,7 +349,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)]", ); } @@ -351,4 +382,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(()) + } }