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

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