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

annotate rust/hg-core/src/revlog/nodemap.rs @ 44420:6329ce04c69f

rust-nodemap: accounting for dead blocks By the very append-only nature of the `NodeTree`, inserting new blocks has the effect of making some of the older ones useless as they become unreachable. Therefore some automatic housekeeping will need to be provided. This is standard procedure in the word of databases, under names such as "repack" or "vacuum". The new `masked_readonly_blocks()` will provide callers with useful information to decide if the nodetree is ripe for repacking, but all the `NodeTree` can provide is how many blocks have been masked in the currently mutable part. Analysing the readonly part would be way too long to do it for each transaction and defeat the whole purpose of nodemap persistence. Serializing callers (from the Python layer) will get this figure before each extraction and maintain an aggregate counter of unreachable blocks separately. Note: at this point, the most efficient repacking is just to restart afresh with a full rescan. Differential Revision: https://phab.mercurial-scm.org/D8097

author	Georges Racinet <georges.racinet@octobus.net>
date	Tue, 18 Feb 2020 19:11:17 +0100
parents	5ac1eecc9c64
children	d518994384a4

rev	line source
44227 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
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	15 use super::{
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	16 node::NULL_NODE, Node, NodeError, NodePrefix, NodePrefixRef, Revision,
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	17 RevlogIndex, NULL_REVISION,
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	18 };
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	19
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	20 use std::cmp::max;
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	21 use std::fmt;
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	22 use std::mem;
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	23 use std::ops::Deref;
44259 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	24 use std::ops::Index;
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	25 use std::slice;
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	26
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	27 #[derive(Debug, PartialEq)]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	28 pub enum NodeMapError {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	29 MultipleResults,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	30 InvalidNodePrefix(NodeError),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	31 /// 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: 44227 diff changeset	32 RevisionNotInIndex(Revision),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	33 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	34
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	35 impl From<NodeError> for NodeMapError {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	36 fn from(err: NodeError) -> Self {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	37 NodeMapError::InvalidNodePrefix(err)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	38 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	39 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	40
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	41 /// Mapping system from Mercurial nodes to revision numbers.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	42 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	43 /// ## `RevlogIndex` and `NodeMap`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	44 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	45 /// One way to think about their relationship is that
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	46 /// 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: 44227 diff changeset	47 /// carried by a [`RevlogIndex`].
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	48 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	49 /// 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: 44227 diff changeset	50 /// 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: 44227 diff changeset	51 /// 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: 44227 diff changeset	52 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	53 /// Notably, the `NodeMap` must not store
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	54 /// 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: 44227 diff changeset	55 /// 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: 44227 diff changeset	56 /// [`RevisionNotInIndex`] error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	57 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	58 /// 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: 44227 diff changeset	59 /// be updated after the `RevlogIndex`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	60 /// be updated first, and the `NodeMap` second.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	61 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	62 /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	63 /// [`RevlogIndex`]: ../trait.RevlogIndex.html
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	64 pub trait NodeMap {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	65 /// Find the unique `Revision` having the given `Node`
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	66 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	67 /// 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: 44227 diff changeset	68 fn find_node(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	69 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	70 index: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	71 node: &Node,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	72 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	73 self.find_bin(index, node.into())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	74 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	75
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	76 /// 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: 44227 diff changeset	77 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	78 /// 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: 44227 diff changeset	79 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	80 /// If several Revisions match the given prefix, a [`MultipleResults`]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	81 /// error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	82 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	83 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	84 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	85 prefix: NodePrefixRef<'a>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	86 ) -> Result<Option<Revision>, NodeMapError>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	87
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	88 /// Find the unique Revision whose `Node` hexadecimal string representation
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	89 /// starts with a given prefix
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	90 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	91 /// 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: 44227 diff changeset	92 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	93 /// If several Revisions match the given prefix, a [`MultipleResults`]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	94 /// error is returned.
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	95 fn find_hex(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	96 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	97 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	98 prefix: &str,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	99 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	100 self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	101 }
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	102
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	103 /// Give the size of the shortest node prefix that determines
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	104 /// the revision uniquely.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	105 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	106 /// From a binary node prefix, if it is matched in the node map, this
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	107 /// returns the number of hexadecimal digits that would had sufficed
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	108 /// to find the revision uniquely.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	109 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	110 /// Returns `None` if no `Revision` could be found for the prefix.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	111 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	112 /// If several Revisions match the given prefix, a [`MultipleResults`]
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	113 /// error is returned.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	114 fn unique_prefix_len_bin<'a>(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	115 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	116 idx: &impl RevlogIndex,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	117 node_prefix: NodePrefixRef<'a>,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	118 ) -> Result<Option<usize>, NodeMapError>;
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	119
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	120 /// Same as `unique_prefix_len_bin`, with the hexadecimal representation
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	121 /// of the prefix as input.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	122 fn unique_prefix_len_hex(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	123 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	124 idx: &impl RevlogIndex,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	125 prefix: &str,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	126 ) -> Result<Option<usize>, NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	127 self.unique_prefix_len_bin(idx, NodePrefix::from_hex(prefix)?.borrow())
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	128 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	129
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	130 /// Same as `unique_prefix_len_bin`, with a full `Node` as input
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	131 fn unique_prefix_len_node(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	132 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	133 idx: &impl RevlogIndex,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	134 node: &Node,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	135 ) -> Result<Option<usize>, NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	136 self.unique_prefix_len_bin(idx, node.into())
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	137 }
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	138 }
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	139
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	140 pub trait MutableNodeMap: NodeMap {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	141 fn insert<I: RevlogIndex>(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	142 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	143 index: &I,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	144 node: &Node,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	145 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	146 ) -> Result<(), NodeMapError>;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	147 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	148
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	149 /// Low level NodeTree [`Blocks`] elements
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 /// 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	152 type RawElement = i32;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	153
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	154 /// High level representation of values in NodeTree
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	155 /// [`Blocks`](struct.Block.html)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	156 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	157 /// 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	158 /// use.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	159 #[derive(Clone, Debug, Eq, PartialEq)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	160 enum Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	161 Rev(Revision),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	162 Block(usize),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	163 None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	164 }
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 impl From<RawElement> for Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	167 /// 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	168 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	169 /// 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	170 fn from(raw: RawElement) -> Element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	171 if raw >= 0 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	172 Element::Block(raw as usize)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	173 } else if raw == -1 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	174 Element::None
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	175 } else {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	176 Element::Rev(-raw - 2)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	177 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	178 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	179 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	180
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	181 impl From<Element> for RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	182 fn from(element: Element) -> RawElement {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	183 match element {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	184 Element::None => 0,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	185 Element::Block(i) => i as RawElement,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	186 Element::Rev(rev) => -rev - 2,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	187 }
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 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	190
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	191 /// 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	192 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	193 /// 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	194 /// such as `&Block`
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 /// 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	197 /// 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	198 /// (nybble) `i` is either:
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	199 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	200 /// - absent (value -1)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	201 /// - 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	202 /// - a `Revision` leaf (value ≤ -2)
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	203 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	204 /// 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	205 /// different architectures.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	206 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	207 /// 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	208 /// 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	209 /// 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	210 ///
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	211 /// 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	212 /// 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	213 /// to be valid.
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	214
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	215 #[derive(Copy, Clone)]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	216 pub struct Block([u8; BLOCK_SIZE]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	217
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	218 /// 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: 44390 diff changeset	219 impl PartialEq for Block {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	220 fn eq(&self, other: &Self) -> bool {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	221 &self.0[..] == &other.0[..]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	222 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	223 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	224
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	225 pub const BLOCK_SIZE: usize = 64;
44227 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 impl Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	228 fn new() -> Self {
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	229 // -1 in 2's complement to create an absent node
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	230 let byte: u8 = 255;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	231 Block([byte; BLOCK_SIZE])
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	232 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	233
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	234 fn get(&self, nybble: u8) -> Element {
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	235 let index = nybble as usize * mem::size_of::<RawElement>();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	236 Element::from(RawElement::from_be_bytes([
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	237 self.0[index],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	238 self.0[index + 1],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	239 self.0[index + 2],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	240 self.0[index + 3],
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	241 ]))
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	242 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	243
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	244 fn set(&mut self, nybble: u8, element: Element) {
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	245 let values = RawElement::to_be_bytes(element.into());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	246 let index = nybble as usize * mem::size_of::<RawElement>();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	247 self.0[index] = values[0];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	248 self.0[index + 1] = values[1];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	249 self.0[index + 2] = values[2];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	250 self.0[index + 3] = values[3];
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	251 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	252 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	253
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	254 impl fmt::Debug for Block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	255 /// sparse representation for testing and debugging purposes
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	256 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	257 f.debug_map()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	258 .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	259 Element::None => None,
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	260 element => Some((i, element)),
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	261 }))
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	262 .finish()
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	263 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	264 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	265
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	266 /// 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: 44259 diff changeset	267 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	268 /// 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: 44259 diff changeset	269 /// keep the original untouched and store new blocks separately.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	270 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	271 /// 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: 44259 diff changeset	272 /// it on each insertion.
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	273 pub struct NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	274 readonly: Box<dyn Deref<Target = [Block]> + Send>,
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	275 growable: Vec<Block>,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	276 root: Block,
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	277 masked_inner_blocks: usize,
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	278 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	279
44259 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	280 impl Index<usize> for NodeTree {
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	281 type Output = Block;
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	282
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	283 fn index(&self, i: usize) -> &Block {
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	284 let ro_len = self.readonly.len();
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	285 if i < ro_len {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	286 &self.readonly[i]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	287 } else if i == ro_len + self.growable.len() {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	288 &self.root
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	289 } else {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	290 &self.growable[i - ro_len]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	291 }
44259 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	292 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	293 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	294
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	295 /// Return `None` unless the `Node` for `rev` has given prefix in `index`.
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	296 fn has_prefix_or_none(
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	297 idx: &impl RevlogIndex,
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	298 prefix: NodePrefixRef,
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	299 rev: Revision,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	300 ) -> Result<Option<Revision>, NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	301 idx.node(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	302 .ok_or_else(\|\| NodeMapError::RevisionNotInIndex(rev))
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	303 .map(\|node\| {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	304 if prefix.is_prefix_of(node) {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	305 Some(rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	306 } else {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	307 None
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	308 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	309 })
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	310 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	311
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	312 /// validate that the candidate's node starts indeed with given prefix,
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	313 /// and treat ambiguities related to `NULL_REVISION`.
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	314 ///
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	315 /// From the data in the NodeTree, one can only conclude that some
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	316 /// revision is the only one for a subprefix of the one being looked up.
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	317 fn validate_candidate(
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	318 idx: &impl RevlogIndex,
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	319 prefix: NodePrefixRef,
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	320 candidate: (Option<Revision>, usize),
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	321 ) -> Result<(Option<Revision>, usize), NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	322 let (rev, steps) = candidate;
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	323 if let Some(nz_nybble) = prefix.first_different_nybble(&NULL_NODE) {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	324 rev.map_or(Ok((None, steps)), \|r\| {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	325 has_prefix_or_none(idx, prefix, r)
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	326 .map(\|opt\| (opt, max(steps, nz_nybble + 1)))
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	327 })
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	328 } else {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	329 // the prefix is only made of zeros; NULL_REVISION always matches it
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	330 // and any other valid result is an ambiguity
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	331 match rev {
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	332 None => Ok((Some(NULL_REVISION), steps + 1)),
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	333 Some(r) => match has_prefix_or_none(idx, prefix, r)? {
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	334 None => Ok((Some(NULL_REVISION), steps + 1)),
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	335 _ => Err(NodeMapError::MultipleResults),
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	336 },
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	337 }
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	338 }
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	339 }
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	340
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	341 impl NodeTree {
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	342 /// Initiate a NodeTree from an immutable slice-like of `Block`
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	343 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	344 /// 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: 44259 diff changeset	345 fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	346 let root = readonly
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	347 .last()
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	348 .map(\|b\| b.clone())
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	349 .unwrap_or_else(\|\| Block::new());
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	350 NodeTree {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	351 readonly: readonly,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	352 growable: Vec::new(),
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	353 root: root,
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	354 masked_inner_blocks: 0,
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	355 }
44259 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	356 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	357
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	358 /// Create from an opaque bunch of bytes
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	359 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	360 /// The created `NodeTreeBytes` from `buffer`,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	361 /// of which exactly `amount` bytes are used.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	362 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	363 /// - `buffer` could be derived from `PyBuffer` and `Mmap` objects.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	364 /// - `offset` allows for the final file format to include fixed data
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	365 /// (generation number, behavioural flags)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	366 /// - `amount` is expressed in bytes, and is not automatically derived from
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	367 /// `bytes`, so that a caller that manages them atomically can perform
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	368 /// temporary disk serializations and still rollback easily if needed.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	369 /// 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: 44390 diff changeset	370 ///
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	371 /// panics if `buffer` is smaller than `amount`
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	372 pub fn load_bytes(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	373 bytes: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	374 amount: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	375 ) -> Self {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	376 NodeTree::new(Box::new(NodeTreeBytes::new(bytes, amount)))
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	377 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	378
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	379 /// Retrieve added `Block` and the original immutable data
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	380 pub fn into_readonly_and_added(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	381 self,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	382 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<Block>) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	383 let mut vec = self.growable;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	384 let readonly = self.readonly;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	385 if readonly.last() != Some(&self.root) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	386 vec.push(self.root);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	387 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	388 (readonly, vec)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	389 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	390
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	391 /// Retrieve added `Blocks` as bytes, ready to be written to persistent
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	392 /// storage
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	393 pub fn into_readonly_and_added_bytes(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	394 self,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	395 ) -> (Box<dyn Deref<Target = [Block]> + Send>, Vec<u8>) {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	396 let (readonly, vec) = self.into_readonly_and_added();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	397 // Prevent running `v`'s destructor so we are in complete control
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	398 // of the allocation.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	399 let vec = mem::ManuallyDrop::new(vec);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	400
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	401 // Transmute the `Vec<Block>` to a `Vec<u8>`. Blocks are contiguous
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	402 // bytes, so this is perfectly safe.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	403 let bytes = unsafe {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	404 // Assert that `Block` hasn't been changed and has no padding
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	405 let _: [u8; 4 * BLOCK_SIZE] =
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	406 std::mem::transmute([Block::new(); 4]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	407
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	408 // /!\ Any use of `vec` after this is use-after-free.
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	409 // TODO: use `into_raw_parts` once stabilized
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	410 Vec::from_raw_parts(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	411 vec.as_ptr() as *mut u8,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	412 vec.len() * BLOCK_SIZE,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	413 vec.capacity() * BLOCK_SIZE,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	414 )
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	415 };
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	416 (readonly, bytes)
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	417 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	418
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	419 /// Total number of blocks
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	420 fn len(&self) -> usize {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	421 self.readonly.len() + self.growable.len() + 1
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	422 }
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	423
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	424 /// Implemented for completeness
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	425 ///
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	426 /// A `NodeTree` always has at least the mutable root block.
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	427 #[allow(dead_code)]
44259 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	428 fn is_empty(&self) -> bool {
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	429 false
44259 220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	430 }
220d4d2e3185 rust-nodemap: abstracting the indexing Georges Racinet <georges.racinet@octobus.net> parents: 44258 diff changeset	431
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	432 /// Main working method for `NodeTree` searches
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	433 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	434 /// The first returned value is the result of analysing `NodeTree` data
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	435 /// alone: whereas `None` guarantees that the given prefix is absent
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	436 /// from the `NodeTree` data (but still could match `NULL_NODE`), with
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	437 /// `Some(rev)`, it is to be understood that `rev` is the unique `Revision`
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	438 /// that could match the prefix. Actually, all that can be inferred from
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	439 /// the `NodeTree` data is that `rev` is the revision with the longest
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	440 /// common node prefix with the given prefix.
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	441 ///
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	442 /// The second returned value is the size of the smallest subprefix
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	443 /// of `prefix` that would give the same result, i.e. not the
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	444 /// `MultipleResults` error variant (again, using only the data of the
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	445 /// `NodeTree`).
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	446 fn lookup(
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	447 &self,
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	448 prefix: NodePrefixRef,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	449 ) -> Result<(Option<Revision>, usize), NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	450 for (i, visit_item) in self.visit(prefix).enumerate() {
44261 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	451 if let Some(opt) = visit_item.final_revision() {
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	452 return Ok((opt, i + 1));
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	453 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	454 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	455 Err(NodeMapError::MultipleResults)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	456 }
44261 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	457
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	458 fn visit<'n, 'p>(
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	459 &'n self,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	460 prefix: NodePrefixRef<'p>,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	461 ) -> NodeTreeVisitor<'n, 'p> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	462 NodeTreeVisitor {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	463 nt: self,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	464 prefix: prefix,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	465 visit: self.len() - 1,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	466 nybble_idx: 0,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	467 done: false,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	468 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	469 }
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	470 /// Return a mutable reference for `Block` at index `idx`.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	471 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	472 /// If `idx` lies in the immutable area, then the reference is to
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	473 /// a newly appended copy.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	474 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	475 /// Returns (new_idx, glen, mut_ref) where
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	476 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	477 /// - `new_idx` is the index of the mutable `Block`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	478 /// - `mut_ref` is a mutable reference to the mutable Block.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	479 /// - `glen` is the new length of `self.growable`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	480 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	481 /// Note: the caller wouldn't be allowed to query `self.growable.len()`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	482 /// itself because of the mutable borrow taken with the returned `Block`
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	483 fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	484 let ro_blocks = &self.readonly;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	485 let ro_len = ro_blocks.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	486 let glen = self.growable.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	487 if idx < ro_len {
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	488 self.masked_inner_blocks += 1;
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	489 // TODO OPTIM I think this makes two copies
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	490 self.growable.push(ro_blocks[idx].clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	491 (glen + ro_len, &mut self.growable[glen], glen + 1)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	492 } else if glen + ro_len == idx {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	493 (idx, &mut self.root, glen)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	494 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	495 (idx, &mut self.growable[idx - ro_len], glen)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	496 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	497 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	498
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	499 /// Main insertion method
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	500 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	501 /// 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: 44261 diff changeset	502 /// `node`, split it as much as needed and record `node` in there.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	503 /// The method then backtracks, updating references in all the visited
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	504 /// blocks from the root.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	505 ///
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	506 /// All the mutated `Block` are copied first to the growable part if
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	507 /// needed. That happens for those in the immutable part except the root.
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	508 pub fn insert<I: RevlogIndex>(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	509 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	510 index: &I,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	511 node: &Node,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	512 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	513 ) -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	514 let ro_len = &self.readonly.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	515
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	516 let mut visit_steps: Vec<_> = self.visit(node.into()).collect();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	517 let read_nybbles = visit_steps.len();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	518 // visit_steps cannot be empty, since we always visit the root block
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	519 let deepest = visit_steps.pop().unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	520
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	521 let (mut block_idx, mut block, mut glen) =
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	522 self.mutable_block(deepest.block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	523
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	524 if let Element::Rev(old_rev) = deepest.element {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	525 let old_node = index
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	526 .node(old_rev)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	527 .ok_or_else(\|\| NodeMapError::RevisionNotInIndex(old_rev))?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	528 if old_node == node {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	529 return Ok(()); // avoid creating lots of useless blocks
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	530 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	531
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	532 // Looping over the tail of nybbles in both nodes, creating
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	533 // new blocks until we find the difference
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	534 let mut new_block_idx = ro_len + glen;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	535 let mut nybble = deepest.nybble;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	536 for nybble_pos in read_nybbles..node.nybbles_len() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	537 block.set(nybble, Element::Block(new_block_idx));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	538
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	539 let new_nybble = node.get_nybble(nybble_pos);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	540 let old_nybble = old_node.get_nybble(nybble_pos);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	541
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	542 if old_nybble == new_nybble {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	543 self.growable.push(Block::new());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	544 block = &mut self.growable[glen];
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	545 glen += 1;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	546 new_block_idx += 1;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	547 nybble = new_nybble;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	548 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	549 let mut new_block = Block::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	550 new_block.set(old_nybble, Element::Rev(old_rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	551 new_block.set(new_nybble, Element::Rev(rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	552 self.growable.push(new_block);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	553 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	554 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	555 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	556 } else {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	557 // Free slot in the deepest block: no splitting has to be done
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	558 block.set(deepest.nybble, Element::Rev(rev));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	559 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	560
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	561 // Backtrack over visit steps to update references
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	562 while let Some(visited) = visit_steps.pop() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	563 let to_write = Element::Block(block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	564 if visit_steps.is_empty() {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	565 self.root.set(visited.nybble, to_write);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	566 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	567 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	568 let (new_idx, block, _) = self.mutable_block(visited.block_idx);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	569 if block.get(visited.nybble) == to_write {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	570 break;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	571 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	572 block.set(visited.nybble, to_write);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	573 block_idx = new_idx;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	574 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	575 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	576 }
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	577
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	578 /// Return the number of blocks in the readonly part that are currently
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	579 /// masked in the mutable part.
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	580 ///
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	581 /// The `NodeTree` structure has no efficient way to know how many blocks
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	582 /// are already unreachable in the readonly part.
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	583 pub fn masked_readonly_blocks(&self) -> usize {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	584 if let Some(readonly_root) = self.readonly.last() {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	585 if readonly_root == &self.root {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	586 return 0;
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	587 }
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	588 } else {
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	589 return 0;
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	590 }
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	591 self.masked_inner_blocks + 1
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	592 }
44261 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	593 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	594
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	595 pub struct NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	596 buffer: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	597 len_in_blocks: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	598 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	599
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	600 impl NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	601 fn new(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	602 buffer: Box<dyn Deref<Target = [u8]> + Send>,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	603 amount: usize,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	604 ) -> Self {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	605 assert!(buffer.len() >= amount);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	606 let len_in_blocks = amount / BLOCK_SIZE;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	607 NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	608 buffer,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	609 len_in_blocks,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	610 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	611 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	612 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	613
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	614 impl Deref for NodeTreeBytes {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	615 type Target = [Block];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	616
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	617 fn deref(&self) -> &[Block] {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	618 unsafe {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	619 slice::from_raw_parts(
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	620 (&self.buffer).as_ptr() as *const Block,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	621 self.len_in_blocks,
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	622 )
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	623 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	624 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	625 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	626
44261 796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	627 struct NodeTreeVisitor<'n, 'p> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	628 nt: &'n NodeTree,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	629 prefix: NodePrefixRef<'p>,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	630 visit: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	631 nybble_idx: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	632 done: bool,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	633 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	634
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	635 #[derive(Debug, PartialEq, Clone)]
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	636 struct NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	637 block_idx: usize,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	638 nybble: u8,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	639 element: Element,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	640 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	641
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	642 impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	643 type Item = NodeTreeVisitItem;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	644
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	645 fn next(&mut self) -> Option<Self::Item> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	646 if self.done \|\| self.nybble_idx >= self.prefix.len() {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	647 return None;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	648 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	649
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	650 let nybble = self.prefix.get_nybble(self.nybble_idx);
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	651 self.nybble_idx += 1;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	652
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	653 let visit = self.visit;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	654 let element = self.nt[visit].get(nybble);
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	655 if let Element::Block(idx) = element {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	656 self.visit = idx;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	657 } else {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	658 self.done = true;
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	659 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	660
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	661 Some(NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	662 block_idx: visit,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	663 nybble: nybble,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	664 element: element,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	665 })
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	666 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	667 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	668
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	669 impl NodeTreeVisitItem {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	670 // Return `Some(opt)` if this item is final, with `opt` being the
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	671 // `Revision` that it may represent.
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	672 //
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	673 // If the item is not terminal, return `None`
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	674 fn final_revision(&self) -> Option<Option<Revision>> {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	675 match self.element {
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	676 Element::Block(_) => None,
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	677 Element::Rev(r) => Some(Some(r)),
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	678 Element::None => Some(None),
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	679 }
796d05f3fa84 rust-nodemap: generic NodeTreeVisitor Georges Racinet <georges.racinet@octobus.net> parents: 44260 diff changeset	680 }
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	681 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	682
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	683 impl From<Vec<Block>> for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	684 fn from(vec: Vec<Block>) -> Self {
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	685 Self::new(Box::new(vec))
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	686 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	687 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	688
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	689 impl fmt::Debug for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	690 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	691 let readonly: &[Block] = &*self.readonly;
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	692 write!(
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	693 f,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	694 "readonly: {:?}, growable: {:?}, root: {:?}",
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	695 readonly, self.growable, self.root
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	696 )
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	697 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	698 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	699
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	700 impl Default for NodeTree {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	701 /// Create a fully mutable empty NodeTree
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	702 fn default() -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	703 NodeTree::new(Box::new(Vec::new()))
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	704 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	705 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	706
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	707 impl NodeMap for NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	708 fn find_bin<'a>(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	709 &self,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	710 idx: &impl RevlogIndex,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	711 prefix: NodePrefixRef<'a>,
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	712 ) -> Result<Option<Revision>, NodeMapError> {
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	713 validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	714 .map(\|(opt, _shortest)\| opt)
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	715 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	716
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	717 fn unique_prefix_len_bin<'a>(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	718 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	719 idx: &impl RevlogIndex,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	720 prefix: NodePrefixRef<'a>,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	721 ) -> Result<Option<usize>, NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	722 validate_candidate(idx, prefix.clone(), self.lookup(prefix)?)
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	723 .map(\|(opt, shortest)\| opt.map(\|_rev\| shortest))
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	724 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	725 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	726
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	727 #[cfg(test)]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	728 mod tests {
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	729 use super::NodeMapError::*;
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	730 use super::*;
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	731 use crate::revlog::node::{hex_pad_right, Node};
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	732 use std::collections::HashMap;
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	733
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	734 /// 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	735 macro_rules! block {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	736 {$($nybble:tt : $variant:ident($val:tt)),*} => (
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	737 {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	738 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	739 $(block.set($nybble, Element::$variant($val)));*;
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	740 block
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	741 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	742 )
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	743 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	744
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	745 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	746 fn test_block_debug() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	747 let mut block = Block::new();
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	748 block.set(1, Element::Rev(3));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	749 block.set(10, Element::Block(0));
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	750 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	751 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	752
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	753 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	754 fn test_block_macro() {
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	755 let block = block! {5: Block(2)};
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	756 assert_eq!(format!("{:?}", block), "{5: Block(2)}");
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	757
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	758 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	759 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	760 }
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	761
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	762 #[test]
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	763 fn test_raw_block() {
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	764 let mut raw = [255u8; 64];
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	765
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	766 let mut counter = 0;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	767 for val in [0, 15, -2, -1, -3].iter() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	768 for byte in RawElement::to_be_bytes(*val).iter() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	769 raw[counter] = *byte;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	770 counter += 1;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	771 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	772 }
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	773 let block = Block(raw);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	774 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	775 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	776 assert_eq!(block.get(3), Element::None);
63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	777 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	778 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	779 }
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	780
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	781 type TestIndex = HashMap<Revision, Node>;
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	782
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	783 impl RevlogIndex for TestIndex {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	784 fn node(&self, rev: Revision) -> Option<&Node> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	785 self.get(&rev)
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	786 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	787
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	788 fn len(&self) -> usize {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	789 self.len()
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	790 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	791 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	792
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	793 /// Pad hexadecimal Node prefix with zeros on the right
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	794 ///
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	795 /// This avoids having to repeatedly write very long hexadecimal
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	796 /// strings for test data, and brings actual hash size independency.
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	797 #[cfg(test)]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	798 fn pad_node(hex: &str) -> Node {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	799 Node::from_hex(&hex_pad_right(hex)).unwrap()
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	800 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	801
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	802 /// Pad hexadecimal Node prefix with zeros on the right, then insert
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	803 fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) {
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	804 idx.insert(rev, pad_node(hex));
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	805 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	806
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	807 fn sample_nodetree() -> NodeTree {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	808 NodeTree::from(vec![
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	809 block![0: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	810 block![0: Rev(0), 1: Rev(9)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	811 block![0: Block(1), 1:Rev(1)],
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	812 ])
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	813 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	814
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	815 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	816 fn test_nt_debug() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	817 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	818 assert_eq!(
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	819 format!("{:?}", nt),
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	820 "readonly: \
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	821 [{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: 44259 diff changeset	822 growable: [], \
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	823 root: {0: Block(1), 1: Rev(1)}",
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	824 );
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	825 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	826
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	827 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	828 fn test_immutable_find_simplest() -> Result<(), NodeMapError> {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	829 let mut idx: TestIndex = HashMap::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	830 pad_insert(&mut idx, 1, "1234deadcafe");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	831
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	832 let nt = NodeTree::from(vec![block! {1: Rev(1)}]);
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	833 assert_eq!(nt.find_hex(&idx, "1")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	834 assert_eq!(nt.find_hex(&idx, "12")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	835 assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	836 assert_eq!(nt.find_hex(&idx, "1a")?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	837 assert_eq!(nt.find_hex(&idx, "ab")?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	838
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	839 // and with full binary Nodes
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	840 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: 44227 diff changeset	841 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: 44227 diff changeset	842 assert_eq!(nt.find_node(&idx, &unknown)?, None);
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	843 Ok(())
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	844 }
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	845
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	846 #[test]
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	847 fn test_immutable_find_one_jump() {
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	848 let mut idx = TestIndex::new();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	849 pad_insert(&mut idx, 9, "012");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	850 pad_insert(&mut idx, 0, "00a");
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	851
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	852 let nt = sample_nodetree();
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	853
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	854 assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults));
e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	855 assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9)));
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	856 assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	857 assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0)));
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	858 assert_eq!(nt.unique_prefix_len_hex(&idx, "00a"), Ok(Some(3)));
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	859 assert_eq!(nt.find_hex(&idx, "000"), Ok(Some(NULL_REVISION)));
44258 e52401a95b94 rust-nodemap: NodeMap trait with simplest implementation Georges Racinet <georges.racinet@octobus.net> parents: 44227 diff changeset	860 }
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	861
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	862 #[test]
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	863 fn test_mutated_find() -> Result<(), NodeMapError> {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	864 let mut idx = TestIndex::new();
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	865 pad_insert(&mut idx, 9, "012");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	866 pad_insert(&mut idx, 0, "00a");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	867 pad_insert(&mut idx, 2, "cafe");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	868 pad_insert(&mut idx, 3, "15");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	869 pad_insert(&mut idx, 1, "10");
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	870
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	871 let nt = NodeTree {
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	872 readonly: sample_nodetree().readonly,
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	873 growable: vec![block![0: Rev(1), 5: Rev(3)]],
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	874 root: block![0: Block(1), 1:Block(3), 12: Rev(2)],
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	875 masked_inner_blocks: 1,
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	876 };
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	877 assert_eq!(nt.find_hex(&idx, "10")?, Some(1));
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	878 assert_eq!(nt.find_hex(&idx, "c")?, Some(2));
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	879 assert_eq!(nt.unique_prefix_len_hex(&idx, "c")?, Some(1));
44418 00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	880 assert_eq!(nt.find_hex(&idx, "00"), Err(MultipleResults));
00d251d32007 rust-nodemap: special case for prefixes of NULL_NODE Georges Racinet <georges.racinet@octobus.net> parents: 44416 diff changeset	881 assert_eq!(nt.find_hex(&idx, "000")?, Some(NULL_REVISION));
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	882 assert_eq!(nt.unique_prefix_len_hex(&idx, "000")?, Some(3));
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	883 assert_eq!(nt.find_hex(&idx, "01")?, Some(9));
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	884 assert_eq!(nt.masked_readonly_blocks(), 2);
44260 a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	885 Ok(())
a19331456d48 rust-nodemap: mutable NodeTree data structure Georges Racinet <georges.racinet@octobus.net> parents: 44259 diff changeset	886 }
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	887
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	888 struct TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	889 index: TestIndex,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	890 nt: NodeTree,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	891 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	892
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	893 impl TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	894 fn new() -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	895 TestNtIndex {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	896 index: HashMap::new(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	897 nt: NodeTree::default(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	898 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	899 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	900
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	901 fn insert(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	902 &mut self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	903 rev: Revision,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	904 hex: &str,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	905 ) -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	906 let node = pad_node(hex);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	907 self.index.insert(rev, node.clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	908 self.nt.insert(&self.index, &node, rev)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	909 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	910 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	911
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	912 fn find_hex(
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	913 &self,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	914 prefix: &str,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	915 ) -> Result<Option<Revision>, NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	916 self.nt.find_hex(&self.index, prefix)
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	917 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	918
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	919 fn unique_prefix_len_hex(
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	920 &self,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	921 prefix: &str,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	922 ) -> Result<Option<usize>, NodeMapError> {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	923 self.nt.unique_prefix_len_hex(&self.index, prefix)
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	924 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	925
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	926 /// Drain `added` and restart a new one
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	927 fn commit(self) -> Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	928 let mut as_vec: Vec<Block> =
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	929 self.nt.readonly.iter().map(\|block\| block.clone()).collect();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	930 as_vec.extend(self.nt.growable);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	931 as_vec.push(self.nt.root);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	932
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	933 Self {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	934 index: self.index,
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	935 nt: NodeTree::from(as_vec).into(),
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	936 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	937 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	938 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	939
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	940 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	941 fn test_insert_full_mutable() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	942 let mut idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	943 idx.insert(0, "1234")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	944 assert_eq!(idx.find_hex("1")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	945 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	946
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	947 // let's trigger a simple split
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	948 idx.insert(1, "1a34")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	949 assert_eq!(idx.nt.growable.len(), 1);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	950 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	951 assert_eq!(idx.find_hex("1a")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	952
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	953 // reinserting is a no_op
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	954 idx.insert(1, "1a34")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	955 assert_eq!(idx.nt.growable.len(), 1);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	956 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	957 assert_eq!(idx.find_hex("1a")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	958
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	959 idx.insert(2, "1a01")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	960 assert_eq!(idx.nt.growable.len(), 2);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	961 assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	962 assert_eq!(idx.find_hex("12")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	963 assert_eq!(idx.find_hex("1a3")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	964 assert_eq!(idx.find_hex("1a0")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	965 assert_eq!(idx.find_hex("1a12")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	966
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	967 // 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: 44261 diff changeset	968 idx.insert(3, "1a345")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	969 assert_eq!(idx.nt.growable.len(), 4);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	970 assert_eq!(idx.find_hex("1a340")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	971 assert_eq!(idx.find_hex("1a345")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	972 assert_eq!(idx.find_hex("1a341")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	973
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	974 // there's no readonly block to mask
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	975 assert_eq!(idx.nt.masked_readonly_blocks(), 0);
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	976 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	977 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	978
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	979 #[test]
44419 5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	980 fn test_unique_prefix_len_zero_prefix() {
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	981 let mut idx = TestNtIndex::new();
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	982 idx.insert(0, "00000abcd").unwrap();
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	983
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	984 assert_eq!(idx.find_hex("000"), Err(NodeMapError::MultipleResults));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	985 // in the nodetree proper, this will be found at the first nybble
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	986 // yet the correct answer for unique_prefix_len is not 1, nor 1+1,
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	987 // but the first difference with `NULL_NODE`
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	988 assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	989 assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	990
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	991 // same with odd result
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	992 idx.insert(1, "00123").unwrap();
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	993 assert_eq!(idx.unique_prefix_len_hex("001"), Ok(Some(3)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	994 assert_eq!(idx.unique_prefix_len_hex("0012"), Ok(Some(3)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	995
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	996 // these are unchanged of course
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	997 assert_eq!(idx.unique_prefix_len_hex("00000a"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	998 assert_eq!(idx.unique_prefix_len_hex("00000ab"), Ok(Some(6)));
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	999 }
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	1000
5ac1eecc9c64 rust-nodemap: core implementation for shortest Georges Racinet <georges.racinet@octobus.net> parents: 44418 diff changeset	1001 #[test]
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1002 fn test_insert_extreme_splitting() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1003 // check that the splitting loop is long enough
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1004 let mut nt_idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1005 let nt = &mut nt_idx.nt;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1006 let idx = &mut nt_idx.index;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1007
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1008 let node0_hex = hex_pad_right("444444");
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1009 let mut node1_hex = hex_pad_right("444444").clone();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1010 node1_hex.pop();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1011 node1_hex.push('5');
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1012 let node0 = Node::from_hex(&node0_hex).unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1013 let node1 = Node::from_hex(&node1_hex).unwrap();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1014
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1015 idx.insert(0, node0.clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1016 nt.insert(idx, &node0, 0)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1017 idx.insert(1, node1.clone());
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1018 nt.insert(idx, &node1, 1)?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1019
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1020 assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1021 assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1022 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1023 }
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1024
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1025 #[test]
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1026 fn test_insert_partly_immutable() -> Result<(), NodeMapError> {
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1027 let mut idx = TestNtIndex::new();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1028 idx.insert(0, "1234")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1029 idx.insert(1, "1235")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1030 idx.insert(2, "131")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1031 idx.insert(3, "cafe")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1032 let mut idx = idx.commit();
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1033 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1034 assert_eq!(idx.find_hex("1235")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1035 assert_eq!(idx.find_hex("131")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1036 assert_eq!(idx.find_hex("cafe")?, Some(3));
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1037 // we did not add anything since init from readonly
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1038 assert_eq!(idx.nt.masked_readonly_blocks(), 0);
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1039
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1040 idx.insert(4, "123A")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1041 assert_eq!(idx.find_hex("1234")?, Some(0));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1042 assert_eq!(idx.find_hex("1235")?, Some(1));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1043 assert_eq!(idx.find_hex("131")?, Some(2));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1044 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1045 assert_eq!(idx.find_hex("123A")?, Some(4));
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1046 // we masked blocks for all prefixes of "123", including the root
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1047 assert_eq!(idx.nt.masked_readonly_blocks(), 4);
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1048
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1049 eprintln!("{:?}", idx.nt);
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1050 idx.insert(5, "c0")?;
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1051 assert_eq!(idx.find_hex("cafe")?, Some(3));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1052 assert_eq!(idx.find_hex("c0")?, Some(5));
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1053 assert_eq!(idx.find_hex("c1")?, None);
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1054 assert_eq!(idx.find_hex("1234")?, Some(0));
44420 6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1055 // inserting "c0" is just splitting the 'c' slot of the mutable root,
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1056 // it doesn't mask anything
6329ce04c69f rust-nodemap: accounting for dead blocks Georges Racinet <georges.racinet@octobus.net> parents: 44419 diff changeset	1057 assert_eq!(idx.nt.masked_readonly_blocks(), 4);
44390 d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1058
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1059 Ok(())
d2da8667125b rust-nodemap: insert method Georges Racinet <georges.racinet@octobus.net> parents: 44261 diff changeset	1060 }
44416 a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1061
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1062 #[test]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1063 fn test_into_added_empty() {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1064 assert!(sample_nodetree().into_readonly_and_added().1.is_empty());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1065 assert!(sample_nodetree()
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1066 .into_readonly_and_added_bytes()
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1067 .1
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1068 .is_empty());
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1069 }
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1070
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1071 #[test]
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1072 fn test_into_added_bytes() -> Result<(), NodeMapError> {
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1073 let mut idx = TestNtIndex::new();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1074 idx.insert(0, "1234")?;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1075 let mut idx = idx.commit();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1076 idx.insert(4, "cafe")?;
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1077 let (_, bytes) = idx.nt.into_readonly_and_added_bytes();
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1078
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1079 // only the root block has been changed
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1080 assert_eq!(bytes.len(), BLOCK_SIZE);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1081 // big endian for -2
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1082 assert_eq!(&bytes[4..2 * 4], [255, 255, 255, 254]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1083 // big endian for -6
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1084 assert_eq!(&bytes[12 * 4..13 * 4], [255, 255, 255, 250]);
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1085 Ok(())
a98ba6983a63 rust-nodemap: input/output primitives Georges Racinet <georges.racinet@octobus.net> parents: 44390 diff changeset	1086 }
44227 63db6657d280 rust-nodemap: building blocks for nodetree structures Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	1087 }

Mercurial > public > mercurial-scm > hg-stable

annotate rust/hg-core/src/revlog/nodemap.rs @ 44420:6329ce04c69f