diff options
-rw-r--r-- | Action.c | 2 | ||||
-rw-r--r-- | Hashtable.c | 294 | ||||
-rw-r--r-- | Hashtable.h | 28 | ||||
-rw-r--r-- | Object.c | 5 | ||||
-rw-r--r-- | Process.c | 18 | ||||
-rw-r--r-- | Process.h | 1 | ||||
-rw-r--r-- | UsersTable.c | 2 | ||||
-rw-r--r-- | Vector.c | 18 | ||||
-rw-r--r-- | Vector.h | 4 | ||||
-rw-r--r-- | configure.ac | 1 | ||||
-rw-r--r-- | dragonflybsd/DragonFlyBSDProcess.c | 1 | ||||
-rw-r--r-- | freebsd/FreeBSDProcess.c | 1 | ||||
-rw-r--r-- | linux/LinuxProcess.c | 1 | ||||
-rw-r--r-- | openbsd/OpenBSDProcess.c | 6 | ||||
-rw-r--r-- | solaris/SolarisProcess.c | 1 |
15 files changed, 268 insertions, 115 deletions
@@ -100,7 +100,7 @@ static bool changePriority(MainPanel* panel, int delta) { return anyTagged; } -static void addUserToVector(int key, void* userCast, void* panelCast) { +static void addUserToVector(hkey_t key, void* userCast, void* panelCast) { const char* user = userCast; Panel* panel = panelCast; Panel_add(panel, (Object*) ListItem_new(user, key)); diff --git a/Hashtable.c b/Hashtable.c index 92337822..cdfb4ec3 100644 --- a/Hashtable.c +++ b/Hashtable.c @@ -8,32 +8,55 @@ in the source distribution for its full text. #include "Hashtable.h" #include "XUtils.h" -#include <stdlib.h> #include <assert.h> +#include <stdint.h> +#include <stdlib.h> #ifndef NDEBUG -static bool Hashtable_isConsistent(Hashtable* this) { - int items = 0; - for (int i = 0; i < this->size; i++) { - HashtableItem* bucket = this->buckets[i]; - while (bucket) { +static void Hashtable_dump(const Hashtable* this) { + fprintf(stderr, "Hashtable %p: size=%u items=%u owner=%s\n", + (const void*)this, + this->size, + this->items, + this->owner ? "yes" : "no"); + + unsigned int items = 0; + for (unsigned int i = 0; i < this->size; i++) { + fprintf(stderr, " item %5u: key = %5u probe = %2u value = %p\n", + i, + this->buckets[i].key, + this->buckets[i].probe, + this->buckets[i].value ? (const void*)this->buckets[i].value : "(nil)"); + + if (this->buckets[i].value) items++; - bucket = bucket->next; - } } - return items == this->items; + + fprintf(stderr, "Hashtable %p: items=%u counted=%u\n", + (const void*)this, + this->items, + items); } -int Hashtable_count(Hashtable* this) { - int items = 0; - for (int i = 0; i < this->size; i++) { - HashtableItem* bucket = this->buckets[i]; - while (bucket) { +static bool Hashtable_isConsistent(const Hashtable* this) { + unsigned int items = 0; + for (unsigned int i = 0; i < this->size; i++) { + if (this->buckets[i].value) + items++; + } + bool res = items == this->items; + if (!res) + Hashtable_dump(this); + return res; +} + +unsigned int Hashtable_count(const Hashtable* this) { + unsigned int items = 0; + for (unsigned int i = 0; i < this->size; i++) { + if (this->buckets[i].value) items++; - bucket = bucket->next; - } } assert(items == this->items); return items; @@ -41,117 +64,228 @@ int Hashtable_count(Hashtable* this) { #endif /* NDEBUG */ -static HashtableItem* HashtableItem_new(unsigned int key, void* value) { - HashtableItem* this; +/* https://oeis.org/A014234 */ +static const uint64_t OEISprimes[] = { + 2, 3, 7, 13, 31, 61, 127, 251, 509, 1021, 2039, 4093, 8191, + 16381, 32749, 65521, 131071, 262139, 524287, 1048573, + 2097143, 4194301, 8388593, 16777213, 33554393, + 67108859, 134217689, 268435399, 536870909, 1073741789, + 2147483647, 4294967291, 8589934583, 17179869143, + 34359738337, 68719476731, 137438953447 +}; - this = xMalloc(sizeof(HashtableItem)); - this->key = key; - this->value = value; - this->next = NULL; - return this; +static uint64_t nextPrime(unsigned int n) { + assert(n <= OEISprimes[ARRAYSIZE(OEISprimes) - 1]); + + for (unsigned int i = 0; i < ARRAYSIZE(OEISprimes); i++) { + if (n <= OEISprimes[i]) + return OEISprimes[i]; + } + + return OEISprimes[ARRAYSIZE(OEISprimes) - 1]; } -Hashtable* Hashtable_new(int size, bool owner) { +Hashtable* Hashtable_new(unsigned int size, bool owner) { Hashtable* this; this = xMalloc(sizeof(Hashtable)); this->items = 0; - this->size = size; - this->buckets = (HashtableItem**) xCalloc(size, sizeof(HashtableItem*)); + this->size = size ? nextPrime(size) : 13; + this->buckets = (HashtableItem*) xCalloc(this->size, sizeof(HashtableItem)); this->owner = owner; assert(Hashtable_isConsistent(this)); return this; } void Hashtable_delete(Hashtable* this) { + assert(Hashtable_isConsistent(this)); - for (int i = 0; i < this->size; i++) { - HashtableItem* walk = this->buckets[i]; - while (walk != NULL) { - if (this->owner) - free(walk->value); - - HashtableItem* savedWalk = walk; - walk = savedWalk->next; - free(savedWalk); - } + + if (this->owner) { + for (unsigned int i = 0; i < this->size; i++) + free(this->buckets[i].value); } + free(this->buckets); free(this); } -void Hashtable_put(Hashtable* this, unsigned int key, void* value) { +static void insert(Hashtable* this, hkey_t key, void* value) { unsigned int index = key % this->size; - HashtableItem** bucketPtr = &(this->buckets[index]); - while (true) - if (*bucketPtr == NULL) { - *bucketPtr = HashtableItem_new(key, value); + unsigned int probe = 0; +#ifndef NDEBUG + unsigned int origIndex = index; +#endif + + for (;;) { + if (!this->buckets[index].value) { this->items++; - break; - } else if ((*bucketPtr)->key == key) { - if (this->owner && (*bucketPtr)->value != value) - free((*bucketPtr)->value); + this->buckets[index].key = key; + this->buckets[index].probe = probe; + this->buckets[index].value = value; + return; + } - (*bucketPtr)->value = value; - break; - } else { - bucketPtr = &((*bucketPtr)->next); + if (this->buckets[index].key == key) { + if (this->owner && this->buckets[index].value != value) + free(this->buckets[index].value); + this->buckets[index].value = value; + return; + } + + /* Robin Hood swap */ + if (probe > this->buckets[index].probe) { + HashtableItem tmp = this->buckets[index]; + + this->buckets[index].key = key; + this->buckets[index].probe = probe; + this->buckets[index].value = value; + + key = tmp.key; + probe = tmp.probe; + value = tmp.value; } + index = (index + 1) % this->size; + probe++; + + assert(index != origIndex); + } +} + +void Hashtable_setSize(Hashtable* this, unsigned int size) { + + assert(Hashtable_isConsistent(this)); + + if (size <= this->items) + return; + + HashtableItem* oldBuckets = this->buckets; + unsigned int oldSize = this->size; + + this->size = nextPrime(size); + this->buckets = (HashtableItem*) xCalloc(this->size, sizeof(HashtableItem)); + this->items = 0; + + /* rehash */ + for (unsigned int i = 0; i < oldSize; i++) { + if (!oldBuckets[i].value) + continue; + + insert(this, oldBuckets[i].key, oldBuckets[i].value); + } + + free(oldBuckets); + + assert(Hashtable_isConsistent(this)); +} + +void Hashtable_put(Hashtable* this, hkey_t key, void* value) { + + assert(Hashtable_isConsistent(this)); + assert(this->size > 0); + assert(value); + + /* grow on load-factor > 0.7 */ + if (10 * this->items > 7 * this->size) + Hashtable_setSize(this, 2 * this->size); + + insert(this, key, value); + assert(Hashtable_isConsistent(this)); + assert(Hashtable_get(this, key) != NULL); + assert(this->size > this->items); } -void* Hashtable_remove(Hashtable* this, unsigned int key) { +void* Hashtable_remove(Hashtable* this, hkey_t key) { unsigned int index = key % this->size; + unsigned int probe = 0; +#ifndef NDEBUG + unsigned int origIndex = index; +#endif assert(Hashtable_isConsistent(this)); - HashtableItem** bucket; - for (bucket = &(this->buckets[index]); *bucket; bucket = &((*bucket)->next) ) { - if ((*bucket)->key == key) { - void* value = (*bucket)->value; - HashtableItem* next = (*bucket)->next; - free(*bucket); - (*bucket) = next; - this->items--; + void* res = NULL; + + while (this->buckets[index].value) { + if (this->buckets[index].key == key) { if (this->owner) { - free(value); - assert(Hashtable_isConsistent(this)); - return NULL; + free(this->buckets[index].value); } else { - assert(Hashtable_isConsistent(this)); - return value; + res = this->buckets[index].value; + } + + unsigned int next = (index + 1) % this->size; + + while (this->buckets[next].value && this->buckets[next].probe > 0) { + this->buckets[index] = this->buckets[next]; + this->buckets[index].probe -= 1; + + index = next; + next = (index + 1) % this->size; } + + /* set empty after backward shifting */ + this->buckets[index].value = NULL; + this->items--; + + break; } + + if (this->buckets[index].probe < probe) + break; + + index = (index + 1) % this->size; + probe++; + + assert(index != origIndex); } + assert(Hashtable_isConsistent(this)); - return NULL; + assert(Hashtable_get(this, key) == NULL); + + /* shrink on load-factor < 0.125 */ + if (8 * this->items < this->size) + Hashtable_setSize(this, this->size / 2); + + return res; } -void* Hashtable_get(Hashtable* this, unsigned int key) { +void* Hashtable_get(Hashtable* this, hkey_t key) { unsigned int index = key % this->size; - HashtableItem* bucketPtr = this->buckets[index]; - while (true) { - if (bucketPtr == NULL) { - assert(Hashtable_isConsistent(this)); - return NULL; - } else if (bucketPtr->key == key) { - assert(Hashtable_isConsistent(this)); - return bucketPtr->value; - } else { - bucketPtr = bucketPtr->next; + unsigned int probe = 0; + void* res = NULL; +#ifndef NDEBUG + unsigned int origIndex = index; +#endif + + assert(Hashtable_isConsistent(this)); + + while (this->buckets[index].value) { + if (this->buckets[index].key == key) { + res = this->buckets[index].value; + break; } + + if (this->buckets[index].probe < probe) + break; + + index = (index + 1) != this->size ? (index + 1) : 0; + probe++; + + assert(index != origIndex); } + + return res; } void Hashtable_foreach(Hashtable* this, Hashtable_PairFunction f, void* userData) { assert(Hashtable_isConsistent(this)); - for (int i = 0; i < this->size; i++) { - HashtableItem* walk = this->buckets[i]; - while (walk != NULL) { + for (unsigned int i = 0; i < this->size; i++) { + HashtableItem* walk = &this->buckets[i]; + if (walk->value) f(walk->key, walk->value, userData); - walk = walk->next; - } } assert(Hashtable_isConsistent(this)); } diff --git a/Hashtable.h b/Hashtable.h index dcdc89fe..f7d1aae2 100644 --- a/Hashtable.h +++ b/Hashtable.h @@ -10,36 +10,40 @@ in the source distribution for its full text. #include <stdbool.h> -typedef void(*Hashtable_PairFunction)(int, void*, void*); +typedef unsigned int hkey_t; -typedef struct HashtableItem { - unsigned int key; +typedef void(*Hashtable_PairFunction)(hkey_t key, void* value, void* userdata); + +typedef struct HashtableItem_ { + hkey_t key; + unsigned int probe; void* value; - struct HashtableItem* next; } HashtableItem; typedef struct Hashtable_ { - int size; - HashtableItem** buckets; - int items; + unsigned int size; + HashtableItem* buckets; + unsigned int items; bool owner; } Hashtable; #ifndef NDEBUG -int Hashtable_count(Hashtable* this); +unsigned int Hashtable_count(const Hashtable* this); #endif /* NDEBUG */ -Hashtable* Hashtable_new(int size, bool owner); +Hashtable* Hashtable_new(unsigned int size, bool owner); void Hashtable_delete(Hashtable* this); -void Hashtable_put(Hashtable* this, unsigned int key, void* value); +void Hashtable_setSize(Hashtable* this, unsigned int size); + +void Hashtable_put(Hashtable* this, hkey_t key, void* value); -void* Hashtable_remove(Hashtable* this, unsigned int key); +void* Hashtable_remove(Hashtable* this, hkey_t key); -void* Hashtable_get(Hashtable* this, unsigned int key); +void* Hashtable_get(Hashtable* this, hkey_t key); void Hashtable_foreach(Hashtable* this, Hashtable_PairFunction f, void* userData); @@ -21,13 +21,10 @@ bool Object_isA(const Object* o, const ObjectClass* klass) { if (!o) return false; - const ObjectClass* type = o->klass; - while (type) { + for (const ObjectClass* type = o->klass; type; type = type->extends) { if (type == klass) { return true; } - - type = type->extends; } return false; @@ -257,13 +257,18 @@ void Process_writeField(const Process* this, RichString* str, ProcessField field bool coloring = this->settings->highlightMegabytes; switch (field) { - case PERCENT_CPU: { - if (this->percent_cpu > 999.9) { - xSnprintf(buffer, n, "%4u ", (unsigned int)this->percent_cpu); - } else if (this->percent_cpu > 99.9) { - xSnprintf(buffer, n, "%3u. ", (unsigned int)this->percent_cpu); + case PERCENT_CPU: + case PERCENT_NORM_CPU: { + float cpuPercentage = this->percent_cpu; + if (field == PERCENT_NORM_CPU) { + cpuPercentage /= this->processList->cpuCount; + } + if (cpuPercentage > 999.9) { + xSnprintf(buffer, n, "%4u ", (unsigned int)cpuPercentage); + } else if (cpuPercentage > 99.9) { + xSnprintf(buffer, n, "%3u. ", (unsigned int)cpuPercentage); } else { - xSnprintf(buffer, n, "%4.1f ", this->percent_cpu); + xSnprintf(buffer, n, "%4.1f ", cpuPercentage); } break; } @@ -492,6 +497,7 @@ long Process_compare(const void* v1, const void* v2) { switch (settings->sortKey) { case PERCENT_CPU: + case PERCENT_NORM_CPU: return SPACESHIP_NUMBER(p2->percent_cpu, p1->percent_cpu); case PERCENT_MEM: return SPACESHIP_NUMBER(p2->m_resident, p1->m_resident); @@ -48,6 +48,7 @@ typedef enum ProcessFields { TIME = 50, NLWP = 51, TGID = 52, + PERCENT_NORM_CPU = 53, } ProcessField; typedef struct ProcessPidColumn_ { diff --git a/UsersTable.c b/UsersTable.c index 25e44883..fdbfd68f 100644 --- a/UsersTable.c +++ b/UsersTable.c @@ -20,7 +20,7 @@ in the source distribution for its full text. UsersTable* UsersTable_new() { UsersTable* this; this = xMalloc(sizeof(UsersTable)); - this->users = Hashtable_new(20, true); + this->users = Hashtable_new(10, true); return this; } @@ -48,33 +48,33 @@ void Vector_delete(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)) { + if (!this->array[i]) { return false; } } - return true; - } else { - return true; } + + return true; } -int Vector_count(const 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]) { items++; } } - assert(items == this->items); + assert(items == (unsigned int)this->items); return items; } -Object* Vector_get(Vector* this, int idx) { +Object* Vector_get(const Vector* this, int idx) { assert(idx >= 0 && idx < this->items); - assert(Vector_isConsistent(this)); assert(this->array[idx]); + assert(Object_isA(this->array[idx], this->type)); return this->array[idx]; } @@ -52,9 +52,9 @@ void Vector_set(Vector* this, int idx, void* data_); #ifndef NDEBUG -Object* Vector_get(Vector* this, int idx); +Object* Vector_get(const Vector* this, int idx); int Vector_size(const Vector* this); -int Vector_count(const Vector* this); +unsigned int Vector_count(const Vector* this); #else /* NDEBUG */ diff --git a/configure.ac b/configure.ac index 59beba32..aed4947e 100644 --- a/configure.ac +++ b/configure.ac @@ -400,4 +400,5 @@ AC_MSG_RESULT([ unicode: $enable_unicode hwloc: $enable_hwloc setuid: $enable_setuid + debug: $enable_debug ]) diff --git a/dragonflybsd/DragonFlyBSDProcess.c b/dragonflybsd/DragonFlyBSDProcess.c index 55e4fbac..4130e799 100644 --- a/dragonflybsd/DragonFlyBSDProcess.c +++ b/dragonflybsd/DragonFlyBSDProcess.c @@ -48,6 +48,7 @@ ProcessFieldData Process_fields[] = { [M_RESIDENT] = { .name = "M_RESIDENT", .title = " RES ", .description = "Resident set size, size of the text and data sections, plus stack usage", .flags = 0, }, [ST_UID] = { .name = "ST_UID", .title = " UID ", .description = "User ID of the process owner", .flags = 0, }, [PERCENT_CPU] = { .name = "PERCENT_CPU", .title = "CPU% ", .description = "Percentage of the CPU time the process used in the last sampling", .flags = 0, }, + [PERCENT_NORM_CPU] = { .name = "PERCENT_NORM_CPU", .title = "NCPU%", .description = "Normalized percentage of the CPU time the process used in the last sampling (normalized by cpu count)", .flags = 0, }, [PERCENT_MEM] = { .name = "PERCENT_MEM", .title = "MEM% ", .description = "Percentage of the memory the process is using, based on resident memory size", .flags = 0, }, [USER] = { .name = "USER", .title = "USER ", .description = "Username of the process owner (or user ID if name cannot be determined)", .flags = 0, }, [TIME] = { .name = "TIME", .title = " TIME+ ", .description = "Total time the process has spent in user and system time", .flags = 0, }, diff --git a/freebsd/FreeBSDProcess.c b/freebsd/FreeBSDProcess.c index 695594e8..57e64118 100644 --- a/freebsd/FreeBSDProcess.c +++ b/freebsd/FreeBSDProcess.c @@ -40,6 +40,7 @@ ProcessFieldData Process_fields[] = { [M_RESIDENT] = { .name = "M_RESIDENT", .title = " RES ", .description = "Resident set size, size of the text and data sections, plus stack usage", .flags = 0, }, [ST_UID] = { .name = "ST_UID", .title = " UID ", .description = "User ID of the process owner", .flags = 0, }, [PERCENT_CPU] = { .name = "PERCENT_CPU", .title = "CPU% ", .description = "Percentage of the CPU time the process used in the last sampling", .flags = 0, }, + [PERCENT_NORM_CPU] = { .name = "PERCENT_NORM_CPU", .title = "NCPU%", .description = "Normalized percentage of the CPU time the process used in the last sampling (normalized by cpu count)", .flags = 0, }, [PERCENT_MEM] = { .name = "PERCENT_MEM", .title = "MEM% ", .description = "Percentage of the memory the process is using, based on resident memory size", .flags = 0, }, [USER] = { .name = "USER", .title = "USER ", .description = "Username of the process owner (or user ID if name cannot be determined)", .flags = 0, }, [TIME] = { .name = "TIME", .title = " TIME+ ", .description = "Total time the process has spent in user and system time", .flags = 0, }, diff --git a/linux/LinuxProcess.c b/linux/LinuxProcess.c index 2fec52f1..5868ea29 100644 --- a/linux/LinuxProcess.c +++ b/linux/LinuxProcess.c @@ -73,6 +73,7 @@ ProcessFieldData Process_fields[] = { [M_DT] = { .name = "M_DT", .title = " DIRTY ", .description = "Size of the dirty pages of the process (unused since Linux 2.6; always 0)", .flags = 0, }, [ST_UID] = { .name = "ST_UID", .title = " UID ", .description = "User ID of the process owner", .flags = 0, }, [PERCENT_CPU] = { .name = "PERCENT_CPU", .title = "CPU% ", .description = "Percentage of the CPU time the process used in the last sampling", .flags = 0, }, + [PERCENT_NORM_CPU] = { .name = "PERCENT_NORM_CPU", .title = "NCPU%", .description = "Normalized percentage of the CPU time the process used in the last sampling (normalized by cpu count)", .flags = 0, }, [PERCENT_MEM] = { .name = "PERCENT_MEM", .title = "MEM% ", .description = "Percentage of the memory the process is using, based on resident memory size", .flags = 0, }, [USER] = { .name = "USER", .title = "USER ", .description = "Username of the process owner (or user ID if name cannot be determined)", .flags = 0, }, [TIME] = { .name = "TIME", .title = " TIME+ ", .description = "Total time the process has spent in user and system time", .flags = 0, }, diff --git a/openbsd/OpenBSDProcess.c b/openbsd/OpenBSDProcess.c index 1013d3b4..de823ce4 100644 --- a/openbsd/OpenBSDProcess.c +++ b/openbsd/OpenBSDProcess.c @@ -142,6 +142,12 @@ ProcessFieldData Process_fields[] = { .description = "Percentage of the CPU time the process used in the last sampling", .flags = 0, }, + [PERCENT_NORM_CPU] = { + .name = "PERCENT_NORM_CPU", + .title = "NCPU%", + .description = "Normalized percentage of the CPU time the process used in the last sampling (normalized by cpu count)", + .flags = 0, + }, [PERCENT_MEM] = { .name = "PERCENT_MEM", .title = "MEM% ", diff --git a/solaris/SolarisProcess.c b/solaris/SolarisProcess.c index 7d833fe9..c11c6de8 100644 --- a/solaris/SolarisProcess.c +++ b/solaris/SolarisProcess.c @@ -48,6 +48,7 @@ ProcessFieldData Process_fields[] = { [M_RESIDENT] = { .name = "M_RESIDENT", .title = " RES ", .description = "Resident set size, size of the text and data sections, plus stack usage", .flags = 0, }, [ST_UID] = { .name = "ST_UID", .title = " UID ", .description = "User ID of the process owner", .flags = 0, }, [PERCENT_CPU] = { .name = "PERCENT_CPU", .title = "CPU% ", .description = "Percentage of the CPU time the process used in the last sampling", .flags = 0, }, + [PERCENT_NORM_CPU] = { .name = "PERCENT_NORM_CPU", .title = "NCPU%", .description = "Normalized percentage of the CPU time the process used in the last sampling (normalized by cpu count)", .flags = 0, }, [PERCENT_MEM] = { .name = "PERCENT_MEM", .title = "MEM% ", .description = "Percentage of the memory the process is using, based on resident memory size", .flags = 0, }, [USER] = { .name = "USER", .title = "USER ", .description = "Username of the process owner (or user ID if name cannot be determined)", .flags = 0, }, [TIME] = { .name = "TIME", .title = " TIME+ ", .description = "Total time the process has spent in user and system time", .flags = 0, }, |