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
14 #define IF_EDGE_HASH(e) ((e)->sourceNode)
15 #define IF_NODE_HASH(n) ((n)->nodeNumber)
16 #define IF_NODE_NEIGHBOUR_SLOTS 8
18 static int if_edge_cmp(const void* p1, const void* p2, size_t size) {
19 const be_if_edge_t* e1 = p1;
20 const be_if_edge_t* e2 = p2;
22 return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode));
25 static int if_node_cmp(const void* p1, const void* p2, size_t size) {
26 const be_if_node_t* n1 = p1;
27 const be_if_node_t* n2 = p2;
29 return (n1->nodeNumber != n2->nodeNumber);
32 static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) {
33 /* Bring the smaller entry to src. */
34 if (source > target) {
35 edge->sourceNode = target;
36 edge->targetNode = source;
38 edge->sourceNode = source;
39 edge->targetNode = target;
44 be_if_graph_t* be_ifg_new(int slots) {
45 be_if_graph_t* graph = malloc(sizeof(*graph));
46 graph->edges = new_set(if_edge_cmp, slots);
47 graph->nodes = new_set(if_node_cmp, slots);
51 void be_ifg_free(be_if_graph_t* graph) {
53 for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) {
54 free(ifn->neighbourNodes);
55 ifn->neighbourNodes = 0;
64 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) {
67 edge_init(&edge, source, target);
68 set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
72 node.nodeNumber = source;
73 node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
74 be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
75 node.nodeNumber = target;
76 node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
77 be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
79 /* insert neighbors into nodes */
80 pset_insert_ptr(sourceNode->neighbourNodes, targetNode);
81 pset_insert_ptr(targetNode->neighbourNodes, sourceNode);
84 static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) {
86 edge_init(&edge, source, target);
87 return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
90 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) {
91 return are_connected(graph, n1->nodeNumber, n2->nodeNumber);