diff options
author | Charlie Vieth <charlie.vieth@gmail.com> | 2022-02-05 18:47:43 -0500 |
---|---|---|
committer | BenBE <BenBE@geshi.org> | 2022-05-05 09:17:51 +0200 |
commit | 08166b27b191e7be62d74054d92a9720c3a141ab (patch) | |
tree | c5b839805f0565b11058ff7b7832b5fadfb4bc55 /Vector.h | |
parent | c7413fd6771b65388bea14ef42863444c6eaa419 (diff) |
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.
Diffstat (limited to 'Vector.h')
-rw-r--r-- | Vector.h | 20 |
1 files changed, 19 insertions, 1 deletions
@@ -22,6 +22,11 @@ typedef struct Vector_ { int arraySize; int growthRate; int items; + /* lowest index of a pending soft remove/delete operation, + used to speed up compaction */ + int dirty_index; + /* count of soft deletes, required for Vector_count to work in debug mode */ + int dirty_count; bool owner; } Vector; @@ -44,6 +49,15 @@ Object* Vector_take(Vector* this, int idx); Object* Vector_remove(Vector* this, int idx); +/* Vector_softRemove marks the item at index idx for deletion without + reclaiming any space. If owned, the item is immediately freed. + + Vector_compact must be called to reclaim space.*/ +Object* Vector_softRemove(Vector* this, int idx); + +/* Vector_compact reclaims space free'd up by Vector_softRemove, if any. */ +void Vector_compact(Vector* this); + void Vector_moveUp(Vector* this, int idx); void Vector_moveDown(Vector* this, int idx); @@ -54,7 +68,11 @@ void Vector_set(Vector* this, int idx, void* data_); Object* Vector_get(const Vector* this, int idx); int Vector_size(const Vector* this); -unsigned int Vector_count(const Vector* this); + +/* Vector_countEquals returns true if the number of non-NULL items + in the Vector is equal to expectedCount. This is only for debugging + and consistency checks. */ +bool Vector_countEquals(const Vector* this, unsigned int expectedCount); #else /* NDEBUG */ |