nsz Git - libfirm/blob - ir/ana/dfs_t.h

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   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.
  10  *
  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.
  14  *
  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
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file    dfs_t.h
  22  * @author  Sebastian Hack
  23  * @date    21.04.2007
  24  * @brief
  25  *
  26  * depth first search internal stuff.
  27  */
  28 #ifndef FIRM_ANA_DFS_T_H
  29 #define FIRM_ANA_DFS_T_H
  30
  31 #include "hashptr.h"
  32 #include "absgraph.h"
  33 #include "obst.h"
  34 #include "dfs.h"
  35
  36 struct dfs_node_t {
  37         int visited;
  38         const void *node;
  39         const void *ancestor;
  40         int pre_num;
  41         int max_pre_num;
  42         int post_num;
  43         int level;
  44 };
  45
  46 struct dfs_edge_t {
  47         const void *src, *tgt;
  48         dfs_node_t *s, *t;
  49         dfs_edge_kind_t kind;
  50 };
  51
  52 struct dfs_t {
  53         void *graph;
  54         const absgraph_t *graph_impl;
  55         struct obstack obst;
  56
  57         set *nodes;
  58         set *edges;
  59         dfs_node_t **pre_order;
  60         dfs_node_t **post_order;
  61
  62         int pre_num;
  63         int post_num;
  64
  65         unsigned edges_classified : 1;
  66 };
  67
  68 static dfs_node_t *_dfs_get_node(const dfs_t *self, const void *node)
  69 {
  70         dfs_node_t templ;
  71         memset(&templ, 0, sizeof(templ));
  72         templ.node = node;
  73         return set_insert(dfs_node_t, self->nodes, &templ, sizeof(templ), hash_ptr(node));
  74 }
  75
  76 #define _dfs_int_is_ancestor(n, m) ((m)->pre_num >= (n)->pre_num && (m)->pre_num <= (n)->max_pre_num)
  77
  78 static inline int _dfs_is_ancestor(const dfs_t *dfs, const void *a, const void *b)
  79 {
  80         dfs_node_t *n = _dfs_get_node(dfs, a);
  81         dfs_node_t *m = _dfs_get_node(dfs, b);
  82         return _dfs_int_is_ancestor(n, m);
  83 }
  84
  85 #define dfs_get_n_nodes(dfs)            ((dfs)->pre_num)
  86 #define dfs_get_pre_num(dfs, node)      (_dfs_get_node((dfs), (node))->pre_num)
  87 #define dfs_get_post_num(dfs, node)     (_dfs_get_node((dfs), (node))->post_num)
  88 #define dfs_get_pre_num_node(dfs, num)  ((dfs)->pre_order[num]->node)
  89 #define dfs_get_post_num_node(dfs, num) ((dfs)->post_order[num]->node)
  90 #define dfs_is_ancestor(dfs, n, m)      _dfs_is_ancestor((n), (m))
  91
  92 #endif /* FIRM_ANA_DFS_T_H */