author | Georges Racinet <georges.racinet@octobus.net> |
Tue, 31 Dec 2019 12:43:57 +0100 | |
changeset 44356 | d2da8667125b |
parent 44186 | 796d05f3fa84 |
child 44385 | a98ba6983a63 |
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 |
}; |
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
18 |
|
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
19 |
use std::fmt; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
20 |
use std::ops::Deref; |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
21 |
use std::ops::Index; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
22 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
23 |
#[derive(Debug, PartialEq)] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
24 |
pub enum NodeMapError { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
25 |
MultipleResults, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
26 |
InvalidNodePrefix(NodeError), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
27 |
/// 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
|
28 |
RevisionNotInIndex(Revision), |
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 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
31 |
impl From<NodeError> for NodeMapError { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
32 |
fn from(err: NodeError) -> Self { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
33 |
NodeMapError::InvalidNodePrefix(err) |
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 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
37 |
/// 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
|
38 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
39 |
/// ## `RevlogIndex` and `NodeMap` |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
40 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
41 |
/// 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
|
42 |
/// 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
|
43 |
/// carried by a [`RevlogIndex`]. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
44 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
45 |
/// 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
|
46 |
/// 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
|
47 |
/// 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
|
48 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
49 |
/// Notably, the `NodeMap` must not store |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
50 |
/// 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
|
51 |
/// 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
|
52 |
/// [`RevisionNotInIndex`] error is returned. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
53 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
54 |
/// 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
|
55 |
/// be updated after the `RevlogIndex` |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
56 |
/// 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
|
57 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
58 |
/// [`RevisionNotInIndex`]: enum.NodeMapError.html#variant.RevisionNotInIndex |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
59 |
/// [`RevlogIndex`]: ../trait.RevlogIndex.html |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
60 |
pub trait NodeMap { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
61 |
/// 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
|
62 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
63 |
/// 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
|
64 |
fn find_node( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
65 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
66 |
index: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
67 |
node: &Node, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
68 |
) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
69 |
self.find_bin(index, node.into()) |
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 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
72 |
/// 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
|
73 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
74 |
/// 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
|
75 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
76 |
/// 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
|
77 |
/// error is returned. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
78 |
fn find_bin<'a>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
79 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
80 |
idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
81 |
prefix: NodePrefixRef<'a>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
82 |
) -> Result<Option<Revision>, NodeMapError>; |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
83 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
84 |
/// 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
|
85 |
/// starts with a given prefix |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
86 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
87 |
/// 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
|
88 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
89 |
/// 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
|
90 |
/// error is returned. |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
91 |
fn find_hex( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
92 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
93 |
idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
94 |
prefix: &str, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
95 |
) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
96 |
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
|
97 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
98 |
} |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
99 |
|
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
100 |
pub trait MutableNodeMap: NodeMap { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
101 |
fn insert<I: RevlogIndex>( |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
102 |
&mut self, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
103 |
index: &I, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
104 |
node: &Node, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
105 |
rev: Revision, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
106 |
) -> Result<(), NodeMapError>; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
107 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
108 |
|
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
109 |
/// Low level NodeTree [`Blocks`] elements |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
110 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
111 |
/// 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
|
112 |
type RawElement = i32; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
113 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
114 |
/// High level representation of values in NodeTree |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
115 |
/// [`Blocks`](struct.Block.html) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
116 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
117 |
/// 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
|
118 |
/// use. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
119 |
#[derive(Clone, Debug, Eq, PartialEq)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
120 |
enum Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
121 |
Rev(Revision), |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
122 |
Block(usize), |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
123 |
None, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
124 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
125 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
126 |
impl From<RawElement> for Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
127 |
/// 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
|
128 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
129 |
/// 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
|
130 |
fn from(raw: RawElement) -> Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
131 |
if raw >= 0 { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
132 |
Element::Block(raw as usize) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
133 |
} else if raw == -1 { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
134 |
Element::None |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
135 |
} else { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
136 |
Element::Rev(-raw - 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 |
impl From<Element> for RawElement { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
142 |
fn from(element: Element) -> RawElement { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
143 |
match element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
144 |
Element::None => 0, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
145 |
Element::Block(i) => i as RawElement, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
146 |
Element::Rev(rev) => -rev - 2, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
147 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
148 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
149 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
150 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
151 |
/// 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
|
152 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
153 |
/// 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
|
154 |
/// such as `&Block` |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
155 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
156 |
/// 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
|
157 |
/// 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
|
158 |
/// (nybble) `i` is either: |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
159 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
160 |
/// - absent (value -1) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
161 |
/// - 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
|
162 |
/// - a `Revision` leaf (value ≤ -2) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
163 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
164 |
/// 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
|
165 |
/// different architectures. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
166 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
167 |
/// 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
|
168 |
/// 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
|
169 |
/// 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
|
170 |
/// |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
171 |
/// 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
|
172 |
/// 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
|
173 |
/// to be valid. |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
174 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
175 |
#[derive(Clone, PartialEq)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
176 |
pub struct Block([RawElement; 16]); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
177 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
178 |
impl Block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
179 |
fn new() -> Self { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
180 |
Block([-1; 16]) |
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 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
183 |
fn get(&self, nybble: u8) -> Element { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
184 |
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
|
185 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
186 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
187 |
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
|
188 |
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
|
189 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
190 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
191 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
192 |
impl fmt::Debug for Block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
193 |
/// sparse representation for testing and debugging purposes |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
194 |
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
|
195 |
f.debug_map() |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
196 |
.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
|
197 |
Element::None => None, |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
198 |
element => Some((i, element)), |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
199 |
})) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
200 |
.finish() |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
201 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
202 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
203 |
|
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
204 |
/// 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
|
205 |
/// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
206 |
/// 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
|
207 |
/// 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
|
208 |
/// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
209 |
/// 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
|
210 |
/// it on each insertion. |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
211 |
pub struct NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
212 |
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
|
213 |
growable: Vec<Block>, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
214 |
root: Block, |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
215 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
216 |
|
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
217 |
impl Index<usize> for NodeTree { |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
218 |
type Output = Block; |
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 |
fn index(&self, i: usize) -> &Block { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
221 |
let ro_len = self.readonly.len(); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
222 |
if i < ro_len { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
223 |
&self.readonly[i] |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
224 |
} 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
|
225 |
&self.root |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
226 |
} else { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
227 |
&self.growable[i - ro_len] |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
228 |
} |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
229 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
230 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
231 |
|
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
232 |
/// 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
|
233 |
fn has_prefix_or_none<'p>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
234 |
idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
235 |
prefix: NodePrefixRef<'p>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
236 |
rev: Revision, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
237 |
) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
238 |
idx.node(rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
239 |
.ok_or_else(|| NodeMapError::RevisionNotInIndex(rev)) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
240 |
.map(|node| { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
241 |
if prefix.is_prefix_of(node) { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
242 |
Some(rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
243 |
} else { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
244 |
None |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
245 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
246 |
}) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
247 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
248 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
249 |
impl NodeTree { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
250 |
/// 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
|
251 |
/// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
252 |
/// 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
|
253 |
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
|
254 |
let root = readonly |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
255 |
.last() |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
256 |
.map(|b| b.clone()) |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
257 |
.unwrap_or_else(|| Block::new()); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
258 |
NodeTree { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
259 |
readonly: readonly, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
260 |
growable: Vec::new(), |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
261 |
root: root, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
262 |
} |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
263 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
264 |
|
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
265 |
/// Total number of blocks |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
266 |
fn len(&self) -> usize { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
267 |
self.readonly.len() + self.growable.len() + 1 |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
268 |
} |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
269 |
|
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
270 |
/// Implemented for completeness |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
271 |
/// |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
272 |
/// 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
|
273 |
#[allow(dead_code)] |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
274 |
fn is_empty(&self) -> bool { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
275 |
false |
44184
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
276 |
} |
220d4d2e3185
rust-nodemap: abstracting the indexing
Georges Racinet <georges.racinet@octobus.net>
parents:
44183
diff
changeset
|
277 |
|
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
278 |
/// Main working method for `NodeTree` searches |
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 |
/// 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
|
281 |
fn lookup<'p>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
282 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
283 |
prefix: NodePrefixRef<'p>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
284 |
) -> Result<Option<Revision>, NodeMapError> { |
44186
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
285 |
for visit_item in self.visit(prefix) { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
286 |
if let Some(opt) = visit_item.final_revision() { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
287 |
return Ok(opt); |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
288 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
289 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
290 |
Err(NodeMapError::MultipleResults) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
291 |
} |
44186
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
292 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
293 |
fn visit<'n, 'p>( |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
294 |
&'n self, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
295 |
prefix: NodePrefixRef<'p>, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
296 |
) -> NodeTreeVisitor<'n, 'p> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
297 |
NodeTreeVisitor { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
298 |
nt: self, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
299 |
prefix: prefix, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
300 |
visit: self.len() - 1, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
301 |
nybble_idx: 0, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
302 |
done: false, |
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 |
} |
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
305 |
/// Return a mutable reference for `Block` at index `idx`. |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
306 |
/// |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
307 |
/// If `idx` lies in the immutable area, then the reference is to |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
308 |
/// a newly appended copy. |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
309 |
/// |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
310 |
/// Returns (new_idx, glen, mut_ref) where |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
311 |
/// |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
312 |
/// - `new_idx` is the index of the mutable `Block` |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
313 |
/// - `mut_ref` is a mutable reference to the mutable Block. |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
314 |
/// - `glen` is the new length of `self.growable` |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
315 |
/// |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
316 |
/// Note: the caller wouldn't be allowed to query `self.growable.len()` |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
317 |
/// itself because of the mutable borrow taken with the returned `Block` |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
318 |
fn mutable_block(&mut self, idx: usize) -> (usize, &mut Block, usize) { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
319 |
let ro_blocks = &self.readonly; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
320 |
let ro_len = ro_blocks.len(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
321 |
let glen = self.growable.len(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
322 |
if idx < ro_len { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
323 |
// TODO OPTIM I think this makes two copies |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
324 |
self.growable.push(ro_blocks[idx].clone()); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
325 |
(glen + ro_len, &mut self.growable[glen], glen + 1) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
326 |
} else if glen + ro_len == idx { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
327 |
(idx, &mut self.root, glen) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
328 |
} else { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
329 |
(idx, &mut self.growable[idx - ro_len], glen) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
330 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
331 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
332 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
333 |
/// Main insertion method |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
334 |
/// |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
335 |
/// This will dive in the node tree to find the deepest `Block` for |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
336 |
/// `node`, split it as much as needed and record `node` in there. |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
337 |
/// The method then backtracks, updating references in all the visited |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
338 |
/// blocks from the root. |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
339 |
/// |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
340 |
/// All the mutated `Block` are copied first to the growable part if |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
341 |
/// needed. That happens for those in the immutable part except the root. |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
342 |
pub fn insert<I: RevlogIndex>( |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
343 |
&mut self, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
344 |
index: &I, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
345 |
node: &Node, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
346 |
rev: Revision, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
347 |
) -> Result<(), NodeMapError> { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
348 |
let ro_len = &self.readonly.len(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
349 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
350 |
let mut visit_steps: Vec<_> = self.visit(node.into()).collect(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
351 |
let read_nybbles = visit_steps.len(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
352 |
// visit_steps cannot be empty, since we always visit the root block |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
353 |
let deepest = visit_steps.pop().unwrap(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
354 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
355 |
let (mut block_idx, mut block, mut glen) = |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
356 |
self.mutable_block(deepest.block_idx); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
357 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
358 |
if let Element::Rev(old_rev) = deepest.element { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
359 |
let old_node = index |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
360 |
.node(old_rev) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
361 |
.ok_or_else(|| NodeMapError::RevisionNotInIndex(old_rev))?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
362 |
if old_node == node { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
363 |
return Ok(()); // avoid creating lots of useless blocks |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
364 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
365 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
366 |
// Looping over the tail of nybbles in both nodes, creating |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
367 |
// new blocks until we find the difference |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
368 |
let mut new_block_idx = ro_len + glen; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
369 |
let mut nybble = deepest.nybble; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
370 |
for nybble_pos in read_nybbles..node.nybbles_len() { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
371 |
block.set(nybble, Element::Block(new_block_idx)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
372 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
373 |
let new_nybble = node.get_nybble(nybble_pos); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
374 |
let old_nybble = old_node.get_nybble(nybble_pos); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
375 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
376 |
if old_nybble == new_nybble { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
377 |
self.growable.push(Block::new()); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
378 |
block = &mut self.growable[glen]; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
379 |
glen += 1; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
380 |
new_block_idx += 1; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
381 |
nybble = new_nybble; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
382 |
} else { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
383 |
let mut new_block = Block::new(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
384 |
new_block.set(old_nybble, Element::Rev(old_rev)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
385 |
new_block.set(new_nybble, Element::Rev(rev)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
386 |
self.growable.push(new_block); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
387 |
break; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
388 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
389 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
390 |
} else { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
391 |
// Free slot in the deepest block: no splitting has to be done |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
392 |
block.set(deepest.nybble, Element::Rev(rev)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
393 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
394 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
395 |
// Backtrack over visit steps to update references |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
396 |
while let Some(visited) = visit_steps.pop() { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
397 |
let to_write = Element::Block(block_idx); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
398 |
if visit_steps.is_empty() { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
399 |
self.root.set(visited.nybble, to_write); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
400 |
break; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
401 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
402 |
let (new_idx, block, _) = self.mutable_block(visited.block_idx); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
403 |
if block.get(visited.nybble) == to_write { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
404 |
break; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
405 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
406 |
block.set(visited.nybble, to_write); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
407 |
block_idx = new_idx; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
408 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
409 |
Ok(()) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
410 |
} |
44186
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
411 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
412 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
413 |
struct NodeTreeVisitor<'n, 'p> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
414 |
nt: &'n NodeTree, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
415 |
prefix: NodePrefixRef<'p>, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
416 |
visit: usize, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
417 |
nybble_idx: usize, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
418 |
done: bool, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
419 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
420 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
421 |
#[derive(Debug, PartialEq, Clone)] |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
422 |
struct NodeTreeVisitItem { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
423 |
block_idx: usize, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
424 |
nybble: u8, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
425 |
element: Element, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
426 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
427 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
428 |
impl<'n, 'p> Iterator for NodeTreeVisitor<'n, 'p> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
429 |
type Item = NodeTreeVisitItem; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
430 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
431 |
fn next(&mut self) -> Option<Self::Item> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
432 |
if self.done || self.nybble_idx >= self.prefix.len() { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
433 |
return None; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
434 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
435 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
436 |
let nybble = self.prefix.get_nybble(self.nybble_idx); |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
437 |
self.nybble_idx += 1; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
438 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
439 |
let visit = self.visit; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
440 |
let element = self.nt[visit].get(nybble); |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
441 |
if let Element::Block(idx) = element { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
442 |
self.visit = idx; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
443 |
} else { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
444 |
self.done = true; |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
445 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
446 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
447 |
Some(NodeTreeVisitItem { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
448 |
block_idx: visit, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
449 |
nybble: nybble, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
450 |
element: element, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
451 |
}) |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
452 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
453 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
454 |
|
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
455 |
impl NodeTreeVisitItem { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
456 |
// 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
|
457 |
// `Revision` that it may represent. |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
458 |
// |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
459 |
// If the item is not terminal, return `None` |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
460 |
fn final_revision(&self) -> Option<Option<Revision>> { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
461 |
match self.element { |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
462 |
Element::Block(_) => None, |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
463 |
Element::Rev(r) => Some(Some(r)), |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
464 |
Element::None => Some(None), |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
465 |
} |
796d05f3fa84
rust-nodemap: generic NodeTreeVisitor
Georges Racinet <georges.racinet@octobus.net>
parents:
44185
diff
changeset
|
466 |
} |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
467 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
468 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
469 |
impl From<Vec<Block>> for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
470 |
fn from(vec: Vec<Block>) -> Self { |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
471 |
Self::new(Box::new(vec)) |
44183
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 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
474 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
475 |
impl fmt::Debug for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
476 |
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
|
477 |
let readonly: &[Block] = &*self.readonly; |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
478 |
write!( |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
479 |
f, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
480 |
"readonly: {:?}, growable: {:?}, root: {:?}", |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
481 |
readonly, self.growable, self.root |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
482 |
) |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
483 |
} |
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 |
|
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
486 |
impl Default for NodeTree { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
487 |
/// Create a fully mutable empty NodeTree |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
488 |
fn default() -> Self { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
489 |
NodeTree::new(Box::new(Vec::new())) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
490 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
491 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
492 |
|
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
493 |
impl NodeMap for NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
494 |
fn find_bin<'a>( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
495 |
&self, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
496 |
idx: &impl RevlogIndex, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
497 |
prefix: NodePrefixRef<'a>, |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
498 |
) -> Result<Option<Revision>, NodeMapError> { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
499 |
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
|
500 |
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
|
501 |
}) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
502 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
503 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
504 |
|
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
505 |
#[cfg(test)] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
506 |
mod tests { |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
507 |
use super::NodeMapError::*; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
508 |
use super::*; |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
509 |
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
|
510 |
use std::collections::HashMap; |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
511 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
512 |
/// 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
|
513 |
macro_rules! block { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
514 |
{$($nybble:tt : $variant:ident($val:tt)),*} => ( |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
515 |
{ |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
516 |
let mut block = Block::new(); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
517 |
$(block.set($nybble, Element::$variant($val)));*; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
518 |
block |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
519 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
520 |
) |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
521 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
522 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
523 |
#[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
524 |
fn test_block_debug() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
525 |
let mut block = Block::new(); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
526 |
block.set(1, Element::Rev(3)); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
527 |
block.set(10, Element::Block(0)); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
528 |
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
|
529 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
530 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
531 |
#[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
532 |
fn test_block_macro() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
533 |
let block = block! {5: Block(2)}; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
534 |
assert_eq!(format!("{:?}", block), "{5: Block(2)}"); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
535 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
536 |
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
|
537 |
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
|
538 |
} |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
539 |
|
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
540 |
#[test] |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
541 |
fn test_raw_block() { |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
542 |
let mut raw = [-1; 16]; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
543 |
raw[0] = 0; |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
544 |
raw[1] = RawElement::to_be(15); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
545 |
raw[2] = RawElement::to_be(-2); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
546 |
raw[3] = RawElement::to_be(-1); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
547 |
raw[4] = RawElement::to_be(-3); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
548 |
let block = Block(raw); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
549 |
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
|
550 |
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
|
551 |
assert_eq!(block.get(3), Element::None); |
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
552 |
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
|
553 |
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
|
554 |
} |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
555 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
556 |
type TestIndex = HashMap<Revision, Node>; |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
557 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
558 |
impl RevlogIndex for TestIndex { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
559 |
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
|
560 |
self.get(&rev) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
561 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
562 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
563 |
fn len(&self) -> usize { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
564 |
self.len() |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
565 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
566 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
567 |
|
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
568 |
/// Pad hexadecimal Node prefix with zeros on the right |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
569 |
/// |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
570 |
/// 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
|
571 |
/// strings for test data, and brings actual hash size independency. |
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
572 |
#[cfg(test)] |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
573 |
fn pad_node(hex: &str) -> Node { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
574 |
Node::from_hex(&hex_pad_right(hex)).unwrap() |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
575 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
576 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
577 |
/// Pad hexadecimal Node prefix with zeros on the right, then insert |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
578 |
fn pad_insert(idx: &mut TestIndex, rev: Revision, hex: &str) { |
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
579 |
idx.insert(rev, pad_node(hex)); |
44183
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
580 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
581 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
582 |
fn sample_nodetree() -> NodeTree { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
583 |
NodeTree::from(vec![ |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
584 |
block![0: Rev(9)], |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
585 |
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
|
586 |
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
|
587 |
]) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
588 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
589 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
590 |
#[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
591 |
fn test_nt_debug() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
592 |
let nt = sample_nodetree(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
593 |
assert_eq!( |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
594 |
format!("{:?}", nt), |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
595 |
"readonly: \ |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
596 |
[{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
|
597 |
growable: [], \ |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
598 |
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
|
599 |
); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
600 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
601 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
602 |
#[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
603 |
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
|
604 |
let mut idx: TestIndex = HashMap::new(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
605 |
pad_insert(&mut idx, 1, "1234deadcafe"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
606 |
|
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
607 |
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
|
608 |
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
|
609 |
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
|
610 |
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
|
611 |
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
|
612 |
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
|
613 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
614 |
// and with full binary Nodes |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
615 |
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
|
616 |
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
|
617 |
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
|
618 |
Ok(()) |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
619 |
} |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
620 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
621 |
#[test] |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
622 |
fn test_immutable_find_one_jump() { |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
623 |
let mut idx = TestIndex::new(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
624 |
pad_insert(&mut idx, 9, "012"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
625 |
pad_insert(&mut idx, 0, "00a"); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
626 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
627 |
let nt = sample_nodetree(); |
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
628 |
|
e52401a95b94
rust-nodemap: NodeMap trait with simplest implementation
Georges Racinet <georges.racinet@octobus.net>
parents:
44142
diff
changeset
|
629 |
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
|
630 |
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
|
631 |
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
|
632 |
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
|
633 |
} |
44185
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
634 |
|
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
635 |
#[test] |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
636 |
fn test_mutated_find() -> Result<(), NodeMapError> { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
637 |
let mut idx = TestIndex::new(); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
638 |
pad_insert(&mut idx, 9, "012"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
639 |
pad_insert(&mut idx, 0, "00a"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
640 |
pad_insert(&mut idx, 2, "cafe"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
641 |
pad_insert(&mut idx, 3, "15"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
642 |
pad_insert(&mut idx, 1, "10"); |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
643 |
|
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
644 |
let nt = NodeTree { |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
645 |
readonly: sample_nodetree().readonly, |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
646 |
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
|
647 |
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
|
648 |
}; |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
649 |
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
|
650 |
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
|
651 |
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
|
652 |
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
|
653 |
Ok(()) |
a19331456d48
rust-nodemap: mutable NodeTree data structure
Georges Racinet <georges.racinet@octobus.net>
parents:
44184
diff
changeset
|
654 |
} |
44356
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
655 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
656 |
struct TestNtIndex { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
657 |
index: TestIndex, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
658 |
nt: NodeTree, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
659 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
660 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
661 |
impl TestNtIndex { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
662 |
fn new() -> Self { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
663 |
TestNtIndex { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
664 |
index: HashMap::new(), |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
665 |
nt: NodeTree::default(), |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
666 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
667 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
668 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
669 |
fn insert( |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
670 |
&mut self, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
671 |
rev: Revision, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
672 |
hex: &str, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
673 |
) -> Result<(), NodeMapError> { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
674 |
let node = pad_node(hex); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
675 |
self.index.insert(rev, node.clone()); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
676 |
self.nt.insert(&self.index, &node, rev)?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
677 |
Ok(()) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
678 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
679 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
680 |
fn find_hex( |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
681 |
&self, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
682 |
prefix: &str, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
683 |
) -> Result<Option<Revision>, NodeMapError> { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
684 |
self.nt.find_hex(&self.index, prefix) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
685 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
686 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
687 |
/// Drain `added` and restart a new one |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
688 |
fn commit(self) -> Self { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
689 |
let mut as_vec: Vec<Block> = |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
690 |
self.nt.readonly.iter().map(|block| block.clone()).collect(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
691 |
as_vec.extend(self.nt.growable); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
692 |
as_vec.push(self.nt.root); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
693 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
694 |
Self { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
695 |
index: self.index, |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
696 |
nt: NodeTree::from(as_vec).into(), |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
697 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
698 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
699 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
700 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
701 |
#[test] |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
702 |
fn test_insert_full_mutable() -> Result<(), NodeMapError> { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
703 |
let mut idx = TestNtIndex::new(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
704 |
idx.insert(0, "1234")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
705 |
assert_eq!(idx.find_hex("1")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
706 |
assert_eq!(idx.find_hex("12")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
707 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
708 |
// let's trigger a simple split |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
709 |
idx.insert(1, "1a34")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
710 |
assert_eq!(idx.nt.growable.len(), 1); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
711 |
assert_eq!(idx.find_hex("12")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
712 |
assert_eq!(idx.find_hex("1a")?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
713 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
714 |
// reinserting is a no_op |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
715 |
idx.insert(1, "1a34")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
716 |
assert_eq!(idx.nt.growable.len(), 1); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
717 |
assert_eq!(idx.find_hex("12")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
718 |
assert_eq!(idx.find_hex("1a")?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
719 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
720 |
idx.insert(2, "1a01")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
721 |
assert_eq!(idx.nt.growable.len(), 2); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
722 |
assert_eq!(idx.find_hex("1a"), Err(NodeMapError::MultipleResults)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
723 |
assert_eq!(idx.find_hex("12")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
724 |
assert_eq!(idx.find_hex("1a3")?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
725 |
assert_eq!(idx.find_hex("1a0")?, Some(2)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
726 |
assert_eq!(idx.find_hex("1a12")?, None); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
727 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
728 |
// now let's make it split and create more than one additional block |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
729 |
idx.insert(3, "1a345")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
730 |
assert_eq!(idx.nt.growable.len(), 4); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
731 |
assert_eq!(idx.find_hex("1a340")?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
732 |
assert_eq!(idx.find_hex("1a345")?, Some(3)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
733 |
assert_eq!(idx.find_hex("1a341")?, None); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
734 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
735 |
Ok(()) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
736 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
737 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
738 |
#[test] |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
739 |
fn test_insert_extreme_splitting() -> Result<(), NodeMapError> { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
740 |
// check that the splitting loop is long enough |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
741 |
let mut nt_idx = TestNtIndex::new(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
742 |
let nt = &mut nt_idx.nt; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
743 |
let idx = &mut nt_idx.index; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
744 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
745 |
let node0_hex = hex_pad_right("444444"); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
746 |
let mut node1_hex = hex_pad_right("444444").clone(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
747 |
node1_hex.pop(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
748 |
node1_hex.push('5'); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
749 |
let node0 = Node::from_hex(&node0_hex).unwrap(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
750 |
let node1 = Node::from_hex(&node1_hex).unwrap(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
751 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
752 |
idx.insert(0, node0.clone()); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
753 |
nt.insert(idx, &node0, 0)?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
754 |
idx.insert(1, node1.clone()); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
755 |
nt.insert(idx, &node1, 1)?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
756 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
757 |
assert_eq!(nt.find_bin(idx, (&node0).into())?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
758 |
assert_eq!(nt.find_bin(idx, (&node1).into())?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
759 |
Ok(()) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
760 |
} |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
761 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
762 |
#[test] |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
763 |
fn test_insert_partly_immutable() -> Result<(), NodeMapError> { |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
764 |
let mut idx = TestNtIndex::new(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
765 |
idx.insert(0, "1234")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
766 |
idx.insert(1, "1235")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
767 |
idx.insert(2, "131")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
768 |
idx.insert(3, "cafe")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
769 |
let mut idx = idx.commit(); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
770 |
assert_eq!(idx.find_hex("1234")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
771 |
assert_eq!(idx.find_hex("1235")?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
772 |
assert_eq!(idx.find_hex("131")?, Some(2)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
773 |
assert_eq!(idx.find_hex("cafe")?, Some(3)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
774 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
775 |
idx.insert(4, "123A")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
776 |
assert_eq!(idx.find_hex("1234")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
777 |
assert_eq!(idx.find_hex("1235")?, Some(1)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
778 |
assert_eq!(idx.find_hex("131")?, Some(2)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
779 |
assert_eq!(idx.find_hex("cafe")?, Some(3)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
780 |
assert_eq!(idx.find_hex("123A")?, Some(4)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
781 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
782 |
idx.insert(5, "c0")?; |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
783 |
assert_eq!(idx.find_hex("cafe")?, Some(3)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
784 |
assert_eq!(idx.find_hex("c0")?, Some(5)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
785 |
assert_eq!(idx.find_hex("c1")?, None); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
786 |
assert_eq!(idx.find_hex("1234")?, Some(0)); |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
787 |
|
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
788 |
Ok(()) |
d2da8667125b
rust-nodemap: insert method
Georges Racinet <georges.racinet@octobus.net>
parents:
44186
diff
changeset
|
789 |
} |
44142
63db6657d280
rust-nodemap: building blocks for nodetree structures
Georges Racinet <georges.racinet@octobus.net>
parents:
diff
changeset
|
790 |
} |