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" field:

package Ring;

# return an empty ring structure
sub new {
    my $class = shift;
    my $node  = { };
    $node->{NEXT} = $node->{PREV} = $node;
    my $self  = { DUMMY => $node, COUNT => 0 };
    bless $self, $class;
    return $self;
}

It's the nodes contained in the ring that are circular, not the returned ring object itself. That means code like the following won't cause a memory leak:

use Ring;

$COUNT = 1000;
for (1 .. 20) { 
    my $r = Ring->
new()
;
    for ($i = 0; $i < $COUNT; $i++) { $r->insert($i) } 
}

Even though we create twenty rings of a thousand nodes each, each ring is thrown away before a new one is created. The user of the class need do no more to free the ring's memory than they would to free a string's memory. That is, this all happens automatically, just as it's supposed to.

However, the implementer of the class does have to have a destructor for the ring, one that will manually delete the nodes:

# when a Ring is destroyed, destroy the ring structure it contains 
sub DESTROY {
    my $ring = shift;
    my $node;
    for ( $node  =  $ring->{DUMMY}->{NEXT};
          $node !=  $ring->{DUMMY}; 
          $node  =  $node->{NEXT} )
    {
             $ring->delete_node($node);
    } 
    $node->{PREV} = $node->{NEXT} = undef;
} 

# delete a node from the ring structure
sub delete_node {
    my ($ring, $node) = @_;
    $node->{PREV}->{NEXT} = $node->{NEXT};
    $node->{NEXT}->{PREV} = $node->{PREV};
    --$ring->{COUNT};
} 

Here are a few other methods you might like in your ring class. Notice how the real work lies within the circularity hidden inside the object:

# $node = $ring->search( $value ) : find $value in the ring
# structure in $node
sub search {
    my ($ring, $value) = @_;
    my $node = $ring->{DUMMY}->{NEXT};
    while ($node != $ring->{DUMMY} && $node->{VALUE} != $value) {
          $node = $node->{NEXT};
    }
    return $node;
} 

# $ring->insert( $value ) : insert $value into the ring structure
sub insert_value {
    my ($ring, $value) = @_;
    my $node = { VALUE => $value };
    $node->{NEXT} = $ring->{DUMMY}->{NEXT};
    $ring->{DUMMY}->{NEXT}->{PREV} = $node;
    $ring->{DUMMY}->{NEXT} = $node;
    $node->{PREV} = $ring->{DUMMY};
    ++$ring->{COUNT};
} 

# $ring->delete_value( $value ) : delete a node from the ring
# structure by value
sub delete_value {
    my ($ring, $value) = @_;
    my $node = $ring->search($value);
    return if $node == $ring->{DUMMY};
    $ring->delete_node($node);
}





1;

Here's one for your fortune file: Perl's garbage collector abhors a naked circularity.

See Also

The algorithms in this recipe derive in part from pages 206-207 of the wonderful textbook, Introduction to Algorithms , by Cormen, Leiserson, and Rivest (MIT Press/McGraw-Hill, 1990); see also the section "A Note on Garbage Collection" in Chapter 5 of Programming Perl and in perlobj (1)