girara
datastructures.c
Go to the documentation of this file.
00001 /* See LICENSE file for license and copyright information */
00002 
00003 #include <stdlib.h>
00004 #include <glib.h>
00005 
00006 #include "datastructures.h"
00007 #include "utils.h"
00008 
00009 struct girara_tree_node_s
00010 {
00011   girara_free_function_t free; 
00012   GNode* node; /* The node object */
00013 };
00014 
00015 typedef struct girara_tree_node_data_s
00016 {
00017   girara_tree_node_t* node; 
00018   void* data; 
00019 } girara_tree_node_data_t;
00020 
00021 struct girara_list_s
00022 {
00023   girara_free_function_t free; 
00024   girara_compare_function_t cmp; 
00025   GList* start; 
00026 };
00027 
00028 struct girara_list_iterator_s
00029 {
00030   girara_list_t* list; 
00031   GList* element; 
00032 };
00033 
00034 girara_list_t*
00035 girara_list_new(void)
00036 {
00037   girara_list_t* list = g_malloc0(sizeof(girara_list_t));
00038 
00039   return list;
00040 }
00041 
00042 girara_list_t*
00043 girara_list_new2(girara_free_function_t gfree)
00044 {
00045   girara_list_t* list = girara_list_new();
00046   if (list == NULL) {
00047     return NULL;
00048   }
00049 
00050   girara_list_set_free_function(list, gfree);
00051   return list;
00052 }
00053 
00054 girara_list_t*
00055 girara_sorted_list_new(girara_compare_function_t cmp)
00056 {
00057   girara_list_t* list = girara_list_new();
00058   if (list == NULL) {
00059     return NULL;
00060   }
00061 
00062   list->cmp = cmp;
00063   return list;
00064 }
00065 
00066 girara_list_t*
00067 girara_sorted_list_new2(girara_compare_function_t cmp, girara_free_function_t gfree)
00068 {
00069   girara_list_t* list = girara_list_new2(gfree);
00070   if (list == NULL) {
00071     return NULL;
00072   }
00073 
00074   list->cmp = cmp;
00075   return list;
00076 }
00077 
00078 void
00079 girara_list_set_free_function(girara_list_t* list, girara_free_function_t gfree)
00080 {
00081   g_return_if_fail(list);
00082   list->free = gfree;
00083 }
00084 
00085 void
00086 girara_list_clear(girara_list_t* list)
00087 {
00088   if (list == NULL || list->start == NULL) {
00089     return;
00090   }
00091 
00092   if (list->free) {
00093 #if (GLIB_MAJOR_VERSION >= 2) && (GLIB_MINOR_VERSION >= 28)
00094     g_list_free_full(list->start, list->free);
00095 #else
00096     g_list_foreach(list->start, (GFunc)list->free, NULL);
00097     g_list_free(list->start);
00098 #endif
00099   } else {
00100     g_list_free(list->start);
00101   }
00102   list->start = NULL;
00103 }
00104 
00105 void
00106 girara_list_free(girara_list_t* list)
00107 {
00108   if (!list) {
00109     return;
00110   }
00111 
00112   girara_list_clear(list);
00113   g_free(list);
00114 }
00115 
00116 void
00117 girara_list_append(girara_list_t* list, void* data)
00118 {
00119   g_return_if_fail(list);
00120 
00121   if (list->cmp) {
00122     list->start = g_list_insert_sorted(list->start, data, list->cmp);
00123   } else {
00124     list->start = g_list_append(list->start, data);
00125   }
00126 }
00127 
00128 void
00129 girara_list_prepend(girara_list_t* list, void* data)
00130 {
00131   g_return_if_fail(list);
00132 
00133   if (list->cmp) {
00134     girara_list_append(list, data);
00135   } else {
00136     list->start = g_list_prepend(list->start, data);
00137   }
00138 }
00139 
00140 void
00141 girara_list_remove(girara_list_t* list, void* data)
00142 {
00143   g_return_if_fail(list);
00144   if (!list->start) {
00145     return;
00146   }
00147 
00148   GList* tmp = g_list_find(list->start, data);
00149   if (!tmp) {
00150     return;
00151   }
00152 
00153   if (list->free) {
00154     (list->free)(tmp->data);
00155   }
00156   list->start = g_list_delete_link(list->start, tmp);
00157 }
00158 
00159 void*
00160 girara_list_nth(girara_list_t* list, size_t n)
00161 {
00162   g_return_val_if_fail(list, NULL);
00163   g_return_val_if_fail(!list->start || (n < g_list_length(list->start)), NULL);
00164 
00165   GList* tmp = g_list_nth(list->start, n);
00166   g_return_val_if_fail(tmp, NULL);
00167 
00168   return tmp->data;
00169 }
00170 
00171 bool
00172 girara_list_contains(girara_list_t* list, void* data)
00173 {
00174   g_return_val_if_fail(list, false);
00175   if (!list->start) {
00176     return false;
00177   }
00178 
00179   GList* tmp = g_list_find(list->start, data);
00180 
00181   if (!tmp) {
00182     return false;
00183   }
00184 
00185   return true;
00186 }
00187 
00188 void*
00189 girara_list_find(girara_list_t* list, girara_compare_function_t compare, const void* data)
00190 {
00191   g_return_val_if_fail(list && compare, NULL);
00192   if (list->start == NULL) {
00193     return NULL;
00194   }
00195 
00196   GList* element = g_list_find_custom(list->start, data, compare);
00197   if (element == NULL) {
00198     return NULL;
00199   }
00200 
00201   return element->data;
00202 }
00203 
00204 
00205 girara_list_iterator_t*
00206 girara_list_iterator(girara_list_t* list)
00207 {
00208   g_return_val_if_fail(list, NULL);
00209 
00210   if (!list->start) {
00211     return NULL;
00212   }
00213 
00214   girara_list_iterator_t* iter = g_malloc0(sizeof(girara_list_iterator_t));
00215   iter->list = list;
00216   iter->element = list->start;
00217 
00218   return iter;
00219 }
00220 
00221 girara_list_iterator_t*
00222 girara_list_iterator_next(girara_list_iterator_t* iter)
00223 {
00224   if (!iter || !iter->element) {
00225     return NULL;
00226   }
00227 
00228   iter->element = g_list_next(iter->element);
00229 
00230   if (!iter->element) {
00231     return NULL;
00232   }
00233 
00234   return iter;
00235 }
00236 
00237 bool
00238 girara_list_iterator_has_next(girara_list_iterator_t* iter)
00239 {
00240   return iter && iter->element && g_list_next(iter->element);
00241 }
00242 
00243 bool
00244 girara_list_iterator_is_valid(girara_list_iterator_t* iter)
00245 {
00246   return iter && iter->element;
00247 }
00248 
00249 void*
00250 girara_list_iterator_data(girara_list_iterator_t* iter)
00251 {
00252   g_return_val_if_fail(iter && iter->element, NULL);
00253 
00254   return iter->element->data;
00255 }
00256 
00257 void
00258 girara_list_iterator_set(girara_list_iterator_t* iter, void *data)
00259 {
00260   g_return_if_fail(iter && iter->element && iter->list && !iter->list->cmp);
00261 
00262   if (iter->list->free) {
00263     (*iter->list->free)(iter->element->data);
00264   }
00265 
00266   iter->element->data = data;
00267 }
00268 
00269 void
00270 girara_list_iterator_free(girara_list_iterator_t* iter)
00271 {
00272   if (!iter) {
00273     return;
00274   }
00275 
00276   g_free(iter);
00277 }
00278 
00279 size_t
00280 girara_list_size(girara_list_t* list)
00281 {
00282   g_return_val_if_fail(list, 0);
00283 
00284   if (!list->start) {
00285     return 0;
00286   }
00287 
00288   return g_list_length(list->start);
00289 }
00290 
00291 ssize_t
00292 girara_list_position(girara_list_t* list, void* data)
00293 {
00294   g_return_val_if_fail(list != NULL, -1);
00295 
00296   if (list->start == NULL) {
00297     return -1;
00298   }
00299 
00300   size_t pos = 0;
00301   GIRARA_LIST_FOREACH(list, void*, iter, tmp)
00302     if (tmp == data) {
00303       girara_list_iterator_free(iter);
00304       return pos;
00305     }
00306     ++pos;
00307   GIRARA_LIST_FOREACH_END(list, void*, iter, tmp);
00308 
00309   return -1;
00310 }
00311 
00312 void
00313 girara_list_sort(girara_list_t* list, girara_compare_function_t compare)
00314 {
00315   g_return_if_fail(list != NULL);
00316   if (list->start == NULL || compare == NULL) {
00317     return;
00318   }
00319 
00320   list->start = g_list_sort(list->start, compare);
00321 }
00322 
00323 void
00324 girara_list_foreach(girara_list_t* list, girara_list_callback_t callback, void* data)
00325 {
00326   g_return_if_fail(list && list->start && callback);
00327 
00328   g_list_foreach(list->start, callback, data);
00329 }
00330 
00331 girara_list_t*
00332 girara_list_merge(girara_list_t* list, girara_list_t* other)
00333 {
00334   if (list == NULL) {
00335     return other;
00336   }
00337   if (other == NULL) {
00338     return list;
00339   }
00340 
00341   if (list->free != other->free) {
00342     girara_warning("girara_list_merge: merging lists with different free functions!");
00343   }
00344   other->free = NULL;
00345 
00346   GIRARA_LIST_FOREACH(other, void*, iter, data)
00347     girara_list_append(list, data);
00348   GIRARA_LIST_FOREACH_END(other, void*, iter, data);
00349   return list;
00350 }
00351 
00352 girara_tree_node_t*
00353 girara_node_new(void* data)
00354 {
00355   girara_tree_node_t* node = g_malloc0(sizeof(girara_tree_node_t));
00356   girara_tree_node_data_t* nodedata = g_malloc0(sizeof(girara_tree_node_data_t));
00357 
00358   nodedata->data = data;
00359   nodedata->node = node;
00360   node->node = g_node_new(nodedata);
00361 
00362   if (!node->node) {
00363     g_free(node);
00364     g_free(nodedata);
00365     return NULL;
00366   }
00367 
00368   return node;
00369 }
00370 
00371 void
00372 girara_node_set_free_function(girara_tree_node_t* node, girara_free_function_t gfree)
00373 {
00374   g_return_if_fail(node);
00375   node->free = gfree;
00376 }
00377 
00378 void
00379 girara_node_free(girara_tree_node_t* node)
00380 {
00381   if (!node) {
00382     return;
00383   }
00384 
00385   g_return_if_fail(node->node);
00386   girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
00387   g_return_if_fail(nodedata);
00388 
00389   if (node->free) {
00390     (*node->free)(nodedata->data);
00391   }
00392 
00393   g_free(nodedata);
00394 
00395   GNode* childnode = node->node->children;
00396   while (childnode) {
00397     girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
00398     girara_node_free(nodedata->node);
00399     childnode = childnode->next;
00400   }
00401 
00402   g_node_destroy(node->node);
00403   g_free(node);
00404 }
00405 
00406 void
00407 girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child)
00408 {
00409   g_return_if_fail(parent && child);
00410   g_node_append(parent->node, child->node);
00411 }
00412 
00413 girara_tree_node_t*
00414 girara_node_append_data(girara_tree_node_t* parent, void* data)
00415 {
00416   g_return_val_if_fail(parent, NULL);
00417   girara_tree_node_t* child = girara_node_new(data);
00418   g_return_val_if_fail(child, NULL);
00419   child->free = parent->free;
00420   girara_node_append(parent, child);
00421 
00422   return child;
00423 }
00424 
00425 girara_tree_node_t*
00426 girara_node_get_parent(girara_tree_node_t* node)
00427 {
00428   g_return_val_if_fail(node && node->node, NULL);
00429 
00430   if (!node->node->parent) {
00431     return NULL;
00432   }
00433 
00434   girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->parent->data;
00435   g_return_val_if_fail(nodedata, NULL);
00436 
00437   return nodedata->node;
00438 }
00439 
00440 girara_tree_node_t*
00441 girara_node_get_root(girara_tree_node_t* node)
00442 {
00443   g_return_val_if_fail(node && node->node, NULL);
00444 
00445   if (!node->node->parent) {
00446     return node;
00447   }
00448 
00449   GNode* root = g_node_get_root(node->node);
00450   g_return_val_if_fail(root, NULL);
00451   girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) root->data;
00452   g_return_val_if_fail(nodedata, NULL);
00453 
00454   return nodedata->node;
00455 }
00456 
00457 girara_list_t*
00458 girara_node_get_children(girara_tree_node_t* node)
00459 {
00460   g_return_val_if_fail(node, NULL);
00461   girara_list_t* list = girara_list_new();
00462   g_return_val_if_fail(list, NULL);
00463 
00464   GNode* childnode = node->node->children;
00465   while (childnode) {
00466     girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
00467     girara_list_append(list, nodedata->node);
00468     childnode = childnode->next;
00469   }
00470 
00471   return list;
00472 }
00473 
00474 size_t
00475 girara_node_get_num_children(girara_tree_node_t* node)
00476 {
00477   g_return_val_if_fail(node && node->node, 0);
00478 
00479   return g_node_n_children(node->node);
00480 }
00481 
00482 void*
00483 girara_node_get_data(girara_tree_node_t* node)
00484 {
00485   g_return_val_if_fail(node && node->node, NULL);
00486   girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
00487   g_return_val_if_fail(nodedata, NULL);
00488 
00489   return nodedata->data;
00490 }
00491 
00492 void
00493 girara_node_set_data(girara_tree_node_t* node, void* data)
00494 {
00495   g_return_if_fail(node && node->node);
00496   girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
00497   g_return_if_fail(nodedata);
00498 
00499   if (node->free) {
00500     (*node->free)(nodedata->data);
00501   }
00502 
00503   nodedata->data = data;
00504 }
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Defines