libcnary/node.c - third_party/libplist - Git at Google

 /*
  * node.c
  *
  *  Created on: Mar 7, 2011
  *      Author: posixninja
  *
  * Copyright (c) 2011 Joshua Hill. All Rights Reserved.
  *
  * This library is free software; you can redistribute it and/or
  * modify it under the terms of the GNU Lesser General Public
  * License as published by the Free Software Foundation; either
  * version 2.1 of the License, or (at your option) any later version.
  *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the Free Software
  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
  */
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

 #include "node.h"
 #include "node_list.h"

 void node_destroy(node_t node)
 {
 	if(!node) return;

 	if (node->children && node->children->count > 0) {
 		node_t ch;
 		while ((ch = node->children->begin)) {
 			node_list_remove(node->children, ch);
 			node_destroy(ch);
 		}
 	}
 	node_list_destroy(node->children);
 	node->children = NULL;

 	free(node);
 }

 node_t node_create(node_t parent, void* data)
 {
 	int error = 0;

 	node_t node = (node_t)calloc(1, sizeof(struct node));
 	if (node == NULL) {
 		return NULL;
 	}

 	node->data = data;
 	node->next = NULL;
 	node->prev = NULL;
 	node->count = 0;
 	node->parent = NULL;
 	node->children = NULL;

 	// Pass NULL to create a root node
 	if (parent != NULL) {
 		// This is a child node so attach it to it's parent
 		error = node_attach(parent, node);
 		if (error < 0) {
 			// Unable to attach nodes
 			node_destroy(node);
 			return NULL;
 		}
 	}

 	return node;
 }

 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 NODE_ERR_INVALID_ARG;
 	int node_index = node_list_remove(parent->children, child);
 	if (node_index >= 0) {
 		parent->count--;
 	}
 	return node_index;
 }

 int node_insert(node_t parent, unsigned int node_index, 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_insert(parent->children, node_index, child);
 	if (res == 0) {
 		child->parent = parent;
 		parent->count++;
 	}
 	return res;
 }

 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->parent) {
 		printf("ROOT\n");
 	}

 	if(!node->children && node->parent) {
 		printf("LEAF\n");
 	} else {
 		if(node->parent) {
 			printf("NODE\n");
 		}
 		for (current = node_first_child(node); current; current = node_next_sibling(current)) {
 			_node_debug(current, depth+1);
 		}
 	}

 }

 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(node_t node, unsigned int n)
 {
 	if (!node || !node->children || !node->children->begin) return NULL;
 	unsigned int node_index = 0;
 	int found = 0;
 	node_t ch;
 	for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
 		if (node_index++ == n) {
 			found = 1;
 			break;
 		}
 	}
 	if (!found) {
 		return NULL;
 	}
 	return ch;
 }

 node_t node_first_child(node_t node)
 {
 	if (!node || !node->children) return NULL;
 	return node->children->begin;
 }

 node_t node_prev_sibling(node_t node)
 {
 	if (!node) return NULL;
 	return node->prev;
 }

 node_t node_next_sibling(node_t node)
 {
 	if (!node) return NULL;
 	return node->next;
 }

 int node_child_position(node_t parent, node_t child)
 {
 	if (!parent || !parent->children || !parent->children->begin || !child) return NODE_ERR_INVALID_ARG;
 	int node_index = 0;
 	int found = 0;
 	node_t ch;
 	for (ch = node_first_child(parent); ch; ch = node_next_sibling(ch)) {
 		if (ch == child) {
 			found = 1;
 			break;
 		}
 		node_index++;
 	}
 	if (!found) {
 		return NODE_ERR_NOT_FOUND;
 	}
 	return node_index;
 }

 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);
 	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);
 		if (!cc) {
 			node_destroy(copy);
 			return NULL;
 		}
 		if (node_attach(copy, cc) < 0) {
 			node_destroy(copy);
 			return NULL;
 		}
 	}
 	return copy;
 }
	/*
	* node.c
	*
	* Created on: Mar 7, 2011
	* Author: posixninja
	*
	* Copyright (c) 2011 Joshua Hill. All Rights Reserved.
	*
	* This library is free software; you can redistribute it and/or
	* modify it under the terms of the GNU Lesser General Public
	* License as published by the Free Software Foundation; either
	* version 2.1 of the License, or (at your option) any later version.
	*
	* This library is distributed in the hope that it will be useful,
	* but WITHOUT ANY WARRANTY; without even the implied warranty of
	* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	* Lesser General Public License for more details.
	*
	* You should have received a copy of the GNU Lesser General Public
	* License along with this library; if not, write to the Free Software
	* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
	*/
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>

	#include "node.h"
	#include "node_list.h"

	void node_destroy(node_t node)
	{
	if(!node) return;

	if (node->children && node->children->count > 0) {
	node_t ch;
	while ((ch = node->children->begin)) {
	node_list_remove(node->children, ch);
	node_destroy(ch);
	}
	}
	node_list_destroy(node->children);
	node->children = NULL;

	free(node);
	}

	node_t node_create(node_t parent, void* data)
	{
	int error = 0;

	node_t node = (node_t)calloc(1, sizeof(struct node));
	if (node == NULL) {
	return NULL;
	}

	node->data = data;
	node->next = NULL;
	node->prev = NULL;
	node->count = 0;
	node->parent = NULL;
	node->children = NULL;

	// Pass NULL to create a root node
	if (parent != NULL) {
	// This is a child node so attach it to it's parent
	error = node_attach(parent, node);
	if (error < 0) {
	// Unable to attach nodes
	node_destroy(node);
	return NULL;
	}
	}

	return node;
	}

	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 NODE_ERR_INVALID_ARG;
	int node_index = node_list_remove(parent->children, child);
	if (node_index >= 0) {
	parent->count--;
	}
	return node_index;
	}

	int node_insert(node_t parent, unsigned int node_index, 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_insert(parent->children, node_index, child);
	if (res == 0) {
	child->parent = parent;
	parent->count++;
	}
	return res;
	}

	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->parent) {
	printf("ROOT\n");
	}

	if(!node->children && node->parent) {
	printf("LEAF\n");
	} else {
	if(node->parent) {
	printf("NODE\n");
	}
	for (current = node_first_child(node); current; current = node_next_sibling(current)) {
	_node_debug(current, depth+1);
	}
	}

	}

	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(node_t node, unsigned int n)
	{
	if (!node \|\| !node->children \|\| !node->children->begin) return NULL;
	unsigned int node_index = 0;
	int found = 0;
	node_t ch;
	for (ch = node_first_child(node); ch; ch = node_next_sibling(ch)) {
	if (node_index++ == n) {
	found = 1;
	break;
	}
	}
	if (!found) {
	return NULL;
	}
	return ch;
	}

	node_t node_first_child(node_t node)
	{
	if (!node \|\| !node->children) return NULL;
	return node->children->begin;
	}

	node_t node_prev_sibling(node_t node)
	{
	if (!node) return NULL;
	return node->prev;
	}

	node_t node_next_sibling(node_t node)
	{
	if (!node) return NULL;
	return node->next;
	}

	int node_child_position(node_t parent, node_t child)
	{
	if (!parent \|\| !parent->children \|\| !parent->children->begin \|\| !child) return NODE_ERR_INVALID_ARG;
	int node_index = 0;
	int found = 0;
	node_t ch;
	for (ch = node_first_child(parent); ch; ch = node_next_sibling(ch)) {
	if (ch == child) {
	found = 1;
	break;
	}
	node_index++;
	}
	if (!found) {
	return NODE_ERR_NOT_FOUND;
	}
	return node_index;
	}

	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);
	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);
	if (!cc) {
	node_destroy(copy);
	return NULL;
	}
	if (node_attach(copy, cc) < 0) {
	node_destroy(copy);
	return NULL;
	}
	}
	return copy;
	}