Question on tree-walking and mutually-recursive types

[Michael Matz]

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}


Ciao,
Michael.