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) {
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);
120 
121  if (list->cmp) {
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);
132 
133  if (list->cmp) {
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);
144  if (!list->start) {
145  return;
146  }
147 
148  GList* tmp = g_list_find(list->start, data);
149  if (!tmp) {
150  return;
151  }
152 
153  if (list->free) {
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_next(girara_list_iterator_t* iter)
223 {
224  if (!iter || !iter->element) {
225  return NULL;
226  }
227 
228  iter->element = g_list_next(iter->element);
229 
230  if (!iter->element) {
231  return NULL;
232  }
233 
234  return iter;
235 }
236 
237 bool
238 girara_list_iterator_has_next(girara_list_iterator_t* iter)
239 {
240  return iter && iter->element && g_list_next(iter->element);
241 }
242 
243 bool
244 girara_list_iterator_is_valid(girara_list_iterator_t* iter)
245 {
246  return iter && iter->element;
247 }
248 
249 void*
250 girara_list_iterator_data(girara_list_iterator_t* iter)
251 {
252  g_return_val_if_fail(iter && iter->element, NULL);
253 
254  return iter->element->data;
255 }
256 
257 void
258 girara_list_iterator_set(girara_list_iterator_t* iter, void *data)
259 {
260  g_return_if_fail(iter && iter->element && iter->list && !iter->list->cmp);
261 
262  if (iter->list->free) {
263  (*iter->list->free)(iter->element->data);
264  }
265 
266  iter->element->data = data;
267 }
268 
269 void
270 girara_list_iterator_free(girara_list_iterator_t* iter)
271 {
272  if (!iter) {
273  return;
274  }
275 
276  g_free(iter);
277 }
278 
279 size_t
280 girara_list_size(girara_list_t* list)
281 {
282  g_return_val_if_fail(list, 0);
283 
284  if (!list->start) {
285  return 0;
286  }
287 
288  return g_list_length(list->start);
289 }
290 
291 ssize_t
292 girara_list_position(girara_list_t* list, void* data)
293 {
294  g_return_val_if_fail(list != NULL, -1);
295 
296  if (list->start == NULL) {
297  return -1;
298  }
299 
300  size_t pos = 0;
301  GIRARA_LIST_FOREACH(list, void*, iter, tmp)
302  if (tmp == data) {
304  return pos;
305  }
306  ++pos;
307  GIRARA_LIST_FOREACH_END(list, void*, iter, tmp);
308 
309  return -1;
310 }
311 
312 void
313 girara_list_sort(girara_list_t* list, girara_compare_function_t compare)
314 {
315  g_return_if_fail(list != NULL);
316  if (list->start == NULL || compare == NULL) {
317  return;
318  }
319 
320  list->start = g_list_sort(list->start, compare);
321 }
322 
323 void
324 girara_list_foreach(girara_list_t* list, girara_list_callback_t callback, void* data)
325 {
326  g_return_if_fail(list && list->start && callback);
327 
328  g_list_foreach(list->start, callback, data);
329 }
330 
331 girara_list_t*
332 girara_list_merge(girara_list_t* list, girara_list_t* other)
333 {
334  if (list == NULL) {
335  return other;
336  }
337  if (other == NULL) {
338  return list;
339  }
340 
341  if (list->free != other->free) {
342  girara_warning("girara_list_merge: merging lists with different free functions!");
343  }
344  other->free = NULL;
345 
346  GIRARA_LIST_FOREACH(other, void*, iter, data)
347  girara_list_append(list, data);
348  GIRARA_LIST_FOREACH_END(other, void*, iter, data);
349  return list;
350 }
351 
352 girara_tree_node_t*
353 girara_node_new(void* data)
354 {
355  girara_tree_node_t* node = g_malloc0(sizeof(girara_tree_node_t));
356  girara_tree_node_data_t* nodedata = g_malloc0(sizeof(girara_tree_node_data_t));
357 
358  nodedata->data = data;
359  nodedata->node = node;
360  node->node = g_node_new(nodedata);
361 
362  if (!node->node) {
363  g_free(node);
364  g_free(nodedata);
365  return NULL;
366  }
367 
368  return node;
369 }
370 
371 void
373 {
374  g_return_if_fail(node);
375  node->free = gfree;
376 }
377 
378 void
379 girara_node_free(girara_tree_node_t* node)
380 {
381  if (!node) {
382  return;
383  }
384 
385  g_return_if_fail(node->node);
386  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
387  g_return_if_fail(nodedata);
388 
389  if (node->free) {
390  (*node->free)(nodedata->data);
391  }
392 
393  g_free(nodedata);
394 
395  GNode* childnode = node->node->children;
396  while (childnode) {
397  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
398  girara_node_free(nodedata->node);
399  childnode = childnode->next;
400  }
401 
402  g_node_destroy(node->node);
403  g_free(node);
404 }
405 
406 void
407 girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child)
408 {
409  g_return_if_fail(parent && child);
410  g_node_append(parent->node, child->node);
411 }
412 
413 girara_tree_node_t*
414 girara_node_append_data(girara_tree_node_t* parent, void* data)
415 {
416  g_return_val_if_fail(parent, NULL);
417  girara_tree_node_t* child = girara_node_new(data);
418  g_return_val_if_fail(child, NULL);
419  child->free = parent->free;
420  girara_node_append(parent, child);
421 
422  return child;
423 }
424 
425 girara_tree_node_t*
426 girara_node_get_parent(girara_tree_node_t* node)
427 {
428  g_return_val_if_fail(node && node->node, NULL);
429 
430  if (!node->node->parent) {
431  return NULL;
432  }
433 
434  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->parent->data;
435  g_return_val_if_fail(nodedata, NULL);
436 
437  return nodedata->node;
438 }
439 
440 girara_tree_node_t*
441 girara_node_get_root(girara_tree_node_t* node)
442 {
443  g_return_val_if_fail(node && node->node, NULL);
444 
445  if (!node->node->parent) {
446  return node;
447  }
448 
449  GNode* root = g_node_get_root(node->node);
450  g_return_val_if_fail(root, NULL);
452  g_return_val_if_fail(nodedata, NULL);
453 
454  return nodedata->node;
455 }
456 
457 girara_list_t*
458 girara_node_get_children(girara_tree_node_t* node)
459 {
460  g_return_val_if_fail(node, NULL);
461  girara_list_t* list = girara_list_new();
462  g_return_val_if_fail(list, NULL);
463 
464  GNode* childnode = node->node->children;
465  while (childnode) {
466  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
467  girara_list_append(list, nodedata->node);
468  childnode = childnode->next;
469  }
470 
471  return list;
472 }
473 
474 size_t
475 girara_node_get_num_children(girara_tree_node_t* node)
476 {
477  g_return_val_if_fail(node && node->node, 0);
478 
479  return g_node_n_children(node->node);
480 }
481 
482 void*
483 girara_node_get_data(girara_tree_node_t* node)
484 {
485  g_return_val_if_fail(node && node->node, NULL);
486  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
487  g_return_val_if_fail(nodedata, NULL);
488 
489  return nodedata->data;
490 }
491 
492 void
493 girara_node_set_data(girara_tree_node_t* node, void* data)
494 {
495  g_return_if_fail(node && node->node);
496  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
497  g_return_if_fail(nodedata);
498 
499  if (node->free) {
500  (*node->free)(nodedata->data);
501  }
502 
503  nodedata->data = data;
504 }