datastructures.h 9.84 KB
Newer Older
1
/* SPDX-License-Identifier: Zlib */
2 3 4 5 6

#ifndef GIRARA_DATASTRUCTURES_H
#define GIRARA_DATASTRUCTURES_H

#include <stddef.h>
7
#include <stdbool.h>
8
#include <sys/types.h>
9
#include "macros.h"
Sebastian Ramacher's avatar
Sebastian Ramacher committed
10
#include "types.h"
11 12 13

/**
 * Create a new list.
14
 *
15
 * @return The girara list object or NULL if an error occurred
16
 */
17
girara_list_t* girara_list_new(void) GIRARA_VISIBLE;
18

Sebastian Ramacher's avatar
Sebastian Ramacher committed
19 20 21 22
/**
 * Create a new list.
 *
 * @param gfree Pointer to the free function
23
 * @return The girara list object or NULL if an error occurred.
Sebastian Ramacher's avatar
Sebastian Ramacher committed
24
 */
25
girara_list_t* girara_list_new2(girara_free_function_t gfree) GIRARA_VISIBLE;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
26 27 28 29 30

/**
 * Create a new (sorted) list.
 *
 * @param cmp Pointer to the compare function.
31
 * @return The girara list object or NULL if an error occurred.
Sebastian Ramacher's avatar
Sebastian Ramacher committed
32
 */
33
girara_list_t* girara_sorted_list_new(girara_compare_function_t cmp) GIRARA_VISIBLE;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
34 35 36 37 38 39

/**
 * Create a new (sorted) list.
 *
 * @param cmp Pointer to the compare function.
 * @param gfree Pointer to the free function
40
 * @return The girara list object or NULL if an error occurred.
Sebastian Ramacher's avatar
Sebastian Ramacher committed
41 42
 */

Moritz Lipp's avatar
Moritz Lipp committed
43
girara_list_t* girara_sorted_list_new2(girara_compare_function_t cmp,
44
    girara_free_function_t gfree) GIRARA_VISIBLE;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
45

46 47
/**
 * Set the function which should be called if the stored data should be freed.
48 49 50
 *
 * @param list The girara list object
 * @param gfree Pointer to the free function
51
 */
Moritz Lipp's avatar
Moritz Lipp committed
52
void girara_list_set_free_function(girara_list_t* list,
53
    girara_free_function_t gfree) GIRARA_VISIBLE;
54

Sebastian Ramacher's avatar
Sebastian Ramacher committed
55 56 57 58 59
/**
 * Remove all elements from a list.
 *
 * @param list The girara list object
 */
60
void girara_list_clear(girara_list_t* list) GIRARA_VISIBLE;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
61

62 63
/**
 * Destroy list.
64 65
 *
 * @param list The girara list object
66
 */
67
void girara_list_free(girara_list_t* list) GIRARA_VISIBLE;
68 69 70

/**
 * Append an element to the list.
71 72 73
 *
 * @param list The girara list object
 * @param data The element
74
 */
75
void girara_list_append(girara_list_t* list, void* data) GIRARA_VISIBLE;
76 77 78

/**
 * Prepend an element to the list.
79 80 81
 *
 * @param list The girara list object
 * @param data The element
82
 */
83
void girara_list_prepend(girara_list_t* list, void* data) GIRARA_VISIBLE;
Moritz Lipp's avatar
Moritz Lipp committed
84 85 86

/**
 * Remove an element of the list
87 88 89
 *
 * @param list The girara list object
 * @param data The element
Moritz Lipp's avatar
Moritz Lipp committed
90
 */
91
void girara_list_remove(girara_list_t* list, void* data) GIRARA_VISIBLE;
92

93 94
/**
 * Returns nth entry
95 96 97
 *
 * @param list The girara list object
 * @param n Index of the entry
98
 * @return The nth element or NULL if an error occurred
99
 */
100
void* girara_list_nth(girara_list_t* list, size_t n) GIRARA_VISIBLE;
101 102 103

/**
 * Checks if the list contains the given element
104 105 106 107
 *
 * @param list The girara list object
 * @param data The element
 * @return true if the list contains the element
108
 */
109
bool girara_list_contains(girara_list_t* list, void* data) GIRARA_VISIBLE;
110

111 112
/**
 * Get size of the list.
113 114 115
 *
 * @param list The girara list object
 * @return The size of the list
116
 */
117
size_t girara_list_size(girara_list_t* list) GIRARA_VISIBLE;
118

119 120 121 122 123 124 125
/**
 * Returns the position of the element in the list
 *
 * @param list The girara list object
 * @param data The element
 * @return The position or -1 if the data is not found
 */
126
ssize_t girara_list_position(girara_list_t* list, void* data) GIRARA_VISIBLE;
127

128 129 130 131 132 133
/**
 * Sort a list
 *
 * @param list The list to sort
 * @param compare compare function
 */
134
void girara_list_sort(girara_list_t* list, girara_compare_function_t compare) GIRARA_VISIBLE;
135

136 137 138 139 140 141 142 143
/**
 * Find an element
 *
 * @param list The list
 * @param compare compare function
 * @param data data passed as the second argument to the compare function
 * @return the element if found or NULL
 */
Sebastian Ramacher's avatar
Sebastian Ramacher committed
144
void* girara_list_find(const girara_list_t* list, girara_compare_function_t compare,
145
    const void* data) GIRARA_VISIBLE;
146

147 148
/**
 * Create an iterator pointing at the start of list.
149 150
 *
 * @param list The girara list object
151
 * @return The list iterator or NULL if an error occurred
152
 */
153
girara_list_iterator_t* girara_list_iterator(girara_list_t* list) GIRARA_VISIBLE;
154

155 156 157
/**
 * Create an iterator pointing to the same element as iter.
 *
158
 * @param iter The girara list iterator to be copied
159
 * @return The list iterator or NULL if an error occurred
160
 */
161
girara_list_iterator_t* girara_list_iterator_copy(girara_list_iterator_t* iter) GIRARA_VISIBLE;
162

163 164
/**
 * Move iterator to next element.
165
 *
166
 * @param iter The list iterator
167
 * @return The moved iterator or NULL if an error occurred
168
 */
169
girara_list_iterator_t* girara_list_iterator_next(girara_list_iterator_t* iter) GIRARA_VISIBLE;
170

171 172 173
/**
 * Check if iterator has next element.
 *
174
 * @param iter The list iterator
175 176
 * @return true if iterator has a next element, false otherwise
 */
177
bool girara_list_iterator_has_next(girara_list_iterator_t* iter) GIRARA_VISIBLE;
178

179 180 181 182
/**
 * Move iterator to previous element.
 *
 * @param iter The list iterator
183
 * @return The moved iterator or NULL if an error occurred
184
 */
185
girara_list_iterator_t* girara_list_iterator_previous(girara_list_iterator_t* iter) GIRARA_VISIBLE;
186 187 188 189 190 191 192

/**
 * Check if iterator has previous element.
 *
 * @param iter The list iterator
 * @return true if iterator has a previous element, false otherwise
 */
193
bool girara_list_iterator_has_previous(girara_list_iterator_t* iter) GIRARA_VISIBLE;
194 195 196 197 198 199 200

/**
 * Remove element pointed by the iterator, and updates the iterator
 * to the next element
 *
 * @param iter The list iterator
 */
201
void girara_list_iterator_remove(girara_list_iterator_t* iter) GIRARA_VISIBLE;
202

Sebastian Ramacher's avatar
Sebastian Ramacher committed
203 204 205
/**
 * Check if iterator is valid
 *
206
 * @param iter The list iterator
Sebastian Ramacher's avatar
Sebastian Ramacher committed
207 208
 * @return true if iterator is valid, false otherwise
 */
209
bool girara_list_iterator_is_valid(girara_list_iterator_t* iter) GIRARA_VISIBLE;
210

211 212
/**
 * Get data from the element pointed to by the iterator.
213
 *
214
 * @param iter The list iterator
215
 * @return The data of the current element
216
 */
217
void* girara_list_iterator_data(girara_list_iterator_t* iter) GIRARA_VISIBLE;
218 219 220

/**
 * Set data from the element pointed to by the iterator.
221
 *
222
 * @param iter The list iterator
223
 * @param data Sets the list iterator to a specific element
224
 */
225
void girara_list_iterator_set(girara_list_iterator_t* iter, void *data) GIRARA_VISIBLE;
226 227 228

/**
 * Destroy the iterator.
229
 *
230
 * @param iter The list iterator
231
 */
232
void girara_list_iterator_free(girara_list_iterator_t* iter) GIRARA_VISIBLE;
233

234 235 236 237 238 239 240
/**
 * Call function for each element in the list.
 *
 * @param list The list
 * @param callback The function to call.
 * @param data Passed to the callback as second argument.
 */
Moritz Lipp's avatar
Moritz Lipp committed
241
void girara_list_foreach(girara_list_t* list, girara_list_callback_t callback,
242
    void* data) GIRARA_VISIBLE;
243 244

#define GIRARA_LIST_FOREACH(list, type, iter, data) \
Sebastian Ramacher's avatar
Sebastian Ramacher committed
245 246 247
  do { \
    girara_list_iterator_t* iter = girara_list_iterator(list); \
    while (girara_list_iterator_is_valid(iter)) { \
248
      type data = (type)girara_list_iterator_data(iter);
249 250

#define GIRARA_LIST_FOREACH_END(list, type, iter, data) \
Sebastian Ramacher's avatar
Sebastian Ramacher committed
251 252 253
      girara_list_iterator_next(iter); \
    } \
    girara_list_iterator_free(iter); \
254
  } while(0)
255

256 257 258 259 260 261 262 263 264 265
#define GIRARA_LIST_FOREACH_BODY_WITH_ITER(list, type, iter, data, ...) \
  GIRARA_LIST_FOREACH(list, type, iter, data) \
  __VA_ARGS__ \
  GIRARA_LIST_FOREACH_END(list, type, iter, data)

#define GIRARA_LIST_FOREACH_BODY(list, type, data, ...) \
  GIRARA_LIST_FOREACH(list, type, girara_list_foreach_iterator, data) \
  __VA_ARGS__ \
  GIRARA_LIST_FOREACH_END(list, type, girara_list_foreach_iterator, data)

266
/**
267
 * Merge a list into another one. Both lists need to have the same free
268 269 270 271 272 273
 * function. If other has a source free function set it will be set to NULL as
 * the elements then belong to list.
 * @param list the target list
 * @param other the source list
 * @returns list with the elements from other.
 */
274
girara_list_t* girara_list_merge(girara_list_t* list, girara_list_t* other) GIRARA_VISIBLE;
275

276 277
/**
 * Create a new node.
278 279
 *
 * @param data Data of the new node
280
 * @return A girara node object or NULL if an error occurred
281
 */
282
girara_tree_node_t* girara_node_new(void* data) GIRARA_VISIBLE;
283 284 285

/**
 * Set the function which should be called if the stored data should be freed.
286 287 288
 *
 * @param node The girara node object
 * @param gfree Pointer to the free function
289
 */
Moritz Lipp's avatar
Moritz Lipp committed
290
void girara_node_set_free_function(girara_tree_node_t* node,
291
    girara_free_function_t gfree) GIRARA_VISIBLE;
292 293 294 295

/**
 * Free a node. This will remove the node from its' parent and will destroy all
 * its' children.
296 297
 *
 * @param node The girara node object
298
 */
299
void girara_node_free(girara_tree_node_t* node) GIRARA_VISIBLE;
300 301 302

/**
 * Append a node to another node.
303 304 305
 *
 * @param parent The parent node
 * @param child The child node
306
 */
307
void girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child) GIRARA_VISIBLE;
308 309 310

/**
 * Append data as new node to another node.
311 312 313
 *
 * @param parent The parent node
 * @param data The data of the node
314
 * @return The node object or NULL if an error occurred
315
 */
Moritz Lipp's avatar
Moritz Lipp committed
316
girara_tree_node_t* girara_node_append_data(girara_tree_node_t* parent,
317
    void* data) GIRARA_VISIBLE;
318 319 320

/**
 * Get parent node.
321 322
 *
 * @param node The girara node object
323
 * @return The parent node or NULL if an error occurred or no parent exists
324
 */
325
girara_tree_node_t* girara_node_get_parent(girara_tree_node_t* node) GIRARA_VISIBLE;
326

327 328
/**
 * Get root node.
329 330
 *
 * @param node The girara node object
331
 * @return The root node or NULL if an error occurred
332
 */
333
girara_tree_node_t* girara_node_get_root(girara_tree_node_t* node) GIRARA_VISIBLE;
334

335 336
/**
 * Get list of children.
337 338
 *
 * @param node The girara node object
339
 * @return List object containing all child nodes or NULL if an error occurred
340
 */
341
girara_list_t* girara_node_get_children(girara_tree_node_t* node) GIRARA_VISIBLE;
342 343 344

/**
 * Get number of children.
345 346 347
 *
 * @param node The girara node object
 * @return The number of child nodes
348
 */
349
size_t girara_node_get_num_children(girara_tree_node_t* node) GIRARA_VISIBLE;
350 351 352

/**
 * Get data.
353 354 355
 *
 * @param node The girara node object
 * @return The data of the node
356
 */
357
void* girara_node_get_data(girara_tree_node_t* node) GIRARA_VISIBLE;
358 359 360

/**
 * Set data.
361 362 363
 *
 * @param node The girara node object
 * @param data The new data of the object
364
 */
365
void girara_node_set_data(girara_tree_node_t* node, void* data) GIRARA_VISIBLE;
366 367

#endif