tree.c File Reference

#include <rz_util.h>
#include <rz_vector.h>

Go to the source code of this file.

Functions
static void	tree_dfs_node (RTreeNode *r, RTreeVisitor *vis)
static void	rz_tree_node_free (RTreeNode *n)
static void	node_free (RTreeNode *n, RTreeVisitor *vis)
static void	free_all_children (RTree *t)
static void	update_depth (RTreeNode *n, RTreeVisitor *vis)
static RTreeNode *	node_new (RTree *t, void *data)
RZ_API RTree *	rz_tree_new (void)
RZ_API void	rz_tree_free (RTree *t)
RZ_API void	rz_tree_reset (RTree *t)
RZ_API RTreeNode *	rz_tree_add_node (RTree *t, RTreeNode *node, void *child_data)
RZ_API void	rz_tree_dfs (RTree *t, RTreeVisitor *vis)
RZ_API void	rz_tree_bfs (RTree *t, RTreeVisitor *vis)

Function Documentation

free_all_children()

static void free_all_children ( RTree *  t )

static

Definition at line 51 of file tree.c.

                                        {
    RTreeVisitor vis = { 0 };
    vis.post_visit = (RTreeNodeVisitCb)node_free;
    rz_tree_bfs(t, &vis);
}

References node_free(), rz_tree_visitor_t::post_visit, and rz_tree_bfs().

Referenced by rz_tree_free(), and rz_tree_reset().

node_free()

static void node_free ( RTreeNode *  n, RTreeVisitor *  vis  )

static

Definition at line 47 of file tree.c.

                                                       {
    rz_tree_node_free(n);
}

References n, and rz_tree_node_free().

Referenced by free_all_children().

node_new()

static RTreeNode* node_new ( RTree *  t, void *  data  )

static

Definition at line 61 of file tree.c.

                                                 {
    RTreeNode *n = RZ_NEW0(RTreeNode);
    if (!n) {
        return NULL;
    }
    n->children = rz_list_new();
    n->data = data;
    n->tree = t;
    return n;
}

References n, NULL, rz_list_new(), and RZ_NEW0.

Referenced by rz_tree_add_node().

rz_tree_add_node()

RZ_API RTreeNode* rz_tree_add_node	(	RTree *	t,
		RTreeNode *	node,
		void *	child_data
	)

Definition at line 99 of file tree.c.

                                                                                {
    RTreeNode *child;
    RTreeVisitor vis = { 0 };
 
    /* a NULL node is allowed only the first time, to set the root */
    if (!t || (node && node->tree != t) || (t->root && !node)) {
        return NULL;
    }
 
    child = node_new(t, child_data);
    if (!node && !t->root) {
        t->root = child;
    } else if (node) {
        rz_list_append(node->children, child);
        node->n_children++;
    }
    child->parent = node;
 
    /* update depth */
    vis.pre_visit = (RTreeNodeVisitCb)update_depth;
    tree_dfs_node(child, &vis);
 
    return child;
}

References rz_tree_node_t::children, rz_tree_node_t::n_children, node_new(), NULL, rz_tree_node_t::parent, rz_tree_visitor_t::pre_visit, rz_tree_t::root, rz_list_append(), rz_tree_node_t::tree, tree_dfs_node(), and update_depth().

Referenced by add_trace_tree_child(), and do_debug_trace_calls().

rz_tree_bfs()

RZ_API void rz_tree_bfs	(	RTree *	t,
		RTreeVisitor *	vis
	)

Definition at line 132 of file tree.c.

                                                     {
    if (!t || !t->root) {
        return;
    }
 
    RzPVector *pv = rz_pvector_new(NULL);
    if (!pv) {
        return;
    }
    rz_pvector_reserve(pv, 16);
    rz_pvector_push(pv, t->root);
    while (!rz_pvector_empty(pv)) {
        RTreeNode *el = (RTreeNode *)rz_pvector_pop_front(pv);
        if (!el) {
            break;
        }
        RTreeNode *n;
        RzListIter *it;
 
        if (vis->pre_visit) {
            vis->pre_visit(el, vis);
        }
 
        rz_list_foreach (el->children, it, n) {
            if (vis->discover_child) {
                vis->discover_child(n, vis);
            }
            rz_pvector_push(pv, n);
        }
 
        if (vis->post_visit) {
            vis->post_visit(el, vis);
        }
    }
 
    rz_pvector_free(pv);
}

References rz_tree_node_t::children, rz_tree_visitor_t::discover_child, n, NULL, rz_tree_visitor_t::post_visit, rz_tree_visitor_t::pre_visit, rz_tree_t::root, rz_pvector_empty(), rz_pvector_free(), rz_pvector_new(), rz_pvector_pop_front(), rz_pvector_push(), and rz_pvector_reserve().

Referenced by dot_trace_traverse(), and free_all_children().

rz_tree_dfs()

RZ_API void rz_tree_dfs	(	RTree *	t,
		RTreeVisitor *	vis
	)

Definition at line 124 of file tree.c.

                                                     {
    if (!t || !t->root) {
        return;
    }
 
    tree_dfs_node(t->root, vis);
}

References rz_tree_t::root, and tree_dfs_node().

Referenced by trace_traverse().

rz_tree_free()

RZ_API void rz_tree_free

(

RTree *

t

)

Definition at line 76 of file tree.c.

                                   {
    if (!t) {
        return;
    }
 
    free_all_children(t);
    free(t);
}

References free(), and free_all_children().

Referenced by rz_debug_free().

rz_tree_new()

RZ_API RTree* rz_tree_new

(

void

)

Definition at line 72 of file tree.c.

                                {
    return RZ_NEW0(RTree);
}

References RZ_NEW0.

Referenced by rz_debug_new().

rz_tree_node_free()

static void rz_tree_node_free ( RTreeNode *  n )

static

Definition at line 39 of file tree.c.

                                            {
    rz_list_free(n->children);
    if (n->free) {
        n->free(n->data);
    }
    free(n);
}

References free(), n, and rz_list_free().

Referenced by node_free().

rz_tree_reset()

RZ_API void rz_tree_reset

(

RTree *

t

)

Definition at line 85 of file tree.c.

                                    {
    if (!t) {
        return;
    }
 
    free_all_children(t);
    t->root = NULL;
}

References free_all_children(), NULL, and rz_tree_t::root.

Referenced by rz_cmd_debug_traces_reset_handler().

tree_dfs_node()

static void tree_dfs_node ( RTreeNode *  r, RTreeVisitor *  vis  )

static

Definition at line 7 of file tree.c.

                                                           {
    RzStack *s;
    RzListIter *it;
    RTreeNode *n;
 
    s = rz_stack_new(16);
    if (!s) {
        return;
    }
    rz_stack_push(s, r);
    while (!rz_stack_is_empty(s)) {
        RTreeNode *el = (RTreeNode *)rz_stack_pop(s);
 
        if (vis->pre_visit) {
            vis->pre_visit(el, vis);
        }
 
        rz_list_foreach_prev(el->children, it, n) {
            if (vis->discover_child) {
                vis->discover_child(n, vis);
            }
            rz_stack_push(s, n);
        }
 
        if (vis->post_visit) {
            vis->post_visit(el, vis);
        }
    }
 
    rz_stack_free(s);
}

References rz_tree_node_t::children, rz_tree_visitor_t::discover_child, n, rz_tree_visitor_t::post_visit, rz_tree_visitor_t::pre_visit, r, rz_stack_free(), rz_stack_is_empty(), rz_stack_new(), rz_stack_pop(), rz_stack_push(), and s.

Referenced by rz_tree_add_node(), and rz_tree_dfs().

update_depth()

static void update_depth ( RTreeNode *  n, RTreeVisitor *  vis  )

static

Definition at line 57 of file tree.c.

                                                          {
    n->depth = n->parent ? n->parent->depth + 1 : 0;
}

References n.

Referenced by rz_tree_add_node().