1 files changed, 166 insertions, 69 deletions

diff --git a/libcnary/node.c b/libcnary/node.c
index 0a8f414..63b449c 100644
--- a/libcnary/node.c
+++ b/libcnary/node.c
@@ -26,13 +26,13 @@
 
 #include "node.h"
 #include "node_list.h"
-#include "node_iterator.h"
 
-void node_destroy(node_t* node) {
+void node_destroy(node_t node)
+{
 	if(!node) return;
 
 	if (node->children && node->children->count > 0) {
-		node_t* ch;
+		node_t ch;
 		while ((ch = node->children->begin)) {
 			node_list_remove(node->children, ch);
 			node_destroy(ch);
@@ -44,32 +44,28 @@ void node_destroy(node_t* node) {
 	free(node);
 }
 
-node_t* node_create(node_t* parent, void* data) {
+node_t node_create(node_t parent, void* data)
+{
 	int error = 0;
 
-	node_t* node = (node_t*) malloc(sizeof(node_t));
-	if(node == NULL) {
+	node_t node = (node_t)calloc(1, sizeof(struct node));
+	if (node == NULL) {
 		return NULL;
 	}
-	memset(node, '\0', sizeof(node_t));
 
 	node->data = data;
-	node->depth = 0;
 	node->next = NULL;
 	node->prev = NULL;
 	node->count = 0;
-	node->isLeaf = TRUE;
-	node->isRoot = TRUE;
 	node->parent = NULL;
-	node->children = node_list_create(node);
+	node->children = NULL;
 
 	// Pass NULL to create a root node
-	if(parent != NULL) {
+	if (parent != NULL) {
 		// This is a child node so attach it to it's parent
 		error = node_attach(parent, node);
-		if(error < 0) {
+		if (error < 0) {
 			// Unable to attach nodes
-			printf("ERROR: %d \"Unable to attach nodes\"\n", error);
 			node_destroy(node);
 			return NULL;
 		}
@@ -78,88 +74,180 @@ node_t* node_create(node_t* parent, void* data) {
 	return node;
 }
 
-int node_attach(node_t* parent, node_t* child) {
-	if (!parent || !child) return -1;
-	child->isLeaf = TRUE;
-	child->isRoot = FALSE;
-	child->parent = parent;
-	child->depth = parent->depth + 1;
-	if(parent->isLeaf == TRUE) {
-		parent->isLeaf = FALSE;
+static int node_depth_from_root(node_t n)
+{
+	int d = 0;
+	while (n && n->parent) {
+		d++;
+		n = n->parent;
+		if (d > NODE_MAX_DEPTH) return d; // early out
+	}
+	return d;
+}
+
+static int node_subtree_max_depth(node_t root)
+{
+	if (!root) return 0;
+
+	typedef struct { node_t n; int depth; } frame_t;
+	size_t cap = 64, sp = 0;
+	frame_t *st = (frame_t*)malloc(cap * sizeof(*st));
+	if (!st) return NODE_MAX_DEPTH + 1;
+
+	st[sp++] = (frame_t){ root, 0 };
+	int maxd = 0;
+
+	while (sp) {
+		frame_t f = st[--sp];
+		if (f.depth > maxd) maxd = f.depth;
+		if (maxd > NODE_MAX_DEPTH) break;
+
+		if (!f.n->children) continue;
+
+		for (node_t ch = node_first_child(f.n); ch; ch = node_next_sibling(ch)) {
+			if (sp == cap) {
+				cap *= 2;
+				frame_t *tmp = (frame_t*)realloc(st, cap * sizeof(*st));
+				if (!tmp) { maxd = NODE_MAX_DEPTH + 1; goto out; }
+				st = tmp;
+			}
+			st[sp++] = (frame_t){ ch, f.depth + 1 };
+		}
+	}
+
+out:
+	free(st);
+	return maxd;
+}
+
+static int would_create_cycle(node_t parent, node_t child)
+{
+	// if parent is anywhere in child's ancestor chain => cycle
+	for (node_t p = parent; p; p = p->parent) {
+		if (p == child) return 1;
+	}
+	return 0;
+}
+
+int node_attach(node_t parent, node_t child)
+{
+	if (!parent || !child) return NODE_ERR_INVALID_ARG;
+
+	// already parented?
+	if (child->parent) return NODE_ERR_PARENT;
+
+	// self/cycle guard
+	if (parent == child) return NODE_ERR_CIRCULAR_REF;
+	if (would_create_cycle(parent, child)) return NODE_ERR_CIRCULAR_REF;
+
+	// depth guard: depth(parent)+1+max_depth(child_subtree) <= NODE_MAX_DEPTH
+	int pd = node_depth_from_root(parent);
+	int cd = node_subtree_max_depth(child);
+	if (pd + 1 + cd > NODE_MAX_DEPTH) {
+		return NODE_ERR_MAX_DEPTH;
+	}
+
+	if (!parent->children) {
+		parent->children = node_list_create();
+		if (!parent->children) return NODE_ERR_NO_MEM;
 	}
 	int res = node_list_add(parent->children, child);
 	if (res == 0) {
+		child->parent = parent;
 		parent->count++;
 	}
 	return res;
 }
 
-int node_detach(node_t* parent, node_t* child) {
-	if (!parent || !child) return -1;
-	int index = node_list_remove(parent->children, child);
-	if (index >= 0) {
-		parent->count--;
+int node_detach(node_t parent, node_t child)
+{
+	if (!parent || !child) return NODE_ERR_INVALID_ARG;
+	if (!parent->children) return NODE_ERR_NOT_FOUND;
+	if (child->parent && child->parent != parent) return NODE_ERR_PARENT;
+
+	int node_index = node_list_remove(parent->children, child);
+	if (node_index >= 0) {
+		if (parent->count > 0) parent->count--;
+		child->parent = NULL;
+		child->prev = NULL;
+		child->next = NULL;
 	}
-	return index;
+	return node_index;
 }
 
-int node_insert(node_t* parent, unsigned int index, node_t* child)
+int node_insert(node_t parent, unsigned int node_index, node_t child)
 {
-	if (!parent || !child) return -1;
-	child->isLeaf = TRUE;
-	child->isRoot = FALSE;
-	child->parent = parent;
-	child->depth = parent->depth + 1;
-	if(parent->isLeaf == TRUE) {
-		parent->isLeaf = FALSE;
+	if (!parent || !child) return NODE_ERR_INVALID_ARG;
+
+	// already parented?
+	if (child->parent) return NODE_ERR_PARENT;
+
+	// self/cycle guard
+	if (parent == child) return NODE_ERR_CIRCULAR_REF;
+	if (would_create_cycle(parent, child)) return NODE_ERR_CIRCULAR_REF;
+
+	// depth guard: depth(parent)+1+max_depth(child_subtree) <= NODE_MAX_DEPTH
+	int pd = node_depth_from_root(parent);
+	int cd = node_subtree_max_depth(child);
+	if (pd + 1 + cd > NODE_MAX_DEPTH) {
+		return NODE_ERR_MAX_DEPTH;
 	}
-	int res = node_list_insert(parent->children, index, child);
+
+	if (!parent->children) {
+		parent->children = node_list_create();
+		if (!parent->children) return NODE_ERR_NO_MEM;
+	}
+	int res = node_list_insert(parent->children, node_index, child);
 	if (res == 0) {
+		child->parent = parent;
 		parent->count++;
 	}
 	return res;
 }
 
-void node_debug(node_t* node) {
-	int i = 0;
-	node_t* current = NULL;
-	node_iterator_t* iter = NULL;
-	for(i = 0; i < node->depth; i++) {
+static void _node_debug(node_t node, unsigned int depth)
+{
+	unsigned int i = 0;
+	node_t current = NULL;
+	for(i = 0; i < depth; i++) {
 		printf("\t");
 	}
-	if(node->isRoot) {
+	if(!node->parent) {
 		printf("ROOT\n");
 	}
 
-	if(node->isLeaf && !node->isRoot) {
+	if(!node->children && node->parent) {
 		printf("LEAF\n");
-
 	} else {
-		if(!node->isRoot) {
+		if(node->parent) {
 			printf("NODE\n");
 		}
-		iter = node_iterator_create(node->children);
-		for(current = iter->begin; current != NULL; current = iter->next(iter)) {
-			node_debug(current);
+		for (current = node_first_child(node); current; current = node_next_sibling(current)) {
+			_node_debug(current, depth+1);
 		}
 	}
 
 }
 
-unsigned int node_n_children(struct node_t* node)
+void node_debug(node_t node)
+{
+	_node_debug(node, 0);
+}
+
+unsigned int node_n_children(node_t node)
 {
 	if (!node) return 0;
 	return node->count;
 }
 
-node_t* node_nth_child(struct node_t* node, unsigned int n)
+node_t node_nth_child(node_t node, unsigned int n)
 {
 	if (!node || !node->children || !node->children->begin) return NULL;
-	int index = 0;
+	unsigned int node_index = 0;
 	int found = 0;
-	node_t *ch;
+	node_t ch;
 	for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-		if (index++ == n) {
+		if (node_index++ == n) {
 			found = 1;
 			break;
 		}
@@ -170,55 +258,64 @@ node_t* node_nth_child(struct node_t* node, unsigned int n)
 	return ch;
 }
 
-node_t* node_first_child(struct node_t* node)
+node_t node_first_child(node_t node)
 {
 	if (!node || !node->children) return NULL;
 	return node->children->begin;
 }
 
-node_t* node_prev_sibling(struct node_t* node)
+node_t node_prev_sibling(node_t node)
 {
 	if (!node) return NULL;
 	return node->prev;
 }
 
-node_t* node_next_sibling(struct node_t* node)
+node_t node_next_sibling(node_t node)
 {
 	if (!node) return NULL;
 	return node->next;
 }
 
-int node_child_position(struct node_t* parent, node_t* child)
+int node_child_position(node_t parent, node_t child)
 {
-	if (!parent || !parent->children || !parent->children->begin || !child) return -1;
-	int index = 0;
+	if (!parent || !parent->children || !parent->children->begin || !child) return NODE_ERR_INVALID_ARG;
+	int node_index = 0;
 	int found = 0;
-	node_t *ch;
+	node_t ch;
 	for (ch = node_first_child(parent); ch; ch = node_next_sibling(ch)) {
 		if (ch == child) {
 			found = 1;
 			break;
 		}
-		index++;
+		node_index++;
 	}
 	if (!found) {
-		return -1;
+		return NODE_ERR_NOT_FOUND;
 	}
-	return index;
+	return node_index;
 }
 
-node_t* node_copy_deep(node_t* node, copy_func_t copy_func)
+node_t node_copy_deep(node_t node, copy_func_t copy_func)
 {
 	if (!node) return NULL;
 	void *data = NULL;
 	if (copy_func) {
 		data = copy_func(node->data);
 	}
-	node_t* copy = node_create(NULL, data);
-	node_t* ch;
+	node_t copy = node_create(NULL, data);
+	if (!copy) return NULL;
+	node_t ch;
 	for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
-		node_t* cc = node_copy_deep(ch, copy_func);
-		node_attach(copy, cc);
+		node_t cc = node_copy_deep(ch, copy_func);
+		if (!cc) {
+			node_destroy(copy);
+			return NULL;
+		}
+		if (node_attach(copy, cc) < 0) {
+                        node_destroy(cc);
+			node_destroy(copy);
+			return NULL;
+		}
 	}
 	return copy;
 }