A very efficient way to detect loops in a chain is to compare each element
chain[i] with chain[j], where j is the largest power of 2 less than i.
E.g.
void
traverse_linked_list(struct linked_list *p)
{
struct linked_list *bookmark = NULL;
unsigned counter = 0;
while (p && p != bookmark) {
process_node(p);
counter++;
if (!(counter & (counter-1)) /* Is counter a power of 2? */
bookmark = p;
p = p->next;
}
if (p) {
/* We have processed part of the chain twice, but
* at least we can escape the loop.
*/
printk("Bad chain, aborting traversal.");
}
}
Hacking this into kernel code is left as an exercise for the reader...
-- -Colin- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu