list.h 4.58 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
/** A generic list implementation.
 *
 * 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().
 *
 * @file
 * @author Steffen Vogel <stvogel@eonerc.rwth-aachen.de>
Steffen Vogel's avatar
Steffen Vogel committed
11
 * @copyright 2014-2019, Institute for Automation of Complex Power Systems, EONERC
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
*
 * VILLAScommon
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
27
28
29
30
 *********************************************************************************/

#pragma once

31
#include <sys/types.h>
32
33
34
35
36
37
38
39
40
#include <pthread.h>

#include <villas/common.h>

#define LIST_CHUNKSIZE		16

/** Static list initialization */
#define LIST_INIT_STATIC(l)					\
__attribute__((constructor(105))) static void UNIQUE(__ctor)() {\
Steffen Vogel's avatar
Steffen Vogel committed
41
	if ((l)->state == State::DESTROYED)			\
Steffen Vogel's avatar
Steffen Vogel committed
42
		vlist_init(l);					\
43
44
}								\
__attribute__((destructor(105))) static void UNIQUE(__dtor)() {	\
Steffen Vogel's avatar
Steffen Vogel committed
45
	vlist_destroy(l, nullptr, false);				\
46
47
}

Steffen Vogel's avatar
Steffen Vogel committed
48
#define vlist_length(list)		((list)->length)
Steffen Vogel's avatar
Steffen Vogel committed
49
#define vlist_at_safe(list, index)	((list)->length > index ? (list)->array[index] : nullptr)
Steffen Vogel's avatar
Steffen Vogel committed
50
#define vlist_at(list, index)		((list)->array[index])
51

Steffen Vogel's avatar
Steffen Vogel committed
52
#define vlist_first(list)		vlist_at(list, 0)
Steffen Vogel's avatar
Steffen Vogel committed
53
#define vlist_last(list)		vlist_at(list, (list)->length-1)
54
55
56
57
58

/** Callback to search or sort a list. */
typedef int (*cmp_cb_t)(const void *, const void *);

/* The list data structure. */
Steffen Vogel's avatar
Steffen Vogel committed
59
struct vlist {
Steffen Vogel's avatar
Steffen Vogel committed
60
	enum State state;	/**< The state of this list. */
61
62
63
64
65
66
67
68
69
70
	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 */
};

/** Initialize a list.
 *
 * @param l A pointer to the list data structure.
 */
Steffen Vogel's avatar
Steffen Vogel committed
71
int vlist_init(struct vlist *l);
72
73
74

/** Destroy a list and call destructors for all list elements
 *
Steffen Vogel's avatar
Steffen Vogel committed
75
 * @param free free() all list members during when calling vlist_destroy()
76
77
78
 * @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.
 */
Steffen Vogel's avatar
Steffen Vogel committed
79
int vlist_destroy(struct vlist *l, dtor_cb_t dtor, bool free);
80
81

/** Append an element to the end of the list */
Steffen Vogel's avatar
Steffen Vogel committed
82
void vlist_push(struct vlist *l, void *p);
83
84

/** Remove all occurences of a list item */
85
86
87
88
89
void vlist_remove_all(struct vlist *l, void *p);

int vlist_remove(struct vlist *l, size_t idx);

int vlist_insert(struct vlist *l, size_t idx, void *p);
90
91
92
93
94
95
96
97
98
99
100
101

/** Return the first list element which is identified by a string in its first member variable.
 *
 * List elements are pointers to structures of the following form:
 *
 * struct obj {
 *    char *name;
 *    // more members
 * }
 *
 * @see Only possible because of §1424 of http://c0x.coding-guidelines.com/6.7.2.1.html
 */
Steffen Vogel's avatar
Steffen Vogel committed
102
void * vlist_lookup(struct vlist *l, const char *name);
103

Steffen Vogel's avatar
Steffen Vogel committed
104
ssize_t vlist_lookup_index(struct vlist *l, const char *name);
105

106
/** Return the first element of the list for which cmp returns zero */
Steffen Vogel's avatar
Steffen Vogel committed
107
void * vlist_search(struct vlist *l, cmp_cb_t cmp, void *ctx);
108
109

/** Returns the number of occurences for which cmp returns zero when called on all list elements. */
Steffen Vogel's avatar
Steffen Vogel committed
110
int vlist_count(struct vlist *l, cmp_cb_t cmp, void *ctx);
111
112

/** Return 0 if list contains pointer p */
Steffen Vogel's avatar
Steffen Vogel committed
113
int vlist_contains(struct vlist *l, void *p);
114
115

/** Sort the list using the quicksort algorithm of libc */
Steffen Vogel's avatar
Steffen Vogel committed
116
void vlist_sort(struct vlist *l, cmp_cb_t cmp);
117
118

/** Set single element in list */
Steffen Vogel's avatar
Steffen Vogel committed
119
int vlist_set(struct vlist *l, unsigned index, void *value);
120

121
122
123
124
125
/** 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.
 */
Steffen Vogel's avatar
Steffen Vogel committed
126
ssize_t vlist_index(struct vlist *l, void *value);
127
128

/** Extend the list to the given length by filling new slots with given value. */
Steffen Vogel's avatar
Steffen Vogel committed
129
void vlist_extend(struct vlist *l, size_t len, void *val);
130

131
132
/** Remove all elements for which the callback returns a non-zero return code. */
void vlist_filter(struct vlist *l, dtor_cb_t cb);