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
25 #define IF_EDGE_HASH(e) ((e)->sourceNode)
26 #define IF_NODE_HASH(n) ((n)->nodeNumber)
27 #define IF_NODE_NEIGHBOUR_SLOTS 8
29 static int if_edge_cmp(const void* p1, const void* p2, size_t size) {
30 const be_if_edge_t* e1 = p1;
31 const be_if_edge_t* e2 = p2;
33 return !((e1->sourceNode == e2->sourceNode) && (e1->targetNode == e2->targetNode));
36 static int if_node_cmp(const void* p1, const void* p2, size_t size) {
37 const be_if_node_t* n1 = p1;
38 const be_if_node_t* n2 = p2;
40 return (n1->nodeNumber != n2->nodeNumber);
43 static INLINE be_if_edge_t *edge_init(be_if_edge_t* edge, int source, int target) {
44 /* Bring the smaller entry to src. */
45 if (source > target) {
46 edge->sourceNode = target;
47 edge->targetNode = source;
49 edge->sourceNode = source;
50 edge->targetNode = target;
55 be_if_graph_t* be_ifg_new(int slots) {
56 be_if_graph_t* graph = malloc(sizeof(*graph));
57 graph->edges = new_set(if_edge_cmp, slots);
58 graph->nodes = new_set(if_node_cmp, slots);
62 void be_ifg_free(be_if_graph_t* graph) {
64 for (ifn = set_first(graph->nodes); ifn; ifn = set_next(graph->nodes)) {
65 free(ifn->neighbourNodes);
66 ifn->neighbourNodes = 0;
75 void be_ifg_add_interference(be_if_graph_t* graph, int source, int target) {
78 edge_init(&edge, source, target);
79 set_insert(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge));
83 node.nodeNumber = source;
84 node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
85 be_if_node_t* sourceNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
86 node.nodeNumber = target;
87 node.neighbourNodes = pset_new_ptr(IF_NODE_NEIGHBOUR_SLOTS);
88 be_if_node_t* targetNode = set_insert(graph->nodes, &node, sizeof(node), IF_NODE_HASH(&node));
90 /* insert neighbors into nodes */
91 pset_insert_ptr(sourceNode->neighbourNodes, targetNode);
92 pset_insert_ptr(targetNode->neighbourNodes, sourceNode);
95 static INLINE int are_connected(const be_if_graph_t* graph, int source, int target) {
97 edge_init(&edge, source, target);
98 return set_find(graph->edges, &edge, sizeof(edge), IF_EDGE_HASH(&edge)) != NULL;
101 int be_ifg_has_edge(const be_if_graph_t* graph, const be_if_node_t* n1, const be_if_node_t* n2) {
102 return are_connected(graph, n1->nodeNumber, n2->nodeNumber);