From 82d34deaf14e8f44ba6623bc5ca5cc41a7d9012b Mon Sep 17 00:00:00 2001 From: Denis Lisov Date: Fri, 7 Jan 2022 21:05:43 +0300 Subject: ProcessList: cleanup the tree set sorting remains They're no longer needed as rebuilding the tree from scratch is just as fast. --- ProcessList.c | 180 ++-------------------------------------------------------- 1 file changed, 4 insertions(+), 176 deletions(-) (limited to 'ProcessList.c') 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); - } } -- cgit v1.2.3