From 65357c8c46154de4e4eca14075bfe5523bb5fc14 Mon Sep 17 00:00:00 2001 From: Daniel Lange Date: Mon, 7 Dec 2020 10:26:01 +0100 Subject: New upstream version 3.0.3 --- Vector.c | 166 +++++++++++++++++++++++++++++++++------------------------------ 1 file changed, 88 insertions(+), 78 deletions(-) (limited to 'Vector.c') diff --git a/Vector.c b/Vector.c index e51fd7b..40e6203 100644 --- a/Vector.c +++ b/Vector.c @@ -1,7 +1,7 @@ /* htop - Vector.c (C) 2004-2011 Hisham H. Muhammad -Released under the GNU GPL, see the COPYING file +Released under the GNU GPLv2, see the COPYING file in the source distribution for its full text. */ @@ -10,14 +10,18 @@ in the source distribution for its full text. #include #include #include -#include +#include "XUtils.h" -Vector* Vector_new(ObjectClass* type, bool owner, int size) { + +Vector* Vector_new(const ObjectClass* type, bool owner, int size) { Vector* this; - if (size == DEFAULT_SIZE) + if (size == DEFAULT_SIZE) { size = 10; + } + + assert(size > 0); this = xMalloc(sizeof(Vector)); this->growthRate = size; this->array = (Object**) xCalloc(size, sizeof(Object*)); @@ -30,39 +34,56 @@ Vector* Vector_new(ObjectClass* type, bool owner, int size) { void Vector_delete(Vector* this) { if (this->owner) { - for (int i = 0; i < this->items; i++) - if (this->array[i]) + for (int i = 0; i < this->items; i++) { + if (this->array[i]) { Object_delete(this->array[i]); + } + } } free(this->array); free(this); } -#ifdef DEBUG +#ifndef NDEBUG -static inline bool Vector_isConsistent(Vector* this) { +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] && !Object_isA(this->array[i], this->type)) + for (int i = 0; i < this->items; i++) { + if (!this->array[i]) { return false; - return true; - } else { - return true; + } + } } + + return true; } -int Vector_count(Vector* this) { - int items = 0; +unsigned int Vector_count(const Vector* this) { + unsigned int items = 0; for (int i = 0; i < this->items; i++) { - if (this->array[i]) + if (this->array[i]) { items++; + } } - assert(items == this->items); + assert(items == (unsigned int)this->items); return items; } -#endif +Object* Vector_get(const Vector* this, int idx) { + assert(idx >= 0 && idx < this->items); + assert(this->array[idx]); + assert(Object_isA(this->array[idx], this->type)); + return this->array[idx]; +} + +int Vector_size(const Vector* this) { + assert(Vector_isConsistent(this)); + return this->items; +} + +#endif /* NDEBUG */ void Vector_prune(Vector* this) { assert(Vector_isConsistent(this)); @@ -76,14 +97,22 @@ void Vector_prune(Vector* this) { this->items = 0; } -static int comparisons = 0; +//static int comparisons = 0; + +static void swap(Object** array, int indexA, int indexB) { + assert(indexA >= 0); + assert(indexB >= 0); + Object* tmp = array[indexA]; + array[indexA] = array[indexB]; + array[indexB] = tmp; +} static int partition(Object** array, int left, int right, int pivotIndex, Object_Compare compare) { - void* pivotValue = array[pivotIndex]; + const Object* pivotValue = array[pivotIndex]; swap(array, pivotIndex, right); int storeIndex = left; for (int i = left; i < right; i++) { - comparisons++; + //comparisons++; if (compare(array[i], pivotValue) <= 0) { swap(array, i, storeIndex); storeIndex++; @@ -96,7 +125,8 @@ static int partition(Object** array, int left, int right, int pivotIndex, Object static void quickSort(Object** array, int left, int right, Object_Compare compare) { if (left >= right) return; - int pivotIndex = (left+right) / 2; + + int pivotIndex = (left + right) / 2; int pivotNewIndex = partition(array, left, right, pivotIndex, compare); quickSort(array, left, pivotNewIndex - 1, compare); quickSort(array, pivotNewIndex + 1, right, compare); @@ -126,24 +156,25 @@ static void combSort(Object** array, int left, int right, Object_Compare compare */ static void insertionSort(Object** array, int left, int right, Object_Compare compare) { - for (int i = left+1; i <= right; i++) { - void* t = array[i]; + for (int i = left + 1; i <= right; i++) { + Object* t = array[i]; int j = i - 1; while (j >= left) { - comparisons++; + //comparisons++; if (compare(array[j], t) <= 0) break; - array[j+1] = array[j]; + + array[j + 1] = array[j]; j--; } - array[j+1] = t; + array[j + 1] = t; } } -void Vector_quickSort(Vector* this) { - assert(this->type->compare); +void Vector_quickSortCustomCompare(Vector* this, Object_Compare compare) { + assert(compare); assert(Vector_isConsistent(this)); - quickSort(this->array, 0, this->items - 1, this->type->compare); + quickSort(this->array, 0, this->items - 1, compare); assert(Vector_isConsistent(this)); } @@ -179,8 +210,8 @@ void Vector_insert(Vector* this, int idx, void* data_) { Vector_checkArraySize(this); //assert(this->array[this->items] == NULL); - for (int i = this->items; i > idx; i--) { - this->array[i] = this->array[i-1]; + if (idx < this->items) { + memmove(&this->array[idx + 1], &this->array[idx], (this->items - idx) * sizeof(this->array[0])); } this->array[idx] = data; this->items++; @@ -191,10 +222,11 @@ Object* Vector_take(Vector* this, int idx) { assert(idx >= 0 && idx < this->items); assert(Vector_isConsistent(this)); Object* removed = this->array[idx]; - //assert (removed != NULL); + assert(removed); this->items--; - for (int i = idx; i < this->items; i++) - this->array[i] = this->array[i+1]; + if (idx < this->items) { + memmove(&this->array[idx], &this->array[idx + 1], (this->items - idx) * sizeof(this->array[0])); + } //this->array[this->items] = NULL; assert(Vector_isConsistent(this)); return removed; @@ -205,15 +237,18 @@ Object* Vector_remove(Vector* this, int idx) { if (this->owner) { Object_delete(removed); return NULL; - } else + } else { return removed; + } } void Vector_moveUp(Vector* this, int idx) { assert(idx >= 0 && idx < this->items); assert(Vector_isConsistent(this)); + if (idx == 0) return; + Object* temp = this->array[idx]; this->array[idx] = this->array[idx - 1]; this->array[idx - 1] = temp; @@ -222,8 +257,10 @@ void Vector_moveUp(Vector* this, int idx) { void Vector_moveDown(Vector* this, int idx) { assert(idx >= 0 && idx < this->items); assert(Vector_isConsistent(this)); + if (idx == this->items - 1) return; + Object* temp = this->array[idx]; this->array[idx] = this->array[idx + 1]; this->array[idx + 1] = temp; @@ -232,52 +269,23 @@ void Vector_moveDown(Vector* this, int idx) { void Vector_set(Vector* this, int idx, void* data_) { Object* data = data_; assert(idx >= 0); - assert(Object_isA((Object*)data, this->type)); + assert(Object_isA(data, this->type)); assert(Vector_isConsistent(this)); Vector_checkArraySize(this); if (idx >= this->items) { - this->items = idx+1; + this->items = idx + 1; } else { if (this->owner) { Object* removed = this->array[idx]; assert (removed != NULL); - if (this->owner) { - Object_delete(removed); - } + Object_delete(removed); } } this->array[idx] = data; assert(Vector_isConsistent(this)); } -#ifdef DEBUG - -inline Object* Vector_get(Vector* this, int idx) { - assert(idx < this->items); - assert(Vector_isConsistent(this)); - return this->array[idx]; -} - -#else - -// In this case, Vector_get is defined as a macro in vector.h - -#endif - -#ifdef DEBUG - -inline int Vector_size(Vector* this) { - assert(Vector_isConsistent(this)); - return this->items; -} - -#else - -// In this case, Vector_size is defined as a macro in vector.h - -#endif - /* static void Vector_merge(Vector* this, Vector* v2) { @@ -295,24 +303,25 @@ static void Vector_merge(Vector* this, Vector* v2) { void Vector_add(Vector* this, void* data_) { Object* data = data_; - assert(Object_isA((Object*)data, this->type)); + assert(Object_isA(data, this->type)); assert(Vector_isConsistent(this)); int i = this->items; Vector_set(this, this->items, data); - assert(this->items == i+1); (void)(i); + assert(this->items == i + 1); (void)(i); assert(Vector_isConsistent(this)); } -inline int Vector_indexOf(Vector* this, void* search_, Object_Compare compare) { - Object* search = search_; - assert(Object_isA((Object*)search, this->type)); +int Vector_indexOf(const Vector* this, const void* search_, Object_Compare compare) { + const Object* search = search_; + assert(Object_isA(search, this->type)); assert(compare); assert(Vector_isConsistent(this)); for (int i = 0; i < this->items; i++) { - Object* o = (Object*)this->array[i]; + const Object* o = this->array[i]; assert(o); - if (compare(search, o) == 0) + if (compare(search, o) == 0) { return i; + } } return -1; } @@ -322,9 +331,10 @@ void Vector_splice(Vector* this, Vector* from) { assert(Vector_isConsistent(from)); assert(!(this->owner && from->owner)); - int olditmes = this->items; + int olditems = this->items; this->items += from->items; Vector_checkArraySize(this); - for (int j = 0; j < from->items; j++) - this->array[olditmes + j] = from->array[j]; + for (int j = 0; j < from->items; j++) { + this->array[olditems + j] = from->array[j]; + } } -- cgit v1.2.3