Perl Cd Bookshelf [Electronic resources] نسخه متنی

13.13. Coping with Circular Data Structures Using Objects

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

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.

Or use weak references, as described in Recipe 11.15.

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.

In Recipe 11.15, we see an alternate
implementation for this same code, one that doesn't involve objects
at all. Because it uses weak references for the data structure's own
references back to itself, Perl's memory management system suffices
to clean up the data structure once it's no longer needed. This
obviates the need for a destructor, and therefore even allows the
data structure to be constructed using simple reference without
recourse to classes or objects.

13.13.4. See Also

The
algorithms in both this recipe and Recipe 11.15 derive in part from Introduction to
Algorithms, by Cormen, Leiserson, and Rivest (MIT
Press/McGraw-Hill); the section on "Garbage Collection, Circular
References, and Weak References" in Chapter 8 of
Programming Perl; the documentation for the
standard Devel::Peek and Scalar::Util modules