+ real_t diff = c1->cost - c2->cost;
+ return (diff > 0) - (diff < 0);
+}
+
+static int cmp_col_cost_gt(const void *a, const void *b) {
+ const col_cost_t *c1 = a;
+ const col_cost_t *c2 = b;
+ real_t diff = c2->cost - c1->cost;
+ return (diff > 0) - (diff < 0);
+}
+
+/**
+ * Creates a new affinity chunk
+ */
+static INLINE aff_chunk_t *new_aff_chunk(co_mst_env_t *env) {
+ aff_chunk_t *c = xmalloc(sizeof(*c) + (env->n_regs - 1) * sizeof(c->color_affinity[0]));
+ c->n = NEW_ARR_F(const ir_node *, 0);
+ c->interfere = NEW_ARR_F(const ir_node *, 0);
+ c->weight = -1;
+ c->weight_consistent = 0;
+ c->deleted = 0;
+ c->id = ++last_chunk_id;
+ c->visited = 0;
+ pset_insert(env->chunkset, c, c->id);
+ return c;
+}
+
+/**
+ * Frees all memory allocated by an affinity chunk.
+ */
+static INLINE void delete_aff_chunk(co_mst_env_t *env, aff_chunk_t *c) {
+ pset_remove(env->chunkset, c, c->id);
+ DEL_ARR_F(c->interfere);
+ DEL_ARR_F(c->n);
+ c->deleted = 1;
+ free(c);
+}
+
+/**
+ * binary search of sorted nodes.
+ *
+ * @return the position where n is found in the array arr or ~pos
+ * if the nodes is not here.
+ */
+static INLINE int nodes_bsearch(const ir_node **arr, const ir_node *n) {
+ int hi = ARR_LEN(arr);
+ int lo = 0;
+
+ while (lo < hi) {
+ int md = lo + ((hi - lo) >> 1);
+
+ if (arr[md] == n)
+ return md;
+ if (arr[md] < n)
+ lo = md + 1;
+ else
+ hi = md;
+ }
+
+ return ~lo;
+}
+
+/** Check if a node n can be found inside arr. */
+static int node_contains(const ir_node **arr, const ir_node *n) {
+ int i = nodes_bsearch(arr, n);
+ return i >= 0;
+}
+
+/**
+ * Insert a node into the sorted nodes list.
+ *
+ * @return 1 if the node was inserted, 0 else
+ */
+static int nodes_insert(const ir_node ***arr, const ir_node *irn) {
+ int idx = nodes_bsearch(*arr, irn);
+
+ if (idx < 0) {
+ int i, n = ARR_LEN(*arr);
+ const ir_node **l;
+
+ ARR_APP1(const ir_node *, *arr, irn);
+
+ /* move it */
+ idx = ~idx;
+ l = *arr;
+ for (i = n - 1; i >= idx; --i)
+ l[i + 1] = l[i];
+ l[idx] = irn;
+ return 1;
+ }
+ return 0;
+}
+
+/**
+ * Adds a node to an affinity chunk
+ */
+static INLINE void aff_chunk_add_node(aff_chunk_t *c, co_mst_irn_t *node) {
+ int i;
+
+ if (! nodes_insert(&c->n, node->irn))
+ return;