This looks like a bug, it's a different pattern everywhere else. See my patch.
D.
On Mon, Jan 25, 2010 at 4:16 PM, Benson Margulies <bimargul...@gmail.com> wrote:
> Well,
>
> I deleted my Harmony tree, I'll refetch it tonight and check.
>
> --benson
>
>
> On Mon, Jan 25, 2010 at 8:26 AM, Dawid Weiss <dawid.we...@gmail.com> wrote:
>> 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
>>
>
