datastructures.c 11.2 KB
Newer Older
1 2
/* See LICENSE file for license and copyright information */

Moritz Lipp's avatar
Moritz Lipp committed
3
#include <stdlib.h>
4 5
#include <glib.h>

Sebastian Ramacher's avatar
Sebastian Ramacher committed
6
#include "datastructures.h"
7
#include "utils.h"
Moritz Lipp's avatar
Moritz Lipp committed
8

9 10
struct girara_tree_node_s
{
Moritz Lipp's avatar
Moritz Lipp committed
11
  GNode* node; /* The node object */
12
  girara_free_function_t free; /**> The free function */
13 14 15 16
};

typedef struct girara_tree_node_data_s
{
Moritz Lipp's avatar
Moritz Lipp committed
17 18
  girara_tree_node_t* node; /**> The node */
  void* data; /**> The data */
19 20 21 22
} girara_tree_node_data_t;

struct girara_list_s
{
23
  GList* start; /**> List start */
Moritz Lipp's avatar
Moritz Lipp committed
24
  girara_free_function_t free; /**> The free function */
Sebastian Ramacher's avatar
Sebastian Ramacher committed
25
  girara_compare_function_t cmp; /**> The sort function */
26 27 28 29
};

struct girara_list_iterator_s
{
Moritz Lipp's avatar
Moritz Lipp committed
30 31
  girara_list_t* list; /**> The list */
  GList* element; /**> The list object */
32 33
};

Sebastian Ramacher's avatar
Sebastian Ramacher committed
34 35
girara_list_t*
girara_list_new(void)
36
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
37
  return girara_list_new2(NULL);
38 39
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
40 41 42
girara_list_t*
girara_list_new2(girara_free_function_t gfree)
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
43
  girara_list_t* list = g_try_malloc0(sizeof(girara_list_t));
Sebastian Ramacher's avatar
Sebastian Ramacher committed
44 45 46 47
  if (list == NULL) {
    return NULL;
  }

Sebastian Ramacher's avatar
Sebastian Ramacher committed
48
  list->free = gfree;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
  return list;
}

girara_list_t*
girara_sorted_list_new(girara_compare_function_t cmp)
{
  girara_list_t* list = girara_list_new();
  if (list == NULL) {
    return NULL;
  }

  list->cmp = cmp;
  return list;
}

girara_list_t*
girara_sorted_list_new2(girara_compare_function_t cmp, girara_free_function_t gfree)
{
  girara_list_t* list = girara_list_new2(gfree);
  if (list == NULL) {
    return NULL;
  }

  list->cmp = cmp;
  return list;
}

void
girara_list_set_free_function(girara_list_t* list, girara_free_function_t gfree)
78
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
79
  g_return_if_fail(list != NULL);
80 81 82
  list->free = gfree;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
83
void
Sebastian Ramacher's avatar
Sebastian Ramacher committed
84
girara_list_clear(girara_list_t* list)
85
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
86
  if (list == NULL || list->start == NULL) {
87
    return;
Moritz Lipp's avatar
Moritz Lipp committed
88
  }
89

Sebastian Ramacher's avatar
Sebastian Ramacher committed
90
  if (list->free != NULL) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
91 92 93
    g_list_free_full(list->start, list->free);
  } else {
    g_list_free(list->start);
94
  }
Sebastian Ramacher's avatar
Sebastian Ramacher committed
95 96 97 98 99 100
  list->start = NULL;
}

void
girara_list_free(girara_list_t* list)
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
101
  if (list == NULL) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
102 103 104 105
    return;
  }

  girara_list_clear(list);
106 107 108
  g_free(list);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
109 110
void
girara_list_append(girara_list_t* list, void* data)
111
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
112
  g_return_if_fail(list != NULL);
Moritz Lipp's avatar
Moritz Lipp committed
113

Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
114
  if (list->cmp != NULL) {
115 116 117
    list->start = g_list_insert_sorted(list->start, data, list->cmp);
  } else {
    list->start = g_list_append(list->start, data);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
118
  }
119 120
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
121 122
void
girara_list_prepend(girara_list_t* list, void* data)
123
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
124
  g_return_if_fail(list != NULL);
Moritz Lipp's avatar
Moritz Lipp committed
125

Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
126
  if (list->cmp != NULL) {
127 128 129
    girara_list_append(list, data);
  } else {
    list->start = g_list_prepend(list->start, data);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
130
  }
131 132
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
133 134
void
girara_list_remove(girara_list_t* list, void* data)
Moritz Lipp's avatar
Moritz Lipp committed
135
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
136 137
  g_return_if_fail(list != NULL);
  if (list->start == NULL) {
138 139
    return;
  }
Moritz Lipp's avatar
Moritz Lipp committed
140

141
  GList* tmp = g_list_find(list->start, data);
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
142
  if (tmp == NULL) {
143 144
    return;
  }
Moritz Lipp's avatar
Moritz Lipp committed
145

Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
146
  if (list->free != NULL) {
147 148 149
    (list->free)(tmp->data);
  }
  list->start = g_list_delete_link(list->start, tmp);
150 151
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
152 153
void*
girara_list_nth(girara_list_t* list, size_t n)
154
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
155
  g_return_val_if_fail(list != NULL, NULL);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
156
  g_return_val_if_fail(list->start != NULL && (n < g_list_length(list->start)), NULL);
Moritz Lipp's avatar
Moritz Lipp committed
157

158
  GList* tmp = g_list_nth(list->start, n);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
159
  g_return_val_if_fail(tmp != NULL, NULL);
160 161 162 163

  return tmp->data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
164 165
bool
girara_list_contains(girara_list_t* list, void* data)
166
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
167
  g_return_val_if_fail(list != NULL, false);
168 169 170
  if (!list->start) {
    return false;
  }
171 172

  GList* tmp = g_list_find(list->start, data);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
173
  if (tmp == NULL) {
174 175
    return false;
  }
Moritz Lipp's avatar
Moritz Lipp committed
176 177

  return true;
Moritz Lipp's avatar
Moritz Lipp committed
178 179
}

180 181 182
void*
girara_list_find(girara_list_t* list, girara_compare_function_t compare, const void* data)
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
183
  g_return_val_if_fail(list != NULL && compare != NULL, NULL);
184 185 186 187 188 189 190 191 192 193 194 195 196
  if (list->start == NULL) {
    return NULL;
  }

  GList* element = g_list_find_custom(list->start, data, compare);
  if (element == NULL) {
    return NULL;
  }

  return element->data;
}


Sebastian Ramacher's avatar
Sebastian Ramacher committed
197 198
girara_list_iterator_t*
girara_list_iterator(girara_list_t* list)
199
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
200
  g_return_val_if_fail(list != NULL, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
201

Sebastian Ramacher's avatar
Sebastian Ramacher committed
202
  if (list->start == NULL) {
203
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
204
  }
205

Sebastian Ramacher's avatar
Sebastian Ramacher committed
206 207 208 209 210 211
  girara_list_iterator_t* iter = g_try_malloc0(sizeof(girara_list_iterator_t));
  if (iter == NULL) {
    return NULL;
  }

  iter->list    = list;
212
  iter->element = list->start;
Moritz Lipp's avatar
Moritz Lipp committed
213

214 215 216
  return iter;
}

217
girara_list_iterator_t*
Sebastian Ramacher's avatar
Sebastian Ramacher committed
218 219 220
girara_list_iterator_copy(girara_list_iterator_t* iter)
{
  g_return_val_if_fail(iter != NULL, NULL);
221

Sebastian Ramacher's avatar
Sebastian Ramacher committed
222 223 224 225 226 227
  girara_list_iterator_t* iter2 = g_try_malloc0(sizeof(girara_list_iterator_t));
  if (iter2 == NULL) {
    return NULL;
  }

  iter2->list    = iter->list;
228 229 230 231
  iter2->element = iter->element;
  return iter2;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
232 233
girara_list_iterator_t*
girara_list_iterator_next(girara_list_iterator_t* iter)
234
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
235
  if (girara_list_iterator_is_valid(iter) == false) {
236
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
237
  }
238 239

  iter->element = g_list_next(iter->element);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
240
  if (iter->element == NULL) {
241
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
242 243
  }

244 245 246
  return iter;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
247 248
bool
girara_list_iterator_has_next(girara_list_iterator_t* iter)
249
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
250 251 252 253 254
  if (girara_list_iterator_is_valid(iter) == false) {
    return false;
  }

  return g_list_next(iter->element);
255 256
}

257 258 259
girara_list_iterator_t*
girara_list_iterator_previous(girara_list_iterator_t* iter)
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
260
  if (girara_list_iterator_is_valid(iter) == false) {
261 262 263 264
    return NULL;
  }

  iter->element = g_list_previous(iter->element);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
265
  if (iter->element == NULL) {
266 267 268 269 270 271 272 273 274
    return NULL;
  }

  return iter;
}

bool
girara_list_iterator_has_previous(girara_list_iterator_t* iter)
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
275 276 277 278 279
  if (girara_list_iterator_is_valid(iter) == false) {
    return false;
  }

  return g_list_previous(iter->element);
280 281 282 283
}

void
girara_list_iterator_remove(girara_list_iterator_t* iter) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
284 285 286
  if (girara_list_iterator_is_valid(iter) == false) {
    return;
  }
287

Sebastian Ramacher's avatar
Sebastian Ramacher committed
288 289 290
  GList* el = iter->element;
  if (iter->list != NULL && iter->list->free != NULL) {
    (iter->list->free)(iter->element->data);
291
  }
Sebastian Ramacher's avatar
Sebastian Ramacher committed
292 293 294

  iter->element     = el->next;
  iter->list->start = g_list_delete_link(iter->list->start, el);
295 296
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
297 298
bool
girara_list_iterator_is_valid(girara_list_iterator_t* iter)
Sebastian Ramacher's avatar
Sebastian Ramacher committed
299
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
300
  return iter != NULL && iter->element != NULL;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
301 302
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
303 304
void*
girara_list_iterator_data(girara_list_iterator_t* iter)
305
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
306
  g_return_val_if_fail(girara_list_iterator_is_valid(iter), NULL);
Moritz Lipp's avatar
Moritz Lipp committed
307

308 309 310
  return iter->element->data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
311 312
void
girara_list_iterator_set(girara_list_iterator_t* iter, void *data)
313
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
314 315
  g_return_if_fail(girara_list_iterator_is_valid(iter));
  g_return_if_fail(iter->list->cmp == NULL);
Moritz Lipp's avatar
Moritz Lipp committed
316

Sebastian Ramacher's avatar
Sebastian Ramacher committed
317
  if (iter->list->free != NULL) {
318
    (*iter->list->free)(iter->element->data);
Moritz Lipp's avatar
Moritz Lipp committed
319 320
  }

321 322 323
  iter->element->data = data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
324 325
void
girara_list_iterator_free(girara_list_iterator_t* iter)
326
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
327
  if (iter == NULL) {
328
    return;
Moritz Lipp's avatar
Moritz Lipp committed
329 330
  }

331 332 333
  g_free(iter);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
334 335
size_t
girara_list_size(girara_list_t* list)
336
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
337
  g_return_val_if_fail(list != NULL, 0);
Moritz Lipp's avatar
Moritz Lipp committed
338

Sebastian Ramacher's avatar
Sebastian Ramacher committed
339
  if (list->start == NULL) {
340
    return 0;
Moritz Lipp's avatar
Moritz Lipp committed
341 342
  }

343 344 345
  return g_list_length(list->start);
}

346
ssize_t
347 348 349 350 351 352 353 354
girara_list_position(girara_list_t* list, void* data)
{
  g_return_val_if_fail(list != NULL, -1);

  if (list->start == NULL) {
    return -1;
  }

355 356 357
  bool found = false;
  ssize_t pos = 0;
  GIRARA_LIST_FOREACH_BODY(list, void*, tmp,
358
    if (tmp == data) {
359 360
      found = true;
      break;
361
    }
362
    ++pos;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
363
  );
364

365
  return found ? pos : -1;
366
}
367

Sebastian Ramacher's avatar
Sebastian Ramacher committed
368 369
void
girara_list_sort(girara_list_t* list, girara_compare_function_t compare)
370 371
{
  g_return_if_fail(list != NULL);
372
  if (list->start == NULL || compare == NULL) {
373 374 375 376 377 378
    return;
  }

  list->start = g_list_sort(list->start, compare);
}

379 380 381 382 383 384 385 386
void
girara_list_foreach(girara_list_t* list, girara_list_callback_t callback, void* data)
{
  g_return_if_fail(list && list->start && callback);

  g_list_foreach(list->start, callback, data);
}

387 388 389 390 391 392 393
static void
list_append(void* data, void* userdata)
{
  girara_list_t* list = userdata;
  girara_list_append(list, data);
}

394 395 396 397 398 399 400 401 402 403 404 405 406 407 408
girara_list_t*
girara_list_merge(girara_list_t* list, girara_list_t* other)
{
  if (list == NULL) {
    return other;
  }
  if (other == NULL) {
    return list;
  }

  if (list->free != other->free) {
    girara_warning("girara_list_merge: merging lists with different free functions!");
  }
  other->free = NULL;

409
  girara_list_foreach(other, list_append, list);
410 411 412
  return list;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
413 414
girara_tree_node_t*
girara_node_new(void* data)
415
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
416 417 418 419 420 421 422 423 424 425
  girara_tree_node_t* node = g_try_malloc0(sizeof(girara_tree_node_t));
  if (node == NULL) {
    return NULL;
  }

  girara_tree_node_data_t* nodedata = g_try_malloc0(sizeof(girara_tree_node_data_t));
  if (nodedata == NULL) {
    g_free(node);
    return NULL;
  }
Moritz Lipp's avatar
Moritz Lipp committed
426

427 428
  nodedata->data = data;
  nodedata->node = node;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
429
  node->node     = g_node_new(nodedata);
Moritz Lipp's avatar
Moritz Lipp committed
430

Sebastian Ramacher's avatar
Sebastian Ramacher committed
431
  if (node->node == NULL) {
432 433 434 435 436 437 438 439
    g_free(node);
    g_free(nodedata);
    return NULL;
  }

  return node;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
440 441
void
girara_node_set_free_function(girara_tree_node_t* node, girara_free_function_t gfree)
442 443 444 445 446
{
  g_return_if_fail(node);
  node->free = gfree;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
447 448
void
girara_node_free(girara_tree_node_t* node)
449
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
450
  if (node == NULL) {
451
    return;
Moritz Lipp's avatar
Moritz Lipp committed
452
  }
453 454

  g_return_if_fail(node->node);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
455
  girara_tree_node_data_t* nodedata = node->node->data;
456
  g_return_if_fail(nodedata);
Moritz Lipp's avatar
Moritz Lipp committed
457

Sebastian Ramacher's avatar
Sebastian Ramacher committed
458
  if (node->free != NULL) {
459
    (*node->free)(nodedata->data);
Moritz Lipp's avatar
Moritz Lipp committed
460 461
  }

462 463 464
  g_free(nodedata);

  GNode* childnode = node->node->children;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
465
  while (childnode != NULL) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
466 467
    girara_tree_node_data_t* childnodedata = childnode->data;
    girara_node_free(childnodedata->node);
468 469 470 471 472 473 474
    childnode = childnode->next;
  }

  g_node_destroy(node->node);
  g_free(node);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
475 476
void
girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child)
477 478 479 480 481
{
  g_return_if_fail(parent && child);
  g_node_append(parent->node, child->node);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
482 483
girara_tree_node_t*
girara_node_append_data(girara_tree_node_t* parent, void* data)
484
{
485 486 487
  g_return_val_if_fail(parent, NULL);
  girara_tree_node_t* child = girara_node_new(data);
  g_return_val_if_fail(child, NULL);
488
  child->free = parent->free;
489
  girara_node_append(parent, child);
Moritz Lipp's avatar
Moritz Lipp committed
490

491
  return child;
492 493
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
494 495
girara_tree_node_t*
girara_node_get_parent(girara_tree_node_t* node)
496 497
{
  g_return_val_if_fail(node && node->node, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
498

Sebastian Ramacher's avatar
Sebastian Ramacher committed
499
  if (node->node->parent == NULL) {
500
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
501
  }
502 503 504

  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->parent->data;
  g_return_val_if_fail(nodedata, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
505

506 507 508
  return nodedata->node;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
509 510
girara_tree_node_t*
girara_node_get_root(girara_tree_node_t* node)
511 512
{
  g_return_val_if_fail(node && node->node, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
513

Sebastian Ramacher's avatar
Sebastian Ramacher committed
514
  if (node->node->parent == NULL) {
515
    return node;
Moritz Lipp's avatar
Moritz Lipp committed
516
  }
517 518 519 520 521

  GNode* root = g_node_get_root(node->node);
  g_return_val_if_fail(root, NULL);
  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) root->data;
  g_return_val_if_fail(nodedata, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
522

523 524 525
  return nodedata->node;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
526 527
girara_list_t*
girara_node_get_children(girara_tree_node_t* node)
528 529
{
  g_return_val_if_fail(node, NULL);
530
  girara_list_t* list = girara_list_new();
531 532 533
  g_return_val_if_fail(list, NULL);

  GNode* childnode = node->node->children;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
534
  while (childnode != NULL) {
535 536 537 538 539 540 541 542
    girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
    girara_list_append(list, nodedata->node);
    childnode = childnode->next;
  }

  return list;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
543 544
size_t
girara_node_get_num_children(girara_tree_node_t* node)
545 546
{
  g_return_val_if_fail(node && node->node, 0);
Moritz Lipp's avatar
Moritz Lipp committed
547

548 549 550
  return g_node_n_children(node->node);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
551 552
void*
girara_node_get_data(girara_tree_node_t* node)
553 554 555 556
{
  g_return_val_if_fail(node && node->node, NULL);
  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
  g_return_val_if_fail(nodedata, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
557

558 559 560
  return nodedata->data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
561 562
void
girara_node_set_data(girara_tree_node_t* node, void* data)
563 564 565 566
{
  g_return_if_fail(node && node->node);
  girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) node->node->data;
  g_return_if_fail(nodedata);
Moritz Lipp's avatar
Moritz Lipp committed
567

Sebastian Ramacher's avatar
Sebastian Ramacher committed
568
  if (node->free != NULL) {
569
    (*node->free)(nodedata->data);
Moritz Lipp's avatar
Moritz Lipp committed
570 571
  }

572 573
  nodedata->data = data;
}