2023-08-28 12:31:18 +02:00
|
|
|
/* A generic list implementation.
|
2018-08-21 13:24:17 +02:00
|
|
|
*
|
|
|
|
* This is a generic implementation of a list which can store void pointers to
|
|
|
|
* arbitrary data. The data itself is not stored or managed by the list.
|
|
|
|
*
|
|
|
|
* Internally, an array of pointers is used to store the pointers.
|
|
|
|
* If needed, this array will grow by realloc().
|
|
|
|
*
|
2023-08-31 11:17:07 +02:00
|
|
|
* 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
|
|
|
|
*/
|
2018-08-21 13:24:17 +02:00
|
|
|
|
|
|
|
#pragma once
|
|
|
|
|
2020-08-25 19:55:14 +02:00
|
|
|
#include <cstring>
|
2018-08-21 13:24:17 +02:00
|
|
|
#include <pthread.h>
|
2023-09-07 13:19:19 +02:00
|
|
|
#include <string>
|
|
|
|
#include <sys/types.h>
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2019-10-27 20:23:47 +01:00
|
|
|
#include <villas/common.hpp>
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-09-07 13:19:19 +02:00
|
|
|
#define LIST_CHUNKSIZE 16
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Static list initialization
|
2023-09-07 13:19:19 +02:00
|
|
|
#define LIST_INIT_STATIC(l) \
|
|
|
|
__attribute__((constructor(105))) static void UNIQUE(__ctor)() { \
|
|
|
|
int ret __attribute__((unused)); \
|
|
|
|
ret = list_init(l); \
|
|
|
|
} \
|
|
|
|
__attribute__((destructor(105))) static void UNIQUE(__dtor)() { \
|
|
|
|
int ret __attribute__((unused)); \
|
|
|
|
ret = list_destroy(l, nullptr, false); \
|
|
|
|
}
|
|
|
|
|
|
|
|
#define list_length(list) ((list)->length)
|
|
|
|
#define list_at_safe(list, index) \
|
|
|
|
((list)->length > index ? (list)->array[index] : nullptr)
|
|
|
|
#define list_at(list, index) ((list)->array[index])
|
|
|
|
|
|
|
|
#define list_first(list) list_at(list, 0)
|
|
|
|
#define list_last(list) list_at(list, (list)->length - 1)
|
2021-08-11 12:40:19 -04:00
|
|
|
|
|
|
|
namespace villas {
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2022-12-02 17:16:44 +01:00
|
|
|
// Callback to search or sort a list.
|
2018-08-21 13:24:17 +02:00
|
|
|
typedef int (*cmp_cb_t)(const void *, const void *);
|
|
|
|
|
2022-12-02 17:16:44 +01:00
|
|
|
// The list data structure.
|
2021-08-11 12:40:19 -04:00
|
|
|
struct List {
|
2023-09-07 13:19:19 +02:00
|
|
|
enum State state; // The state of this list.
|
|
|
|
void **array; // Array of pointers to list elements.
|
|
|
|
size_t capacity; // Size of list::array in elements.
|
|
|
|
size_t length; // Number of elements of list::array which are in use.
|
|
|
|
pthread_mutex_t lock; // A mutex to allow thread-safe accesses.
|
2018-08-21 13:24:17 +02:00
|
|
|
};
|
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Initialize a list.
|
|
|
|
//
|
|
|
|
// @param l A pointer to the list data structure.
|
2023-09-07 13:19:19 +02:00
|
|
|
int list_init(struct List *l) __attribute__((warn_unused_result));
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Destroy a list and call destructors for all list elements
|
|
|
|
//
|
|
|
|
// @param free free() all list members during when calling list_destroy()
|
|
|
|
// @param dtor A function pointer to a desctructor which will be called for every list item when the list is destroyed.
|
|
|
|
// @param l A pointer to the list data structure.
|
2023-09-07 13:19:19 +02:00
|
|
|
int list_destroy(struct List *l, dtor_cb_t dtor = nullptr, bool free = false)
|
|
|
|
__attribute__((warn_unused_result));
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Append an element to the end of the list.
|
2021-08-11 12:40:19 -04:00
|
|
|
void list_push(struct List *l, void *p);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Clear list.
|
2021-08-11 12:40:19 -04:00
|
|
|
void list_clear(struct List *l);
|
2020-10-21 20:59:23 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Remove all occurences of a list item.
|
2021-08-11 12:40:19 -04:00
|
|
|
void list_remove_all(struct List *l, void *p);
|
2019-02-24 09:22:20 +01:00
|
|
|
|
2021-08-11 12:40:19 -04:00
|
|
|
int list_remove(struct List *l, size_t idx);
|
2019-02-24 09:22:20 +01:00
|
|
|
|
2021-08-11 12:40:19 -04:00
|
|
|
int list_insert(struct List *l, size_t idx, void *p);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Return the first element of the list for which cmp returns zero.
|
2023-09-07 13:19:19 +02:00
|
|
|
void *list_search(struct List *l, cmp_cb_t cmp, const void *ctx);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Returns the number of occurences for which cmp returns zero when called on all list elements.
|
2021-08-11 12:40:19 -04:00
|
|
|
int list_count(struct List *l, cmp_cb_t cmp, void *ctx);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Return 0 if list contains pointer p.
|
2021-08-11 12:40:19 -04:00
|
|
|
int list_contains(struct List *l, void *p);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Sort the list using the quicksort algorithm of libc.
|
2021-08-11 12:40:19 -04:00
|
|
|
void list_sort(struct List *l, cmp_cb_t cmp);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Set single element in list.
|
2021-08-11 12:40:19 -04:00
|
|
|
int list_set(struct List *l, unsigned index, void *value);
|
2018-08-21 13:24:17 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Return index in list for value.
|
|
|
|
//
|
|
|
|
// @retval <0 No list entry matching \p value was found.
|
|
|
|
// @retval >=0 Entry \p value was found at returned index.
|
2021-08-11 12:40:19 -04:00
|
|
|
ssize_t list_index(struct List *l, void *value);
|
2018-08-22 11:29:39 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Extend the list to the given length by filling new slots with given value.
|
2021-08-11 12:40:19 -04:00
|
|
|
void list_extend(struct List *l, size_t len, void *val);
|
2018-08-22 11:29:39 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Remove all elements for which the callback returns a non-zero return code.
|
2021-08-11 12:40:19 -04:00
|
|
|
void list_filter(struct List *l, dtor_cb_t cb);
|
2020-08-25 19:55:14 +02:00
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Lookup an element from the list based on a name.
|
2023-09-07 13:19:19 +02:00
|
|
|
template <typename T>
|
|
|
|
T *list_lookup_name(struct List *l, const std::string &name) {
|
|
|
|
return (T *)list_search(
|
|
|
|
l,
|
|
|
|
[](const void *a, const void *b) -> int {
|
|
|
|
auto *e = reinterpret_cast<const T *>(a);
|
|
|
|
auto *s = reinterpret_cast<const std::string *>(b);
|
|
|
|
|
|
|
|
return *s == e->name ? 0 : 1;
|
|
|
|
},
|
|
|
|
&name);
|
2020-08-25 19:55:14 +02:00
|
|
|
}
|
|
|
|
|
2023-04-03 10:00:02 +00:00
|
|
|
// Lookup index of list element based on name.
|
2023-09-07 13:19:19 +02:00
|
|
|
template <typename T>
|
|
|
|
ssize_t list_lookup_index(struct List *l, const std::string &name) {
|
|
|
|
auto *f = list_lookup_name<T>(l, name);
|
2020-08-25 19:55:14 +02:00
|
|
|
|
2023-09-07 13:19:19 +02:00
|
|
|
return f ? list_index(l, f) : -1;
|
2020-09-03 14:45:17 +02:00
|
|
|
}
|
2021-08-11 12:40:19 -04:00
|
|
|
|
2022-12-02 17:16:44 +01:00
|
|
|
} // namespace villas
|