Hi Benson (and others),
Say, when you moved the code from Apache Harmony, did you modify it
along the way, or is it what's found in the Harmony's
source code? I'm asking because we're still hitting those array out of
bounds exceptions sometimes. They are tough to isolate, so I reverted
to white-box code inspection. There is a repeated snippet of code that
just isn't right to me, look here:
comparison = comp.compare(c, partitionIndex);
while (c >= b && comparison >= 0) {
if (comparison == 0) {
if (c == partitionIndex) {
partitionIndex = d;
} else if (d == partitionIndex) {
partitionIndex = c;
}
swap.swap(c, d);
d--;
}
c--;
comparison = comp.compare(c, partitionIndex);
}
doing eager comparison counting is wrong because variable c _can go
below _b_ (which can be the start index or zero). To keep
the invariants correct, the code should read as follows:
int comparison;
while (c >= b && (comparison = comp.compare(c, partitionIndex)) >= 0) {
if (comparison == 0) {
if (c == partitionIndex) {
partitionIndex = d;
} else if (d == partitionIndex) {
partitionIndex = c;
}
swap.swap(c, d);
d--;
}
c--;
}
Note that I did not analyze the whole logic flow of qsort in this
ported code, but just looking at the code above it seems
that c can indeed go beyond the marker limit.
What do you think? A bug or am I just being dim?
Dawid
