##// END OF EJS Templates
rust-nodemap: pure Rust example...
Georges Racinet -
r44870:8f7c6656 default
parent child Browse files
Show More
@@ -0,0 +1,95 b''
1 // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net>
2 //
3 // This software may be used and distributed according to the terms of the
4 // GNU General Public License version 2 or any later version.
5
6 //! Minimal `RevlogIndex`, readable from standard Mercurial file format
7 use hg::*;
8 use memmap::*;
9 use std::fs::File;
10 use std::ops::Deref;
11 use std::path::Path;
12 use std::slice;
13
14 pub struct Index {
15 data: Box<dyn Deref<Target = [IndexEntry]> + Send>,
16 }
17
18 /// A fixed sized index entry. All numbers are big endian
19 #[repr(C)]
20 pub struct IndexEntry {
21 not_used_yet: [u8; 24],
22 p1: Revision,
23 p2: Revision,
24 node: Node,
25 unused_node: [u8; 12],
26 }
27
28 pub const INDEX_ENTRY_SIZE: usize = 64;
29
30 impl IndexEntry {
31 fn parents(&self) -> [Revision; 2] {
32 [Revision::from_be(self.p1), Revision::from_be(self.p1)]
33 }
34 }
35
36 impl RevlogIndex for Index {
37 fn len(&self) -> usize {
38 self.data.len()
39 }
40
41 fn node(&self, rev: Revision) -> Option<&Node> {
42 if rev == NULL_REVISION {
43 return None;
44 }
45 let i = rev as usize;
46 if i >= self.len() {
47 None
48 } else {
49 Some(&self.data[i].node)
50 }
51 }
52 }
53
54 impl Graph for &Index {
55 fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
56 let [p1, p2] = (*self).data[rev as usize].parents();
57 let len = (*self).len();
58 if p1 < NULL_REVISION
59 || p2 < NULL_REVISION
60 || p1 as usize >= len
61 || p2 as usize >= len
62 {
63 return Err(GraphError::ParentOutOfRange(rev));
64 }
65 Ok([p1, p2])
66 }
67 }
68
69 struct IndexMmap(Mmap);
70
71 impl Deref for IndexMmap {
72 type Target = [IndexEntry];
73
74 fn deref(&self) -> &[IndexEntry] {
75 let ptr = self.0.as_ptr() as *const IndexEntry;
76 // Any misaligned data will be ignored.
77 debug_assert_eq!(
78 self.0.len() % std::mem::align_of::<IndexEntry>(),
79 0,
80 "Misaligned data in mmap"
81 );
82 unsafe { slice::from_raw_parts(ptr, self.0.len() / INDEX_ENTRY_SIZE) }
83 }
84 }
85
86 impl Index {
87 pub fn load_mmap(path: impl AsRef<Path>) -> Self {
88 let file = File::open(path).unwrap();
89 let msg = "Index file is missing, or missing permission";
90 let mmap = unsafe { MmapOptions::new().map(&file) }.expect(msg);
91 Self {
92 data: Box::new(IndexMmap(mmap)),
93 }
94 }
95 }
@@ -0,0 +1,146 b''
1 // Copyright 2019-2020 Georges Racinet <georges.racinet@octobus.net>
2 //
3 // This software may be used and distributed according to the terms of the
4 // GNU General Public License version 2 or any later version.
5
6 use clap::*;
7 use hg::revlog::node::*;
8 use hg::revlog::nodemap::*;
9 use hg::revlog::*;
10 use memmap::MmapOptions;
11 use rand::Rng;
12 use std::fs::File;
13 use std::io;
14 use std::io::Write;
15 use std::path::{Path, PathBuf};
16 use std::str::FromStr;
17 use std::time::Instant;
18
19 mod index;
20 use index::Index;
21
22 fn mmap_index(repo_path: &Path) -> Index {
23 let mut path = PathBuf::from(repo_path);
24 path.extend([".hg", "store", "00changelog.i"].iter());
25 Index::load_mmap(path)
26 }
27
28 fn mmap_nodemap(path: &Path) -> NodeTree {
29 let file = File::open(path).unwrap();
30 let mmap = unsafe { MmapOptions::new().map(&file).unwrap() };
31 let len = mmap.len();
32 NodeTree::load_bytes(Box::new(mmap), len)
33 }
34
35 /// Scan the whole index and create the corresponding nodemap file at `path`
36 fn create(index: &Index, path: &Path) -> io::Result<()> {
37 let mut file = File::create(path)?;
38 let start = Instant::now();
39 let mut nm = NodeTree::default();
40 for rev in 0..index.len() {
41 let rev = rev as Revision;
42 nm.insert(index, index.node(rev).unwrap(), rev).unwrap();
43 }
44 eprintln!("Nodemap constructed in RAM in {:?}", start.elapsed());
45 file.write(&nm.into_readonly_and_added_bytes().1)?;
46 eprintln!("Nodemap written to disk");
47 Ok(())
48 }
49
50 fn query(index: &Index, nm: &NodeTree, prefix: &str) {
51 let start = Instant::now();
52 let res = nm.find_hex(index, prefix);
53 println!("Result found in {:?}: {:?}", start.elapsed(), res);
54 }
55
56 fn bench(index: &Index, nm: &NodeTree, queries: usize) {
57 let len = index.len() as u32;
58 let mut rng = rand::thread_rng();
59 let nodes: Vec<Node> = (0..queries)
60 .map(|_| {
61 index
62 .node((rng.gen::<u32>() % len) as Revision)
63 .unwrap()
64 .clone()
65 })
66 .collect();
67 if queries < 10 {
68 let nodes_hex: Vec<String> =
69 nodes.iter().map(|n| n.encode_hex()).collect();
70 println!("Nodes: {:?}", nodes_hex);
71 }
72 let mut last: Option<Revision> = None;
73 let start = Instant::now();
74 for node in nodes.iter() {
75 last = nm.find_bin(index, node.into()).unwrap();
76 }
77 let elapsed = start.elapsed();
78 println!(
79 "Did {} queries in {:?} (mean {:?}), last was {:?} with result {:?}",
80 queries,
81 elapsed,
82 elapsed / (queries as u32),
83 nodes.last().unwrap().encode_hex(),
84 last
85 );
86 }
87
88 fn main() {
89 let matches = App::new("Nodemap pure Rust example")
90 .arg(
91 Arg::with_name("REPOSITORY")
92 .help("Path to the repository, always necessary for its index")
93 .required(true),
94 )
95 .arg(
96 Arg::with_name("NODEMAP_FILE")
97 .help("Path to the nodemap file, independent of REPOSITORY")
98 .required(true),
99 )
100 .subcommand(
101 SubCommand::with_name("create")
102 .about("Create NODEMAP_FILE by scanning repository index"),
103 )
104 .subcommand(
105 SubCommand::with_name("query")
106 .about("Query NODEMAP_FILE for PREFIX")
107 .arg(Arg::with_name("PREFIX").required(true)),
108 )
109 .subcommand(
110 SubCommand::with_name("bench")
111 .about(
112 "Perform #QUERIES random successful queries on NODEMAP_FILE")
113 .arg(Arg::with_name("QUERIES").required(true)),
114 )
115 .get_matches();
116
117 let repo = matches.value_of("REPOSITORY").unwrap();
118 let nm_path = matches.value_of("NODEMAP_FILE").unwrap();
119
120 let index = mmap_index(&Path::new(repo));
121
122 if let Some(_) = matches.subcommand_matches("create") {
123 println!("Creating nodemap file {} for repository {}", nm_path, repo);
124 create(&index, &Path::new(nm_path)).unwrap();
125 return;
126 }
127
128 let nm = mmap_nodemap(&Path::new(nm_path));
129 if let Some(matches) = matches.subcommand_matches("query") {
130 let prefix = matches.value_of("PREFIX").unwrap();
131 println!(
132 "Querying {} in nodemap file {} of repository {}",
133 prefix, nm_path, repo
134 );
135 query(&index, &nm, prefix);
136 }
137 if let Some(matches) = matches.subcommand_matches("bench") {
138 let queries =
139 usize::from_str(matches.value_of("QUERIES").unwrap()).unwrap();
140 println!(
141 "Doing {} random queries in nodemap file {} of repository {}",
142 queries, nm_path, repo
143 );
144 bench(&index, &nm, queries);
145 }
146 }
@@ -17,6 +17,16 b' dependencies = ['
17 17 ]
18 18
19 19 [[package]]
20 name = "atty"
21 version = "0.2.14"
22 source = "registry+https://github.com/rust-lang/crates.io-index"
23 dependencies = [
24 "hermit-abi 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)",
25 "libc 0.2.66 (registry+https://github.com/rust-lang/crates.io-index)",
26 "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)",
27 ]
28
29 [[package]]
20 30 name = "autocfg"
21 31 version = "0.1.7"
22 32 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -55,6 +65,20 b' version = "0.1.10"'
55 65 source = "registry+https://github.com/rust-lang/crates.io-index"
56 66
57 67 [[package]]
68 name = "clap"
69 version = "2.33.0"
70 source = "registry+https://github.com/rust-lang/crates.io-index"
71 dependencies = [
72 "ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
73 "atty 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)",
74 "bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)",
75 "strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
76 "textwrap 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
77 "unicode-width 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
78 "vec_map 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)",
79 ]
80
81 [[package]]
58 82 name = "cloudabi"
59 83 version = "0.0.3"
60 84 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -167,10 +191,12 b' version = "0.1.0"'
167 191 dependencies = [
168 192 "byteorder 1.3.2 (registry+https://github.com/rust-lang/crates.io-index)",
169 193 "cc 1.0.50 (registry+https://github.com/rust-lang/crates.io-index)",
194 "clap 2.33.0 (registry+https://github.com/rust-lang/crates.io-index)",
170 195 "hex 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
171 196 "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
172 197 "libc 0.2.66 (registry+https://github.com/rust-lang/crates.io-index)",
173 198 "memchr 2.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
199 "memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)",
174 200 "pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
175 201 "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)",
176 202 "rand_pcg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -214,6 +240,15 b' version = "2.3.0"'
214 240 source = "registry+https://github.com/rust-lang/crates.io-index"
215 241
216 242 [[package]]
243 name = "memmap"
244 version = "0.7.0"
245 source = "registry+https://github.com/rust-lang/crates.io-index"
246 dependencies = [
247 "libc 0.2.66 (registry+https://github.com/rust-lang/crates.io-index)",
248 "winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)",
249 ]
250
251 [[package]]
217 252 name = "memoffset"
218 253 version = "0.5.3"
219 254 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -523,6 +558,11 b' version = "0.7.0"'
523 558 source = "registry+https://github.com/rust-lang/crates.io-index"
524 559
525 560 [[package]]
561 name = "strsim"
562 version = "0.8.0"
563 source = "registry+https://github.com/rust-lang/crates.io-index"
564
565 [[package]]
526 566 name = "syn"
527 567 version = "1.0.14"
528 568 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -546,6 +586,14 b' dependencies = ['
546 586 ]
547 587
548 588 [[package]]
589 name = "textwrap"
590 version = "0.11.0"
591 source = "registry+https://github.com/rust-lang/crates.io-index"
592 dependencies = [
593 "unicode-width 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)",
594 ]
595
596 [[package]]
549 597 name = "thread_local"
550 598 version = "1.0.1"
551 599 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -562,11 +610,21 b' dependencies = ['
562 610 ]
563 611
564 612 [[package]]
613 name = "unicode-width"
614 version = "0.1.7"
615 source = "registry+https://github.com/rust-lang/crates.io-index"
616
617 [[package]]
565 618 name = "unicode-xid"
566 619 version = "0.2.0"
567 620 source = "registry+https://github.com/rust-lang/crates.io-index"
568 621
569 622 [[package]]
623 name = "vec_map"
624 version = "0.8.1"
625 source = "registry+https://github.com/rust-lang/crates.io-index"
626
627 [[package]]
570 628 name = "wasi"
571 629 version = "0.9.0+wasi-snapshot-preview1"
572 630 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -601,6 +659,7 b' source = "registry+https://github.com/ru'
601 659 [metadata]
602 660 "checksum aho-corasick 0.7.8 (registry+https://github.com/rust-lang/crates.io-index)" = "743ad5a418686aad3b87fd14c43badd828cf26e214a00f92a384291cf22e1811"
603 661 "checksum ansi_term 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ee49baf6cb617b853aa8d93bf420db2383fab46d314482ca2803b40d5fde979b"
662 "checksum atty 0.2.14 (registry+https://github.com/rust-lang/crates.io-index)" = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8"
604 663 "checksum autocfg 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "1d49d90015b3c36167a20fe2810c5cd875ad504b39cff3d4eae7977e6b7c1cb2"
605 664 "checksum autocfg 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "f8aac770f1885fd7e387acedd76065302551364496e46b3dd00860b2f8359b9d"
606 665 "checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
@@ -608,6 +667,7 b' source = "registry+https://github.com/ru'
608 667 "checksum c2-chacha 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "214238caa1bf3a496ec3392968969cab8549f96ff30652c9e56885329315f6bb"
609 668 "checksum cc 1.0.50 (registry+https://github.com/rust-lang/crates.io-index)" = "95e28fa049fda1c330bcf9d723be7663a899c4679724b34c81e9f5a326aab8cd"
610 669 "checksum cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"
670 "checksum clap 2.33.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9"
611 671 "checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
612 672 "checksum cpython 0.4.1 (registry+https://github.com/rust-lang/crates.io-index)" = "bfaf3847ab963e40c4f6dd8d6be279bdf74007ae2413786a0dcbb28c52139a95"
613 673 "checksum crossbeam-deque 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "c3aa945d63861bfe624b55d153a39684da1e8c0bc8fba932f7ee3a3c16cea3ca"
@@ -624,6 +684,7 b' source = "registry+https://github.com/ru'
624 684 "checksum lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646"
625 685 "checksum libc 0.2.66 (registry+https://github.com/rust-lang/crates.io-index)" = "d515b1f41455adea1313a4a2ac8a8a477634fbae63cc6100e3aebb207ce61558"
626 686 "checksum memchr 2.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3197e20c7edb283f87c071ddfc7a2cca8f8e0b888c242959846a6fce03c72223"
687 "checksum memmap 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "6585fd95e7bb50d6cc31e20d4cf9afb4e2ba16c5846fc76793f11218da9c475b"
627 688 "checksum memoffset 0.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "75189eb85871ea5c2e2c15abbdd541185f63b408415e5051f5cac122d8c774b9"
628 689 "checksum num-traits 0.2.11 (registry+https://github.com/rust-lang/crates.io-index)" = "c62be47e61d1842b9170f0fdeec8eba98e60e90e5446449a0545e5152acd7096"
629 690 "checksum num_cpus 1.12.0 (registry+https://github.com/rust-lang/crates.io-index)" = "46203554f085ff89c235cd12f7075f3233af9b11ed7c9e16dfe2560d03313ce6"
@@ -660,11 +721,15 b' source = "registry+https://github.com/ru'
660 721 "checksum scopeguard 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "b42e15e59b18a828bbf5c58ea01debb36b9b096346de35d941dcb89009f24a0d"
661 722 "checksum semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403"
662 723 "checksum semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3"
724 "checksum strsim 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)" = "8ea5119cdb4c55b55d432abb513a0429384878c15dde60cc77b1c99de1a95a6a"
663 725 "checksum syn 1.0.14 (registry+https://github.com/rust-lang/crates.io-index)" = "af6f3550d8dff9ef7dc34d384ac6f107e5d31c8f57d9f28e0081503f547ac8f5"
664 726 "checksum tempfile 3.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6e24d9338a0a5be79593e2fa15a648add6138caa803e2d5bc782c371732ca9"
727 "checksum textwrap 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d326610f408c7a4eb6f51c37c330e496b08506c9457c9d34287ecc38809fb060"
665 728 "checksum thread_local 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)" = "d40c6d1b69745a6ec6fb1ca717914848da4b44ae29d9b3080cbee91d72a69b14"
666 729 "checksum twox-hash 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "3bfd5b7557925ce778ff9b9ef90e3ade34c524b5ff10e239c69a42d546d2af56"
730 "checksum unicode-width 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "caaa9d531767d1ff2150b9332433f32a24622147e5ebb1f26409d5da67afd479"
667 731 "checksum unicode-xid 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "826e7639553986605ec5979c7dd957c7895e93eabed50ab2ffa7f6128a75097c"
732 "checksum vec_map 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "05c78687fb1a80548ae3250346c3db86a80a7cdd77bda190189f2d0a0987c81a"
668 733 "checksum wasi 0.9.0+wasi-snapshot-preview1 (registry+https://github.com/rust-lang/crates.io-index)" = "cccddf32554fecc6acb585f82a32a72e28b48f8c4c1883ddfeeeaa96f7d8e519"
669 734 "checksum winapi 0.3.8 (registry+https://github.com/rust-lang/crates.io-index)" = "8093091eeb260906a183e6ae1abdba2ef5ef2257a21801128899c3fc699229c6"
670 735 "checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6"
@@ -23,8 +23,10 b' twox-hash = "1.5.0"'
23 23 same-file = "1.0.6"
24 24
25 25 [dev-dependencies]
26 clap = "*"
27 memmap = "0.7.0"
28 pretty_assertions = "0.6.1"
26 29 tempfile = "3.1.0"
27 pretty_assertions = "0.6.1"
28 30
29 31 [build-dependencies]
30 32 cc = { version = "1.0.48", optional = true }
General Comments 0
You need to be logged in to leave comments. Login now