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 358 359
  size_t pos = 0;
  GIRARA_LIST_FOREACH(list, void*, iter, tmp)
    if (tmp == data) {
      girara_list_iterator_free(iter);
      return pos;
360
    }
361 362
    ++pos;
  GIRARA_LIST_FOREACH_END(list, void*, iter, tmp);
363 364 365

  return -1;
}
366

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

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

378 379 380 381 382 383 384 385
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);
}

386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406
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;

  GIRARA_LIST_FOREACH(other, void*, iter, data)
    girara_list_append(list, data);
  GIRARA_LIST_FOREACH_END(other, void*, iter, data);
  return list;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
407 408
girara_tree_node_t*
girara_node_new(void* data)
409
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
410 411 412 413 414 415 416 417 418 419
  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
420

421 422
  nodedata->data = data;
  nodedata->node = node;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
423
  node->node     = g_node_new(nodedata);
Moritz Lipp's avatar
Moritz Lipp committed
424

Sebastian Ramacher's avatar
Sebastian Ramacher committed
425
  if (node->node == NULL) {
426 427 428 429 430 431 432 433
    g_free(node);
    g_free(nodedata);
    return NULL;
  }

  return node;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
434 435
void
girara_node_set_free_function(girara_tree_node_t* node, girara_free_function_t gfree)
436 437 438 439 440
{
  g_return_if_fail(node);
  node->free = gfree;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
441 442
void
girara_node_free(girara_tree_node_t* node)
443
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
444
  if (node == NULL) {
445
    return;
Moritz Lipp's avatar
Moritz Lipp committed
446
  }
447 448 449 450

  g_return_if_fail(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
451

Sebastian Ramacher's avatar
Sebastian Ramacher committed
452
  if (node->free != NULL) {
453
    (*node->free)(nodedata->data);
Moritz Lipp's avatar
Moritz Lipp committed
454 455
  }

456 457 458
  g_free(nodedata);

  GNode* childnode = node->node->children;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
459
  while (childnode != NULL) {
460 461 462 463 464 465 466 467 468
    girara_tree_node_data_t* nodedata = (girara_tree_node_data_t*) childnode->data;
    girara_node_free(nodedata->node);
    childnode = childnode->next;
  }

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

Sebastian Ramacher's avatar
Sebastian Ramacher committed
469 470
void
girara_node_append(girara_tree_node_t* parent, girara_tree_node_t* child)
471 472 473 474 475
{
  g_return_if_fail(parent && child);
  g_node_append(parent->node, child->node);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
476 477
girara_tree_node_t*
girara_node_append_data(girara_tree_node_t* parent, void* data)
478
{
479 480 481
  g_return_val_if_fail(parent, NULL);
  girara_tree_node_t* child = girara_node_new(data);
  g_return_val_if_fail(child, NULL);
482
  child->free = parent->free;
483
  girara_node_append(parent, child);
Moritz Lipp's avatar
Moritz Lipp committed
484

485
  return child;
486 487
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
488 489
girara_tree_node_t*
girara_node_get_parent(girara_tree_node_t* node)
490 491
{
  g_return_val_if_fail(node && node->node, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
492

Sebastian Ramacher's avatar
Sebastian Ramacher committed
493
  if (node->node->parent == NULL) {
494
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
495
  }
496 497 498

  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
499

500 501 502
  return nodedata->node;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
503 504
girara_tree_node_t*
girara_node_get_root(girara_tree_node_t* node)
505 506
{
  g_return_val_if_fail(node && node->node, NULL);
Moritz Lipp's avatar
Moritz Lipp committed
507

Sebastian Ramacher's avatar
Sebastian Ramacher committed
508
  if (node->node->parent == NULL) {
509
    return node;
Moritz Lipp's avatar
Moritz Lipp committed
510
  }
511 512 513 514 515

  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
516

517 518 519
  return nodedata->node;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
520 521
girara_list_t*
girara_node_get_children(girara_tree_node_t* node)
522 523
{
  g_return_val_if_fail(node, NULL);
524
  girara_list_t* list = girara_list_new();
525 526 527
  g_return_val_if_fail(list, NULL);

  GNode* childnode = node->node->children;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
528
  while (childnode != NULL) {
529 530 531 532 533 534 535 536
    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
537 538
size_t
girara_node_get_num_children(girara_tree_node_t* node)
539 540
{
  g_return_val_if_fail(node && node->node, 0);
Moritz Lipp's avatar
Moritz Lipp committed
541

542 543 544
  return g_node_n_children(node->node);
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
545 546
void*
girara_node_get_data(girara_tree_node_t* node)
547 548 549 550
{
  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
551

552 553 554
  return nodedata->data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
555 556
void
girara_node_set_data(girara_tree_node_t* node, void* data)
557 558 559 560
{
  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
561

Sebastian Ramacher's avatar
Sebastian Ramacher committed
562
  if (node->free != NULL) {
563
    (*node->free)(nodedata->data);
Moritz Lipp's avatar
Moritz Lipp committed
564 565
  }

566 567
  nodedata->data = data;
}