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

annotate rust/hg-core/src/revlog/nodemap.rs @ 48973:e2f8ed37201c stable

rust-status: cap the number of concurrent threads to 16 During benchmarking it was determined that the use of more threads is very advantageous... until we use more than 16. This is most likely due to some resource contention (thrashing, etc.). Until we have time to figure out and fix the underlying cause, let's just cap at 16 threads. Differential Revision: https://phab.mercurial-scm.org/D12384

author	Rapha?l Gom?s <rgomes@octobus.net>
date	Fri, 18 Mar 2022 16:15:44 +0100
parents	18a261b11b20
children	b97835b2e2d4

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

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/revlog/nodemap.rs @ 48973:e2f8ed37201c stable