From 08166b27b191e7be62d74054d92a9720c3a141ab Mon Sep 17 00:00:00 2001 From: Charlie Vieth Date: Sat, 5 Feb 2022 18:47:43 -0500 Subject: ProcessList: fix quadratic process removal when scanning This commit changes ProcessList_scan to lazily remove Processes by index, which is known, instead of performing a brute-force search by pid and immediately reclaiming the lost vector space via compaction. Searching by pid is potentially quadratic in ProcessList_scan because the process we are searching for is always at the back of the vector (the scan starts from the back of the vector). Additionally, removal via Vector_remove immediately reclaims space (by sliding elements down). With these changes process removal in ProcessList_scan is now linear. Changes: * ProcessList: add new ProcessList_removeIndex function to remove by index * Vector: add Vector_softRemove and Vector_compact functions to support lazy removal/deletion of entries Vector_softRemove Vector_compact * Vector: replace Vector_count with Vector_countEquals since it only used for consistency assertions. --- Process.h | 6 +++++- 1 file changed, 5 insertions(+), 1 deletion(-) (limited to 'Process.h') diff --git a/Process.h b/Process.h index e1408c21..ebaf230b 100644 --- a/Process.h +++ b/Process.h @@ -394,7 +394,11 @@ bool Process_changePriorityBy(Process* this, Arg delta); bool Process_sendSignal(Process* this, Arg sgn); -int Process_pidCompare(const void* v1, const void* v2); +static inline int Process_pidEqualCompare(const void* v1, const void* v2) { + const pid_t p1 = ((const Process*)v1)->pid; + const pid_t p2 = ((const Process*)v2)->pid; + return p1 != p2; /* return zero when equal */ +} int Process_compareByKey_Base(const Process* p1, const Process* p2, ProcessField key); -- cgit v1.2.3