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