📄 ch13_14.htm
字号:
<HTML><HEAD><TITLE>Recipe 13.13. Coping with Circular Data Structures (Perl Cookbook)</TITLE><METANAME="DC.title"CONTENT="Perl Cookbook"><METANAME="DC.creator"CONTENT="Tom Christiansen & Nathan Torkington"><METANAME="DC.publisher"CONTENT="O'Reilly & Associates, Inc."><METANAME="DC.date"CONTENT="1999-07-02T01:42:30Z"><METANAME="DC.type"CONTENT="Text.Monograph"><METANAME="DC.format"CONTENT="text/html"SCHEME="MIME"><METANAME="DC.source"CONTENT="1-56592-243-3"SCHEME="ISBN"><METANAME="DC.language"CONTENT="en-US"><METANAME="generator"CONTENT="Jade 1.1/O'Reilly DocBook 3.0 to HTML 4.0"><LINKREV="made"HREF="mailto:online-books@oreilly.com"TITLE="Online Books Comments"><LINKREL="up"HREF="ch13_01.htm"TITLE="13. Classes, Objects, and Ties"><LINKREL="prev"HREF="ch13_13.htm"TITLE="13.12. Solving the Data Inheritance Problem"><LINKREL="next"HREF="ch13_15.htm"TITLE="13.14. Overloading Operators"></HEAD><BODYBGCOLOR="#FFFFFF"><img alt="Book Home" border="0" src="gifs/smbanner.gif" usemap="#banner-map" /><map name="banner-map"><area shape="rect" coords="1,-2,616,66" href="index.htm" alt="Perl Cookbook"><area shape="rect" coords="629,-11,726,25" href="jobjects/fsearch.htm" alt="Search this book" /></map><div class="navbar"><p><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch13_13.htm"TITLE="13.12. Solving the Data Inheritance Problem"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 13.12. Solving the Data Inheritance Problem"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><B><FONTFACE="ARIEL,HELVETICA,HELV,SANSERIF"SIZE="-1"><ACLASS="chapter"REL="up"HREF="ch13_01.htm"TITLE="13. Classes, Objects, and Ties"></A></FONT></B></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch13_15.htm"TITLE="13.14. Overloading Operators"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 13.14. Overloading Operators"BORDER="0"></A></TD></TR></TABLE></DIV><DIVCLASS="sect1"><H2CLASS="sect1"><ACLASS="title"NAME="ch13-25755">13.13. Coping with Circular Data Structures</A></H2><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch13-pgfId-1607">Problem<ACLASS="indexterm"NAME="ch13-idx-1000004613-0"></A><ACLASS="indexterm"NAME="ch13-idx-1000004613-1"></A><ACLASS="indexterm"NAME="ch13-idx-1000004613-2"></A><ACLASS="indexterm"NAME="ch13-idx-1000004613-3"></A><ACLASS="indexterm"NAME="ch13-idx-1000004613-4"></A><ACLASS="indexterm"NAME="ch13-idx-1000004613-5"></A></A></H3><PCLASS="para"><ACLASS="indexterm"NAME="ch13-idx-1000004644-0"></A><ACLASS="indexterm"NAME="ch13-idx-1000004644-1"></A>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.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch13-pgfId-1613">Solution</A></H3><PCLASS="para">Create a non-circular container object that holds a pointer to the self-referential data structure. Define a <CODECLASS="literal">DESTROY</CODE> method for the containing object's class that manually breaks the self-referential circularities.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch13-pgfId-1619">Discussion</A></H3><PCLASS="para">Many interesting data structures include references back to themselves. This can occur in code as simple as this:</P><PRECLASS="programlisting">$node->{NEXT} = $node;</PRE><PCLASS="para">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.</P><PCLASS="para">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.</P><PCLASS="para">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 <CODECLASS="literal">"DUMMY"</CODE> field:</P><PRECLASS="programlisting">package Ring;# return an empty ring structuresub new { my $class = shift; my $node = { }; $node->{NEXT} = $node->{PREV} = $node; my $self = { DUMMY => $node, COUNT => 0 }; bless $self, $class; return $self;}</PRE><PCLASS="para">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:</P><PRECLASS="programlisting">use Ring;$COUNT = 1000;for (1 .. 20) { my $r = Ring-><CODECLASS="literal">new()</CODE>; for ($i = 0; $i < $COUNT; $i++) { $r->insert($i) } }</PRE><PCLASS="para">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.</P><PCLASS="para">However, the implementer of the class does have to have a destructor for the ring, one that will manually delete the nodes:</P><PRECLASS="programlisting"># 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 structuresub delete_node { my ($ring, $node) = @_; $node->{PREV}->{NEXT} = $node->{NEXT}; $node->{NEXT}->{PREV} = $node->{PREV}; --$ring->{COUNT};} </PRE><PCLASS="para">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:</P><PRECLASS="programlisting"># $node = $ring->search( $value ) : find $value in the ring# structure in $nodesub 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 structuresub 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 valuesub delete_value { my ($ring, $value) = @_; my $node = $ring->search($value); return if $node == $ring->{DUMMY}; $ring->delete_node($node);}<ACLASS="indexterm"NAME="ch13-idx-1000004642-0"></A><ACLASS="indexterm"NAME="ch13-idx-1000004642-1"></A>1;<ACLASS="indexterm"NAME="ch13-idx-1000004634-0"></A><ACLASS="indexterm"NAME="ch13-idx-1000004634-1"></A><ACLASS="indexterm"NAME="ch13-idx-1000004634-2"></A><ACLASS="indexterm"NAME="ch13-idx-1000004634-3"></A><ACLASS="indexterm"NAME="ch13-idx-1000004634-4"></A><ACLASS="indexterm"NAME="ch13-idx-1000004634-5"></A></PRE><PCLASS="para">Here's one for your <EMCLASS="emphasis">fortune</EM> file: Perl's garbage collector abhors a naked circularity.</P></DIV><DIVCLASS="sect2"><H3CLASS="sect2"><ACLASS="title"NAME="ch13-pgfId-1783">See Also</A></H3><PCLASS="para">The algorithms in this recipe derive in part from pages 206-207 of the wonderful textbook, <CITECLASS="citetitle">Introduction to Algorithms</CITE>, by Cormen, Leiserson, and Rivest (MIT Press/McGraw-Hill, 1990); see also the section <ACLASS="olink"HREF="../prog/ch05_03.htm#PERL2-CH-5-SECT-3.9">"A Note on Garbage Collection"</A> in <ACLASS="olink"HREF="../prog/ch05_01.htm">Chapter 5</A> of <ACLASS="citetitle"HREF="../prog/index.htm"TITLE="Programming Perl"><CITECLASS="citetitle">Programming Perl</CITE></A> and in <ICLASS="filename">perlobj </I>(1)</P></DIV></DIV><DIVCLASS="htmlnav"><P></P><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><TABLEWIDTH="684"BORDER="0"CELLSPACING="0"CELLPADDING="0"><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch13_13.htm"TITLE="13.12. Solving the Data Inheritance Problem"><IMGSRC="../gifs/txtpreva.gif"ALT="Previous: 13.12. Solving the Data Inheritance Problem"BORDER="0"></A></TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="book"HREF="index.htm"TITLE="Perl Cookbook"><IMGSRC="../gifs/txthome.gif"ALT="Perl Cookbook"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228"><ACLASS="sect1"HREF="ch13_15.htm"TITLE="13.14. Overloading Operators"><IMGSRC="../gifs/txtnexta.gif"ALT="Next: 13.14. Overloading Operators"BORDER="0"></A></TD></TR><TR><TDALIGN="LEFT"VALIGN="TOP"WIDTH="228">13.12. Solving the Data Inheritance Problem</TD><TDALIGN="CENTER"VALIGN="TOP"WIDTH="228"><ACLASS="index"HREF="index/index.htm"TITLE="Book Index"><IMGSRC="../gifs/index.gif"ALT="Book Index"BORDER="0"></A></TD><TDALIGN="RIGHT"VALIGN="TOP"WIDTH="228">13.14. Overloading Operators</TD></TR></TABLE><HRALIGN="LEFT"WIDTH="684"TITLE="footer"><FONTSIZE="-1"></DIV<!-- LIBRARY NAV BAR --> <img src="../gifs/smnavbar.gif" usemap="#library-map" border="0" alt="Library Navigation Links"><p> <a href="copyrght.htm">Copyright © 2002</a> O'Reilly & Associates. All rights reserved.</font> </p> <map name="library-map"> <area shape="rect" coords="1,0,85,94" href="../index.htm"><area shape="rect" coords="86,1,178,103" href="../lwp/index.htm"><area shape="rect" coords="180,0,265,103" href="../lperl/index.htm"><area shape="rect" coords="267,0,353,105" href="../perlnut/index.htm"><area shape="rect" coords="354,1,446,115" href="../prog/index.htm"><area shape="rect" coords="448,0,526,132" href="../tk/index.htm"><area shape="rect" coords="528,1,615,119" href="../cookbook/index.htm"><area shape="rect" coords="617,0,690,135" href="../pxml/index.htm"></map> </BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -