1 files changed, 103 insertions, 38 deletions

diff --git a/Vector.c b/Vector.c
index 40e6203f..aeb19391 100644
--- a/Vector.c
+++ b/Vector.c
@@ -1,10 +1,12 @@
 /*
 htop - Vector.c
 (C) 2004-2011 Hisham H. Muhammad
-Released under the GNU GPLv2, see the COPYING file
+Released under the GNU GPLv2+, see the COPYING file
 in the source distribution for its full text.
 */
 
+#include "config.h" // IWYU pragma: keep
+
 #include "Vector.h"
 
 #include <assert.h>
@@ -23,12 +25,16 @@ Vector* Vector_new(const ObjectClass* type, bool owner, int size) {
 
    assert(size > 0);
    this = xMalloc(sizeof(Vector));
-   this->growthRate = size;
-   this->array = (Object**) xCalloc(size, sizeof(Object*));
-   this->arraySize = size;
-   this->items = 0;
-   this->type = type;
-   this->owner = owner;
+   *this = (Vector) {
+      .growthRate = size,
+      .array = xCalloc(size, sizeof(Object*)),
+      .arraySize = size,
+      .items = 0,
+      .type = type,
+      .owner = owner,
+      .dirty_index = -1,
+      .dirty_count = 0,
+   };
    return this;
 }
 
@@ -44,31 +50,33 @@ void Vector_delete(Vector* this) {
    free(this);
 }
 
+static inline bool Vector_isDirty(const Vector* this) {
+   if (this->dirty_count > 0) {
+      assert(0 <= this->dirty_index && this->dirty_index < this->items);
+      assert(this->dirty_count <= this->items);
+      return true;
+   }
+   assert(this->dirty_index == -1);
+   return false;
+}
+
 #ifndef NDEBUG
 
 static bool Vector_isConsistent(const Vector* this) {
    assert(this->items <= this->arraySize);
-
-   if (this->owner) {
-      for (int i = 0; i < this->items; i++) {
-         if (!this->array[i]) {
-            return false;
-         }
-      }
-   }
+   assert(!Vector_isDirty(this));
 
    return true;
 }
 
-unsigned int Vector_count(const Vector* this) {
-   unsigned int items = 0;
+bool Vector_countEquals(const Vector* this, unsigned int expectedCount) {
+   unsigned int n = 0;
    for (int i = 0; i < this->items; i++) {
       if (this->array[i]) {
-         items++;
+         n++;
       }
    }
-   assert(items == (unsigned int)this->items);
-   return items;
+   return n == expectedCount;
 }
 
 Object* Vector_get(const Vector* this, int idx) {
@@ -88,13 +96,16 @@ int Vector_size(const Vector* this) {
 void Vector_prune(Vector* this) {
    assert(Vector_isConsistent(this));
    if (this->owner) {
-      for (int i = 0; i < this->items; i++)
+      for (int i = 0; i < this->items; i++) {
          if (this->array[i]) {
             Object_delete(this->array[i]);
-            //this->array[i] = NULL;
          }
+      }
    }
    this->items = 0;
+   this->dirty_index = -1;
+   this->dirty_count = 0;
+   memset(this->array, '\0', this->arraySize * sizeof(Object*));
 }
 
 //static int comparisons = 0;
@@ -185,15 +196,13 @@ void Vector_insertionSort(Vector* this) {
    assert(Vector_isConsistent(this));
 }
 
-static void Vector_checkArraySize(Vector* this) {
-   assert(Vector_isConsistent(this));
-   if (this->items >= this->arraySize) {
-      //int i;
-      //i = this->arraySize;
-      this->arraySize = this->items + this->growthRate;
-      this->array = (Object**) xRealloc(this->array, sizeof(Object*) * this->arraySize);
-      //for (; i < this->arraySize; i++)
-      //   this->array[i] = NULL;
+static void Vector_resizeIfNecessary(Vector* this, int newSize) {
+   assert(newSize >= 0);
+   if (newSize > this->arraySize) {
+      assert(Vector_isConsistent(this));
+      int oldSize = this->arraySize;
+      this->arraySize = newSize + this->growthRate;
+      this->array = (Object**)xReallocArrayZero(this->array, oldSize, this->arraySize, sizeof(Object*));
    }
    assert(Vector_isConsistent(this));
 }
@@ -208,7 +217,7 @@ void Vector_insert(Vector* this, int idx, void* data_) {
       idx = this->items;
    }
 
-   Vector_checkArraySize(this);
+   Vector_resizeIfNecessary(this, this->items + 1);
    //assert(this->array[this->items] == NULL);
    if (idx < this->items) {
       memmove(&this->array[idx + 1], &this->array[idx], (this->items - idx) * sizeof(this->array[0]));
@@ -227,7 +236,7 @@ Object* Vector_take(Vector* this, int idx) {
    if (idx < this->items) {
       memmove(&this->array[idx], &this->array[idx + 1], (this->items - idx) * sizeof(this->array[0]));
    }
-   //this->array[this->items] = NULL;
+   this->array[this->items] = NULL;
    assert(Vector_isConsistent(this));
    return removed;
 }
@@ -242,6 +251,61 @@ Object* Vector_remove(Vector* this, int idx) {
    }
 }
 
+Object* Vector_softRemove(Vector* this, int idx) {
+   assert(idx >= 0 && idx < this->items);
+
+   Object* removed = this->array[idx];
+   assert(removed);
+   if (removed) {
+      this->array[idx] = NULL;
+
+      this->dirty_count++;
+      if (this->dirty_index < 0 || idx < this->dirty_index) {
+         this->dirty_index = idx;
+      }
+
+      if (this->owner) {
+         Object_delete(removed);
+         return NULL;
+      }
+   }
+
+   return removed;
+}
+
+void Vector_compact(Vector* this) {
+   if (!Vector_isDirty(this)) {
+      return;
+   }
+
+   const int size = this->items;
+   assert(0 <= this->dirty_index && this->dirty_index < size);
+   assert(this->array[this->dirty_index] == NULL);
+
+   int idx = this->dirty_index;
+
+   // one deletion: use memmove, which should be faster
+   if (this->dirty_count == 1) {
+      memmove(&this->array[idx], &this->array[idx + 1], (this->items - idx - 1) * sizeof(this->array[0]));
+      this->array[this->items - 1] = NULL;
+   } else {
+      // multiple deletions
+      for (int i = idx + 1; i < size; i++) {
+         if (this->array[i]) {
+            this->array[idx++] = this->array[i];
+         }
+      }
+      // idx is now at the end of the vector and on the first index which should be set to NULL
+      memset(&this->array[idx], '\0', (size - idx) * sizeof(this->array[0]));
+   }
+
+   this->items -= this->dirty_count;
+   this->dirty_index = -1;
+   this->dirty_count = 0;
+
+   assert(Vector_isConsistent(this));
+}
+
 void Vector_moveUp(Vector* this, int idx) {
    assert(idx >= 0 && idx < this->items);
    assert(Vector_isConsistent(this));
@@ -272,14 +336,15 @@ void Vector_set(Vector* this, int idx, void* data_) {
    assert(Object_isA(data, this->type));
    assert(Vector_isConsistent(this));
 
-   Vector_checkArraySize(this);
+   Vector_resizeIfNecessary(this, idx + 1);
    if (idx >= this->items) {
       this->items = idx + 1;
    } else {
       if (this->owner) {
          Object* removed = this->array[idx];
-         assert (removed != NULL);
-         Object_delete(removed);
+         if (removed != NULL) {
+            Object_delete(removed);
+         }
       }
    }
    this->array[idx] = data;
@@ -329,11 +394,11 @@ int Vector_indexOf(const Vector* this, const void* search_, Object_Compare compa
 void Vector_splice(Vector* this, Vector* from) {
    assert(Vector_isConsistent(this));
    assert(Vector_isConsistent(from));
-   assert(!(this->owner && from->owner));
+   assert(!this->owner);
 
    int olditems = this->items;
+   Vector_resizeIfNecessary(this, this->items + from->items);
    this->items += from->items;
-   Vector_checkArraySize(this);
    for (int j = 0; j < from->items; j++) {
       this->array[olditems + j] = from->array[j];
    }