[Sheepdog] [PATCH 03/18] add common tree utilities

[MORITA Kazutaka]

This utilities will be used by cluster startup, vdi deletion, and other
tree manipulations.

Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp>
---
 include/tree.h |   48 +++++++++++++
 lib/tree.c     |  203 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 251 insertions(+), 0 deletions(-)
 create mode 100644 include/tree.h
 create mode 100644 lib/tree.c

diff --git a/include/tree.h b/include/tree.h
new file mode 100644
index 0000000..b005f32
--- /dev/null
+++ b/include/tree.h
@@ -0,0 +1,48 @@
+/*
+ * Copyright (C) 2010 Nippon Telegraph and Telephone Corporation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License version
+ * 2 as published by the Free Software Foundation.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef __TREE_H__
+#define __TREE_H__
+
+#include <stdint.h>
+
+#include "list.h"
+
+struct tree_vertex {
+	uint64_t id;
+	uint64_t parent_id;
+	struct tree_vertex *parent;
+	struct list_head children;
+	struct list_head siblings;
+};
+
+typedef int (*tree_vertex_func_t)(struct tree_vertex *vertex, int depth,
+				  void *data);
+typedef int (*tree_str_func_t)(struct tree_vertex *vertex, char *buf, int len);
+
+
+
+void INIT_TREE_VERTEX(struct tree_vertex *tree, uint64_t id, uint64_t parent_id);
+int tree_no_children(struct tree_vertex *vertex);
+struct tree_vertex *tree_parent(struct tree_vertex *vertex);
+struct tree_vertex *tree_first_child(struct tree_vertex *vertex);
+struct tree_vertex *tree_last_child(struct tree_vertex *vertex);
+
+int tree_walk(struct tree_vertex *root, tree_vertex_func_t func, void *data);
+void tree_add(struct tree_vertex *new, struct tree_vertex *root);
+void tree_del(struct tree_vertex *vertex);
+struct tree_vertex *tree_find(uint64_t id, struct tree_vertex *root);
+int tree_depth(struct tree_vertex *root);
+void tree_print(struct tree_vertex *root, char *label, tree_str_func_t func);
+
+#define tree_for_each_child(pos, root) \
+	list_for_each_entry(pos, &(root)->children, siblings)
+
+#endif
diff --git a/lib/tree.c b/lib/tree.c
new file mode 100644
index 0000000..af29b41
--- /dev/null
+++ b/lib/tree.c
@@ -0,0 +1,203 @@
+/*
+ * Copyright (C) 2010 Nippon Telegraph and Telephone Corporation.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License version
+ * 2 as published by the Free Software Foundation.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program. If not, see <http://www.gnu.org/licenses/>.
+ */
+#include <stdio.h>
+#include <string.h>
+
+#include "list.h"
+#include "tree.h"
+
+void INIT_TREE_VERTEX(struct tree_vertex *tree, uint64_t id, uint64_t parent_id)
+{
+	tree->id = id;
+	tree->parent_id = parent_id;
+	tree->parent = NULL;
+	INIT_LIST_HEAD(&tree->children);
+	INIT_LIST_HEAD(&tree->siblings);
+}
+
+int tree_no_children(struct tree_vertex *vertex)
+{
+	return list_empty(&vertex->children);
+}
+
+struct tree_vertex *tree_parent(struct tree_vertex *vertex)
+{
+	return vertex->parent;
+}
+
+struct tree_vertex *tree_first_child(struct tree_vertex *vertex)
+{
+	return container_of(vertex->children.next, struct tree_vertex, siblings);
+}
+
+struct tree_vertex *tree_last_child(struct tree_vertex *vertex)
+{
+	return container_of(vertex->children.prev, struct tree_vertex, siblings);
+}
+
+static int __tree_walk(struct tree_vertex *vertex, int depth,
+		       tree_vertex_func_t func, void *data)
+{
+	struct tree_vertex *e, *_n;
+
+	if (func(vertex, depth, data))
+		return 1;
+	list_for_each_entry_safe(e, _n, &vertex->children, siblings)
+		if (__tree_walk(e, depth + 1, func, data))
+			return 1;
+	return 0;
+}
+
+int tree_walk(struct tree_vertex *root, tree_vertex_func_t func, void *data)
+{
+	return __tree_walk(root, 0, func, data);
+}
+
+static int __tree_add(struct tree_vertex *vertex, int depth,
+		      struct tree_vertex *new)
+{
+	if (vertex->id == new->parent_id) {
+		new->parent = vertex;
+		list_del(&new->siblings);
+		list_add(&new->siblings, &vertex->children);
+	} else if (vertex->parent_id == new->id) {
+		vertex->parent = new;
+		list_del(&vertex->siblings);
+		list_add(&vertex->siblings, &new->children);
+	}
+	return 0;
+}
+
+void tree_add(struct tree_vertex *new, struct tree_vertex *root)
+{
+	tree_walk(root, (tree_vertex_func_t)__tree_add, new);
+	if (!new->parent) {
+		new->parent = root;
+		list_add(&new->siblings, &root->children);
+	}
+}
+
+void tree_del(struct tree_vertex *vertex)
+{
+	vertex->parent = NULL;
+	list_del(&vertex->siblings);
+}
+
+struct tree_find_query {
+	uint64_t id;
+	struct tree_vertex *result;
+};
+
+static int __tree_find(struct tree_vertex *vertex, int depth,
+		       struct tree_find_query *query)
+{
+	if (vertex->id == query->id) {
+		query->result = vertex;
+		return 1;
+	}
+	return 0;
+}
+
+struct tree_vertex *tree_find(uint64_t id, struct tree_vertex *root)
+{
+	struct tree_find_query query = { id, NULL };
+
+	tree_walk(root, (tree_vertex_func_t)__tree_find, &query);
+	return query.result;
+}
+
+static int __tree_depth(struct tree_vertex *vertex, int depth,
+			int *max_depth)
+{
+	if (depth > *max_depth)
+		*max_depth = depth;
+	return 0;
+}
+
+int tree_depth(struct tree_vertex *root)
+{
+	int res = 0;
+
+	tree_walk(root, (tree_vertex_func_t)__tree_depth, &res);
+	return res;
+}
+
+#define TREE_MAX_PRINT_DEPTH 1024
+
+static int width[TREE_MAX_PRINT_DEPTH];
+static int more[TREE_MAX_PRINT_DEPTH];
+
+static void spaces(int n)
+{
+	while (n--)
+		putchar(' ');
+}
+
+static void indent(int level, int first, int last)
+{
+	int lvl;
+
+	if (first)
+		printf(last ? "---" : "-+-");
+	else {
+		for (lvl = 0; lvl < level - 1; lvl++) {
+			spaces(width[lvl] + 1);
+			printf(more[lvl + 1] ? "| " : "  ");
+		}
+
+		spaces(width[level - 1] + 1);
+		printf(last ? "`-" : "|-");
+	}
+}
+
+static int __tree_print(struct tree_vertex *vertex, int depth,
+			tree_str_func_t print_func)
+{
+	char buf[1024];
+	int first, last;
+	int w;
+
+	if (tree_parent(vertex)) {
+		first = (vertex == tree_first_child(vertex->parent));
+		last = (vertex == tree_last_child(vertex->parent));
+	} else {
+		first = 1;
+		last = 1;
+	}
+
+	indent(depth, first, last);
+
+	w = print_func(vertex, buf, sizeof(buf));
+	printf(buf);
+
+	if (tree_no_children(vertex)) {
+		putchar('\n');
+		return 0;
+	}
+
+	width[depth] = w;
+	more[depth] = !last;
+
+	return 0;
+}
+
+void tree_print(struct tree_vertex *root, char *label, tree_str_func_t func)
+{
+	int depth = tree_depth(root);
+
+	if (depth > TREE_MAX_PRINT_DEPTH)
+		return;
+
+	printf(label);
+	more[0] = 0;
+	width[0] = strlen(label);
+	tree_walk(root, (tree_vertex_func_t)__tree_print, func);
+}
-- 
1.5.6.5