13.13.1. Problem

13.13.2. 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.

13.13.3. 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 invoked when your program exits, but sometimes you 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 be automatically 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 20 rings of 1,000 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.

13.13.4. See Also