I agree, based on my memory of thrashing around on this.
On Mon, Jan 25, 2010 at 10:21 AM, Dawid Weiss <dawid.we...@gmail.com> wrote:
> 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
>>>
>>
>
