Perl Cookbook

Coping with Circular Data Structures

Problem

You have an inherently self-referential data structure so Perl’s reference-based garbage collection system won’t notice when it’s no longer being used. You want to prevent your program from leaking memory.

Solution

Create a non-circular container object that holds a pointer to the self-referential data structure. Define a DESTROY method for the containing object’s class that manually breaks the self-referential circularities.

Discussion

Many interesting data structures include references back to themselves. This can occur in code as simple as this:

$node->{NEXT} = $node;

As soon as you do that, you’ve created a circularity that will hide the data structure from Perl’s referenced-based garbage collection system. Destructors will eventually be called when your program exits, but you sometimes don’t want to wait that long.

A circular linked list is similarly self-referential. Each node contains a front pointer, a back pointer, and the node’s value. If you implement it with references in Perl, you get a circular set of references and the data structure won’t naturally be garbage collected when there are no external references to its nodes.

Making each node an instance of class Ring doesn’t solve the problem. What you want is for Perl to clean up this structure as it would any other structure—which it will do if you implement your object as a structure that contains a reference to the real circle. That reference will be stored in the "DUMMY" ...