Bill Sommerfeld's Weblog

Wednesday January 26, 2005

Another production use of the infamous circularity detector.. Bryan asks:

    "Is this the only use of this infamous technique in shipping production code?"

Nope.

It took me less than a minute to find a place where the same technique was used in GNU Emacs, in src/print.c:print_object(), in the C implementation of the LISP s-expression printing code.   In LISP systems, the s-expression printer gets used from debuggers and the like; as with dtrace, it's generally bad form to get stuck chasing your tail printing out a broken data structure, so this hack is used a fair bit..

The emacs implementation is slightly different; instead of moving the scout out ahead, it instead has a "halftail" pointer lagging behind, moving at half the speed of the main pointer.  Actually, in the dtrace code in question, the half-tail approach might be slightly more efficient in the normal case where the data
structures aren't circular and the thing you're looking for is usually in the list.

(2005-01-25 21:09:04.0) Permalink