2 * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
4 * This file is part of libFirm.
6 * This file may be distributed and/or modified under the terms of the
7 * GNU General Public License version 2 as published by the Free Software
8 * Foundation and appearing in the file LICENSE.GPL included in the
9 * packaging of this file.
11 * Licensees holding valid libFirm Professional Edition licenses may use
12 * this file in accordance with the libFirm Commercial License.
13 * Agreement provided with the Software.
15 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
16 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
22 * @author Sebastian Hack
27 * depth first search internal stuff.
29 #ifndef FIRM_ANA_DFS_T_H
30 #define FIRM_ANA_DFS_T_H
48 const void *src, *tgt;
55 const absgraph_t *graph_impl;
60 dfs_node_t **pre_order;
61 dfs_node_t **post_order;
66 unsigned edges_classified : 1;
69 static dfs_node_t *_dfs_get_node(const dfs_t *self, const void *node)
72 memset(&templ, 0, sizeof(templ));
74 return set_insert(self->nodes, &templ, sizeof(templ), HASH_PTR(node));
77 #define _dfs_int_is_ancestor(n, m) ((m)->pre_num >= (n)->pre_num && (m)->pre_num <= (n)->max_pre_num)
79 static inline int _dfs_is_ancestor(const dfs_t *dfs, const void *a, const void *b)
81 dfs_node_t *n = _dfs_get_node(dfs, a);
82 dfs_node_t *m = _dfs_get_node(dfs, b);
83 return _dfs_int_is_ancestor(n, m);
86 #define dfs_get_n_nodes(dfs) ((dfs)->pre_num)
87 #define dfs_get_pre_num(dfs, node) (_dfs_get_node((dfs), (node))->pre_num)
88 #define dfs_get_post_num(dfs, node) (_dfs_get_node((dfs), (node))->post_num)
89 #define dfs_get_pre_num_node(dfs, num) ((dfs)->pre_order[num]->node)
90 #define dfs_get_post_num_node(dfs, num) ((dfs)->post_order[num]->node)
91 #define dfs_is_ancestor(dfs, n, m) _dfs_is_ancestor((n), (m))
93 #endif /* FIRM_ANA_DFS_T_H */