datastructures.c 11.1 KB
Newer Older
1
/* SPDX-License-Identifier: Zlib */
2

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_slice_new0(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);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
106
  g_slice_free(girara_list_t, list);
107 108
}

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
void*
Sebastian Ramacher's avatar
Sebastian Ramacher committed
181
girara_list_find(const girara_list_t* list, girara_compare_function_t compare, const void* data)
182
{
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
  girara_list_iterator_t* iter = g_slice_new0(girara_list_iterator_t);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
207 208 209 210 211
  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
  return g_slice_copy(sizeof(girara_list_iterator_t), iter);
223 224
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
225 226
girara_list_iterator_t*
girara_list_iterator_next(girara_list_iterator_t* iter)
227
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
228
  if (girara_list_iterator_is_valid(iter) == false) {
229
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
230
  }
231 232

  iter->element = g_list_next(iter->element);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
233
  if (iter->element == NULL) {
234
    return NULL;
Moritz Lipp's avatar
Moritz Lipp committed
235 236
  }

237 238 239
  return iter;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
240 241
bool
girara_list_iterator_has_next(girara_list_iterator_t* iter)
242
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
243 244 245 246 247
  if (girara_list_iterator_is_valid(iter) == false) {
    return false;
  }

  return g_list_next(iter->element);
248 249
}

250 251 252
girara_list_iterator_t*
girara_list_iterator_previous(girara_list_iterator_t* iter)
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
253
  if (girara_list_iterator_is_valid(iter) == false) {
254 255 256 257
    return NULL;
  }

  iter->element = g_list_previous(iter->element);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
258
  if (iter->element == NULL) {
259 260 261 262 263 264 265 266 267
    return NULL;
  }

  return iter;
}

bool
girara_list_iterator_has_previous(girara_list_iterator_t* iter)
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
268 269 270 271 272
  if (girara_list_iterator_is_valid(iter) == false) {
    return false;
  }

  return g_list_previous(iter->element);
273 274 275 276
}

void
girara_list_iterator_remove(girara_list_iterator_t* iter) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
277 278 279
  if (girara_list_iterator_is_valid(iter) == false) {
    return;
  }
280

Sebastian Ramacher's avatar
Sebastian Ramacher committed
281
  GList* el = iter->element;
282
  if (iter->list->free != NULL) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
283
    (iter->list->free)(iter->element->data);
284
  }
Sebastian Ramacher's avatar
Sebastian Ramacher committed
285 286 287

  iter->element     = el->next;
  iter->list->start = g_list_delete_link(iter->list->start, el);
288 289
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
290 291
bool
girara_list_iterator_is_valid(girara_list_iterator_t* iter)
Sebastian Ramacher's avatar
Sebastian Ramacher committed
292
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
293
  return iter != NULL && iter->element != NULL;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
294 295
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
296 297
void*
girara_list_iterator_data(girara_list_iterator_t* iter)
298
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
299
  g_return_val_if_fail(girara_list_iterator_is_valid(iter), NULL);
Moritz Lipp's avatar
Moritz Lipp committed
300

301 302 303
  return iter->element->data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
304 305
void
girara_list_iterator_set(girara_list_iterator_t* iter, void *data)
306
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
307 308
  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
309

Sebastian Ramacher's avatar
Sebastian Ramacher committed
310
  if (iter->list->free != NULL) {
311
    (*iter->list->free)(iter->element->data);
Moritz Lipp's avatar
Moritz Lipp committed
312 313
  }

314 315 316
  iter->element->data = data;
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
317 318
void
girara_list_iterator_free(girara_list_iterator_t* iter)
319
{
Sebastian Ramacher's avatar
Sebastian Ramacher committed
320
  if (iter == NULL) {
321
    return;
Moritz Lipp's avatar
Moritz Lipp committed
322 323
  }

Sebastian Ramacher's avatar
Sebastian Ramacher committed
324
  g_slice_free(girara_list_iterator_t, iter);
325 326
}

Sebastian Ramacher's avatar
Sebastian Ramacher committed
327 328
size_t
girara_list_size(girara_list_t* list)
329
{
Sebastian Ramacher's avatar
CS  
Sebastian Ramacher committed
330
  g_return_val_if_fail(list != NULL, 0);
Moritz Lipp's avatar
Moritz Lipp committed
331

Sebastian Ramacher's avatar
Sebastian Ramacher committed
332
  if (list->start == NULL) {
333
    return 0;
Moritz Lipp's avatar
Moritz Lipp committed
334 335
  }

336 337 338
  return g_list_length(list->start);
}

339
ssize_t
340 341 342 343 344 345 346 347
girara_list_position(girara_list_t* list, void* data)
{
  g_return_val_if_fail(list != NULL, -1);

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

348 349 350
  bool found = false;
  ssize_t pos = 0;
  GIRARA_LIST_FOREACH_BODY(list, void*, tmp,
351
    if (tmp == data) {
352 353
      found = true;
      break;
354
    }
355
    ++pos;
Sebastian Ramacher's avatar
Sebastian Ramacher committed
356
  );
357

358
  return found ? pos : -1;
359
}
360

Sebastian Ramacher's avatar
Sebastian Ramacher committed
361 362
void
girara_list_sort(girara_list_t* list, girara_compare_function_t compare)
363 364
{
  g_return_if_fail(list != NULL);
365
  if (list->start == NULL || compare == NULL) {
366 367 368 369 370 371
    return;
  }

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

372 373 374
void
girara_list_foreach(girara_list_t* list, girara_list_callback_t callback, void* data)
{
375 376 377 378
  g_return_if_fail(list != NULL && callback != NULL);
  if (list->start == NULL) {
    return;
  }
379 380 381 382

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

383 384 385 386 387 388 389
static void
list_append(void* data, void* userdata)
{
  girara_list_t* list = userdata;
  girara_list_append(list, data);
}

390 391 392
girara_list_t*
girara_list_merge(girara_list_t* list, girara_list_t* other)
{
393
  g_return_val_if_fail(list != NULL, NULL);
394 395 396 397 398 399 400 401 402
  if (other == NULL) {
    return list;
  }

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

403
  girara_list_foreach(other, list_append, list);
404 405 406
  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

  g_return_if_fail(node->node);
Sebastian Ramacher's avatar
Sebastian Ramacher committed
449
  girara_tree_node_data_t* nodedata = node->node->data;
450
  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) {
Sebastian Ramacher's avatar
Sebastian Ramacher committed
460 461
    girara_tree_node_data_t* childnodedata = childnode->data;
    girara_node_free(childnodedata->node);
462 463 464 465 466 467 468
    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;
}