graph.c File Reference

#include <rz_util.h>

Go to the source code of this file.

Enumerations
enum	{ WHITE_COLOR = 0 , GRAY_COLOR , BLACK_COLOR }

Functions
static RzGraphNode *	rz_graph_node_new (void *data)
static void	rz_graph_node_free (RzGraphNode *n)
static int	node_cmp (unsigned int idx, RzGraphNode *b)
static void	dfs_node (RzGraph *g, RzGraphNode *n, RzGraphVisitor *vis, int color[], const bool direction)
RZ_API RzGraph *	rz_graph_new (void)
RZ_API void	rz_graph_free (RzGraph *t)
RZ_API RzGraphNode *	rz_graph_get_node (const RzGraph *t, unsigned int idx)
RZ_API RzListIter *	rz_graph_node_iter (const RzGraph *t, unsigned int idx)
RZ_API void	rz_graph_reset (RzGraph *t)
RZ_API RzGraphNode *	rz_graph_add_node (RzGraph *t, void *data)
RZ_API RzGraphNode *	rz_graph_add_nodef (RzGraph *graph, void *data, RzListFree user_free)
RZ_API void	rz_graph_del_node (RzGraph *t, RzGraphNode *n)
RZ_API void	rz_graph_add_edge (RzGraph *t, RzGraphNode *from, RzGraphNode *to)
RZ_API void	rz_graph_add_edge_at (RzGraph *t, RzGraphNode *from, RzGraphNode *to, int nth)
RZ_API RzGraphNode *	rz_graph_node_split_forward (RzGraph *g, RzGraphNode *split_me, void *data)
RZ_API void	rz_graph_del_edge (RzGraph *t, RzGraphNode *from, RzGraphNode *to)
RZ_API const RzList *	rz_graph_get_neighbours (const RzGraph *g, const RzGraphNode *n)
RZ_API RzGraphNode *	rz_graph_nth_neighbour (const RzGraph *g, const RzGraphNode *n, int nth)
RZ_API const RzList *	rz_graph_innodes (const RzGraph *g, const RzGraphNode *n)
RZ_API const RzList *	rz_graph_all_neighbours (const RzGraph *g, const RzGraphNode *n)
RZ_API const RzList *	rz_graph_get_nodes (const RzGraph *g)
RZ_API bool	rz_graph_adjacent (const RzGraph *g, const RzGraphNode *from, const RzGraphNode *to)
RZ_API void	rz_graph_dfs_node (RzGraph *g, RzGraphNode *n, RzGraphVisitor *vis)
RZ_API void	rz_graph_dfs_node_reverse (RzGraph *g, RzGraphNode *n, RzGraphVisitor *vis)
RZ_API void	rz_graph_dfs (RzGraph *g, RzGraphVisitor *vis)

Enumeration Type Documentation

anonymous enum

anonymous enum

Enumerator
WHITE_COLOR
GRAY_COLOR
BLACK_COLOR

Definition at line 7 of file graph.c.

     {
    WHITE_COLOR = 0,
    GRAY_COLOR,
    BLACK_COLOR
};

Function Documentation

dfs_node()

static void dfs_node ( RzGraph *  g, RzGraphNode *  n, RzGraphVisitor *  vis, int  color[], const bool  direction  )

static

Definition at line 43 of file graph.c.

                                                                                                         {
    if (!n) {
        return;
    }
    RzStack *s = rz_stack_new(2 * g->n_edges + 1);
    if (!s) {
        return;
    }
    RzGraphEdge *edg = RZ_NEW0(RzGraphEdge);
    if (!edg) {
        rz_stack_free(s);
        return;
    }
    edg->from = NULL;
    edg->to = n;
    rz_stack_push(s, edg);
    while (!rz_stack_is_empty(s)) {
        RzGraphEdge *cur_edge = (RzGraphEdge *)rz_stack_pop(s);
        RzGraphNode *v, *cur = cur_edge->to, *from = cur_edge->from;
        RzListIter *it;
        int i;
 
        if (from && cur) {
            if (color[cur->idx] == WHITE_COLOR && vis->tree_edge) {
                vis->tree_edge(cur_edge, vis);
            } else if (color[cur->idx] == GRAY_COLOR && vis->back_edge) {
                vis->back_edge(cur_edge, vis);
            } else if (color[cur->idx] == BLACK_COLOR && vis->fcross_edge) {
                vis->fcross_edge(cur_edge, vis);
            }
        } else if (!cur && from) {
            if (color[from->idx] != BLACK_COLOR && vis->finish_node) {
                vis->finish_node(from, vis);
            }
            color[from->idx] = BLACK_COLOR;
        }
        free(cur_edge);
        if (!cur || color[cur->idx] != WHITE_COLOR) {
            continue;
        }
        if (color[cur->idx] == WHITE_COLOR && vis->discover_node) {
            vis->discover_node(cur, vis);
        }
        color[cur->idx] = GRAY_COLOR;
 
        edg = RZ_NEW0(RzGraphEdge);
        if (!edg) {
            break;
        }
        edg->from = cur;
        rz_stack_push(s, edg);
 
        i = 0;
        const RzList *neighbours = direction ? cur->out_nodes : cur->in_nodes;
        rz_list_foreach (neighbours, it, v) {
            edg = RZ_NEW(RzGraphEdge);
            edg->from = cur;
            edg->to = v;
            edg->nth = i++;
            rz_stack_push(s, edg);
        }
    }
    rz_stack_free(s);
}

References rz_graph_visitor_t::back_edge, BLACK_COLOR, color, rz_graph_visitor_t::discover_node, rz_graph_visitor_t::fcross_edge, rz_graph_visitor_t::finish_node, free(), rz_graph_edge_t::from, from, g, GRAY_COLOR, i, rz_graph_node_t::idx, rz_graph_node_t::in_nodes, n, rz_graph_edge_t::nth, NULL, rz_graph_node_t::out_nodes, RZ_NEW, RZ_NEW0, rz_stack_free(), rz_stack_is_empty(), rz_stack_new(), rz_stack_pop(), rz_stack_push(), s, rz_graph_edge_t::to, rz_graph_visitor_t::tree_edge, v, and WHITE_COLOR.

Referenced by rz_graph_dfs(), rz_graph_dfs_node(), and rz_graph_dfs_node_reverse().

node_cmp()

static int node_cmp ( unsigned int  idx, RzGraphNode *  b  )

static

Definition at line 38 of file graph.c.

                                                      {
    return idx == b->idx ? 0 : -1;
}

References b, and setup::idx.

Referenced by rz_graph_get_node(), and rz_graph_node_iter().

rz_graph_add_edge()

RZ_API void rz_graph_add_edge	(	RzGraph *	t,
		RzGraphNode *	from,
		RzGraphNode *	to
	)

Definition at line 199 of file graph.c.

                                                                              {
    rz_graph_add_edge_at(t, from, to, -1);
}

References from, rz_graph_add_edge_at(), and to.

Referenced by add_single_addr_xrefs(), create_dummy_nodes(), dot_trace_discover_child(), rz_agraph_add_edge(), and rz_analysis_class_get_inheritance_graph().

rz_graph_add_edge_at()

RZ_API void rz_graph_add_edge_at	(	RzGraph *	t,
		RzGraphNode *	from,
		RzGraphNode *	to,
		int	nth
	)

Definition at line 203 of file graph.c.

                                                                                          {
    if (from && to) {
        rz_list_insert(from->out_nodes, nth, to);
        rz_list_append(from->all_neighbours, to);
        rz_list_append(to->in_nodes, from);
        rz_list_append(to->all_neighbours, from);
        t->n_edges++;
    }
}

References from, rz_graph_t::n_edges, rz_list_append(), rz_list_insert(), and to.

Referenced by rz_agraph_add_edge_at(), and rz_graph_add_edge().

rz_graph_add_node()

RZ_API RzGraphNode* rz_graph_add_node	(	RzGraph *	t,
		void *	data
	)

Definition at line 153 of file graph.c.

                                                              {
    if (!t) {
        return NULL;
    }
    RzGraphNode *n = rz_graph_node_new(data);
    if (!n) {
        return NULL;
    }
    n->idx = t->last_index++;
    rz_list_append(t->nodes, n);
    t->n_nodes++;
    return n;
}

References rz_graph_t::last_index, n, rz_graph_t::n_nodes, rz_graph_t::nodes, NULL, rz_graph_node_new(), and rz_list_append().

Referenced by get_graphtrace_node(), rz_agraph_add_node_with_color(), rz_graph_add_nodef(), and rz_graph_node_split_forward().

rz_graph_add_nodef()

RZ_API RzGraphNode* rz_graph_add_nodef	(	RzGraph *	graph,
		void *	data,
		RzListFree	user_free
	)

Definition at line 167 of file graph.c.

                                                                                         {
    RzGraphNode *node = rz_graph_add_node(graph, data);
    if (node) {
        node->free = user_free;
    }
    return node;
}

References rz_graph_node_t::free, and rz_graph_add_node().

Referenced by rz_graph_add_node_info().

rz_graph_adjacent()

RZ_API bool rz_graph_adjacent	(	const RzGraph *	g,
		const RzGraphNode *	from,
		const RzGraphNode *	to
	)

Definition at line 270 of file graph.c.

                                                                                                {
    if (!g || !from) {
        return false;
    }
    return rz_list_contains(from->out_nodes, to);
}

References from, g, rz_list_contains(), and to.

Referenced by dot_trace_discover_child(), and rz_graph_del_edge().

rz_graph_all_neighbours()

RZ_API const RzList* rz_graph_all_neighbours	(	const RzGraph *	g,
		const RzGraphNode *	n
	)

Definition at line 261 of file graph.c.

                                                                                     {
    return n ? n->all_neighbours : NULL;
}

References n, and NULL.

Referenced by adjust_class().

rz_graph_del_edge()

RZ_API void rz_graph_del_edge	(	RzGraph *	t,
		RzGraphNode *	from,
		RzGraphNode *	to
	)

Definition at line 232 of file graph.c.

                                                                              {
    if (!from || !to || !rz_graph_adjacent(t, from, to)) {
        return;
    }
    rz_list_delete_data(from->out_nodes, to);
    rz_list_delete_data(from->all_neighbours, to);
    rz_list_delete_data(to->in_nodes, from);
    rz_list_delete_data(to->all_neighbours, from);
    t->n_edges--;
}

References from, rz_graph_t::n_edges, rz_graph_adjacent(), rz_list_delete_data(), and to.

Referenced by rz_agraph_del_edge().

rz_graph_del_node()

RZ_API void rz_graph_del_node	(	RzGraph *	t,
		RzGraphNode *	n
	)

Definition at line 177 of file graph.c.

                                                          {
    RzGraphNode *gn;
    RzListIter *it;
    if (!n) {
        return;
    }
    rz_list_foreach (n->in_nodes, it, gn) {
        rz_list_delete_data(gn->out_nodes, n);
        rz_list_delete_data(gn->all_neighbours, n);
        t->n_edges--;
    }
 
    rz_list_foreach (n->out_nodes, it, gn) {
        rz_list_delete_data(gn->in_nodes, n);
        rz_list_delete_data(gn->all_neighbours, n);
        t->n_edges--;
    }
 
    rz_list_delete_data(t->nodes, n);
    t->n_nodes--;
}

References rz_graph_node_t::all_neighbours, rz_graph_node_t::in_nodes, n, rz_graph_t::n_edges, rz_graph_t::n_nodes, rz_graph_t::nodes, rz_graph_node_t::out_nodes, and rz_list_delete_data().

Referenced by fix_back_edge_dummy_nodes(), and rz_agraph_del_node().

rz_graph_dfs()

RZ_API void rz_graph_dfs	(	RzGraph *	g,
		RzGraphVisitor *	vis
	)

Definition at line 299 of file graph.c.

                                                          {
    rz_return_if_fail(g && vis);
    RzGraphNode *n;
    RzListIter *it;
 
    int *color = RZ_NEWS0(int, g->last_index);
    if (color) {
        rz_list_foreach (g->nodes, it, n) {
            if (color[n->idx] == WHITE_COLOR) {
                dfs_node(g, n, vis, color, true);
            }
        }
        free(color);
    }
}

References color, dfs_node(), free(), g, n, RZ_NEWS0, rz_return_if_fail, and WHITE_COLOR.

Referenced by assign_layers(), create_dummy_nodes(), and remove_cycles().

rz_graph_dfs_node()

RZ_API void rz_graph_dfs_node	(	RzGraph *	g,
		RzGraphNode *	n,
		RzGraphVisitor *	vis
	)

Definition at line 277 of file graph.c.

                                                                               {
    if (!g || !n || !vis) {
        return;
    }
    int *color = RZ_NEWS0(int, g->last_index);
    if (color) {
        dfs_node(g, n, vis, color, true);
        free(color);
    }
}

References color, dfs_node(), free(), g, n, and RZ_NEWS0.

rz_graph_dfs_node_reverse()

RZ_API void rz_graph_dfs_node_reverse	(	RzGraph *	g,
		RzGraphNode *	n,
		RzGraphVisitor *	vis
	)

Definition at line 288 of file graph.c.

                                                                                       {
    if (!g || !n || !vis) {
        return;
    }
    int *color = RZ_NEWS0(int, g->last_index);
    if (color) {
        dfs_node(g, n, vis, color, false);
        free(color);
    }
}

References color, dfs_node(), free(), g, n, and RZ_NEWS0.

rz_graph_free()

RZ_API void rz_graph_free

(

RzGraph *

t

)

Definition at line 124 of file graph.c.

                                      {
    rz_list_free(t->nodes);
    free(t);
}

References free(), rz_graph_t::nodes, and rz_list_free().

Referenced by cmd_analysis_graph(), dot_trace_traverse(), rz_agraph_free(), rz_analysis_class_get_inheritance_graph(), rz_analysis_class_graph_handler(), and rz_graph_new().

rz_graph_get_neighbours()

RZ_API const RzList* rz_graph_get_neighbours	(	const RzGraph *	g,
		const RzGraphNode *	n
	)

Definition at line 245 of file graph.c.

                                                                                     {
    return n ? n->out_nodes : NULL;
}

References n, and NULL.

Referenced by agraph_print_edges(), backedge_info(), collect_changes(), dot_trace_traverse(), fix_back_edge_dummy_nodes(), get_crossing_matrix(), get_edge_number(), place_single(), update_graph_sizes(), and user_edge_cb().

rz_graph_get_node()

RZ_API RzGraphNode* rz_graph_get_node	(	const RzGraph *	t,
		unsigned int	idx
	)

Definition at line 129 of file graph.c.

                                                                          {
    RzListIter *it = rz_list_find(t->nodes, (void *)(size_t)idx, (RzListComparator)node_cmp);
    if (!it) {
        return NULL;
    }
    return (RzGraphNode *)it->data;
}

References rz_list_iter_t::data, setup::idx, node_cmp(), rz_graph_t::nodes, NULL, and rz_list_find().

rz_graph_get_nodes()

RZ_API const RzList* rz_graph_get_nodes

(

const RzGraph *

g

)

Definition at line 265 of file graph.c.

                                                          {
    return g ? g->nodes : NULL;
}

References g, and NULL.

Referenced by agraph_print_edges(), agraph_print_edges_simple(), agraph_print_nodes(), agraph_set_layout(), compute_classes(), create_layers(), dot_trace_traverse(), find_near_of(), fold_asm_trace(), place_dummies(), place_original(), rz_agraph_get_first_node(), update_graph_sizes(), and update_node_dimension().

rz_graph_innodes()

RZ_API const RzList* rz_graph_innodes	(	const RzGraph *	g,
		const RzGraphNode *	n
	)

Definition at line 256 of file graph.c.

                                                                              {
    return n ? n->in_nodes : NULL;
}

References n, and NULL.

Referenced by adjust_directions(), assign_layers(), backedge_info(), collect_changes(), get_edge_number(), place_single(), rz_agraph_del_node(), and update_graph_sizes().

rz_graph_new()

RZ_API RzGraph* rz_graph_new

(

void

)

Definition at line 108 of file graph.c.

                                   {
    RzGraph *t = RZ_NEW0(RzGraph);
    if (!t) {
        return NULL;
    }
    t->nodes = rz_list_new();
    if (!t->nodes) {
        rz_graph_free(t);
        return NULL;
    }
    t->nodes->free = (RzListFree)rz_graph_node_free;
    t->n_nodes = 0;
    t->last_index = 0;
    return t;
}

References rz_list_t::free, rz_graph_t::last_index, rz_graph_t::n_nodes, rz_graph_t::nodes, NULL, rz_graph_free(), rz_graph_node_free(), rz_list_new(), and RZ_NEW0.

Referenced by agraph_init(), dot_trace_traverse(), rz_analysis_class_get_inheritance_graph(), rz_core_analysis_codexrefs(), and rz_core_analysis_importxrefs().

rz_graph_node_free()

static void rz_graph_node_free ( RzGraphNode *  n )

static

Definition at line 25 of file graph.c.

                                               {
    if (!n) {
        return;
    }
    if (n->free) {
        n->free(n->data);
    }
    rz_list_free(n->out_nodes);
    rz_list_free(n->in_nodes);
    rz_list_free(n->all_neighbours);
    free(n);
}

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

Referenced by rz_graph_new(), and rz_graph_reset().

rz_graph_node_iter()

RZ_API RzListIter* rz_graph_node_iter	(	const RzGraph *	t,
		unsigned int	idx
	)

Definition at line 137 of file graph.c.

                                                                          {
    return rz_list_find(t->nodes, (void *)(size_t)idx, (RzListComparator)node_cmp);
}

References setup::idx, node_cmp(), rz_graph_t::nodes, and rz_list_find().

rz_graph_node_new()

static RzGraphNode* rz_graph_node_new ( void *  data )

static

Definition at line 13 of file graph.c.

                                                  {
    RzGraphNode *p = RZ_NEW0(RzGraphNode);
    if (p) {
        p->data = data;
        p->free = NULL;
        p->out_nodes = rz_list_new();
        p->in_nodes = rz_list_new();
        p->all_neighbours = rz_list_new();
    }
    return p;
}

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

Referenced by rz_graph_add_node().

rz_graph_node_split_forward()

RZ_API RzGraphNode* rz_graph_node_split_forward	(	RzGraph *	g,
		RzGraphNode *	split_me,
		void *	data
	)

Definition at line 214 of file graph.c.

                                                                                               {
    RzGraphNode *front = rz_graph_add_node(g, data);
    RzList *tmp = front->out_nodes;
    front->out_nodes = split_me->out_nodes;
    split_me->out_nodes = tmp;
    RzListIter *iter;
    RzGraphNode *n;
    rz_list_foreach (front->out_nodes, iter, n) {
        rz_list_delete_data(n->in_nodes, split_me); // optimize me
        rz_list_delete_data(n->all_neighbours, split_me); // boy this all_neighbours is so retarding perf here
        rz_list_delete_data(split_me->all_neighbours, n);
        rz_list_append(n->all_neighbours, front);
        rz_list_append(n->in_nodes, front);
        rz_list_append(front->all_neighbours, n);
    }
    return front;
}

References rz_graph_node_t::all_neighbours, g, n, rz_graph_node_t::out_nodes, rz_graph_add_node(), rz_list_append(), rz_list_delete_data(), and autogen_x86imm::tmp.

rz_graph_nth_neighbour()

RZ_API RzGraphNode* rz_graph_nth_neighbour	(	const RzGraph *	g,
		const RzGraphNode *	n,
		int	nth
	)

Definition at line 251 of file graph.c.

                                                                                            {
    return n ? (RzGraphNode *)rz_list_get_n(n->out_nodes, nth) : NULL;
}

References n, NULL, and rz_list_get_n().

Referenced by adjust_directions(), compute_vertical_nodes(), and follow_nth().

rz_graph_reset()

RZ_API void rz_graph_reset

(

RzGraph *

t

)

Definition at line 141 of file graph.c.

                                       {
    rz_list_free(t->nodes);
    t->nodes = rz_list_new();
    if (!t->nodes) {
        return;
    }
    t->nodes->free = (RzListFree)rz_graph_node_free;
    t->n_nodes = 0;
    t->n_edges = 0;
    t->last_index = 0;
}

References rz_list_t::free, rz_graph_t::last_index, rz_graph_t::n_edges, rz_graph_t::n_nodes, rz_graph_t::nodes, rz_graph_node_free(), rz_list_free(), and rz_list_new().

Referenced by rz_agraph_reset().