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 |