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
23 #define IF_EDGE_HASH(e) ((e)->sourceNode)
24 #define IF_NODE_HASH(n) ((n)->nodeNumber)
25 #define IF_NODE_NEIGHBOUR_SLOTS 8
27 static int if_edge_cmp(const void* p1, const void* p2, size_t size) {
28 const be_if_edge_t* e1 = p1;
29 const be_if_edge_t* e2 = p2;
31 return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode));
34 static int if_node_cmp(const void* p1, const void* p2, size_t size) {
35 const be_if_node_t* n1 = p1;
36 const be_if_node_t* n2 = p2;
38 return (n1->nodeNumber != n2->nodeNumber);
41 static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) {
42 /* Bring the smaller entry to src. */
43 if (source > target) {
44 edge->sourceNode = target;
45 edge->targetNode = source;
47 edge->sourceNode = source;
48 edge->targetNode = target;
53 be_if_graph_t* be_ifg_new(int slots) {
54 be_if_graph_t* graph = malloc(sizeof(*graph));
55 graph->edges = new_set(if_edge_cmp, slots);
56 graph->nodes = new_set(if_node_cmp, slots);
60 void be_ifg_free(be_if_graph_t* graph) {
62 for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) {
63 free(ifn->neighbourNodes);
64 ifn->neighbourNodes = 0;
73 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) {
76 edge_init(&edge, source, target);
77 set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
81 node.nodeNumber = source;
82 node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
83 be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
84 node.nodeNumber = target;
85 node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
86 be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
88 /* insert neighbors into nodes */
89 pset_insert_ptr(sourceNode->neighbourNodes, targetNode);
90 pset_insert_ptr(targetNode->neighbourNodes, sourceNode);
93 static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) {
95 edge_init(&edge, source, target);
96 return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
99 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) {
100 return are_connected(graph, n1->nodeNumber, n2->nodeNumber);