I have found loops in lists with this algorithm that has no recursion.
Obj* pa = pStart;
Obj* pb = pStart;
do {
pb = pb->next;
if (pa == pb)
goto loop_detected;
pa = pa->next;
pb = pb->next;
if (pa == pb)
goto loop_detected;
} while (pb != pEnd);
The algorithm is O(n), exactly N when there is no loop.
I recognize that the pa->next operation may be expensive, but a
general algorithm warrants the change.
-- Marc Singer
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu