Question on tree-walking and mutually-recursive types

[Andreas Schwab]

Michael Matz <matz@suse.de> writes:

> Hi,
>
> On Mon, 28 Jun 2004, Zack Weinberg wrote:
>
>> struct S { struct S *next; };
>> 
>> bool
>> detect_cycle(struct S *list)
>> {
>>     struct S *p, *q;
>>     bool advance_q = false;
>> 
>>     if (list == 0)
>>       return false;
>> 
>>     q = list;
>>     p = list->next;
>> 
>>     do
>>     {
>>         if (q == p)
>>             return true;
>> 
>>         if (advance_q)
>>             q = q->next;
>>         p = p->next;
>>         advance_q = !advance_q;
>>     }
>>     while (p);
>>     return false;
>> }
>
> ???  This tests if list_{2j+1} or list_{2j+2} equals list_j.  Hence it 
> doesn't detect cycles.  Cf list == {1,2,3,1}

It doesn't have to detect it in the first round, but eventually the
pointers will be equal in some other round since they are running at
different speeds through the cycle.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."