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