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) {
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);
156  g_return_val_if_fail(!list->start || (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);
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, false);
168  if (!list->start) {
169  return false;
170  }
171 
172  GList* tmp = g_list_find(list->start, data);
173 
174  if (!tmp) {
175  return false;
176  }
177 
178  return true;
179 }
180 
181 void*
182 girara_list_find(girara_list_t* list, girara_compare_function_t compare, const void* data)
183 {
184  g_return_val_if_fail(list && compare, NULL);
185  if (list->start == NULL) {
186  return NULL;
187  }
188 
189  GList* element = g_list_find_custom(list->start, data, compare);
190  if (element == NULL) {
191  return NULL;
192  }
193 
194  return element->data;
195 }
196 
197 
198 girara_list_iterator_t*
199 girara_list_iterator(girara_list_t* list)
200 {
201  g_return_val_if_fail(list != NULL, NULL);
202 
203  if (list->start == NULL) {
204  return NULL;
205  }
206 
207  girara_list_iterator_t* iter = g_try_malloc0(sizeof(girara_list_iterator_t));
208  if (iter == NULL) {
209  return NULL;
210  }
211 
212  iter->list = list;
213  iter->element = list->start;
214 
215  return iter;
216 }
217 
218 girara_list_iterator_t*
219 girara_list_iterator_copy(girara_list_iterator_t* iter)
220 {
221  g_return_val_if_fail(iter != NULL, NULL);
222 
223  girara_list_iterator_t* iter2 = g_try_malloc0(sizeof(girara_list_iterator_t));
224  if (iter2 == NULL) {
225  return NULL;
226  }
227 
228  iter2->list = iter->list;
229  iter2->element = iter->element;
230  return iter2;
231 }
232 
233 girara_list_iterator_t*
234 girara_list_iterator_next(girara_list_iterator_t* iter)
235 {
236  if (!iter || !iter->element) {
237  return NULL;
238  }
239 
240  iter->element = g_list_next(iter->element);
241 
242  if (!iter->element) {
243  return NULL;
244  }
245 
246  return iter;
247 }
248 
249 bool
250 girara_list_iterator_has_next(girara_list_iterator_t* iter)
251 {
252  return iter && iter->element && g_list_next(iter->element);
253 }
254 
255 girara_list_iterator_t*
256 girara_list_iterator_previous(girara_list_iterator_t* iter)
257 {
258  if (!iter || !iter->element) {
259  return NULL;
260  }
261 
262  iter->element = g_list_previous(iter->element);
263 
264  if (!iter->element) {
265  return NULL;
266  }
267 
268  return iter;
269 }
270 
271 bool
272 girara_list_iterator_has_previous(girara_list_iterator_t* iter)
273 {
274  return iter && iter->element && g_list_previous(iter->element);
275 }
276 
277 void
278 girara_list_iterator_remove(girara_list_iterator_t* iter) {
279  if (iter && iter->element) {
280  GList *el = iter->element;
281  if (iter->list && iter->list->free) {
282  (iter->list->free)(iter->element->data);
283  }
284 
285  iter->element = el->next;
286  iter->list->start = g_list_delete_link(iter->list->start, el);
287  }
288 }
289 
290 bool
291 girara_list_iterator_is_valid(girara_list_iterator_t* iter)
292 {
293  return iter && iter->element;
294 }
295 
296 void*
297 girara_list_iterator_data(girara_list_iterator_t* iter)
298 {
299  g_return_val_if_fail(iter && iter->element, NULL);
300 
301  return iter->element->data;
302 }
303 
304 void
305 girara_list_iterator_set(girara_list_iterator_t* iter, void *data)
306 {
307  g_return_if_fail(iter && iter->element && iter->list && !iter->list->cmp);
308 
309  if (iter->list->free) {
310  (*iter->list->free)(iter->element->data);
311  }
312 
313  iter->element->data = data;
314 }
315 
316 void
317 girara_list_iterator_free(girara_list_iterator_t* iter)
318 {
319  if (!iter) {
320  return;
321  }
322 
323  g_free(iter);
324 }
325 
326 size_t
327 girara_list_size(girara_list_t* list)
328 {
329  g_return_val_if_fail(list, 0);
330 
331  if (!list->start) {
332  return 0;
333  }
334 
335  return g_list_length(list->start);
336 }
337 
338 ssize_t
339 girara_list_position(girara_list_t* list, void* data)
340 {
341  g_return_val_if_fail(list != NULL, -1);
342 
343  if (list->start == NULL) {
344  return -1;
345  }
346 
347  size_t pos = 0;
348  GIRARA_LIST_FOREACH(list, void*, iter, tmp)
349  if (tmp == data) {
351  return pos;
352  }
353  ++pos;
354  GIRARA_LIST_FOREACH_END(list, void*, iter, tmp);
355 
356  return -1;
357 }
358 
359 void
360 girara_list_sort(girara_list_t* list, girara_compare_function_t compare)
361 {
362  g_return_if_fail(list != NULL);
363  if (list->start == NULL || compare == NULL) {
364  return;
365  }
366 
367  list->start = g_list_sort(list->start, compare);
368 }
369 
370 void
371 girara_list_foreach(girara_list_t* list, girara_list_callback_t callback, void* data)
372 {
373  g_return_if_fail(list && list->start && callback);
374 
375  g_list_foreach(list->start, callback, data);
376 }
377 
378 girara_list_t*
379 girara_list_merge(girara_list_t* list, girara_list_t* other)
380 {
381  if (list == NULL) {
382  return other;
383  }
384  if (other == NULL) {
385  return list;
386  }
387 
388  if (list->free != other->free) {
389  girara_warning("girara_list_merge: merging lists with different free functions!");
390  }
391  other->free = NULL;
392 
393  GIRARA_LIST_FOREACH(other, void*, iter, data)
394  girara_list_append(list, data);
395  GIRARA_LIST_FOREACH_END(other, void*, iter, data);
396  return list;
397 }
398 
399 girara_tree_node_t*
400 girara_node_new(void* data)
401 {
402  girara_tree_node_t* node = g_try_malloc0(sizeof(girara_tree_node_t));
403  if (node == NULL) {
404  return NULL;
405  }
406 
407  girara_tree_node_data_t* nodedata = g_try_malloc0(sizeof(girara_tree_node_data_t));
408  if (nodedata == NULL) {
409  g_free(node);
410  return NULL;
411  }
412 
413  nodedata->data = data;
414  nodedata->node = node;
415  node->node = g_node_new(nodedata);
416 
417  if (node->node == NULL) {
418  g_free(node);
419  g_free(nodedata);
420  return NULL;
421  }
422 
423  return node;
424 }
425 
426 void
428 {
429  g_return_if_fail(node);
430  node->free = gfree;
431 }
432 
433 void
434 girara_node_free(girara_tree_node_t* node)
435 {
436  if (!node) {
437  return;
438  }
439 
440  g_return_if_fail(node->node);
441  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
442  g_return_if_fail(nodedata);
443 
444  if (node->free) {
445  (*node->free)(nodedata->data);
446  }
447 
448  g_free(nodedata);
449 
450  GNode* childnode = node->node->children;
451  while (childnode) {
452  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
453  girara_node_free(nodedata->node);
454  childnode = childnode->next;
455  }
456 
457  g_node_destroy(node->node);
458  g_free(node);
459 }
460 
461 void
462 girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child)
463 {
464  g_return_if_fail(parent && child);
465  g_node_append(parent->node, child->node);
466 }
467 
468 girara_tree_node_t*
469 girara_node_append_data(girara_tree_node_t* parent, void* data)
470 {
471  g_return_val_if_fail(parent, NULL);
472  girara_tree_node_t* child = girara_node_new(data);
473  g_return_val_if_fail(child, NULL);
474  child->free = parent->free;
475  girara_node_append(parent, child);
476 
477  return child;
478 }
479 
480 girara_tree_node_t*
481 girara_node_get_parent(girara_tree_node_t* node)
482 {
483  g_return_val_if_fail(node && node->node, NULL);
484 
485  if (!node->node->parent) {
486  return NULL;
487  }
488 
489  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->parent->data;
490  g_return_val_if_fail(nodedata, NULL);
491 
492  return nodedata->node;
493 }
494 
495 girara_tree_node_t*
496 girara_node_get_root(girara_tree_node_t* node)
497 {
498  g_return_val_if_fail(node && node->node, NULL);
499 
500  if (!node->node->parent) {
501  return node;
502  }
503 
504  GNode* root = g_node_get_root(node->node);
505  g_return_val_if_fail(root, NULL);
507  g_return_val_if_fail(nodedata, NULL);
508 
509  return nodedata->node;
510 }
511 
512 girara_list_t*
513 girara_node_get_children(girara_tree_node_t* node)
514 {
515  g_return_val_if_fail(node, NULL);
516  girara_list_t* list = girara_list_new();
517  g_return_val_if_fail(list, NULL);
518 
519  GNode* childnode = node->node->children;
520  while (childnode) {
521  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
522  girara_list_append(list, nodedata->node);
523  childnode = childnode->next;
524  }
525 
526  return list;
527 }
528 
529 size_t
530 girara_node_get_num_children(girara_tree_node_t* node)
531 {
532  g_return_val_if_fail(node && node->node, 0);
533 
534  return g_node_n_children(node->node);
535 }
536 
537 void*
538 girara_node_get_data(girara_tree_node_t* node)
539 {
540  g_return_val_if_fail(node && node->node, NULL);
541  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
542  g_return_val_if_fail(nodedata, NULL);
543 
544  return nodedata->data;
545 }
546 
547 void
548 girara_node_set_data(girara_tree_node_t* node, void* data)
549 {
550  g_return_if_fail(node && node->node);
551  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
552  g_return_if_fail(nodedata);
553 
554  if (node->free) {
555  (*node->free)(nodedata->data);
556  }
557 
558  nodedata->data = data;
559 }