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

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