nsz Git - libfirm/blob - ir/be/beifg.h

   1 /**
   2  * Common use interference graph.
   3  * Originally written by Sebastian Hack. Refactored into a seperate
   4  * source file and header by Kimon Hoffmann.
   5  * @author Sebastian Hack
   6  * @date 27.06.2005
   7  */
   8 #ifndef _BEIFG_H_
   9 #define _BEIFG_H_
  10
  11 typedef struct _be_if_graph_t be_if_graph_t;
  12 typedef struct _be_if_node_t be_if_node_t;
  13 typedef struct _be_if_edge_t be_if_edge_t;
  14
  15 /**
  16  * Creates a new interference graph with the specified number of
  17  * initial slots.
  18  * @param slots the initial number of slots used for hashing.
  19  *              Must be greater than 0.
  20  * @return the created, empty interference graph.
  21  */
  22 be_if_graph_t* be_ifg_new(int slots);
  23
  24 /**
  25  * Frees the passed interference graph an all contained nodes.
  26  * @param graph the interference graph that shall be freed. Please note
  27  *              that after a call to this function all pointers to the graph,
  28  *              its edges or its nodes are invalid.
  29  */
  30 void be_ifg_free(be_if_graph_t* graph);
  31
  32 /**
  33  * Adds a new undirected interference edge between the two nodes
  34  * specified by their node numbers. If the corresponding nodes do
  35  * not yet exist in the iunterference grpah they are created pririor
  36  * to creation of the edge.
  37  * @param graph the graph to add the interference edge to.
  38  * @param source the key of the source node.
  39  * @param target the key of the target node.
  40  */
  41 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target);
  42
  43 /**
  44  * Returns the set of all edges within the specified
  45  * graph.
  46  * @param graph the graph the return the set of edges of.
  47  * @return A set of all edges within the specified graph as
  48  *              be_if_edge_t instances.
  49  */
  50 set* be_get_ifg_edges(const be_if_graph_t* graph);
  51
  52 /**
  53  * Returns the set of all nodes within the specified
  54  * graph.
  55  * @param graph the graph the return the set of nodes of.
  56  * @return A set of all nodes within the specified graph as
  57  *              be_if_node_t instances.
  58  */
  59 set* be_get_ifg_nodes(const be_if_graph_t* graph);
  60
  61 /**
  62  * Returns whether the specified graph alreadz contains an undirected
  63  * edge between the two passed nodes.
  64  * @param graph the graph to which containment both nodes @p n1 and
  65  *              @p n2 belong.
  66  * @param n1 the one end of the edge to query the graph for.
  67  * @param n2 the other end of the edge.
  68  * @return TRUE if the graph contains an edge between @p n1 and @p n2,
  69  *              otherwise FALSE.
  70  */
  71 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2);
  72
  73 #define be_ifn_get_degree(ifnode) \
  74         pset_count(ifnode->neighb)
  75
  76 #define be_ifn_foreach_neighbour(ifnode, curr) \
  77         for (curr = pset_first(ifnode->neighbourNodes); curr; curr = pset_next(ifnode->neighbourNodes))
  78
  79 #define be_ifg_foreach_node(ifgraph, curr) \
  80         for (curr = set_first(ifgraph->nodes); curr; curr = set_next(ifgraph->nodes))
  81
  82 #define be_ifg_foreach_edge(ifgraph, curr) \
  83         for (curr = set_first(ifgraph->edges); curr; curr = set_next(ifgraph->edges))
  84
  85
  86 #endif /*_BEIFG_H_*/