Fix: Predictable iteration order

Sort the Node objects so that duplicate inodes appear in a predictable
order.

Include new sort_by_inode method because this is notably quicker than
sorting by size & name as defined in the nodes.rs file.

1 files changed, 18 insertions, 2 deletions

diff --git a/src/dir_walker.rs b/src/dir_walker.rs
index 9aa64c8..49899ec 100644
--- a/src/dir_walker.rs
+++ b/src/dir_walker.rs
@@ -62,8 +62,10 @@ fn clean_inodes(
         }
     }
 
-    let new_children: Vec<_> = x
-        .children
+    // Sort Nodes so iteration order is predictable
+    let mut tmp: Vec<_> = x.children;
+    tmp.sort_by(sort_by_inode);
+    let new_children: Vec<_> = tmp
         .into_iter()
         .filter_map(|c| clean_inodes(c, inodes, use_apparent_size))
         .collect();
@@ -77,6 +79,20 @@ fn clean_inodes(
     })
 }
 
+fn sort_by_inode(a: &Node, b: &Node) -> std::cmp::Ordering {
+    // Sorting by inode is quicker than by sorting by name/size
+    if let Some(x) = a.inode_device {
+        if let Some(y) = b.inode_device {
+            if x.0 != y.0 {
+                return x.0.cmp(&y.0);
+            } else if x.1 != y.1 {
+                return x.1.cmp(&y.1);
+            }
+        }
+    }
+    a.name.cmp(&b.name)
+}
+
 fn ignore_file(entry: &DirEntry, walk_data: &WalkData) -> bool {
     let is_dot_file = entry.file_name().to_str().unwrap_or("").starts_with('.');
     let is_ignored_path = walk_data.ignore_directories.contains(&entry.path());