girara
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros
datastructures.c
Go to the documentation of this file.
1 /* See LICENSE file for license and copyright information */
2 
3 #include <stdlib.h>
4 #include <glib.h>
5 
6 #include "datastructures.h"
7 #include "utils.h"
8 
10 {
12  GNode* node; /* The node object */
13 };
14 
15 typedef struct girara_tree_node_data_s
16 {
17  girara_tree_node_t* node;
18  void* data;
20 
22 {
25  GList* start;
26 };
27 
29 {
30  girara_list_t* list;
31  GList* element;
32 };
33 
34 girara_list_t*
36 {
37  return g_try_malloc0(sizeof(girara_list_t));
38 }
39 
40 girara_list_t*
42 {
43  girara_list_t* list = girara_list_new();
44  if (list == NULL) {
45  return NULL;
46  }
47 
48  girara_list_set_free_function(list, gfree);
49  return list;
50 }
51 
52 girara_list_t*
54 {
55  girara_list_t* list = girara_list_new();
56  if (list == NULL) {
57  return NULL;
58  }
59 
60  list->cmp = cmp;
61  return list;
62 }
63 
64 girara_list_t*
66 {
67  girara_list_t* list = girara_list_new2(gfree);
68  if (list == NULL) {
69  return NULL;
70  }
71 
72  list->cmp = cmp;
73  return list;
74 }
75 
76 void
78 {
79  g_return_if_fail(list);
80  list->free = gfree;
81 }
82 
83 void
84 girara_list_clear(girara_list_t* list)
85 {
86  if (list == NULL || list->start == NULL) {
87  return;
88  }
89 
90  if (list->free != NULL) {
91  g_list_free_full(list->start, list->free);
92  } else {
93  g_list_free(list->start);
94  }
95  list->start = NULL;
96 }
97 
98 void
99 girara_list_free(girara_list_t* list)
100 {
101  if (list == NULL) {
102  return;
103  }
104 
105  girara_list_clear(list);
106  g_free(list);
107 }
108 
109 void
110 girara_list_append(girara_list_t* list, void* data)
111 {
112  g_return_if_fail(list != NULL);
113 
114  if (list->cmp != NULL) {
115  list->start = g_list_insert_sorted(list->start, data, list->cmp);
116  } else {
117  list->start = g_list_append(list->start, data);
118  }
119 }
120 
121 void
122 girara_list_prepend(girara_list_t* list, void* data)
123 {
124  g_return_if_fail(list != NULL);
125 
126  if (list->cmp != NULL) {
127  girara_list_append(list, data);
128  } else {
129  list->start = g_list_prepend(list->start, data);
130  }
131 }
132 
133 void
134 girara_list_remove(girara_list_t* list, void* data)
135 {
136  g_return_if_fail(list != NULL);
137  if (list->start == NULL) {
138  return;
139  }
140 
141  GList* tmp = g_list_find(list->start, data);
142  if (tmp == NULL) {
143  return;
144  }
145 
146  if (list->free != NULL) {
147  (list->free)(tmp->data);
148  }
149  list->start = g_list_delete_link(list->start, tmp);
150 }
151 
152 void*
153 girara_list_nth(girara_list_t* list, size_t n)
154 {
155  g_return_val_if_fail(list != NULL, NULL);
156  g_return_val_if_fail(list->start != NULL && (n < g_list_length(list->start)), NULL);
157 
158  GList* tmp = g_list_nth(list->start, n);
159  g_return_val_if_fail(tmp != NULL, NULL);
160 
161  return tmp->data;
162 }
163 
164 bool
165 girara_list_contains(girara_list_t* list, void* data)
166 {
167  g_return_val_if_fail(list != NULL, false);
168  if (!list->start) {
169  return false;
170  }
171 
172  GList* tmp = g_list_find(list->start, data);
173  if (tmp == NULL) {
174  return false;
175  }
176 
177  return true;
178 }
179 
180 void*
181 girara_list_find(girara_list_t* list, girara_compare_function_t compare, const void* data)
182 {
183  g_return_val_if_fail(list != NULL && compare != NULL, NULL);
184  if (list->start == NULL) {
185  return NULL;
186  }
187 
188  GList* element = g_list_find_custom(list->start, data, compare);
189  if (element == NULL) {
190  return NULL;
191  }
192 
193  return element->data;
194 }
195 
196 
197 girara_list_iterator_t*
198 girara_list_iterator(girara_list_t* list)
199 {
200  g_return_val_if_fail(list != NULL, NULL);
201 
202  if (list->start == NULL) {
203  return NULL;
204  }
205 
206  girara_list_iterator_t* iter = g_try_malloc0(sizeof(girara_list_iterator_t));
207  if (iter == NULL) {
208  return NULL;
209  }
210 
211  iter->list = list;
212  iter->element = list->start;
213 
214  return iter;
215 }
216 
217 girara_list_iterator_t*
218 girara_list_iterator_copy(girara_list_iterator_t* iter)
219 {
220  g_return_val_if_fail(iter != NULL, NULL);
221 
222  girara_list_iterator_t* iter2 = g_try_malloc0(sizeof(girara_list_iterator_t));
223  if (iter2 == NULL) {
224  return NULL;
225  }
226 
227  iter2->list = iter->list;
228  iter2->element = iter->element;
229  return iter2;
230 }
231 
232 girara_list_iterator_t*
233 girara_list_iterator_next(girara_list_iterator_t* iter)
234 {
235  if (girara_list_iterator_is_valid(iter) == false) {
236  return NULL;
237  }
238 
239  iter->element = g_list_next(iter->element);
240  if (iter->element == NULL) {
241  return NULL;
242  }
243 
244  return iter;
245 }
246 
247 bool
248 girara_list_iterator_has_next(girara_list_iterator_t* iter)
249 {
250  if (girara_list_iterator_is_valid(iter) == false) {
251  return false;
252  }
253 
254  return g_list_next(iter->element);
255 }
256 
257 girara_list_iterator_t*
258 girara_list_iterator_previous(girara_list_iterator_t* iter)
259 {
260  if (girara_list_iterator_is_valid(iter) == false) {
261  return NULL;
262  }
263 
264  iter->element = g_list_previous(iter->element);
265  if (iter->element == NULL) {
266  return NULL;
267  }
268 
269  return iter;
270 }
271 
272 bool
273 girara_list_iterator_has_previous(girara_list_iterator_t* iter)
274 {
275  if (girara_list_iterator_is_valid(iter) == false) {
276  return false;
277  }
278 
279  return g_list_previous(iter->element);
280 }
281 
282 void
283 girara_list_iterator_remove(girara_list_iterator_t* iter) {
284  if (girara_list_iterator_is_valid(iter) == false) {
285  return;
286  }
287 
288  GList* el = iter->element;
289  if (iter->list != NULL && iter->list->free != NULL) {
290  (iter->list->free)(iter->element->data);
291  }
292 
293  iter->element = el->next;
294  iter->list->start = g_list_delete_link(iter->list->start, el);
295 }
296 
297 bool
298 girara_list_iterator_is_valid(girara_list_iterator_t* iter)
299 {
300  return iter != NULL && iter->element != NULL;
301 }
302 
303 void*
304 girara_list_iterator_data(girara_list_iterator_t* iter)
305 {
306  g_return_val_if_fail(girara_list_iterator_is_valid(iter), NULL);
307 
308  return iter->element->data;
309 }
310 
311 void
312 girara_list_iterator_set(girara_list_iterator_t* iter, void *data)
313 {
314  g_return_if_fail(girara_list_iterator_is_valid(iter));
315  g_return_if_fail(iter->list->cmp == NULL);
316 
317  if (iter->list->free != NULL) {
318  (*iter->list->free)(iter->element->data);
319  }
320 
321  iter->element->data = data;
322 }
323 
324 void
325 girara_list_iterator_free(girara_list_iterator_t* iter)
326 {
327  if (iter == NULL) {
328  return;
329  }
330 
331  g_free(iter);
332 }
333 
334 size_t
335 girara_list_size(girara_list_t* list)
336 {
337  g_return_val_if_fail(list, 0);
338 
339  if (list->start == NULL) {
340  return 0;
341  }
342 
343  return g_list_length(list->start);
344 }
345 
346 ssize_t
347 girara_list_position(girara_list_t* list, void* data)
348 {
349  g_return_val_if_fail(list != NULL, -1);
350 
351  if (list->start == NULL) {
352  return -1;
353  }
354 
355  size_t pos = 0;
356  GIRARA_LIST_FOREACH(list, void*, iter, tmp)
357  if (tmp == data) {
359  return pos;
360  }
361  ++pos;
362  GIRARA_LIST_FOREACH_END(list, void*, iter, tmp);
363 
364  return -1;
365 }
366 
367 void
368 girara_list_sort(girara_list_t* list, girara_compare_function_t compare)
369 {
370  g_return_if_fail(list != NULL);
371  if (list->start == NULL || compare == NULL) {
372  return;
373  }
374 
375  list->start = g_list_sort(list->start, compare);
376 }
377 
378 void
379 girara_list_foreach(girara_list_t* list, girara_list_callback_t callback, void* data)
380 {
381  g_return_if_fail(list && list->start && callback);
382 
383  g_list_foreach(list->start, callback, data);
384 }
385 
386 girara_list_t*
387 girara_list_merge(girara_list_t* list, girara_list_t* other)
388 {
389  if (list == NULL) {
390  return other;
391  }
392  if (other == NULL) {
393  return list;
394  }
395 
396  if (list->free != other->free) {
397  girara_warning("girara_list_merge: merging lists with different free functions!");
398  }
399  other->free = NULL;
400 
401  GIRARA_LIST_FOREACH(other, void*, iter, data)
402  girara_list_append(list, data);
403  GIRARA_LIST_FOREACH_END(other, void*, iter, data);
404  return list;
405 }
406 
407 girara_tree_node_t*
408 girara_node_new(void* data)
409 {
410  girara_tree_node_t* node = g_try_malloc0(sizeof(girara_tree_node_t));
411  if (node == NULL) {
412  return NULL;
413  }
414 
415  girara_tree_node_data_t* nodedata = g_try_malloc0(sizeof(girara_tree_node_data_t));
416  if (nodedata == NULL) {
417  g_free(node);
418  return NULL;
419  }
420 
421  nodedata->data = data;
422  nodedata->node = node;
423  node->node = g_node_new(nodedata);
424 
425  if (node->node == NULL) {
426  g_free(node);
427  g_free(nodedata);
428  return NULL;
429  }
430 
431  return node;
432 }
433 
434 void
436 {
437  g_return_if_fail(node);
438  node->free = gfree;
439 }
440 
441 void
442 girara_node_free(girara_tree_node_t* node)
443 {
444  if (node == NULL) {
445  return;
446  }
447 
448  g_return_if_fail(node->node);
449  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
450  g_return_if_fail(nodedata);
451 
452  if (node->free != NULL) {
453  (*node->free)(nodedata->data);
454  }
455 
456  g_free(nodedata);
457 
458  GNode* childnode = node->node->children;
459  while (childnode != NULL) {
460  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
461  girara_node_free(nodedata->node);
462  childnode = childnode->next;
463  }
464 
465  g_node_destroy(node->node);
466  g_free(node);
467 }
468 
469 void
470 girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child)
471 {
472  g_return_if_fail(parent && child);
473  g_node_append(parent->node, child->node);
474 }
475 
476 girara_tree_node_t*
477 girara_node_append_data(girara_tree_node_t* parent, void* data)
478 {
479  g_return_val_if_fail(parent, NULL);
480  girara_tree_node_t* child = girara_node_new(data);
481  g_return_val_if_fail(child, NULL);
482  child->free = parent->free;
483  girara_node_append(parent, child);
484 
485  return child;
486 }
487 
488 girara_tree_node_t*
489 girara_node_get_parent(girara_tree_node_t* node)
490 {
491  g_return_val_if_fail(node && node->node, NULL);
492 
493  if (node->node->parent == NULL) {
494  return NULL;
495  }
496 
497  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->parent->data;
498  g_return_val_if_fail(nodedata, NULL);
499 
500  return nodedata->node;
501 }
502 
503 girara_tree_node_t*
504 girara_node_get_root(girara_tree_node_t* node)
505 {
506  g_return_val_if_fail(node && node->node, NULL);
507 
508  if (node->node->parent == NULL) {
509  return node;
510  }
511 
512  GNode* root = g_node_get_root(node->node);
513  g_return_val_if_fail(root, NULL);
515  g_return_val_if_fail(nodedata, NULL);
516 
517  return nodedata->node;
518 }
519 
520 girara_list_t*
521 girara_node_get_children(girara_tree_node_t* node)
522 {
523  g_return_val_if_fail(node, NULL);
524  girara_list_t* list = girara_list_new();
525  g_return_val_if_fail(list, NULL);
526 
527  GNode* childnode = node->node->children;
528  while (childnode != NULL) {
529  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
530  girara_list_append(list, nodedata->node);
531  childnode = childnode->next;
532  }
533 
534  return list;
535 }
536 
537 size_t
538 girara_node_get_num_children(girara_tree_node_t* node)
539 {
540  g_return_val_if_fail(node && node->node, 0);
541 
542  return g_node_n_children(node->node);
543 }
544 
545 void*
546 girara_node_get_data(girara_tree_node_t* node)
547 {
548  g_return_val_if_fail(node && node->node, NULL);
549  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
550  g_return_val_if_fail(nodedata, NULL);
551 
552  return nodedata->data;
553 }
554 
555 void
556 girara_node_set_data(girara_tree_node_t* node, void* data)
557 {
558  g_return_if_fail(node && node->node);
559  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
560  g_return_if_fail(nodedata);
561 
562  if (node->free != NULL) {
563  (*node->free)(nodedata->data);
564  }
565 
566  nodedata->data = data;
567 }
void girara_list_remove(girara_list_t *list, void *data)
void * girara_list_nth(girara_list_t *list, size_t n)
void girara_list_sort(girara_list_t *list, girara_compare_function_t compare)
girara_free_function_t free
void girara_list_foreach(girara_list_t *list, girara_list_callback_t callback, void *data)
girara_tree_node_t * girara_node_append_data(girara_tree_node_t *parent, void *data)
girara_tree_node_t * girara_node_get_root(girara_tree_node_t *node)
girara_list_t * girara_node_get_children(girara_tree_node_t *node)
void girara_list_append(girara_list_t *list, void *data)
bool girara_list_iterator_has_next(girara_list_iterator_t *iter)
ssize_t girara_list_position(girara_list_t *list, void *data)
void(* girara_free_function_t)(void *data)
Definition: types.h:118
size_t girara_list_size(girara_list_t *list)
girara_list_t * girara_list_new2(girara_free_function_t gfree)
void girara_node_set_data(girara_tree_node_t *node, void *data)
size_t girara_node_get_num_children(girara_tree_node_t *node)
void girara_list_free(girara_list_t *list)
void girara_list_iterator_set(girara_list_iterator_t *iter, void *data)
void * girara_list_find(girara_list_t *list, girara_compare_function_t compare, const void *data)
void girara_list_set_free_function(girara_list_t *list, girara_free_function_t gfree)
int(* girara_compare_function_t)(const void *data1, const void *data2)
Definition: types.h:134
bool girara_list_iterator_has_previous(girara_list_iterator_t *iter)
void girara_node_append(girara_tree_node_t *parent, girara_tree_node_t *child)
void girara_node_set_free_function(girara_tree_node_t *node, girara_free_function_t gfree)
girara_tree_node_t * girara_node_new(void *data)
girara_tree_node_t * node
girara_list_t * girara_list_new(void)
void(* girara_list_callback_t)(void *data, void *userdata)
Definition: types.h:126
girara_list_t * girara_sorted_list_new(girara_compare_function_t cmp)
void girara_list_iterator_free(girara_list_iterator_t *iter)
girara_compare_function_t cmp
girara_free_function_t free
girara_list_t * girara_sorted_list_new2(girara_compare_function_t cmp, girara_free_function_t gfree)
void girara_list_prepend(girara_list_t *list, void *data)
girara_list_iterator_t * girara_list_iterator_copy(girara_list_iterator_t *iter)
#define girara_warning(...)
Definition: utils.h:129
girara_tree_node_t * girara_node_get_parent(girara_tree_node_t *node)
bool girara_list_contains(girara_list_t *list, void *data)
void * girara_node_get_data(girara_tree_node_t *node)
girara_list_iterator_t * girara_list_iterator(girara_list_t *list)
void * girara_list_iterator_data(girara_list_iterator_t *iter)
girara_list_iterator_t * girara_list_iterator_previous(girara_list_iterator_t *iter)
girara_list_iterator_t * girara_list_iterator_next(girara_list_iterator_t *iter)
girara_list_t * girara_list_merge(girara_list_t *list, girara_list_t *other)
bool girara_list_iterator_is_valid(girara_list_iterator_t *iter)
girara_list_t * list
void girara_list_clear(girara_list_t *list)
void girara_list_iterator_remove(girara_list_iterator_t *iter)
void girara_node_free(girara_tree_node_t *node)
#define GIRARA_LIST_FOREACH_END(list, type, iter, data)
#define GIRARA_LIST_FOREACH(list, type, iter, data)