mercurial-scm/hg: rust/hg-core/src/revlog/nodemap.rs annotate

annotate rust/hg-core/src/revlog/nodemap.rs @ 44385:a98ba6983a63

rust-nodemap: input/output primitives These allow to initiate a `NodeTree` from an immutable opaque sequence of bytes, which could be passed over from Python (extracted from a `PyBuffer`) or directly mmapped from a file. Conversely, we can consume a `NodeTree`, extracting the bytes that express what has been added to the immutable part, together with the original immutable part. This gives callers the choice to start a new Nodetree. After writing to disk, some would prefer to reread for best guarantees (very cheap if mmapping), some others will find it more convenient to grow the memory that was considered immutable in the `NodeTree` and continue from there. This is enough to build examples running on real data and start gathering performance hints. Differential Revision: https://phab.mercurial-scm.org/D7796

author	Georges Racinet <georges.racinet@octobus.net>
date	Tue, 18 Feb 2020 19:11:15 +0100
parents	d2da8667125b
children	00d251d32007

rev	line source
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	1 // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net>
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	2 // and Mercurial contributors
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	3 //
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	4 // This software may be used and distributed according to the terms of the
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	5 // GNU General Public License version 2 or any later version.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	6 //! Indexing facilities for fast retrieval of `Revision` from `Node`
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	7 //!
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	8 //! This provides a variation on the 16-ary radix tree that is
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	9 //! provided as "nodetree" in revlog.c, ready for append-only persistence
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	10 //! on disk.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	11 //!
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	12 //! Following existing implicit conventions, the "nodemap" terminology
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	13 //! is used in a more abstract context.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	14
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	15 use super::{
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	16 Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	17 };
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	18
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	19 use std::fmt;
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	20 use std::mem;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	21 use std::ops::Deref;
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	22 use std::ops::Index;
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	23 use std::slice;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	24
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	25 #[derive(Debug, PartialEq)]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	26 pub enum NodeMapError {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	27 MultipleResults,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	28 InvalidNodePrefix(NodeError),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	29 /// A `Revision` stored in the nodemap could not be found in the index
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	30 RevisionNotInIndex(Revision),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	31 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	32
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	33 impl From<NodeError> for NodeMapError {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	34 fn from(err: NodeError) -> Self {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	35 NodeMapError::InvalidNodePrefix(err)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	36 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	37 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	38
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	39 /// Mapping system from Mercurial nodes to revision numbers.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	40 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	41 /// ## `RevlogIndex` and `NodeMap`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	42 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	43 /// One way to think about their relationship is that
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	44 /// the `NodeMap` is a prefix-oriented reverse index of the `Node` information
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	45 /// carried by a [`RevlogIndex`].
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	46 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	47 /// Many of the methods in this trait take a `RevlogIndex` argument
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	48 /// which is used for validation of their results. This index must naturally
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	49 /// be the one the `NodeMap` is about, and it must be consistent.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	50 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	51 /// Notably, the `NodeMap` must not store
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	52 /// information about more `Revision` values than there are in the index.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	53 /// In these methods, an encountered `Revision` is not in the index, a
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	54 /// [`RevisionNotInIndex`] error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	55 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	56 /// In insert operations, the rule is thus that the `NodeMap` must always
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	57 /// be updated after the `RevlogIndex`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	58 /// be updated first, and the `NodeMap` second.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	59 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	60 /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	61 /// [`RevlogIndex`]: ../trait.RevlogIndex.html
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	62 pub trait NodeMap {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	63 /// Find the unique `Revision` having the given `Node`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	64 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	65 /// If no Revision matches the given `Node`, `Ok(None)` is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	66 fn find_node(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	67 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	68 index: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	69 node: &Node,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	70 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	71 self.find_bin(index, node.into())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	72 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	73
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	74 /// Find the unique Revision whose `Node` starts with a given binary prefix
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	75 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	76 /// If no Revision matches the given prefix, `Ok(None)` is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	77 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	78 /// If several Revisions match the given prefix, a [`MultipleResults`]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	79 /// error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	80 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	81 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	82 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	83 prefix: NodePrefixRef<'a>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	84 ) -> Result<Option<Revision>, NodeMapError>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	85
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	86 /// Find the unique Revision whose `Node` hexadecimal string representation
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	87 /// starts with a given prefix
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	88 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	89 /// If no Revision matches the given prefix, `Ok(None)` is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	90 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	91 /// If several Revisions match the given prefix, a [`MultipleResults`]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	92 /// error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	93 fn find_hex(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	94 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	95 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	96 prefix: &str,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	97 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	98 self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	99 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	100 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	101
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	102 pub trait MutableNodeMap: NodeMap {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	103 fn insert<I: RevlogIndex>(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	104 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	105 index: &I,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	106 node: &Node,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	107 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	108 ) -> Result<(), NodeMapError>;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	109 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	110
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	111 /// Low level NodeTree [`Blocks`] elements
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	112 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	113 /// These are exactly as for instance on persistent storage.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	114 type RawElement = i32;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	115
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	116 /// High level representation of values in NodeTree
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	117 /// [`Blocks`](struct.Block.html)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	118 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	119 /// This is the high level representation that most algorithms should
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	120 /// use.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	121 #[derive(Clone, Debug, Eq, PartialEq)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	122 enum Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	123 Rev(Revision),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	124 Block(usize),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	125 None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	126 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	127
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	128 impl From<RawElement> for Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	129 /// Conversion from low level representation, after endianness conversion.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	130 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	131 /// See [`Block`](struct.Block.html) for explanation about the encoding.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	132 fn from(raw: RawElement) -> Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	133 if raw >= 0 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	134 Element::Block(raw as usize)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	135 } else if raw == -1 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	136 Element::None
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	137 } else {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	138 Element::Rev(-raw - 2)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	139 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	140 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	141 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	142
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	143 impl From<Element> for RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	144 fn from(element: Element) -> RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	145 match element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	146 Element::None => 0,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	147 Element::Block(i) => i as RawElement,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	148 Element::Rev(rev) => -rev - 2,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	149 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	150 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	151 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	152
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	153 /// A logical block of the `NodeTree`, packed with a fixed size.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	154 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	155 /// These are always used in container types implementing `Index<Block>`,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	156 /// such as `&Block`
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	157 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	158 /// As an array of integers, its ith element encodes that the
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	159 /// ith potential edge from the block, representing the ith hexadecimal digit
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	160 /// (nybble) `i` is either:
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	161 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	162 /// - absent (value -1)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	163 /// - another `Block` in the same indexable container (value ≥ 0)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	164 /// - a `Revision` leaf (value ≤ -2)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	165 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	166 /// Endianness has to be fixed for consistency on shared storage across
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	167 /// different architectures.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	168 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	169 /// A key difference with the C `nodetree` is that we need to be
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	170 /// able to represent the [`Block`] at index 0, hence -1 is the empty marker
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	171 /// rather than 0 and the `Revision` range upper limit of -2 instead of -1.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	172 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	173 /// Another related difference is that `NULL_REVISION` (-1) is not
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	174 /// represented at all, because we want an immutable empty nodetree
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	175 /// to be valid.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	176
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	177 #[derive(Copy, Clone)]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	178 pub struct Block([u8; BLOCK_SIZE]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	179
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	180 /// Not derivable for arrays of length >32 until const generics are stable
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	181 impl PartialEq for Block {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	182 fn eq(&self, other: &Self) -> bool {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	183 &self.0[..] == &other.0[..]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	184 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	185 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	186
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	187 pub const BLOCK_SIZE: usize = 64;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	188
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	189 impl Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	190 fn new() -> Self {
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	191 // -1 in 2's complement to create an absent node
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	192 let byte: u8 = 255;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	193 Block([byte; BLOCK_SIZE])
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	194 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	195
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	196 fn get(&self, nybble: u8) -> Element {
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	197 let index = nybble as usize * mem::size_of::<RawElement>();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	198 Element::from(RawElement::from_be_bytes([
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	199 self.0[index],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	200 self.0[index + 1],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	201 self.0[index + 2],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	202 self.0[index + 3],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	203 ]))
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	204 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	205
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	206 fn set(&mut self, nybble: u8, element: Element) {
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	207 let values = RawElement::to_be_bytes(element.into());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	208 let index = nybble as usize * mem::size_of::<RawElement>();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	209 self.0[index] = values[0];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	210 self.0[index + 1] = values[1];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	211 self.0[index + 2] = values[2];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	212 self.0[index + 3] = values[3];
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	213 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	214 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	215
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	216 impl fmt::Debug for Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	217 /// sparse representation for testing and debugging purposes
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	218 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	219 f.debug_map()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	220 .entries((0..16).filter_map(\|i\| match self.get(i) {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	221 Element::None => None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	222 element => Some((i, element)),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	223 }))
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	224 .finish()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	225 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	226 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	227
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	228 /// A mutable 16-radix tree with the root block logically at the end
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	229 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	230 /// Because of the append only nature of our node trees, we need to
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	231 /// keep the original untouched and store new blocks separately.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	232 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	233 /// The mutable root `Block` is kept apart so that we don't have to rebump
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	234 /// it on each insertion.
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	235 pub struct NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	236 readonly: Box<dyn Deref<Target = [Block]> + Send>,
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	237 growable: Vec<Block>,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	238 root: Block,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	239 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	240
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	241 impl Index<usize> for NodeTree {
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	242 type Output = Block;
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	243
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	244 fn index(&self, i: usize) -> &Block {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	245 let ro_len = self.readonly.len();
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	246 if i < ro_len {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	247 &self.readonly[i]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	248 } else if i == ro_len + self.growable.len() {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	249 &self.root
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	250 } else {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	251 &self.growable[i - ro_len]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	252 }
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	253 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	254 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	255
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	256 /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	257 fn has_prefix_or_none(
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	258 idx: &impl RevlogIndex,
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	259 prefix: NodePrefixRef,
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	260 rev: Revision,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	261 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	262 idx.node(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	263 .ok_or_else(\|\| NodeMapError::RevisionNotInIndex(rev))
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	264 .map(\|node\| {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	265 if prefix.is_prefix_of(node) {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	266 Some(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	267 } else {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	268 None
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	269 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	270 })
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	271 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	272
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	273 impl NodeTree {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	274 /// Initiate a NodeTree from an immutable slice-like of `Block`
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	275 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	276 /// We keep `readonly` and clone its root block if it isn't empty.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	277 fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	278 let root = readonly
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	279 .last()
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	280 .map(\|b\| b.clone())
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	281 .unwrap_or_else(\|\| Block::new());
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	282 NodeTree {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	283 readonly: readonly,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	284 growable: Vec::new(),
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	285 root: root,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	286 }
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	287 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	288
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	289 /// Create from an opaque bunch of bytes
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	290 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	291 /// The created `NodeTreeBytes` from `buffer`,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	292 /// of which exactly `amount` bytes are used.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	293 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	294 /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	295 /// - `offset` allows for the final file format to include fixed data
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	296 /// (generation number, behavioural flags)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	297 /// - `amount` is expressed in bytes, and is not automatically derived from
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	298 /// `bytes`, so that a caller that manages them atomically can perform
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	299 /// temporary disk serializations and still rollback easily if needed.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	300 /// First use-case for this would be to support Mercurial shell hooks.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	301 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	302 /// panics if `buffer` is smaller than `amount`
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	303 pub fn load_bytes(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	304 bytes: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	305 amount: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	306 ) -> Self {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	307 NodeTree::new(Box::new(NodeTreeBytes::new(bytes, amount)))
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	308 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	309
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	310 /// Retrieve added `Block` and the original immutable data
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	311 pub fn into_readonly_and_added(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	312 self,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	313 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<Block>) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	314 let mut vec = self.growable;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	315 let readonly = self.readonly;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	316 if readonly.last() != Some(&self.root) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	317 vec.push(self.root);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	318 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	319 (readonly, vec)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	320 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	321
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	322 /// Retrieve added `Blocks` as bytes, ready to be written to persistent
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	323 /// storage
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	324 pub fn into_readonly_and_added_bytes(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	325 self,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	326 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<u8>) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	327 let (readonly, vec) = self.into_readonly_and_added();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	328 // Prevent running `v`'s destructor so we are in complete control
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	329 // of the allocation.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	330 let vec = mem::ManuallyDrop::new(vec);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	331
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	332 // Transmute the `Vec<Block>` to a `Vec<u8>`. Blocks are contiguous
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	333 // bytes, so this is perfectly safe.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	334 let bytes = unsafe {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	335 // Assert that `Block` hasn't been changed and has no padding
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	336 let _: [u8; 4 * BLOCK_SIZE] =
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	337 std::mem::transmute([Block::new(); 4]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	338
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	339 // /!\ Any use of `vec` after this is use-after-free.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	340 // TODO: use `into_raw_parts` once stabilized
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	341 Vec::from_raw_parts(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	342 vec.as_ptr() as *mut u8,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	343 vec.len() * BLOCK_SIZE,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	344 vec.capacity() * BLOCK_SIZE,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	345 )
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	346 };
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	347 (readonly, bytes)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	348 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	349
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	350 /// Total number of blocks
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	351 fn len(&self) -> usize {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	352 self.readonly.len() + self.growable.len() + 1
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	353 }
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	354
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	355 /// Implemented for completeness
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	356 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	357 /// A `NodeTree` always has at least the mutable root block.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	358 #[allow(dead_code)]
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	359 fn is_empty(&self) -> bool {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	360 false
44184 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	361 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44183 diff changeset	362
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	363 /// Main working method for `NodeTree` searches
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	364 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	365 /// This partial implementation lacks special cases for NULL_REVISION
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	366 fn lookup<'p>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	367 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	368 prefix: NodePrefixRef<'p>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	369 ) -> Result<Option<Revision>, NodeMapError> {
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	370 for visit_item in self.visit(prefix) {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	371 if let Some(opt) = visit_item.final_revision() {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	372 return Ok(opt);
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	373 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	374 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	375 Err(NodeMapError::MultipleResults)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	376 }
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	377
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	378 fn visit<'n, 'p>(
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	379 &'n self,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	380 prefix: NodePrefixRef<'p>,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	381 ) -> NodeTreeVisitor<'n, 'p> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	382 NodeTreeVisitor {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	383 nt: self,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	384 prefix: prefix,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	385 visit: self.len() - 1,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	386 nybble_idx: 0,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	387 done: false,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	388 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	389 }
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	390 /// Return a mutable reference for `Block` at index `idx`.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	391 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	392 /// If `idx` lies in the immutable area, then the reference is to
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	393 /// a newly appended copy.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	394 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	395 /// Returns (new_idx, glen, mut_ref) where
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	396 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	397 /// - `new_idx` is the index of the mutable `Block`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	398 /// - `mut_ref` is a mutable reference to the mutable Block.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	399 /// - `glen` is the new length of `self.growable`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	400 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	401 /// Note: the caller wouldn't be allowed to query `self.growable.len()`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	402 /// itself because of the mutable borrow taken with the returned `Block`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	403 fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	404 let ro_blocks = &self.readonly;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	405 let ro_len = ro_blocks.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	406 let glen = self.growable.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	407 if idx < ro_len {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	408 // TODO OPTIM I think this makes two copies
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	409 self.growable.push(ro_blocks[idx].clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	410 (glen + ro_len, &mut self.growable[glen], glen + 1)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	411 } else if glen + ro_len == idx {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	412 (idx, &mut self.root, glen)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	413 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	414 (idx, &mut self.growable[idx - ro_len], glen)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	415 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	416 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	417
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	418 /// Main insertion method
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	419 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	420 /// This will dive in the node tree to find the deepest `Block` for
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	421 /// `node`, split it as much as needed and record `node` in there.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	422 /// The method then backtracks, updating references in all the visited
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	423 /// blocks from the root.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	424 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	425 /// All the mutated `Block` are copied first to the growable part if
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	426 /// needed. That happens for those in the immutable part except the root.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	427 pub fn insert<I: RevlogIndex>(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	428 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	429 index: &I,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	430 node: &Node,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	431 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	432 ) -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	433 let ro_len = &self.readonly.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	434
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	435 let mut visit_steps: Vec<_> = self.visit(node.into()).collect();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	436 let read_nybbles = visit_steps.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	437 // visit_steps cannot be empty, since we always visit the root block
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	438 let deepest = visit_steps.pop().unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	439
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	440 let (mut block_idx, mut block, mut glen) =
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	441 self.mutable_block(deepest.block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	442
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	443 if let Element::Rev(old_rev) = deepest.element {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	444 let old_node = index
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	445 .node(old_rev)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	446 .ok_or_else(\|\| NodeMapError::RevisionNotInIndex(old_rev))?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	447 if old_node == node {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	448 return Ok(()); // avoid creating lots of useless blocks
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	449 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	450
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	451 // Looping over the tail of nybbles in both nodes, creating
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	452 // new blocks until we find the difference
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	453 let mut new_block_idx = ro_len + glen;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	454 let mut nybble = deepest.nybble;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	455 for nybble_pos in read_nybbles..node.nybbles_len() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	456 block.set(nybble, Element::Block(new_block_idx));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	457
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	458 let new_nybble = node.get_nybble(nybble_pos);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	459 let old_nybble = old_node.get_nybble(nybble_pos);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	460
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	461 if old_nybble == new_nybble {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	462 self.growable.push(Block::new());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	463 block = &mut self.growable[glen];
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	464 glen += 1;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	465 new_block_idx += 1;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	466 nybble = new_nybble;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	467 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	468 let mut new_block = Block::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	469 new_block.set(old_nybble, Element::Rev(old_rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	470 new_block.set(new_nybble, Element::Rev(rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	471 self.growable.push(new_block);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	472 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	473 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	474 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	475 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	476 // Free slot in the deepest block: no splitting has to be done
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	477 block.set(deepest.nybble, Element::Rev(rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	478 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	479
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	480 // Backtrack over visit steps to update references
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	481 while let Some(visited) = visit_steps.pop() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	482 let to_write = Element::Block(block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	483 if visit_steps.is_empty() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	484 self.root.set(visited.nybble, to_write);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	485 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	486 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	487 let (new_idx, block, _) = self.mutable_block(visited.block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	488 if block.get(visited.nybble) == to_write {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	489 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	490 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	491 block.set(visited.nybble, to_write);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	492 block_idx = new_idx;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	493 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	494 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	495 }
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	496 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	497
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	498 pub struct NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	499 buffer: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	500 len_in_blocks: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	501 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	502
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	503 impl NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	504 fn new(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	505 buffer: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	506 amount: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	507 ) -> Self {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	508 assert!(buffer.len() >= amount);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	509 let len_in_blocks = amount / BLOCK_SIZE;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	510 NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	511 buffer,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	512 len_in_blocks,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	513 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	514 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	515 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	516
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	517 impl Deref for NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	518 type Target = [Block];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	519
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	520 fn deref(&self) -> &[Block] {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	521 unsafe {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	522 slice::from_raw_parts(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	523 (&self.buffer).as_ptr() as *const Block,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	524 self.len_in_blocks,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	525 )
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	526 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	527 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	528 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	529
44186 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	530 struct NodeTreeVisitor<'n, 'p> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	531 nt: &'n NodeTree,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	532 prefix: NodePrefixRef<'p>,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	533 visit: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	534 nybble_idx: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	535 done: bool,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	536 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	537
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	538 #[derive(Debug, PartialEq, Clone)]
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	539 struct NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	540 block_idx: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	541 nybble: u8,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	542 element: Element,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	543 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	544
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	545 impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	546 type Item = NodeTreeVisitItem;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	547
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	548 fn next(&mut self) -> Option<Self::Item> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	549 if self.done \|\| self.nybble_idx >= self.prefix.len() {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	550 return None;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	551 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	552
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	553 let nybble = self.prefix.get_nybble(self.nybble_idx);
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	554 self.nybble_idx += 1;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	555
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	556 let visit = self.visit;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	557 let element = self.nt[visit].get(nybble);
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	558 if let Element::Block(idx) = element {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	559 self.visit = idx;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	560 } else {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	561 self.done = true;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	562 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	563
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	564 Some(NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	565 block_idx: visit,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	566 nybble: nybble,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	567 element: element,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	568 })
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	569 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	570 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	571
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	572 impl NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	573 // Return `Some(opt)` if this item is final, with `opt` being the
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	574 // `Revision` that it may represent.
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	575 //
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	576 // If the item is not terminal, return `None`
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	577 fn final_revision(&self) -> Option<Option<Revision>> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	578 match self.element {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	579 Element::Block(_) => None,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	580 Element::Rev(r) => Some(Some(r)),
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	581 Element::None => Some(None),
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	582 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44185 diff changeset	583 }
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	584 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	585
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	586 impl From<Vec<Block>> for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	587 fn from(vec: Vec<Block>) -> Self {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	588 Self::new(Box::new(vec))
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	589 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	590 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	591
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	592 impl fmt::Debug for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	593 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	594 let readonly: &[Block] = &*self.readonly;
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	595 write!(
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	596 f,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	597 "readonly: {:?}, growable: {:?}, root: {:?}",
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	598 readonly, self.growable, self.root
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	599 )
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	600 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	601 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	602
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	603 impl Default for NodeTree {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	604 /// Create a fully mutable empty NodeTree
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	605 fn default() -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	606 NodeTree::new(Box::new(Vec::new()))
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	607 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	608 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	609
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	610 impl NodeMap for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	611 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	612 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	613 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	614 prefix: NodePrefixRef<'a>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	615 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	616 self.lookup(prefix.clone()).and_then(\|opt\| {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	617 opt.map_or(Ok(None), \|rev\| has_prefix_or_none(idx, prefix, rev))
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	618 })
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	619 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	620 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	621
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	622 #[cfg(test)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	623 mod tests {
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	624 use super::NodeMapError::*;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	625 use super::*;
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	626 use crate::revlog::node::{hex_pad_right, Node};
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	627 use std::collections::HashMap;
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	628
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	629 /// Creates a `Block` using a syntax close to the `Debug` output
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	630 macro_rules! block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	631 {$($nybble:tt : $variant:ident($val:tt)),*} => (
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	632 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	633 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	634 $(block.set($nybble, Element::$variant($val)));*;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	635 block
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	636 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	637 )
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	638 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	639
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	640 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	641 fn test_block_debug() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	642 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	643 block.set(1, Element::Rev(3));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	644 block.set(10, Element::Block(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	645 assert_eq!(format!("{:?}", block), "{1: Rev(3), 10: Block(0)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	646 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	647
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	648 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	649 fn test_block_macro() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	650 let block = block! {5: Block(2)};
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	651 assert_eq!(format!("{:?}", block), "{5: Block(2)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	652
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	653 let block = block! {13: Rev(15), 5: Block(2)};
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	654 assert_eq!(format!("{:?}", block), "{5: Block(2), 13: Rev(15)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	655 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	656
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	657 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	658 fn test_raw_block() {
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	659 let mut raw = [255u8; 64];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	660
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	661 let mut counter = 0;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	662 for val in [0, 15, -2, -1, -3].iter() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	663 for byte in RawElement::to_be_bytes(*val).iter() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	664 raw[counter] = *byte;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	665 counter += 1;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	666 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	667 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	668 let block = Block(raw);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	669 assert_eq!(block.get(0), Element::Block(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	670 assert_eq!(block.get(1), Element::Block(15));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	671 assert_eq!(block.get(3), Element::None);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	672 assert_eq!(block.get(2), Element::Rev(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	673 assert_eq!(block.get(4), Element::Rev(1));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	674 }
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	675
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	676 type TestIndex = HashMap<Revision, Node>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	677
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	678 impl RevlogIndex for TestIndex {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	679 fn node(&self, rev: Revision) -> Option<&Node> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	680 self.get(&rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	681 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	682
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	683 fn len(&self) -> usize {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	684 self.len()
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	685 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	686 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	687
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	688 /// Pad hexadecimal Node prefix with zeros on the right
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	689 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	690 /// This avoids having to repeatedly write very long hexadecimal
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	691 /// strings for test data, and brings actual hash size independency.
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	692 #[cfg(test)]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	693 fn pad_node(hex: &str) -> Node {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	694 Node::from_hex(&hex_pad_right(hex)).unwrap()
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	695 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	696
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	697 /// Pad hexadecimal Node prefix with zeros on the right, then insert
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	698 fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	699 idx.insert(rev, pad_node(hex));
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	700 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	701
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	702 fn sample_nodetree() -> NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	703 NodeTree::from(vec![
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	704 block![0: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	705 block![0: Rev(0), 1: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	706 block![0: Block(1), 1:Rev(1)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	707 ])
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	708 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	709
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	710 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	711 fn test_nt_debug() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	712 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	713 assert_eq!(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	714 format!("{:?}", nt),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	715 "readonly: \
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	716 [{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}], \
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	717 growable: [], \
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	718 root: {0: Block(1), 1: Rev(1)}",
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	719 );
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	720 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	721
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	722 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	723 fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	724 let mut idx: TestIndex = HashMap::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	725 pad_insert(&mut idx, 1, "1234deadcafe");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	726
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	727 let nt = NodeTree::from(vec![block! {1: Rev(1)}]);
44183 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	728 assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	729 assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	730 assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	731 assert_eq!(nt.find_hex(&idx, "1a")?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	732 assert_eq!(nt.find_hex(&idx, "ab")?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	733
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	734 // and with full binary Nodes
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	735 assert_eq!(nt.find_node(&idx, idx.get(&1).unwrap())?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	736 let unknown = Node::from_hex(&hex_pad_right("3d")).unwrap();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	737 assert_eq!(nt.find_node(&idx, &unknown)?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	738 Ok(())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	739 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	740
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	741 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	742 fn test_immutable_find_one_jump() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	743 let mut idx = TestIndex::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	744 pad_insert(&mut idx, 9, "012");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	745 pad_insert(&mut idx, 0, "00a");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	746
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	747 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	748
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	749 assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	750 assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	751 assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0)));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	752 assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44142 diff changeset	753 }
44185 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	754
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	755 #[test]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	756 fn test_mutated_find() -> Result<(), NodeMapError> {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	757 let mut idx = TestIndex::new();
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	758 pad_insert(&mut idx, 9, "012");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	759 pad_insert(&mut idx, 0, "00a");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	760 pad_insert(&mut idx, 2, "cafe");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	761 pad_insert(&mut idx, 3, "15");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	762 pad_insert(&mut idx, 1, "10");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	763
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	764 let nt = NodeTree {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	765 readonly: sample_nodetree().readonly,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	766 growable: vec![block![0: Rev(1), 5: Rev(3)]],
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	767 root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	768 };
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	769 assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	770 assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	771 assert_eq!(nt.find_hex(&idx, "00")?, Some(0));
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	772 assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	773 Ok(())
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44184 diff changeset	774 }
44356 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	775
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	776 struct TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	777 index: TestIndex,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	778 nt: NodeTree,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	779 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	780
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	781 impl TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	782 fn new() -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	783 TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	784 index: HashMap::new(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	785 nt: NodeTree::default(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	786 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	787 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	788
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	789 fn insert(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	790 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	791 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	792 hex: &str,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	793 ) -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	794 let node = pad_node(hex);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	795 self.index.insert(rev, node.clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	796 self.nt.insert(&self.index, &node, rev)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	797 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	798 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	799
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	800 fn find_hex(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	801 &self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	802 prefix: &str,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	803 ) -> Result<Option<Revision>, NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	804 self.nt.find_hex(&self.index, prefix)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	805 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	806
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	807 /// Drain `added` and restart a new one
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	808 fn commit(self) -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	809 let mut as_vec: Vec<Block> =
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	810 self.nt.readonly.iter().map(\|block\| block.clone()).collect();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	811 as_vec.extend(self.nt.growable);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	812 as_vec.push(self.nt.root);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	813
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	814 Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	815 index: self.index,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	816 nt: NodeTree::from(as_vec).into(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	817 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	818 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	819 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	820
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	821 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	822 fn test_insert_full_mutable() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	823 let mut idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	824 idx.insert(0, "1234")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	825 assert_eq!(idx.find_hex("1")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	826 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	827
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	828 // let's trigger a simple split
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	829 idx.insert(1, "1a34")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	830 assert_eq!(idx.nt.growable.len(), 1);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	831 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	832 assert_eq!(idx.find_hex("1a")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	833
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	834 // reinserting is a no_op
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	835 idx.insert(1, "1a34")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	836 assert_eq!(idx.nt.growable.len(), 1);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	837 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	838 assert_eq!(idx.find_hex("1a")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	839
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	840 idx.insert(2, "1a01")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	841 assert_eq!(idx.nt.growable.len(), 2);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	842 assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	843 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	844 assert_eq!(idx.find_hex("1a3")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	845 assert_eq!(idx.find_hex("1a0")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	846 assert_eq!(idx.find_hex("1a12")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	847
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	848 // now let's make it split and create more than one additional block
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	849 idx.insert(3, "1a345")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	850 assert_eq!(idx.nt.growable.len(), 4);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	851 assert_eq!(idx.find_hex("1a340")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	852 assert_eq!(idx.find_hex("1a345")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	853 assert_eq!(idx.find_hex("1a341")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	854
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	855 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	856 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	857
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	858 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	859 fn test_insert_extreme_splitting() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	860 // check that the splitting loop is long enough
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	861 let mut nt_idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	862 let nt = &mut nt_idx.nt;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	863 let idx = &mut nt_idx.index;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	864
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	865 let node0_hex = hex_pad_right("444444");
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	866 let mut node1_hex = hex_pad_right("444444").clone();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	867 node1_hex.pop();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	868 node1_hex.push('5');
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	869 let node0 = Node::from_hex(&node0_hex).unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	870 let node1 = Node::from_hex(&node1_hex).unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	871
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	872 idx.insert(0, node0.clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	873 nt.insert(idx, &node0, 0)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	874 idx.insert(1, node1.clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	875 nt.insert(idx, &node1, 1)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	876
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	877 assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	878 assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	879 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	880 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	881
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	882 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	883 fn test_insert_partly_immutable() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	884 let mut idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	885 idx.insert(0, "1234")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	886 idx.insert(1, "1235")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	887 idx.insert(2, "131")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	888 idx.insert(3, "cafe")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	889 let mut idx = idx.commit();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	890 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	891 assert_eq!(idx.find_hex("1235")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	892 assert_eq!(idx.find_hex("131")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	893 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	894
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	895 idx.insert(4, "123A")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	896 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	897 assert_eq!(idx.find_hex("1235")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	898 assert_eq!(idx.find_hex("131")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	899 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	900 assert_eq!(idx.find_hex("123A")?, Some(4));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	901
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	902 idx.insert(5, "c0")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	903 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	904 assert_eq!(idx.find_hex("c0")?, Some(5));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	905 assert_eq!(idx.find_hex("c1")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	906 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	907
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	908 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44186 diff changeset	909 }
44385 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	910
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	911 #[test]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	912 fn test_into_added_empty() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	913 assert!(sample_nodetree().into_readonly_and_added().1.is_empty());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	914 assert!(sample_nodetree()
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	915 .into_readonly_and_added_bytes()
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	916 .1
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	917 .is_empty());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	918 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	919
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	920 #[test]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	921 fn test_into_added_bytes() -> Result<(), NodeMapError> {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	922 let mut idx = TestNtIndex::new();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	923 idx.insert(0, "1234")?;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	924 let mut idx = idx.commit();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	925 idx.insert(4, "cafe")?;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	926 let (_, bytes) = idx.nt.into_readonly_and_added_bytes();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	927
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	928 // only the root block has been changed
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	929 assert_eq!(bytes.len(), BLOCK_SIZE);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	930 // big endian for -2
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	931 assert_eq!(&bytes[4..2 * 4], [255, 255, 255, 254]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	932 // big endian for -6
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	933 assert_eq!(&bytes[12 * 4..13 * 4], [255, 255, 255, 250]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	934 Ok(())
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44356 diff changeset	935 }
44142 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	936 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/revlog/nodemap.rs @ 44385:a98ba6983a63