Mercurial > hg
annotate rust/hg-core/src/revlog/nodemap.rs @ 44186:796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
This iterator will help avoid code duplication when we'll
implement `insert()`, in which we will need to
traverse the node tree, and to remember the visited blocks.
The structured iterator item will allow different usages from
`lookup()` and the upcoming `insert()`.
Differential Revision: https://phab.mercurial-scm.org/D7794
author | Georges Racinet <georges.racinet@octobus.net> |
---|---|
date | Fri, 27 Dec 2019 16:06:54 +0100 |
parents | a19331456d48 |
children | d2da8667125b |
rev | line source |
---|---|
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
1 // Copyright 2018-2020 Georges Racinet <georges.racinet@octobus.net> |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
2 // and Mercurial contributors |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
3 // |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
4 // This software may be used and distributed according to the terms of the |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
5 // GNU General Public License version 2 or any later version. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
6 //! Indexing facilities for fast retrieval of `Revision` from `Node` |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
7 //! |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
8 //! This provides a variation on the 16-ary radix tree that is |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
9 //! provided as "nodetree" in revlog.c, ready for append-only persistence |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
10 //! on disk. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
11 //! |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
12 //! Following existing implicit conventions, the "nodemap" terminology |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
13 //! is used in a more abstract context. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
14 |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
15 use super::{ |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
16 Node, NodeError, NodePrefix, NodePrefixRef, Revision, RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
17 }; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
18 use std::fmt; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
19 use std::ops::Deref; |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
20 use std::ops::Index; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
21 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
22 #[derive(Debug, PartialEq)] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
23 pub enum NodeMapError { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
24 MultipleResults, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
25 InvalidNodePrefix(NodeError), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
26 /// 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
|
27 RevisionNotInIndex(Revision), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
28 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
29 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
30 impl From<NodeError> for NodeMapError { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
31 fn from(err: NodeError) -> Self { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
32 NodeMapError::InvalidNodePrefix(err) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
33 } |
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 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
36 /// 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
|
37 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
38 /// ## `RevlogIndex` and `NodeMap` |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
39 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
40 /// 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
|
41 /// 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
|
42 /// carried by a [`RevlogIndex`]. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
43 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
44 /// 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
|
45 /// 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
|
46 /// 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
|
47 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
48 /// Notably, the `NodeMap` must not store |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
49 /// 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
|
50 /// 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
|
51 /// [`RevisionNotInIndex`] error is returned. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
52 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
53 /// 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
|
54 /// be updated after the `RevlogIndex` |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
55 /// 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
|
56 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
57 /// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
58 /// [`RevlogIndex`]: ../trait.RevlogIndex.html |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
59 pub trait NodeMap { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
60 /// 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
|
61 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
62 /// 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
|
63 fn find_node( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
64 &self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
65 index: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
66 node: &Node, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
67 ) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
68 self.find_bin(index, node.into()) |
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 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
71 /// 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
|
72 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
73 /// 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
|
74 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
75 /// 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
|
76 /// error is returned. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
77 fn find_bin<'a>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
78 &self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
79 idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
80 prefix: NodePrefixRef<'a>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
81 ) -> Result<Option<Revision>, NodeMapError>; |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
82 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
83 /// Find the unique Revision whose `Node` hexadecimal string representation |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
84 /// starts with a given prefix |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
85 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
86 /// 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
|
87 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
88 /// 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
|
89 /// error is returned. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
90 fn find_hex( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
91 &self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
92 idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
93 prefix: &str, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
94 ) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
95 self.find_bin(idx, NodePrefix::from_hex(prefix)?.borrow()) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
96 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
97 } |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
98 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
99 /// Low level NodeTree [`Blocks`] elements |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
100 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
101 /// These are exactly as for instance on persistent storage. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
102 type RawElement = i32; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
103 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
104 /// High level representation of values in NodeTree |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
105 /// [`Blocks`](struct.Block.html) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
106 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
107 /// 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
|
108 /// use. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
109 #[derive(Clone, Debug, Eq, PartialEq)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
110 enum Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
111 Rev(Revision), |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
112 Block(usize), |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
113 None, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
114 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
115 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
116 impl From<RawElement> for Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
117 /// 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
|
118 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
119 /// 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
|
120 fn from(raw: RawElement) -> Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
121 if raw >= 0 { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
122 Element::Block(raw as usize) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
123 } else if raw == -1 { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
124 Element::None |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
125 } else { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
126 Element::Rev(-raw - 2) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
127 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
128 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
129 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
130 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
131 impl From<Element> for RawElement { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
132 fn from(element: Element) -> RawElement { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
133 match element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
134 Element::None => 0, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
135 Element::Block(i) => i as RawElement, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
136 Element::Rev(rev) => -rev - 2, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
137 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
138 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
139 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
140 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
141 /// 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
|
142 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
143 /// 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
|
144 /// such as `&Block` |
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 /// 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
|
147 /// 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
|
148 /// (nybble) `i` is either: |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
149 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
150 /// - absent (value -1) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
151 /// - 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
|
152 /// - a `Revision` leaf (value ≤ -2) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
153 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
154 /// 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
|
155 /// different architectures. |
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 /// 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
|
158 /// 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
|
159 /// 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
|
160 /// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
161 /// 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
|
162 /// 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
|
163 /// to be valid. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
164 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
165 #[derive(Clone, PartialEq)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
166 pub struct Block([RawElement; 16]); |
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 impl Block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
169 fn new() -> Self { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
170 Block([-1; 16]) |
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 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
173 fn get(&self, nybble: u8) -> Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
174 Element::from(RawElement::from_be(self.0[nybble as usize])) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
175 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
176 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
177 fn set(&mut self, nybble: u8, element: Element) { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
178 self.0[nybble as usize] = RawElement::to_be(element.into()) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
179 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
180 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
181 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
182 impl fmt::Debug for Block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
183 /// sparse representation for testing and debugging purposes |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
184 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
|
185 f.debug_map() |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
186 .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
|
187 Element::None => None, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
188 element => Some((i, element)), |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
189 })) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
190 .finish() |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
191 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
192 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
193 |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
194 /// 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
|
195 /// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
196 /// 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
|
197 /// 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
|
198 /// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
199 /// 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
|
200 /// it on each insertion. |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
201 pub struct NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
202 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
|
203 growable: Vec<Block>, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
204 root: Block, |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
205 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
206 |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
207 impl Index<usize> for NodeTree { |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
208 type Output = Block; |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
209 |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
210 fn index(&self, i: usize) -> &Block { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
211 let ro_len = self.readonly.len(); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
212 if i < ro_len { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
213 &self.readonly[i] |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
214 } 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
|
215 &self.root |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
216 } else { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
217 &self.growable[i - ro_len] |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
218 } |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
219 } |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
220 } |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
221 |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
222 /// Return `None` unless the `Node` for `rev` has given prefix in `index`. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
223 fn has_prefix_or_none<'p>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
224 idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
225 prefix: NodePrefixRef<'p>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
226 rev: Revision, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
227 ) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
228 idx.node(rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
229 .ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
230 .map(|node| { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
231 if prefix.is_prefix_of(node) { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
232 Some(rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
233 } else { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
234 None |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
235 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
236 }) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
237 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
238 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
239 impl NodeTree { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
240 /// 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
|
241 /// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
242 /// 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
|
243 fn new(readonly: Box<dyn Deref<Target = [Block]> + Send>) -> Self { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
244 let root = readonly |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
245 .last() |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
246 .map(|b| b.clone()) |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
247 .unwrap_or_else(|| Block::new()); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
248 NodeTree { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
249 readonly: readonly, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
250 growable: Vec::new(), |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
251 root: root, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
252 } |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
253 } |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
254 |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
255 /// Total number of blocks |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
256 fn len(&self) -> usize { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
257 self.readonly.len() + self.growable.len() + 1 |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
258 } |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
259 |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
260 /// Implemented for completeness |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
261 /// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
262 /// 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
|
263 #[allow(dead_code)] |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
264 fn is_empty(&self) -> bool { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
265 false |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
266 } |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
267 |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
268 /// Main working method for `NodeTree` searches |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
269 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
270 /// This partial implementation lacks special cases for NULL_REVISION |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
271 fn lookup<'p>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
272 &self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
273 prefix: NodePrefixRef<'p>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
274 ) -> Result<Option<Revision>, NodeMapError> { |
44186
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
275 for visit_item in self.visit(prefix) { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
276 if let Some(opt) = visit_item.final_revision() { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
277 return Ok(opt); |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
278 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
279 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
280 Err(NodeMapError::MultipleResults) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
281 } |
44186
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
282 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
283 fn visit<'n, 'p>( |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
284 &'n self, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
285 prefix: NodePrefixRef<'p>, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
286 ) -> NodeTreeVisitor<'n, 'p> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
287 NodeTreeVisitor { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
288 nt: self, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
289 prefix: prefix, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
290 visit: self.len() - 1, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
291 nybble_idx: 0, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
292 done: false, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
293 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
294 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
295 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
296 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
297 struct NodeTreeVisitor<'n, 'p> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
298 nt: &'n NodeTree, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
299 prefix: NodePrefixRef<'p>, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
300 visit: usize, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
301 nybble_idx: usize, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
302 done: bool, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
303 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
304 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
305 #[derive(Debug, PartialEq, Clone)] |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
306 struct NodeTreeVisitItem { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
307 block_idx: usize, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
308 nybble: u8, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
309 element: Element, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
310 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
311 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
312 impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
313 type Item = NodeTreeVisitItem; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
314 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
315 fn next(&mut self) -> Option<Self::Item> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
316 if self.done || self.nybble_idx >= self.prefix.len() { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
317 return None; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
318 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
319 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
320 let nybble = self.prefix.get_nybble(self.nybble_idx); |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
321 self.nybble_idx += 1; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
322 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
323 let visit = self.visit; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
324 let element = self.nt[visit].get(nybble); |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
325 if let Element::Block(idx) = element { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
326 self.visit = idx; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
327 } else { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
328 self.done = true; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
329 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
330 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
331 Some(NodeTreeVisitItem { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
332 block_idx: visit, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
333 nybble: nybble, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
334 element: element, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
335 }) |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
336 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
337 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
338 |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
339 impl NodeTreeVisitItem { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
340 // 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
|
341 // `Revision` that it may represent. |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
342 // |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
343 // If the item is not terminal, return `None` |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
344 fn final_revision(&self) -> Option<Option<Revision>> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
345 match self.element { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
346 Element::Block(_) => None, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
347 Element::Rev(r) => Some(Some(r)), |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
348 Element::None => Some(None), |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
349 } |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
350 } |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
351 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
352 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
353 impl From<Vec<Block>> for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
354 fn from(vec: Vec<Block>) -> Self { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
355 Self::new(Box::new(vec)) |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
356 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
357 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
358 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
359 impl fmt::Debug for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
360 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
|
361 let readonly: &[Block] = &*self.readonly; |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
362 write!( |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
363 f, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
364 "readonly: {:?}, growable: {:?}, root: {:?}", |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
365 readonly, self.growable, self.root |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
366 ) |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
367 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
368 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
369 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
370 impl NodeMap for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
371 fn find_bin<'a>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
372 &self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
373 idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
374 prefix: NodePrefixRef<'a>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
375 ) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
376 self.lookup(prefix.clone()).and_then(|opt| { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
377 opt.map_or(Ok(None), |rev| has_prefix_or_none(idx, prefix, rev)) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
378 }) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
379 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
380 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
381 |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
382 #[cfg(test)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
383 mod tests { |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
384 use super::NodeMapError::*; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
385 use super::*; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
386 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
|
387 use std::collections::HashMap; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
388 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
389 /// 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
|
390 macro_rules! block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
391 {$($nybble:tt : $variant:ident($val:tt)),*} => ( |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
392 { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
393 let mut block = Block::new(); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
394 $(block.set($nybble, Element::$variant($val)));*; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
395 block |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
396 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
397 ) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
398 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
399 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
400 #[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
401 fn test_block_debug() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
402 let mut block = Block::new(); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
403 block.set(1, Element::Rev(3)); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
404 block.set(10, Element::Block(0)); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
405 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
|
406 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
407 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
408 #[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
409 fn test_block_macro() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
410 let block = block! {5: Block(2)}; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
411 assert_eq!(format!("{:?}", block), "{5: Block(2)}"); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
412 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
413 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
|
414 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
|
415 } |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
416 |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
417 #[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
418 fn test_raw_block() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
419 let mut raw = [-1; 16]; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
420 raw[0] = 0; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
421 raw[1] = RawElement::to_be(15); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
422 raw[2] = RawElement::to_be(-2); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
423 raw[3] = RawElement::to_be(-1); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
424 raw[4] = RawElement::to_be(-3); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
425 let block = Block(raw); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
426 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
|
427 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
|
428 assert_eq!(block.get(3), Element::None); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
429 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
|
430 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
|
431 } |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
432 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
433 type TestIndex = HashMap<Revision, Node>; |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
434 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
435 impl RevlogIndex for TestIndex { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
436 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
|
437 self.get(&rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
438 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
439 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
440 fn len(&self) -> usize { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
441 self.len() |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
442 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
443 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
444 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
445 /// Pad hexadecimal Node prefix with zeros on the right, then insert |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
446 /// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
447 /// 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
|
448 /// strings for test data, and brings actual hash size independency. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
449 fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
450 idx.insert(rev, Node::from_hex(&hex_pad_right(hex)).unwrap()); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
451 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
452 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
453 fn sample_nodetree() -> NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
454 NodeTree::from(vec![ |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
455 block![0: Rev(9)], |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
456 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
|
457 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
|
458 ]) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
459 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
460 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
461 #[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
462 fn test_nt_debug() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
463 let nt = sample_nodetree(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
464 assert_eq!( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
465 format!("{:?}", nt), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
466 "readonly: \ |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
467 [{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
|
468 growable: [], \ |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
469 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
|
470 ); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
471 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
472 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
473 #[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
474 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
|
475 let mut idx: TestIndex = HashMap::new(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
476 pad_insert(&mut idx, 1, "1234deadcafe"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
477 |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
478 let nt = NodeTree::from(vec![block! {1: Rev(1)}]); |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
479 assert_eq!(nt.find_hex(&idx, "1")?, Some(1)); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
480 assert_eq!(nt.find_hex(&idx, "12")?, Some(1)); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
481 assert_eq!(nt.find_hex(&idx, "1234de")?, Some(1)); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
482 assert_eq!(nt.find_hex(&idx, "1a")?, None); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
483 assert_eq!(nt.find_hex(&idx, "ab")?, None); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
484 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
485 // and with full binary Nodes |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
486 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
|
487 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
|
488 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
|
489 Ok(()) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
490 } |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
491 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
492 #[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
493 fn test_immutable_find_one_jump() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
494 let mut idx = TestIndex::new(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
495 pad_insert(&mut idx, 9, "012"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
496 pad_insert(&mut idx, 0, "00a"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
497 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
498 let nt = sample_nodetree(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
499 |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
500 assert_eq!(nt.find_hex(&idx, "0"), Err(MultipleResults)); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
501 assert_eq!(nt.find_hex(&idx, "01"), Ok(Some(9))); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
502 assert_eq!(nt.find_hex(&idx, "00"), Ok(Some(0))); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
503 assert_eq!(nt.find_hex(&idx, "00a"), Ok(Some(0))); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
504 } |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
505 |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
506 #[test] |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
507 fn test_mutated_find() -> Result<(), NodeMapError> { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
508 let mut idx = TestIndex::new(); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
509 pad_insert(&mut idx, 9, "012"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
510 pad_insert(&mut idx, 0, "00a"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
511 pad_insert(&mut idx, 2, "cafe"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
512 pad_insert(&mut idx, 3, "15"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
513 pad_insert(&mut idx, 1, "10"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
514 |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
515 let nt = NodeTree { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
516 readonly: sample_nodetree().readonly, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
517 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
|
518 root: block![0: Block(1), 1:Block(3), 12: Rev(2)], |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
519 }; |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
520 assert_eq!(nt.find_hex(&idx, "10")?, Some(1)); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
521 assert_eq!(nt.find_hex(&idx, "c")?, Some(2)); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
522 assert_eq!(nt.find_hex(&idx, "00")?, Some(0)); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
523 assert_eq!(nt.find_hex(&idx, "01")?, Some(9)); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
524 Ok(()) |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
525 } |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
526 } |