girara
|
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 }