Patchwork D10553: dirstate-tree: Use HashMap instead of BTreeMap

login
register
mail settings
Submitter phabricator
Date May 3, 2021, 10:28 a.m.
Message ID <differential-rev-PHID-DREV-r542liknmc3rbyikscqr-req@mercurial-scm.org>
Download mbox | patch
Permalink /patch/48872/
State Superseded
Headers show

Comments

Patch

diff --git a/rust/hg-core/src/dirstate_tree/status.rs b/rust/hg-core/src/dirstate_tree/status.rs
--- a/rust/hg-core/src/dirstate_tree/status.rs
+++ b/rust/hg-core/src/dirstate_tree/status.rs
@@ -108,9 +108,13 @@ 
             return;
         };
 
+        let mut dirstate_nodes: Vec<_> = dirstate_nodes.iter_mut().collect();
+
         // `sort_unstable_by_key` doesn’t allow keys borrowing from the value:
         // https://github.com/rust-lang/rust/issues/34162
         fs_entries.sort_unstable_by(|e1, e2| e1.base_name.cmp(&e2.base_name));
+        dirstate_nodes
+            .sort_unstable_by(|(path1, _), (path2, _)| path1.cmp(path2));
 
         // `merge_join_by` requires both its input iterators to be sorted.
         // * `BTreeMap` iterates according to keys’ ordering by definition
diff --git a/rust/hg-core/src/dirstate_tree/path_with_basename.rs b/rust/hg-core/src/dirstate_tree/path_with_basename.rs
--- a/rust/hg-core/src/dirstate_tree/path_with_basename.rs
+++ b/rust/hg-core/src/dirstate_tree/path_with_basename.rs
@@ -55,6 +55,12 @@ 
     }
 }
 
+impl<T: AsRef<HgPath>> std::hash::Hash for WithBasename<T> {
+    fn hash<H: std::hash::Hasher>(&self, hasher: &mut H) {
+        self.base_name().hash(hasher)
+    }
+}
+
 impl<T: AsRef<HgPath> + PartialEq> PartialEq for WithBasename<T> {
     fn eq(&self, other: &Self) -> bool {
         self.base_name() == other.base_name()
diff --git a/rust/hg-core/src/dirstate_tree/dirstate_map.rs b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
--- a/rust/hg-core/src/dirstate_tree/dirstate_map.rs
+++ b/rust/hg-core/src/dirstate_tree/dirstate_map.rs
@@ -1,7 +1,7 @@ 
 use bytes_cast::BytesCast;
 use micro_timer::timed;
+use std::convert::TryInto;
 use std::path::PathBuf;
-use std::{collections::BTreeMap, convert::TryInto};
 
 use super::path_with_basename::WithBasename;
 use crate::dirstate::parsers::clear_ambiguous_mtime;
@@ -20,6 +20,7 @@ 
 use crate::DirstateParents;
 use crate::DirstateStatus;
 use crate::EntryState;
+use crate::FastHashMap;
 use crate::PatternFileWarning;
 use crate::StateMapIter;
 use crate::StatusError;
@@ -43,7 +44,7 @@ 
 /// path, so comparing full paths gives the same result as comparing base
 /// names. However `BTreeMap` would waste time always re-comparing the same
 /// string prefix.
-pub(super) type ChildNodes = BTreeMap<WithBasename<HgPathBuf>, Node>;
+pub(super) type ChildNodes = FastHashMap<WithBasename<HgPathBuf>, Node>;
 
 /// Represents a file or a directory
 #[derive(Default)]
@@ -86,7 +87,7 @@ 
         Self {
             parents: None,
             dirty_parents: false,
-            root: ChildNodes::new(),
+            root: ChildNodes::default(),
             nodes_with_entry_count: 0,
             nodes_with_copy_source_count: 0,
         }