other: deduplicate sorts, always sort proc by PID first (#898)

* other: deduplicate sorts, sort proc by PID by default

* add proc test

* remove sort in Windows

* fix tree

* fix test

* Remove mut

* Add comment on sorting processes

12 files changed, 163 insertions, 68 deletions

diff --git a/src/app/data_farmer.rs b/src/app/data_farmer.rs
index 2749c9bc..efbc5799 100644
--- a/src/app/data_farmer.rs
+++ b/src/app/data_farmer.rs
@@ -13,10 +13,9 @@
 //! memory usage and higher CPU usage - you will be trying to process more and
 //! more points as this is used!
 
-use std::{time::Instant, vec::Vec};
+use std::{collections::BTreeMap, time::Instant, vec::Vec};
 
 use fxhash::FxHashMap;
-use itertools::Itertools;
 use once_cell::sync::Lazy;
 use regex::Regex;
 
@@ -48,7 +47,7 @@ pub struct TimedData {
 #[derive(Clone, Debug, Default)]
 pub struct ProcessData {
     /// A PID to process data map.
-    pub process_harvest: FxHashMap<Pid, ProcessHarvest>,
+    pub process_harvest: BTreeMap<Pid, ProcessHarvest>,
 
     /// A mapping between a process PID to any children process PIDs.
     pub process_parent_mapping: FxHashMap<Pid, Vec<Pid>>,
@@ -84,22 +83,14 @@ impl ProcessData {
         // We collect all processes that either:
         // - Do not have a parent PID (that is, they are orphan processes)
         // - Have a parent PID but we don't have the parent (we promote them as orphans)
-        // Note this also needs a quick sort + reverse to be in the correct order.
-        self.orphan_pids = {
-            let mut res: Vec<Pid> = self
-                .process_harvest
-                .iter()
-                .filter_map(|(pid, process_harvest)| match process_harvest.parent_pid {
-                    Some(parent_pid) if self.process_harvest.contains_key(&parent_pid) => None,
-                    _ => Some(*pid),
-                })
-                .sorted()
-                .collect();
-
-            res.reverse();
-
-            res
-        }
+        self.orphan_pids = self
+            .process_harvest
+            .iter()
+            .filter_map(|(pid, process_harvest)| match process_harvest.parent_pid {
+                Some(parent_pid) if self.process_harvest.contains_key(&parent_pid) => None,
+                _ => Some(*pid),
+            })
+            .collect();
     }
 }
 
diff --git a/src/app/data_harvester.rs b/src/app/data_harvester.rs
index 08f184d1..25913077 100644
--- a/src/app/data_harvester.rs
+++ b/src/app/data_harvester.rs
@@ -321,7 +321,7 @@ impl DataCollector {
         }
 
         if self.widgets_to_harvest.use_proc {
-            if let Ok(process_list) = {
+            if let Ok(mut process_list) = {
                 #[cfg(target_os = "linux")]
                 {
                     processes::get_process_data(
@@ -357,6 +357,9 @@ impl DataCollector {
                     }
                 }
             } {
+                // NB: To avoid duplicate sorts on rerenders/events, we sort the processes by PID here.
+                // We also want to avoid re-sorting *again* since this process list is sorted!
+                process_list.sort_unstable_by_key(|p| p.pid);
                 self.data.list_of_processes = Some(process_list);
             }
         }
diff --git a/src/app/data_harvester/disks/freebsd.rs b/src/app/data_harvester/disks/freebsd.rs
index d657931b..5c6f6e80 100644
--- a/src/app/data_harvester/disks/freebsd.rs
+++ b/src/app/data_harvester/disks/freebsd.rs
@@ -46,7 +46,7 @@ pub async fn get_disk_usage(
         return Ok(None);
     }
 
-    let mut vec_disks: Vec<DiskHarvest> = get_disk_info().map(|storage_system_information| {
+    let vec_disks: Vec<DiskHarvest> = get_disk_info().map(|storage_system_information| {
         storage_system_information
             .filesystem
             .into_iter()
@@ -80,7 +80,6 @@ pub async fn get_disk_usage(
             .collect()
     })?;
 
-    vec_disks.sort_by(|a, b| a.name.cmp(&b.name));
     Ok(Some(vec_disks))
 }
 
diff --git a/src/app/data_harvester/disks/heim.rs b/src/app/data_harvester/disks/heim.rs
index 85608858..70840aba 100644
--- a/src/app/data_harvester/disks/heim.rs
+++ b/src/app/data_harvester/disks/heim.rs
@@ -135,7 +135,5 @@ pub async fn get_disk_usage(
         }
     }
 
-    vec_disks.sort_by(|a, b| a.name.cmp(&b.name));
-
     Ok(Some(vec_disks))
 }
diff --git a/src/app/data_harvester/temperature.rs b/src/app/data_harvester/temperature.rs
index a9855f51..48d98ad2 100644
--- a/src/app/data_harvester/temperature.rs
+++ b/src/app/data_harvester/temperature.rs
@@ -16,8 +16,6 @@ cfg_if::cfg_if! {
 #[cfg(feature = "nvidia")]
 pub mod nvidia;
 
-use std::cmp::Ordering;
-
 use crate::app::Filter;
 
 #[derive(Default, Debug, Clone)]
@@ -65,20 +63,3 @@ fn is_temp_filtered(filter: &Option<Filter>, text: &str) -> bool {
         true
     }
 }
-
-fn temp_vec_sort(temperature_vec: &mut [TempHarvest]) {
-    // By default, sort temperature, then by alphabetically!
-    // TODO: [TEMPS] Allow users to control this.
-
-    // Note we sort in reverse here; we want greater temps to be higher priority.
-    temperature_vec.sort_by(|a, b| match a.temperature.partial_cmp(&b.temperature) {
-        Some(x) => match x {
-            Ordering::Less => Ordering::Greater,
-            Ordering::Greater => Ordering::Less,
-            Ordering::Equal => Ordering::Equal,
-        },
-        None => Ordering::Equal,
-    });
-
-    temperature_vec.sort_by(|a, b| a.name.partial_cmp(&b.name).unwrap_or(Ordering::Equal));
-}
diff --git a/src/app/data_harvester/temperature/linux.rs b/src/app/data_harvester/temperature/linux.rs
index 0bca3649..166af3db 100644
--- a/src/app/data_harvester/temperature/linux.rs
+++ b/src/app/data_harvester/temperature/linux.rs
@@ -4,7 +4,7 @@ use std::{fs, path::Path};
 
 use anyhow::{anyhow, Result};
 
-use super::{is_temp_filtered, temp_vec_sort, TempHarvest, TemperatureType};
+use super::{is_temp_filtered, TempHarvest, TemperatureType};
 use crate::app::{
     data_harvester::temperature::{convert_celsius_to_fahrenheit, convert_celsius_to_kelvin},
     Filter,
@@ -245,6 +245,5 @@ pub fn get_temperature_data(
         super::nvidia::add_nvidia_data(&mut temperature_vec, temp_type, filter)?;
     }
 
-    temp_vec_sort(&mut temperature_vec);
     Ok(Some(temperature_vec))
 }
diff --git a/src/app/data_harvester/temperature/sysinfo.rs b/src/app/data_harvester/temperature/sysinfo.rs
index 83a15094..c1e11527 100644
--- a/src/app/data_harvester/temperature/sysinfo.rs
+++ b/src/app/data_harvester/temperature/sysinfo.rs
@@ -3,8 +3,8 @@
 use anyhow::Result;
 
 use super::{
-    convert_celsius_to_fahrenheit, convert_celsius_to_kelvin, is_temp_filtered, temp_vec_sort,
-    TempHarvest, TemperatureType,
+    convert_celsius_to_fahrenheit, convert_celsius_to_kelvin, is_temp_filtered, TempHarvest,
+    TemperatureType,
 };
 use crate::app::Filter;
 
@@ -38,6 +38,5 @@ pub fn get_temperature_data(
         super::nvidia::add_nvidia_data(&mut temperature_vec, temp_type, filter)?;
     }
 
-    temp_vec_sort(&mut temperature_vec);
     Ok(Some(temperature_vec))
 }
diff --git a/src/app/widgets/disk_table.rs b/src/app/widgets/disk_table.rs
index 0d2bb1c3..1d4cc604 100644
--- a/src/app/widgets/disk_table.rs
+++ b/src/app/widgets/disk_table.rs
@@ -13,7 +13,7 @@ use crate::{
     utils::gen_util::{get_decimal_bytes, sort_partial_fn, truncate_text},
 };
 
-#[derive(Clone)]
+#[derive(Clone, Debug)]
 pub struct DiskWidgetData {
     pub name: KString,
     pub mount_point: KString,
diff --git a/src/app/widgets/process_table.rs b/src/app/widgets/process_table.rs
index cb630aac..b4fabc7a 100644
--- a/src/app/widgets/process_table.rs
+++ b/src/app/widgets/process_table.rs
@@ -1,4 +1,4 @@
-use std::borrow::Cow;
+use std::{borrow::Cow, collections::BTreeMap};
 
 use fxhash::{FxHashMap, FxHashSet};
 use itertools::Itertools;
@@ -13,7 +13,7 @@ use crate::{
     canvas::canvas_colours::CanvasColours,
     components::data_table::{
         Column, ColumnHeader, ColumnWidthBounds, DataTable, DataTableColumn, DataTableProps,
-        DataTableStyling, SortColumn, SortDataTable, SortDataTableProps, SortOrder,
+        DataTableStyling, SortColumn, SortDataTable, SortDataTableProps, SortOrder, SortsRow,
     },
     Pid,
 };
@@ -384,7 +384,9 @@ impl ProcWidget {
             })
             .collect_vec();
 
-        self.try_sort(&mut stack);
+        stack.sort_unstable_by_key(|p| p.pid);
+        self.try_sort_skip_pid_asc(&mut stack);
+        stack.reverse();
 
         let mut length_stack = vec![stack.len()];
 
@@ -447,6 +449,7 @@ impl ProcWidget {
                 data.push(process.prefix(Some(prefix)).disabled(disabled));
 
                 if let Some(children_pids) = filtered_tree.get(&pid) {
+                    // TODO: Can probably use static strings for prefixes rather than allocating.
                     if prefixes.is_empty() {
                         prefixes.push(String::default());
                     } else {
@@ -485,7 +488,7 @@ impl ProcWidget {
     }
 
     fn get_normal_data(
-        &mut self, process_harvest: &FxHashMap<Pid, ProcessHarvest>,
+        &mut self, process_harvest: &BTreeMap<Pid, ProcessHarvest>,
     ) -> Vec<ProcWidgetData> {
         let search_query = self.get_query();
         let is_using_command = self.is_using_command();
@@ -545,18 +548,11 @@ impl ProcWidget {
         };
 
         self.id_pid_map = id_pid_map;
-        self.try_sort(&mut filtered_data);
+        self.try_sort_skip_pid_asc(&mut filtered_data);
         filtered_data
     }
 
     #[inline(always)]
-    fn try_sort(&self, filtered_data: &mut [ProcWidgetData]) {
-        if let Some(column) = self.table.columns.get(self.table.sort_index()) {
-            column.sort_by(filtered_data, self.table.order());
-        }
-    }
-
-    #[inline(always)]
     fn try_rev_sort(&self, filtered_data: &mut [ProcWidgetData]) {
         if let Some(column) = self.table.columns.get(self.table.sort_index()) {
             column.sort_by(
@@ -570,6 +566,16 @@ impl ProcWidget {
     }
 
     #[inline(always)]
+    fn try_sort_skip_pid_asc(&self, filtered_data: &mut [ProcWidgetData]) {
+        if let Some(column) = self.table.columns.get(self.table.sort_index()) {
+            let column = column.inner();
+            let descending = matches!(self.table.order(), SortOrder::Descending);
+
+            sort_skip_pid_asc(column, filtered_data, descending);
+        }
+    }
+
+    #[inline(always)]
     fn get_mut_proc_col(&mut self, index: usize) -> Option<&mut ProcColumn> {
         self.table.columns.get_mut(index).map(|col| col.inner_mut())
     }
@@ -855,3 +861,113 @@ impl ProcWidget {
         self.force_rerender_and_update();
     }
 }
+
+fn sort_skip_pid_asc(column: &ProcColumn, data: &mut [ProcWidgetData], descending: bool) {
+    match column {
+        ProcColumn::Pid if !descending => {}
+        _ => {
+            column.sort_data(data, descending);
+        }
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use crate::app::widgets::MemUsage;
+
+    #[test]
+    fn sorting_trees() {
+        // FIXME: Add a test for this...
+    }
+
+    #[test]
+    fn test_proc_sort() {
+        let a = ProcWidgetData {
+            pid: 1,
+            ppid: None,
+            id: "A".into(),
+            cpu_usage_percent: 0.0,
+            mem_usage: MemUsage::Percent(1.1),
+            rps: 0,
+            wps: 0,
+            total_read: 0,
+            total_write: 0,
+            process_state: "N/A".to_string(),
+            process_char: '?',
+            #[cfg(target_family = "unix")]
+            user: "root".to_string(),
+            num_similar: 0,
+            disabled: false,
+        };
+
+        let b = ProcWidgetData {
+            pid: 2,
+            id: "B".into(),
+            cpu_usage_percent: 1.1,
+            mem_usage: MemUsage::Percent(2.2),
+            ..(a.clone())
+        };
+
+        let c = ProcWidgetData {
+            pid: 3,
+            id: "C".into(),
+            cpu_usage_percent: 2.2,
+            mem_usage: MemUsage::Percent(0.0),
+            ..(a.clone())
+        };
+
+        let d = ProcWidgetData {
+            pid: 4,
+            id: "D".into(),
+            cpu_usage_percent: 0.0,
+            mem_usage: MemUsage::Percent(0.0),
+            ..(a.clone())
+        };
+
+        let mut data = vec![d.clone(), b.clone(), c.clone(), a.clone()];
+
+        // Assume we had sorted over by pid.
+        data.sort_by_key(|p| p.pid);
+        sort_skip_pid_asc(&ProcColumn::CpuPercent, &mut data, true);
+        assert_eq!(
+            vec![&c, &b, &a, &d]
+                .iter()
+                .map(|d| (d.pid))
+                .collect::<Vec<_>>(),
+            data.iter().map(|d| (d.pid)).collect::<Vec<_>>(),
+        );
+
+        // Note that the PID ordering for ties is still ascending.
+        data.sort_by_key(|p| p.pid);
+        sort_skip_pid_asc(&ProcColumn::CpuPercent, &mut data, false);
+        assert_eq!(
+            vec![&a, &d, &b, &c]
+                .iter()
+                .map(|d| (d.pid))
+                .collect::<Vec<_>>(),
+            data.iter().map(|d| (d.pid)).collect::<Vec<_>>(),
+        );
+
+        data.sort_by_key(|p| p.pid);
+        sort_skip_pid_asc(&ProcColumn::MemoryPercent, &mut data, true);
+        assert_eq!(
+            vec![&b, &a, &c, &d]
+                .iter()
+                .map(|d| (d.pid))
+                .collect::<Vec<_>>(),
+            data.iter().map(|d| (d.pid)).collect::<Vec<_>>(),
+        );
+
+        // Note that the PID ordering for ties is still ascending.
+        data.sort_by_key(|p| p.pid);
+        sort_skip_pid_asc(&ProcColumn::MemoryPercent, &mut data, false);
+        assert_eq!(
+            vec![&c, &d, &a, &b]
+                .iter()
+                .map(|d| (d.pid))
+                .collect::<Vec<_>>(),
+            data.iter().map(|d| (d.pid)).collect::<Vec<_>>(),
+        );
+    }
+}
diff --git a/src/app/widgets/process_table/proc_widget_data.rs b/src/app/widgets/process_table/proc_widget_data.rs
index acb33af4..94736336 100644
--- a/src/app/widgets/process_table/proc_widget_data.rs
+++ b/src/app/widgets/process_table/proc_widget_data.rs
@@ -16,18 +16,27 @@ use crate::{
     Pid,
 };
 
-#[derive(Clone)]
+#[derive(Clone, Debug)]
 enum IdType {
     Name(String),
     Command(String),
 }
 
-#[derive(Clone)]
+#[derive(Clone, Debug)]
 pub struct Id {
     id_type: IdType,
     prefix: Option<String>,
 }
 
+impl From<&'static str> for Id {
+    fn from(s: &'static str) -> Self {
+        Id {
+            id_type: IdType::Name(s.to_string()),
+            prefix: None,
+        }
+    }
+}
+
 impl Id {
     /// Returns the ID as a lowercase [`String`], with no prefix. This is primarily useful for
     /// cases like sorting where we treat everything as the same case (e.g. `Discord` comes before
@@ -73,7 +82,7 @@ impl Display for Id {
 }
 
 // TODO: Can reduce this to 32 bytes.
-#[derive(PartialEq, Clone)]
+#[derive(PartialEq, Clone, Debug)]
 pub enum MemUsage {
     Percent(f64),
     Bytes(u64),
@@ -98,7 +107,7 @@ impl Display for MemUsage {
     }
 }
 
-#[derive(Clone)]
+#[derive(Clone, Debug)]
 pub struct ProcWidgetData {
     pub pid: Pid,
     pub ppid: Option<Pid>,
diff --git a/src/app/widgets/temperature_table.rs b/src/app/widgets/temperature_table.rs
index a19d1fe5..b7ee16a2 100644
--- a/src/app/widgets/temperature_table.rs
+++ b/src/app/widgets/temperature_table.rs
@@ -14,7 +14,7 @@ use crate::{
     utils::gen_util::{sort_partial_fn, truncate_text},
 };
 
-#[derive(Clone)]
+#[derive(Clone, Debug)]
 pub struct TempWidgetData {
     pub sensor: KString,
     pub temperature_value: u64,
@@ -78,7 +78,7 @@ impl SortsRow for TempWidgetColumn {
     fn sort_data(&self, data: &mut [Self::DataType], descending: bool) {
         match self {
             TempWidgetColumn::Sensor => {
-                data.sort_by(|a, b| sort_partial_fn(descending)(&a.sensor, &b.sensor));
+                data.sort_by(move |a, b| sort_partial_fn(descending)(&a.sensor, &b.sensor));
             }
             TempWidgetColumn::Temp => {
                 data.sort_by(|a, b| {
diff --git a/src/utils/gen_util.rs b/src/utils/gen_util.rs
index 2af9d1b0..3a482937 100644
--- a/src/utils/gen_util.rs
+++ b/src/utils/gen_util.rs
@@ -111,7 +111,7 @@ pub fn truncate_text<'a, U: Into<usize>>(content: &str, width: U) -> Text<'a> {
 }
 
 #[inline]
-pub fn sort_partial_fn<T: std::cmp::PartialOrd>(is_descending: bool) -> fn(T, T) -> Ordering {
+pub const fn sort_partial_fn<T: std::cmp::PartialOrd>(is_descending: bool) -> fn(T, T) -> Ordering {
     if is_descending {
         partial_ordering_desc
     } else {