1
0
Fork 0
mirror of https://git.rwth-aachen.de/acs/public/villas/node/ synced 2025-03-09 00:00:00 +01:00
VILLASnode/common/lib/list.cpp

Ignoring revisions in .git-blame-ignore-revs. Click here to bypass and see the normal blame view.

266 lines
5 KiB
C++
Raw Permalink Normal View History

/* A generic linked list.
*
* Linked lists a used for several data structures in the code.
*
* Author: Steffen Vogel <post@steffenvogel.de>
* SPDX-FileCopyrightText: 2014-2023 Institute for Automation of Complex Power Systems, RWTH Aachen University
* SPDX-License-Identifier: Apache-2.0
*/
2020-11-11 21:23:53 +01:00
#include <algorithm>
#include <array>
2020-11-11 21:23:53 +01:00
#include <cstdlib>
#include <cstring>
2021-08-11 12:40:19 -04:00
#include <villas/list.hpp>
2019-04-23 12:57:51 +02:00
#include <villas/utils.hpp>
2021-08-11 12:40:19 -04:00
using namespace villas;
int villas::list_init(struct List *l) {
pthread_mutex_init(&l->lock, nullptr);
l->length = 0;
l->capacity = 0;
l->array = nullptr;
l->state = State::INITIALIZED;
return 0;
}
int villas::list_destroy(struct List *l, dtor_cb_t destructor, bool release) {
pthread_mutex_lock(&l->lock);
assert(l->state != State::DESTROYED);
for (size_t i = 0; i < list_length(l); i++) {
void *e = list_at(l, i);
if (destructor)
destructor(e);
if (release)
free(e);
}
free(l->array);
l->length = -1;
l->capacity = 0;
l->array = nullptr;
l->state = State::DESTROYED;
pthread_mutex_unlock(&l->lock);
pthread_mutex_destroy(&l->lock);
return 0;
}
void villas::list_push(struct List *l, void *p) {
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
// Resize array if out of capacity
if (l->length >= l->capacity) {
l->capacity += LIST_CHUNKSIZE;
l->array = (void **)realloc(l->array, l->capacity * sizeof(void *));
}
l->array[l->length] = p;
l->length++;
pthread_mutex_unlock(&l->lock);
}
void villas::list_clear(struct List *l) {
pthread_mutex_lock(&l->lock);
2020-10-21 20:59:23 +02:00
l->length = 0;
2021-06-21 16:07:12 -04:00
pthread_mutex_unlock(&l->lock);
2020-10-21 20:59:23 +02:00
}
int villas::list_remove(struct List *l, size_t idx) {
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
if (idx >= l->length)
return -1;
for (size_t i = idx; i < l->length - 1; i++)
l->array[i] = l->array[i + 1];
l->length--;
pthread_mutex_unlock(&l->lock);
return 0;
}
int villas::list_insert(struct List *l, size_t idx, void *p) {
size_t i;
void *t, *o;
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
if (idx >= l->length)
return -1;
// Resize array if out of capacity
if (l->length + 1 > l->capacity) {
l->capacity += LIST_CHUNKSIZE;
l->array = (void **)realloc(l->array, l->capacity * sizeof(void *));
}
o = p;
for (i = idx; i < l->length; i++) {
t = l->array[i];
l->array[i] = o;
o = t;
}
l->array[l->length] = o;
l->length++;
pthread_mutex_unlock(&l->lock);
return 0;
}
void villas::list_remove_all(struct List *l, void *p) {
int removed = 0;
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
for (size_t i = 0; i < list_length(l); i++) {
if (list_at(l, i) == p)
removed++;
else
l->array[i - removed] = list_at(l, i);
}
l->length -= removed;
pthread_mutex_unlock(&l->lock);
}
int villas::list_contains(struct List *l, void *p) {
return list_count(
l, [](const void *a, const void *b) { return a == b ? 0 : 1; }, p);
}
int villas::list_count(struct List *l, cmp_cb_t cmp, void *ctx) {
int c = 0;
void *e;
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
for (size_t i = 0; i < list_length(l); i++) {
e = list_at(l, i);
if (cmp(e, ctx) == 0)
c++;
}
pthread_mutex_unlock(&l->lock);
return c;
}
void *villas::list_search(struct List *l, cmp_cb_t cmp, const void *ctx) {
void *e;
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
for (size_t i = 0; i < list_length(l); i++) {
e = list_at(l, i);
if (cmp(e, ctx) == 0)
goto out;
}
e = nullptr; // Not found
out:
pthread_mutex_unlock(&l->lock);
return e;
}
void villas::list_sort(struct List *l, cmp_cb_t cmp) {
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
auto array = std::vector<void *>(l->array, l->array + l->length);
2020-11-11 21:23:53 +01:00
std::sort(array.begin(), array.end(),
[cmp](void *&a, void *&b) -> bool { return cmp(a, b) < 0; });
2020-11-11 21:23:53 +01:00
std::copy(array.begin(), array.end(), l->array);
pthread_mutex_unlock(&l->lock);
}
int villas::list_set(struct List *l, unsigned index, void *value) {
if (index >= l->length)
return -1;
l->array[index] = value;
return 0;
}
ssize_t villas::list_index(struct List *l, void *p) {
void *e;
ssize_t f;
pthread_mutex_lock(&l->lock);
assert(l->state == State::INITIALIZED);
for (size_t i = 0; i < list_length(l); i++) {
e = list_at(l, i);
if (e == p) {
f = i;
goto found;
}
}
f = -1;
found:
pthread_mutex_unlock(&l->lock);
return f;
}
void villas::list_extend(struct List *l, size_t len, void *val) {
while (list_length(l) < len)
list_push(l, val);
}
void villas::list_filter(struct List *l, dtor_cb_t cb) {
size_t i, j;
pthread_mutex_lock(&l->lock);
for (i = 0, j = 0; i < list_length(l); i++) {
void *e = list_at(l, i);
if (!cb(e))
l->array[j++] = e;
}
l->length = j;
pthread_mutex_unlock(&l->lock);
}