The file is: working_vm\vm\jitrino\src\shared\unionfind.h .
In this file, one data structure is implemented to support
the following 3 operations:
MAKE_SET, FIND_SET, UNION_SET
To achieve high efficiency, there are two heuristics--"union by rank"
and "path compression" to improve the performance.
1. find () function implements two version of "path compression"
2. link () function try to implement the "union by rank" algorithm, but
unfortunately, it does not implement it correctly.
Here is the original code snippet
void link(UnionFind *other) {
assert(other);
UnionFind *aroot = find();
UnionFind *broot = other->find();
if (aroot->rank < broot->rank) {
aroot->parent = broot;
} else {
if (aroot->rank == broot->rank) {
broot->rank += 1;
}
broot->parent = aroot;
}
};
And you can check the original algorithm on the following page for more
details if
you want: section 22.3 in page
http://acm2.ustc.edu.cn/~daizisheng/algorithm/clrs/clrs_1st/book6/chap22.htm
Generally, the algorithm try to link the node with lower rank to the node
with higher
rank (rank is the height of the sub-tree rooted at current node, e.g.
height of
one-node-tree is 1), If both tree owns same rank (the if statement), we
break the
tie arbitrarily, here we set broot to be a child of aroot, and SO,
rank of node aroot should be increased by 1, not rank of node broot.
What we need to do to fix it is just changing the statement
broot->rank += 1;
into
aroot->rank += 1;
ANYWAY, such error does not lead to any invalidation, but it do lead an
efficiency problem.
Not sure whether it is a real bug, but at least, it
does not work as what the author expected.
