agendafs

A filesystem for your calendar.
git clone git://mccd.space/agendafs
tree.c (2728B)
      1 #include "tree.h"
      2 #include "arena.h"
      3 #include "util.h"
      4 #include <stdbool.h>
      5 #include <stdio.h>
      6 #include <string.h>
      7 
      8 struct tree_node *
      9 create_tree_node(void *data, void (*free_fn)(void *))
     10 {
     11 	struct tree_node *node = xmalloc(sizeof(struct tree_node));
     12 	if (!node)
     13 		return NULL;
     14 	node->data = data;
     15 	node->parent = NULL;
     16 	node->children = NULL;
     17 	node->child_count = 0;
     18 	node->child_capacity = 0;
     19 	node->free_fn = free_fn;
     20 
     21 	return node;
     22 }
     23 
     24 struct tree_node *
     25 rcreate_tree_node(void *data, arena *m)
     26 {
     27 	struct tree_node *node = rmalloc(m, sizeof(struct tree_node));
     28 	if (!node)
     29 		return NULL;
     30 	node->data = data;
     31 	node->parent = NULL;
     32 	node->children = NULL;
     33 	node->child_count = 0;
     34 	node->child_capacity = 0;
     35 	node->free_fn = NULL;
     36 
     37 	return node;
     38 }
     39 
     40 size_t
     41 add_child(struct tree_node *parent, struct tree_node *child)
     42 {
     43 	if (parent->child_count == parent->child_capacity) {
     44 		size_t new_capacity =
     45 		    parent->child_capacity ? parent->child_capacity * 2 : 4;
     46 
     47 		parent->children = xreallocarray(parent->children, new_capacity,
     48 						 sizeof(struct tree_node *));
     49 		parent->child_capacity = new_capacity;
     50 	}
     51 	parent->children[parent->child_count++] = child;
     52 	child->parent = parent;
     53 	return 0;
     54 }
     55 void
     56 update_node_data(struct tree_node *node, void *data)
     57 {
     58 	if (node->data && node->free_fn) {
     59 		node->free_fn(node->data);
     60 	}
     61 	node->data = data;
     62 }
     63 
     64 bool
     65 node_has_children(const struct tree_node *node)
     66 {
     67 	return node->child_count > 0;
     68 }
     69 
     70 // Free a node and all its children
     71 void
     72 free_tree(struct tree_node *node)
     73 {
     74 	if (!node)
     75 		return;
     76 	for (size_t i = 0; i < node->child_count; ++i) {
     77 		free_tree(node->children[i]);
     78 	}
     79 	if (node->free_fn && node->data) {
     80 		node->free_fn(node->data);
     81 	}
     82 	free(node->children);
     83 	free(node);
     84 }
     85 
     86 void
     87 print_tree(struct tree_node *node, int depth, void (*print_data)(void *))
     88 {
     89 	for (int i = 0; i < depth; i++)
     90 		printf("  ");
     91 	if (print_data)
     92 		print_data(node->data);
     93 	else
     94 		printf("(no data)\n");
     95 
     96 	for (size_t i = 0; i < node->child_count; ++i) {
     97 		print_tree(node->children[i], depth + 1, print_data);
     98 	}
     99 }
    100 
    101 bool
    102 detach_tree_node(struct tree_node *node)
    103 {
    104 	if (!node->parent)
    105 		return false;
    106 
    107 	struct tree_node *parent = node->parent;
    108 
    109 	// Find index of this node in parent->children
    110 	size_t index = (size_t)-1;
    111 	for (size_t i = 0; i < parent->child_count; ++i) {
    112 		if (parent->children[i] == node) {
    113 			index = i;
    114 			break;
    115 		}
    116 	}
    117 
    118 	// Shift remaining children to fill the gap
    119 	for (size_t i = index + 1; i < parent->child_count; ++i) {
    120 		parent->children[i - 1] = parent->children[i];
    121 	}
    122 	parent->child_count--;
    123 
    124 	node->parent = NULL;
    125 	return true;
    126 }
    127 
    128 int
    129 move_node(struct tree_node *new_parent, struct tree_node *child)
    130 {
    131 	detach_tree_node(child);
    132 	return add_child(new_parent, child);
    133 }