Loop-detection in assoc_find..

[Miguel DeAvila]

On Thursday 24 April 2008 14:21:19 Trond Norbye wrote:
> 
> On Apr 24, 2008, at 2:01 PM, Miguel DeAvila wrote:
> >
> > Geez .. am I missing something? Seems like the lookahead pointer  
> > will only
> > equal the 'it' pointer  when
> >
> > lookahead->h_next->h_next == it
> >
> > Imagine list
> >
> > 	A->B->C->A
> >
> > Starting at A,
> >
> > it points to A
> > lookahead points to C
> > lookahead != it
> >
> > advance it
> >
> > it points to B
> > lookahead points to A
> > lookahead != it
> >
> > advance it
> >
> > it points to C
> > lookahead points to B
> > lookahead != it
> >
> > now we're back at the beginning of the loop.
> >
> > Did I miss something?
> >
> 
> Yes.. you stopped too soon ;-)
> 
> advance it..
> 
> it points to A
> lookhead points to A
> lookahead == it
> ...
> 
> It will eventually detect a loop, but it may not be the first time ;-)

Ah yes .. my mistake. Since the lookahead pointer is advanced twice for every advance of
the 'it' pointer it will eventually wrap around and "catch up" with it.

Thanks for the pointer ...

Miguel