Implement sorting in tree mode

5 files changed, 237 insertions, 67 deletions

diff --git a/Action.c b/Action.c
index 47fa6f17..66934bec 100644
--- a/Action.c
+++ b/Action.c
@@ -160,7 +160,6 @@ static bool collapseIntoParent(Panel* panel) {
 Htop_Reaction Action_setSortKey(Settings* settings, ProcessField sortKey) {
    settings->sortKey = sortKey;
    settings->direction = 1;
-   settings->treeView = false;
    return HTOP_REFRESH | HTOP_SAVE_SETTINGS | HTOP_UPDATE_PANELHDR | HTOP_KEEP_FOLLOWING;
 }
 
@@ -661,7 +660,7 @@ void Action_setBindings(Htop_Action* keys) {
    keys['['] = actionLowerPriority;
    keys[KEY_F(8)] = actionLowerPriority;
    keys['I'] = actionInvertSortOrder;
-   keys[KEY_F(6)] = actionExpandCollapseOrSortColumn;
+   keys[KEY_F(6)] = actionSetSortColumn;
    keys[KEY_F(18)] = actionExpandCollapseOrSortColumn;
    keys['<'] = actionSetSortColumn;
    keys[','] = actionSetSortColumn;
diff --git a/MainPanel.c b/MainPanel.c
index 848deae9..0f8d0e75 100644
--- a/MainPanel.c
+++ b/MainPanel.c
@@ -27,10 +27,8 @@ void MainPanel_updateTreeFunctions(MainPanel* this, bool mode) {
    FunctionBar* bar = MainPanel_getFunctionBar(this);
    if (mode) {
       FunctionBar_setLabel(bar, KEY_F(5), "Sorted");
-      FunctionBar_setLabel(bar, KEY_F(6), "Collap");
    } else {
       FunctionBar_setLabel(bar, KEY_F(5), "Tree  ");
-      FunctionBar_setLabel(bar, KEY_F(6), "SortBy");
    }
 }
 
@@ -68,7 +66,6 @@ static HandlerResult MainPanel_eventHandler(Panel* super, int ch) {
       ProcessField field = ProcessList_keyAt(pl, hx);
       if (field == settings->sortKey) {
          Settings_invertSortOrder(settings);
-         settings->treeView = false;
       } else {
          reaction |= Action_setSortKey(settings, field);
       }
diff --git a/Process.h b/Process.h
index 2fb27968..67f7bcc5 100644
--- a/Process.h
+++ b/Process.h
@@ -109,6 +109,11 @@ typedef struct Process_ {
 
    unsigned long int minflt;
    unsigned long int majflt;
+
+   unsigned int tree_left;
+   unsigned int tree_right;
+   unsigned int tree_depth;
+   unsigned int tree_index;
 } Process;
 
 typedef struct ProcessFieldData_ {
diff --git a/ProcessList.c b/ProcessList.c
index 6339546a..00457c02 100644
--- a/ProcessList.c
+++ b/ProcessList.c
@@ -8,10 +8,13 @@ in the source distribution for its full text.
 #include "ProcessList.h"
 
 #include <assert.h>
+#include <stdlib.h>
 #include <string.h>
 #include <time.h>
 
 #include "CRT.h"
+#include "Hashtable.h"
+#include "Vector.h"
 #include "XUtils.h"
 
 
@@ -25,6 +28,9 @@ ProcessList* ProcessList_init(ProcessList* this, const ObjectClass* klass, Users
    // tree-view auxiliary buffer
    this->processes2 = Vector_new(klass, true, DEFAULT_SIZE);
 
+   this->displayTreeSet = Hashtable_new(4096, false);
+   this->draftingTreeSet = Hashtable_new(4096, false);
+
    // set later by platform-specific code
    this->cpuCount = 0;
 
@@ -59,6 +65,8 @@ void ProcessList_done(ProcessList* this) {
       hwloc_topology_destroy(this->topology);
    }
 #endif
+   Hashtable_delete(this->displayTreeSet);
+   Hashtable_delete(this->draftingTreeSet);
    Hashtable_delete(this->processTable);
    Vector_delete(this->processes);
    Vector_delete(this->processes2);
@@ -77,7 +85,7 @@ void ProcessList_printHeader(ProcessList* this, RichString* header) {
          field = "- ";
       }
 
-      int color = (!this->settings->treeView && this->settings->sortKey == fields[i]) ?
+      int color = (this->settings->sortKey == fields[i]) ?
          CRT_colors[PANEL_SELECTION_FOCUS] : CRT_colors[PANEL_HEADER_FOCUS];
       RichString_append(header, color, field);
       if (COMM == fields[i] && this->settings->showMergedCommand) {
@@ -129,7 +137,130 @@ int ProcessList_size(ProcessList* this) {
    return (Vector_size(this->processes));
 }
 
-static void ProcessList_buildTree(ProcessList* this, pid_t pid, int level, int indent, int direction, bool show) {
+// ProcessList_updateTreeSetLayer sorts this->displayTreeSet,
+// relying only on itself.
+//
+// Algorithm
+//
+// The algorithm is based on `depth-first search`,
+// even though `breadth-first search` approach may be more efficient on first glance,
+// after comparision it may be not, as it's not save to go deeper without first updating the tree structure.
+// If it would be save that approach would likely bring an advantage in performance.
+//
+// Each call of the function looks for a 'layer'. A 'layer' is a list of processes with the same depth.
+// First it sorts a list. Then it runs the function recursively for each element of the sorted list.
+// After that it updates the settings of processes.
+//
+// It relies on `leftBound` and `rightBound` as an optimization to cut the list size at the time it builds a 'layer'.
+//
+// It uses a temporary Hashtable `draftingTreeSet` because it's not save to traverse a tree
+// and at the same time make changes in it.
+static void ProcessList_updateTreeSetLayer(ProcessList* this, unsigned int leftBound, unsigned int rightBound, unsigned int deep, unsigned int left, unsigned int right, unsigned int* index, unsigned int* treeIndex, int indent) {
+   // It's guaranted that layer_size is enough space
+   // but most likely it needs less. Specifically on first iteration.
+   int layerSize = (right - left) / 2;
+
+   // check if we reach `children` of `leafes`
+   if (layerSize == 0)
+      return;
+
+   Vector* layer = Vector_new(this->processes->type, false, layerSize);
+
+   // Find all processes on the same layer (process with the same `deep` value
+   // and included in a range from `leftBound` to `rightBound`.
+   //
+   // This loop also keeps track of left_bound and right_bound of these processes
+   // in order not to lose this information once the list is sorted.
+   //
+   // The variables left_bound and right_bound are different from what the values lhs and rhs represent,
+   // While left_bound and right_bound define a range of processes to look at, the values given by lhs and rhs are indices into an array
+   //
+   // In the below example note how filtering a range of indices i is different from filtering for processes in the bounds left_bound < x < right_bound …
+   //
+   // The nested tree set is sorted by left value, which is guaranteed upon entry/exit of this function.
+   //
+   // i | l | r
+   // 1 | 1 | 9
+   // 2 | 2 | 8
+   // 3 | 4 | 5
+   // 4 | 6 | 7
+   for (unsigned int i = leftBound; i < rightBound; i++) {
+      Process* proc = (Process*)Hashtable_get(this->displayTreeSet, i);
+      if (proc->tree_depth == deep && proc->tree_left > left && proc->tree_right < right) {
+         if (Vector_size(layer) > 0) {
+            Process* previous_process = (Process*)Vector_get(layer, Vector_size(layer)-1);
+            // Make a 'right_bound' of previous_process in a layer a current's process index.
+            //
+            // Use 'tree_depth' as a temporal variable.
+            // it is save to do as later 'tree_depth' will be renovated.
+            previous_process->tree_depth = proc->tree_index;
+         }
+         Vector_add(layer, proc);
+      }
+   }
+
+   // The loop above changes process-1 so the last process on the layer
+   // isn't updated by the that loop.
+   //
+   // Thus, if present, set the `rightBound` to the last process on the layer
+   if (Vector_size(layer) > 0) {
+      Process* previous_process = (Process*)Vector_get(layer, Vector_size(layer)-1);
+      previous_process->tree_depth = rightBound;
+   }
+
+   Vector_quickSort(layer);
+
+   int size = Vector_size(layer);
+   for (int i = 0; i < size; i++) {
+      Process* proc = (Process*)Vector_get(layer, i);
+
+      unsigned int idx = (*index)++;
+      int newLeft = (*treeIndex)++;
+
+      int level = deep == 0 ? 0 : (int)deep-1;
+      int currentIndent = indent == -1 ? 0 : indent | (1 << level);
+      int nextIndent = indent == -1 ? 0 : (i < size - 1) ? currentIndent : indent;
+
+      unsigned int newLeftBound = proc->tree_index;
+      unsigned int newRightBound = proc->tree_depth;
+      ProcessList_updateTreeSetLayer(this, newLeftBound, newRightBound, deep+1, proc->tree_left, proc->tree_right, index, treeIndex, nextIndent);
+
+      int newRight = (*treeIndex)++;
+
+      proc->tree_left = newLeft;
+      proc->tree_right = newRight;
+      proc->tree_index = idx;
+      proc->tree_depth = deep;
+
+      if (indent == -1) {
+         proc->indent = 0;
+      } else if (i == size - 1) {
+         proc->indent = -currentIndent;
+      } else {
+         proc->indent = currentIndent;
+      }
+
+      Hashtable_put(this->draftingTreeSet, proc->tree_index, proc);
+   }
+
+   Vector_delete(layer);
+}
+
+static void ProcessList_updateTreeSet(ProcessList* this) {
+   unsigned int index = 0;
+   unsigned int tree_index = 1;
+   int vsize = Vector_size(this->processes);
+
+   ProcessList_updateTreeSetLayer(this, 0, vsize, 0, 0, vsize*2+1, &index, &tree_index, -1);
+   assert((int)Hashtable_count(this->draftingTreeSet) == vsize);
+
+   for(int i = 0; i < vsize; i++) {
+      Process* proc = (Process*)Hashtable_remove(this->draftingTreeSet, i);
+      Hashtable_put(this->displayTreeSet, i, proc);
+   }
+}
+
+static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level, int indent, int direction, bool show, int* node_counter, int* node_index) {
    Vector* children = Vector_new(Class(Process), false, DEFAULT_SIZE);
 
    for (int i = Vector_size(this->processes) - 1; i >= 0; i--) {
@@ -139,9 +270,14 @@ static void ProcessList_buildTree(ProcessList* this, pid_t pid, int level, int i
          Vector_add(children, process);
       }
    }
+
    int size = Vector_size(children);
    for (int i = 0; i < size; i++) {
+      int index = (*node_index)++;
       Process* process = (Process*) (Vector_get(children, i));
+
+      int lft = (*node_counter)++;
+
       if (!show) {
          process->show = false;
       }
@@ -156,13 +292,20 @@ static void ProcessList_buildTree(ProcessList* this, pid_t pid, int level, int i
       assert(Vector_size(this->processes2) == s+1); (void)s;
 
       int nextIndent = indent | (1 << level);
-      ProcessList_buildTree(this, process->pid, level+1, (i < size - 1) ? nextIndent : indent, direction, show ? process->showChildren : false);
-
+      ProcessList_buildTreeBranch(this, process->pid, level+1, (i < size - 1) ? nextIndent : indent, direction, show ? process->showChildren : false, node_counter, node_index);
       if (i == size - 1) {
          process->indent = -nextIndent;
       } else {
          process->indent = nextIndent;
       }
+
+      int rht = (*node_counter)++;
+
+      process->tree_left = lft;
+      process->tree_right = rht;
+      process->tree_depth = level+1;
+      process->tree_index = index;
+      Hashtable_put(this->displayTreeSet, index, process);
    }
    Vector_delete(children);
 }
@@ -171,73 +314,94 @@ static long ProcessList_treeProcessCompare(const void* v1, const void* v2) {
    const Process *p1 = (const Process*)v1;
    const Process *p2 = (const Process*)v2;
 
-   return p1->pid - p2->pid;
+   return SPACESHIP_NUMBER(p1->tree_left, p2->tree_left);
 }
 
-void ProcessList_sort(ProcessList* this) {
-   if (!this->settings->treeView) {
-      Vector_insertionSort(this->processes);
-   } else {
-      // Save settings
-      int direction = this->settings->direction;
-      // Sort by PID
-      Vector_quickSortCustomCompare(this->processes, ProcessList_treeProcessCompare);
-      int vsize = Vector_size(this->processes);
-      // Find all processes whose parent is not visible
-      int size;
-      while ((size = Vector_size(this->processes))) {
-         int i;
-         for (i = 0; i < size; i++) {
-            Process* process = (Process*)(Vector_get(this->processes, i));
-            // Immediately consume not shown processes
-            if (!process->show) {
-               process = (Process*)(Vector_take(this->processes, i));
-               process->indent = 0;
-               Vector_add(this->processes2, process);
-               ProcessList_buildTree(this, process->pid, 0, 0, direction, false);
-               break;
-            }
-            pid_t ppid = Process_getParentPid(process);
-            // Bisect the process vector to find parent
-            int l = 0, r = size;
-            // If PID corresponds with PPID (e.g. "kernel_task" (PID:0, PPID:0)
-            // on Mac OS X 10.11.6) cancel bisecting and regard this process as
-            // root.
-            if (process->pid == ppid)
-               r = 0;
-
-            while (l < r) {
-               int c = (l + r) / 2;
-               pid_t pid = ((Process*)(Vector_get(this->processes, c)))->pid;
-               if (ppid == pid) {
-                  break;
-               } else if (ppid < pid) {
-                  r = c;
-               } else {
-                  l = c + 1;
-               }
-            }
-            // If parent not found, then construct the tree with this root
-            if (l >= r) {
-               process = (Process*)(Vector_take(this->processes, i));
-               process->indent = 0;
-               Vector_add(this->processes2, process);
-               ProcessList_buildTree(this, process->pid, 0, 0, direction, process->showChildren);
+static long ProcessList_treeProcessCompareByPID(const void* v1, const void* v2) {
+   const Process *p1 = (const Process*)v1;
+   const Process *p2 = (const Process*)v2;
+
+   return SPACESHIP_NUMBER(p1->pid, p2->pid);
+}
+
+static void ProcessList_buildTree(ProcessList* this) {
+   int node_counter = 1;
+   int node_index = 0;
+   int direction = this->settings->direction;
+   // Sort by PID
+   Vector_quickSortCustomCompare(this->processes, ProcessList_treeProcessCompareByPID);
+   int vsize = Vector_size(this->processes);
+   // Find all processes whose parent is not visible
+   int size;
+   while ((size = Vector_size(this->processes))) {
+      int i;
+      for (i = 0; i < size; i++) {
+         Process* process = (Process*)(Vector_get(this->processes, i));
+         // Immediately consume not shown processes
+         if (!process->show) {
+            process = (Process*)(Vector_take(this->processes, i));
+            process->indent = 0;
+            process->tree_depth = 0;
+            process->tree_left = (node_counter)++;
+            process->tree_index = (node_index)++;
+            Vector_add(this->processes2, process);
+            ProcessList_buildTreeBranch(this, process->pid, 0, 0, direction, false, &node_counter, &node_index);
+            process->tree_right = (node_counter)++;
+            Hashtable_put(this->displayTreeSet, process->tree_index, process);
+            break;
+         }
+         pid_t ppid = Process_getParentPid(process);
+         // Bisect the process vector to find parent
+         int l = 0, r = size;
+         // If PID corresponds with PPID (e.g. "kernel_task" (PID:0, PPID:0)
+         // on Mac OS X 10.11.6) cancel bisecting and regard this process as
+         // root.
+         if (process->pid == ppid)
+            r = 0;
+         while (l < r) {
+            int c = (l + r) / 2;
+            pid_t pid = ((Process*)(Vector_get(this->processes, c)))->pid;
+            if (ppid == pid) {
                break;
+            } else if (ppid < pid) {
+               r = c;
+            } else {
+               l = c + 1;
             }
          }
-         // There should be no loop in the process tree
-         assert(i < size);
+         // If parent not found, then construct the tree with this root
+         if (l >= r) {
+            process = (Process*)(Vector_take(this->processes, i));
+            process->indent = 0;
+            process->tree_depth = 0;
+            process->tree_left = (node_counter)++;
+            process->tree_index = (node_index)++;
+            Vector_add(this->processes2, process);
+            Hashtable_put(this->displayTreeSet, process->tree_index, process);
+            ProcessList_buildTreeBranch(this, process->pid, 0, 0, direction, process->showChildren, &node_counter, &node_index);
+            process->tree_right = (node_counter)++;
+            break;
+         }
       }
-      assert(Vector_size(this->processes2) == vsize); (void)vsize;
-      assert(Vector_size(this->processes) == 0);
-      // Swap listings around
-      Vector* t = this->processes;
-      this->processes = this->processes2;
-      this->processes2 = t;
+      // There should be no loop in the process tree
+      assert(i < size);
    }
+   assert(Vector_size(this->processes2) == vsize); (void)vsize;
+   assert(Vector_size(this->processes) == 0);
+   // Swap listings around
+   Vector* t = this->processes;
+   this->processes = this->processes2;
+   this->processes2 = t;
 }
 
+void ProcessList_sort(ProcessList* this) {
+   if (!this->settings->treeView) {
+      Vector_insertionSort(this->processes);
+   } else {
+      ProcessList_updateTreeSet(this);
+      Vector_quickSortCustomCompare(this->processes, ProcessList_treeProcessCompare);
+   }
+}
 
 ProcessField ProcessList_keyAt(const ProcessList* this, int at) {
    int x = 0;
@@ -365,4 +529,6 @@ void ProcessList_scan(ProcessList* this, bool pauseProcessUpdate) {
          p->updated = false;
       }
    }
+
+   ProcessList_buildTree(this);
 }
diff --git a/ProcessList.h b/ProcessList.h
index 24fa89b4..b7ae4006 100644
--- a/ProcessList.h
+++ b/ProcessList.h
@@ -42,6 +42,9 @@ typedef struct ProcessList_ {
    Hashtable* processTable;
    UsersTable* usersTable;
 
+   Hashtable* displayTreeSet;
+   Hashtable* draftingTreeSet;
+
    Panel* panel;
    int following;
    uid_t userId;