Skip to content

Commit

Permalink
[Truffle] Fixed issue with pairing ropes incorrectly during the rebal…
Browse files Browse the repository at this point in the history
…ancing process.

By reusing the same queue for all levels, if there's an odd number of nodes in any given level, they'll pair with a node from the next level improperly. Using two queues to separate the levels addresses the problem.
nirvdrum committed Dec 20, 2016
1 parent 8abc05a commit 7020048
Showing 1 changed file with 24 additions and 9 deletions.
33 changes: 24 additions & 9 deletions truffle/src/main/java/org/jruby/truffle/core/rope/RopeNodes.java
Original file line number Diff line number Diff line change
@@ -337,25 +337,35 @@ private boolean isBalanced(Rope left, Rope right) {

@TruffleBoundary
private Rope rebalance(ConcatRope rope, int depthThreshold, FlattenNode flattenNode) {
final Deque<Rope> ropeQueue = new ArrayDeque<>();
Deque<Rope> currentRopeQueue = new ArrayDeque<>();
Deque<Rope> nextLevelQueue = new ArrayDeque<>();

linearizeTree(rope.getLeft(), ropeQueue);
linearizeTree(rope.getRight(), ropeQueue);
linearizeTree(rope.getLeft(), currentRopeQueue);
linearizeTree(rope.getRight(), currentRopeQueue);

final int flattenThreshold = depthThreshold / 2;

Rope root = null;
while (! ropeQueue.isEmpty()) {
Rope left = ropeQueue.pop();
while (! currentRopeQueue.isEmpty()) {
Rope left = currentRopeQueue.pop();

if (left.depth() >= flattenThreshold) {
left = flattenNode.executeFlatten(left);
}

if (ropeQueue.isEmpty()) {
root = left;
if (currentRopeQueue.isEmpty()) {
if (nextLevelQueue.isEmpty()) {
root = left;
} else {
// If a rope can't be paired with another rope at the current level (i.e., odd numbers of ropes),
// it needs to be promoted to the next level where it be tried again. Since by definition every
// rope already present in the next level must have occurred before this rope in the current
// level, this rope must be added to the end of the list in the next level to maintain proper
// position.
nextLevelQueue.add(left);
}
} else {
Rope right = ropeQueue.pop();
Rope right = currentRopeQueue.pop();

if (right.depth() >= flattenThreshold) {
right = flattenNode.executeFlatten(right);
@@ -366,7 +376,12 @@ private Rope rebalance(ConcatRope rope, int depthThreshold, FlattenNode flattenN
left.isSingleByteOptimizable() && right.isSingleByteOptimizable(),
depth(left, right), isBalanced(left, right));

ropeQueue.add(child);
nextLevelQueue.add(child);
}

if (currentRopeQueue.isEmpty() && !nextLevelQueue.isEmpty()) {
currentRopeQueue = nextLevelQueue;
nextLevelQueue = new ArrayDeque<>();
}
}

0 comments on commit 7020048

Please sign in to comment.