Mercurial > hg
comparison rust/hg-core/src/dirstate_tree/dirstate_map.rs @ 47103:214ae40e136b
dirstate-tree: Maintain a counter of DirstateEntry’s and copy sources
This allows implementing __len__ for DirstateMap and CopyMap efficiently,
without traversing the tree.
Differential Revision: https://phab.mercurial-scm.org/D10487
author | Simon Sapin <simon.sapin@octobus.net> |
---|---|
date | Mon, 12 Apr 2021 17:29:55 +0200 |
parents | d6c94ca40863 |
children | fdf6cfa0e254 |
comparison
equal
deleted
inserted
replaced
47102:d6c94ca40863 | 47103:214ae40e136b |
---|---|
28 | 28 |
29 pub struct DirstateMap { | 29 pub struct DirstateMap { |
30 parents: Option<DirstateParents>, | 30 parents: Option<DirstateParents>, |
31 dirty_parents: bool, | 31 dirty_parents: bool, |
32 root: ChildNodes, | 32 root: ChildNodes, |
33 | |
34 /// Number of nodes anywhere in the tree that have `.entry.is_some()`. | |
35 nodes_with_entry_count: usize, | |
36 | |
37 /// Number of nodes anywhere in the tree that have | |
38 /// `.copy_source.is_some()`. | |
39 nodes_with_copy_source_count: usize, | |
33 } | 40 } |
34 | 41 |
35 /// Using a plain `HgPathBuf` of the full path from the repository root as a | 42 /// Using a plain `HgPathBuf` of the full path from the repository root as a |
36 /// map key would also work: all paths in a given map have the same parent | 43 /// map key would also work: all paths in a given map have the same parent |
37 /// path, so comparing full paths gives the same result as comparing base | 44 /// path, so comparing full paths gives the same result as comparing base |
57 pub fn new() -> Self { | 64 pub fn new() -> Self { |
58 Self { | 65 Self { |
59 parents: None, | 66 parents: None, |
60 dirty_parents: false, | 67 dirty_parents: false, |
61 root: ChildNodes::new(), | 68 root: ChildNodes::new(), |
69 nodes_with_entry_count: 0, | |
70 nodes_with_copy_source_count: 0, | |
62 } | 71 } |
63 } | 72 } |
64 | 73 |
65 fn get_node(&self, path: &HgPath) -> Option<&Node> { | 74 fn get_node(&self, path: &HgPath) -> Option<&Node> { |
66 let mut children = &self.root; | 75 let mut children = &self.root; |
76 return Some(child); | 85 return Some(child); |
77 } | 86 } |
78 } | 87 } |
79 } | 88 } |
80 | 89 |
81 fn get_or_insert_node(&mut self, path: &HgPath) -> &mut Node { | 90 /// This takes `root` instead of `&mut self` so that callers can mutate |
82 let mut child_nodes = &mut self.root; | 91 /// other fields while the returned borrow is still valid |
92 fn get_or_insert_node<'tree>( | |
93 root: &'tree mut ChildNodes, | |
94 path: &HgPath, | |
95 ) -> &'tree mut Node { | |
96 let mut child_nodes = root; | |
83 let mut inclusive_ancestor_paths = | 97 let mut inclusive_ancestor_paths = |
84 WithBasename::inclusive_ancestors_of(path); | 98 WithBasename::inclusive_ancestors_of(path); |
85 let mut ancestor_path = inclusive_ancestor_paths | 99 let mut ancestor_path = inclusive_ancestor_paths |
86 .next() | 100 .next() |
87 .expect("expected at least one inclusive ancestor"); | 101 .expect("expected at least one inclusive ancestor"); |
101 ancestor_path = next; | 115 ancestor_path = next; |
102 child_nodes = &mut child_node.children; | 116 child_nodes = &mut child_node.children; |
103 } else { | 117 } else { |
104 return child_node; | 118 return child_node; |
105 } | 119 } |
120 } | |
121 } | |
122 | |
123 /// The meaning of `new_copy_source` is: | |
124 /// | |
125 /// * `Some(Some(x))`: set `Node::copy_source` to `Some(x)` | |
126 /// * `Some(None)`: set `Node::copy_source` to `None` | |
127 /// * `None`: leave `Node::copy_source` unchanged | |
128 fn add_file_node( | |
129 &mut self, | |
130 path: &HgPath, | |
131 new_entry: DirstateEntry, | |
132 new_copy_source: Option<Option<HgPathBuf>>, | |
133 ) { | |
134 let node = Self::get_or_insert_node(&mut self.root, path); | |
135 if node.entry.is_none() { | |
136 self.nodes_with_entry_count += 1 | |
137 } | |
138 if let Some(source) = &new_copy_source { | |
139 if node.copy_source.is_none() && source.is_some() { | |
140 self.nodes_with_copy_source_count += 1 | |
141 } | |
142 if node.copy_source.is_some() && source.is_none() { | |
143 self.nodes_with_copy_source_count -= 1 | |
144 } | |
145 } | |
146 node.entry = Some(new_entry); | |
147 if let Some(source) = new_copy_source { | |
148 node.copy_source = source | |
106 } | 149 } |
107 } | 150 } |
108 | 151 |
109 fn iter_nodes<'a>( | 152 fn iter_nodes<'a>( |
110 &'a self, | 153 &'a self, |
192 fn clear(&mut self) { | 235 fn clear(&mut self) { |
193 self.set_parents(&DirstateParents { | 236 self.set_parents(&DirstateParents { |
194 p1: NULL_NODE, | 237 p1: NULL_NODE, |
195 p2: NULL_NODE, | 238 p2: NULL_NODE, |
196 }); | 239 }); |
197 self.root.clear() | 240 self.root.clear(); |
241 self.nodes_with_entry_count = 0; | |
242 self.nodes_with_copy_source_count = 0; | |
198 } | 243 } |
199 | 244 |
200 fn add_file( | 245 fn add_file( |
201 &mut self, | 246 &mut self, |
202 _filename: &HgPath, | 247 _filename: &HgPath, |
313 } | 358 } |
314 | 359 |
315 let parents = parse_dirstate_entries( | 360 let parents = parse_dirstate_entries( |
316 file_contents, | 361 file_contents, |
317 |path, entry, copy_source| { | 362 |path, entry, copy_source| { |
318 let node = self.get_or_insert_node(path); | 363 self.add_file_node( |
319 node.entry = Some(*entry); | 364 path, |
320 node.copy_source = copy_source.map(HgPath::to_owned); | 365 *entry, |
366 Some(copy_source.map(HgPath::to_owned)), | |
367 ) | |
321 }, | 368 }, |
322 )?; | 369 )?; |
323 | 370 |
324 if !self.dirty_parents { | 371 if !self.dirty_parents { |
325 self.set_parents(parents); | 372 self.set_parents(parents); |
391 > { | 438 > { |
392 todo!() | 439 todo!() |
393 } | 440 } |
394 | 441 |
395 fn copy_map_len(&self) -> usize { | 442 fn copy_map_len(&self) -> usize { |
396 todo!() | 443 self.nodes_with_copy_source_count |
397 } | 444 } |
398 | 445 |
399 fn copy_map_iter(&self) -> CopyMapIter<'_> { | 446 fn copy_map_iter(&self) -> CopyMapIter<'_> { |
400 Box::new(self.iter_nodes().filter_map(|(path, node)| { | 447 Box::new(self.iter_nodes().filter_map(|(path, node)| { |
401 node.copy_source | 448 node.copy_source |
427 ) -> Option<HgPathBuf> { | 474 ) -> Option<HgPathBuf> { |
428 todo!() | 475 todo!() |
429 } | 476 } |
430 | 477 |
431 fn len(&self) -> usize { | 478 fn len(&self) -> usize { |
432 todo!() | 479 self.nodes_with_entry_count |
433 } | 480 } |
434 | 481 |
435 fn contains_key(&self, key: &HgPath) -> bool { | 482 fn contains_key(&self, key: &HgPath) -> bool { |
436 self.get(key).is_some() | 483 self.get(key).is_some() |
437 } | 484 } |