summaryrefslogtreecommitdiffstats
path: root/ProcessList.c
diff options
context:
space:
mode:
authorDenis Lisov <dennis.lissov@gmail.com>2022-01-07 21:05:43 +0300
committerBenBE <BenBE@geshi.org>2022-02-13 19:50:16 +0100
commit82d34deaf14e8f44ba6623bc5ca5cc41a7d9012b (patch)
tree5ac26029bf9713d85a27932df9f19e30f49d8e60 /ProcessList.c
parentfa3e0d06c2ab48c91b1a1e3c5991fefabee870ea (diff)
ProcessList: cleanup the tree set sorting remains
They're no longer needed as rebuilding the tree from scratch is just as fast.
Diffstat (limited to 'ProcessList.c')
-rw-r--r--ProcessList.c180
1 files changed, 4 insertions, 176 deletions
diff --git a/ProcessList.c b/ProcessList.c
index c9b15ff8..186e1edc 100644
--- a/ProcessList.c
+++ b/ProcessList.c
@@ -25,8 +25,6 @@ ProcessList* ProcessList_init(ProcessList* this, const ObjectClass* klass, Users
this->displayList = Vector_new(klass, false, DEFAULT_SIZE);
this->processTable = Hashtable_new(200, false);
- this->displayTreeSet = Hashtable_new(200, false);
- this->draftingTreeSet = Hashtable_new(200, false);
this->needsSort = true;
this->usersTable = usersTable;
@@ -74,8 +72,6 @@ void ProcessList_done(ProcessList* this) {
}
#endif
- Hashtable_delete(this->draftingTreeSet);
- Hashtable_delete(this->displayTreeSet);
Hashtable_delete(this->processTable);
Vector_delete(this->displayList);
@@ -195,144 +191,7 @@ void ProcessList_remove(ProcessList* this, const Process* p) {
assert(Hashtable_count(this->processTable) == Vector_count(this->processes));
}
-// 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 comparison it may be not, as it's not safe to go deeper without first updating the tree structure.
-// If it would be safe 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 safe 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 guaranteed 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 `leaves`
- if (layerSize == 0)
- return;
-
- Vector* layer = Vector_new(Vector_type(this->displayList), 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);
- assert(proc);
- if (proc && 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 the current process's index.
- //
- // Use 'tree_depth' as a temporal variable.
- // It's safe to do as later 'tree_depth' will be renovated.
- previous_process->tree_depth = proc->tree_index;
- }
-
- Vector_add(layer, proc);
- }
- }
-
- // The loop above changes just up to process-1.
- // So the last process of the layer isn't updated by the above code.
- //
- // 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);
-
- // It's not strictly necessary to do this, but doing so anyways
- // allows for checking the correctness of the inner workings.
- Hashtable_remove(this->displayTreeSet, newLeftBound);
- }
-
- Vector_delete(layer);
-}
-
-static void ProcessList_updateTreeSet(ProcessList* this) {
- unsigned int index = 0;
- unsigned int tree_index = 1;
-
- const int vsize = Vector_size(this->displayList);
-
- assert(Hashtable_count(this->draftingTreeSet) == 0);
- assert((int)Hashtable_count(this->displayTreeSet) == vsize);
-
- ProcessList_updateTreeSetLayer(this, 0, vsize, 0, 0, vsize * 2 + 1, &index, &tree_index, -1);
-
- Hashtable* tmp = this->draftingTreeSet;
- this->draftingTreeSet = this->displayTreeSet;
- this->displayTreeSet = tmp;
-
- assert(Hashtable_count(this->draftingTreeSet) == 0);
- assert((int)Hashtable_count(this->displayTreeSet) == vsize);
-}
-
-static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level, int indent, bool show, int* node_counter, int* node_index) {
+static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level, int indent, bool show) {
// On OpenBSD the kernel thread 'swapper' has pid 0.
// Do not treat it as root of any tree.
if (pid == 0)
@@ -366,10 +225,6 @@ static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level,
for (int i = l; i < r; i++) {
Process* process = (Process*)Vector_get(this->processes, i);
- int index = (*node_index)++;
-
- int lft = (*node_counter)++;
-
if (!show) {
process->show = false;
}
@@ -380,30 +235,17 @@ static void ProcessList_buildTreeBranch(ProcessList* this, pid_t pid, int level,
assert(Vector_size(this->displayList) == s + 1); (void)s;
int nextIndent = indent | (1 << level);
- ProcessList_buildTreeBranch(this, process->pid, level + 1, (i < lastShown) ? nextIndent : indent, process->show && process->showChildren, node_counter, node_index);
+ ProcessList_buildTreeBranch(this, process->pid, level + 1, (i < lastShown) ? nextIndent : indent, process->show && process->showChildren);
if (i == lastShown) {
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);
}
}
-static int ProcessList_treeProcessCompare(const void* v1, const void* v2) {
- const Process* p1 = (const Process*)v1;
- const Process* p2 = (const Process*)v2;
-
- return SPACESHIP_NUMBER(p1->tree_left, p2->tree_left);
-}
-
static int compareProcessByKnownParentThenNatural(const void* v1, const void* v2) {
const Process* p1 = (const Process*)v1;
const Process* p2 = (const Process*)v2;
@@ -423,9 +265,6 @@ static int compareProcessByKnownParentThenNatural(const void* v1, const void* v2
static void ProcessList_buildTree(ProcessList* this) {
Vector_prune(this->displayList);
- int node_counter = 1;
- int node_index = 0;
-
// Mark root processes
int vsize = Vector_size(this->processes);
for (int i = 0; i < vsize; i++) {
@@ -460,12 +299,8 @@ static void ProcessList_buildTree(ProcessList* this) {
process = (Process*)Vector_get(this->processes, i);
process->indent = 0;
process->tree_depth = 0;
- process->tree_left = node_counter++;
- process->tree_index = node_index++;
Vector_add(this->displayList, process);
- Hashtable_put(this->displayTreeSet, process->tree_index, process);
- ProcessList_buildTreeBranch(this, process->pid, 0, 0, process->showChildren, &node_counter, &node_index);
- process->tree_right = node_counter++;
+ ProcessList_buildTreeBranch(this, process->pid, 0, 0, process->showChildren);
continue;
}
}
@@ -658,13 +493,6 @@ void ProcessList_scan(ProcessList* this, bool pauseProcessUpdate) {
// Set UID column width based on max UID.
Process_setUidColumnWidth(maxUid);
- if (this->settings->ss->treeView) {
- // Clear out the hashtable to avoid any left-over processes from previous build
- //
- // The sorting algorithm relies on the fact that
- // len(this->displayTreeSet) == len(this->processes)
- Hashtable_clear(this->displayTreeSet);
-
+ if (this->settings->ss->treeView)
ProcessList_buildTree(this);
- }
}

© 2014-2024 Faster IT GmbH | imprint | privacy policy