author | Georges Racinet <georges.racinet@octobus.net> |
Thu, 26 Dec 2019 15:47:14 +0100 | |
changeset 44184 | 220d4d2e3185 |
parent 44183 | e52401a95b94 |
child 44185 | a19331456d48 |
permissions | -rw-r--r-- |
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 |
|
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
194 |
/// A 16-radix tree with the root block at the end |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
195 |
pub struct NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
196 |
readonly: Box<dyn Deref<Target = [Block]> + Send>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
197 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
198 |
|
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
199 |
impl Index<usize> for NodeTree { |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
200 |
type Output = Block; |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
201 |
|
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
202 |
fn index(&self, i: usize) -> &Block { |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
203 |
&self.readonly[i] |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
204 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
205 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
206 |
|
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
207 |
/// 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
|
208 |
fn has_prefix_or_none<'p>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
209 |
idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
210 |
prefix: NodePrefixRef<'p>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
211 |
rev: Revision, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
212 |
) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
213 |
idx.node(rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
214 |
.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
215 |
.map(|node| { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
216 |
if prefix.is_prefix_of(node) { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
217 |
Some(rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
218 |
} else { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
219 |
None |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
220 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
221 |
}) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
222 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
223 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
224 |
impl NodeTree { |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
225 |
fn len(&self) -> usize { |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
226 |
self.readonly.len() |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
227 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
228 |
|
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
229 |
fn is_empty(&self) -> bool { |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
230 |
self.len() == 0 |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
231 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
232 |
|
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
233 |
/// Main working method for `NodeTree` searches |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
234 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
235 |
/// 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
|
236 |
fn lookup<'p>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
237 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
238 |
prefix: NodePrefixRef<'p>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
239 |
) -> Result<Option<Revision>, NodeMapError> { |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
240 |
if self.is_empty() { |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
241 |
return Ok(None); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
242 |
} |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
243 |
let mut visit = self.len() - 1; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
244 |
for i in 0..prefix.len() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
245 |
let nybble = prefix.get_nybble(i); |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
246 |
match self[visit].get(nybble) { |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
247 |
Element::None => return Ok(None), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
248 |
Element::Rev(r) => return Ok(Some(r)), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
249 |
Element::Block(idx) => visit = idx, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
250 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
251 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
252 |
Err(NodeMapError::MultipleResults) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
253 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
254 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
255 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
256 |
impl From<Vec<Block>> for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
257 |
fn from(vec: Vec<Block>) -> Self { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
258 |
NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
259 |
readonly: Box::new(vec), |
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 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
262 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
263 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
264 |
impl fmt::Debug for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
265 |
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
266 |
let blocks: &[Block] = &*self.readonly; |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
267 |
write!(f, "readonly: {:?}", blocks) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
268 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
269 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
270 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
271 |
impl NodeMap for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
272 |
fn find_bin<'a>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
273 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
274 |
idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
275 |
prefix: NodePrefixRef<'a>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
276 |
) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
277 |
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
|
278 |
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
|
279 |
}) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
280 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
281 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
282 |
|
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
283 |
#[cfg(test)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
284 |
mod tests { |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
285 |
use super::NodeMapError::*; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
286 |
use super::*; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
287 |
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
|
288 |
use std::collections::HashMap; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
289 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
290 |
/// 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
|
291 |
macro_rules! block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
292 |
{$($nybble:tt : $variant:ident($val:tt)),*} => ( |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
293 |
{ |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
294 |
let mut block = Block::new(); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
295 |
$(block.set($nybble, Element::$variant($val)));*; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
296 |
block |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
297 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
298 |
) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
299 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
300 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
301 |
#[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
302 |
fn test_block_debug() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
303 |
let mut block = Block::new(); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
304 |
block.set(1, Element::Rev(3)); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
305 |
block.set(10, Element::Block(0)); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
306 |
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
|
307 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
308 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
309 |
#[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
310 |
fn test_block_macro() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
311 |
let block = block! {5: Block(2)}; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
312 |
assert_eq!(format!("{:?}", block), "{5: Block(2)}"); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
313 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
314 |
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
|
315 |
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
|
316 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
317 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
318 |
#[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
319 |
fn test_raw_block() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
320 |
let mut raw = [-1; 16]; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
321 |
raw[0] = 0; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
322 |
raw[1] = RawElement::to_be(15); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
323 |
raw[2] = RawElement::to_be(-2); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
324 |
raw[3] = RawElement::to_be(-1); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
325 |
raw[4] = RawElement::to_be(-3); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
326 |
let block = Block(raw); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
327 |
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
|
328 |
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
|
329 |
assert_eq!(block.get(3), Element::None); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
330 |
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
|
331 |
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
|
332 |
} |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
333 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
334 |
type TestIndex = HashMap<Revision, Node>; |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
335 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
336 |
impl RevlogIndex for TestIndex { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
337 |
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
|
338 |
self.get(&rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
339 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
340 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
341 |
fn len(&self) -> usize { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
342 |
self.len() |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
343 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
344 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
345 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
346 |
/// 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
|
347 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
348 |
/// 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
|
349 |
/// 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
|
350 |
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
|
351 |
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
|
352 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
353 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
354 |
fn sample_nodetree() -> NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
355 |
NodeTree::from(vec![ |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
356 |
block![0: Rev(9)], |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
357 |
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
|
358 |
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
|
359 |
]) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
360 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
361 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
362 |
#[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
363 |
fn test_nt_debug() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
364 |
let nt = sample_nodetree(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
365 |
assert_eq!( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
366 |
format!("{:?}", nt), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
367 |
"readonly: \ |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
368 |
[{0: Rev(9)}, {0: Rev(0), 1: Rev(9)}, {0: Block(1), 1: Rev(1)}]" |
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 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
371 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
372 |
#[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
373 |
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
|
374 |
let mut idx: TestIndex = HashMap::new(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
375 |
pad_insert(&mut idx, 1, "1234deadcafe"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
376 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
377 |
let nt = NodeTree::from(vec![block![1: Rev(1)]]); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
378 |
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
|
379 |
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
|
380 |
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
|
381 |
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
|
382 |
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
|
383 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
384 |
// and with full binary Nodes |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
385 |
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
|
386 |
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
|
387 |
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
|
388 |
Ok(()) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
389 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
390 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
391 |
#[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
392 |
fn test_immutable_find_one_jump() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
393 |
let mut idx = TestIndex::new(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
394 |
pad_insert(&mut idx, 9, "012"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
395 |
pad_insert(&mut idx, 0, "00a"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
396 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
397 |
let nt = sample_nodetree(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
398 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
399 |
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
|
400 |
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
|
401 |
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
|
402 |
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
|
403 |
} |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
404 |
} |