5resource.html

Visual C++ has been one of most effective tool for the large industrial applications. This book is t

{
    _scanner.Accept();
    Node * pRight = Term ();
    pMultiNode->AddChild (pRight, (token == tPlus));
    token = _scanner.Token();
} while (token == tPlus || token == tMinus);</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>The call to <var>Term</var> returns a node pointer that is temporarily stored in <var>pRight</var>. Then the <var>MultiNode's</var> method <var>AddChild</var> is called, and we know very well that it might try to resize its array of children. If the reallocation fails and an exception is thrown, the tree pointed to by <var>pRight</var> will never be deallocated. We have a memory leak.

<P>Before I show you the systematic solution to this problem, let's try the obvious thing. Since our problem stems from the presence of a naked pointer, let's create a special purpose class to encapsulate it. This class should acquire the node in its constructor and release it in the destructor. In addition to that, we would like objects of this class to behave like regular pointers. Here's how we can do it.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class NodePtr
{
public:
    NodePtr (Node * pNode) : _p (pNode) {}
    ~NodePtr () { delete _p; }
    Node * operator--&gt;() const { return _p; }
    Node & operator * () const { return _p; }
private:
    Node * _p;
};</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Such objects are called safe or smart pointers. The pointer-like behavior is implemented by overloading the pointer-access and pointer-dereference operators. This clever device makes an object behave like a pointer. In particular, one can call all the public methods (and access all public data members, if there were any) of <var>Node</var> by "dereferencing" an object of the type <var>NodePtr</var>.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>{
    Node * pNode = Expr ();
    NodePtr pSmartNode (pNode);
    double x = pSmartNode-&gt;Calc (); // pointer-like behavior
    ...
    // Automatic destruction of pSmartNode.
    // pNode is deleted by its destructor.
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<P>Of course, a smart pointer by itself will not solve our problems in the parser. After all we don't want the nodes created by calling <var>Term</var> or <var>Factor</var> to be automatically destroyed upon normal exit from the scope. We want to be able to build them into the parse tree whose lifetime extends well beyond the local scope of these methods. To do that we will have to relax our First Rule of Acquisition .

<h3>Ownership Transfer: First Attempt</h3>

<p>When the lifetime of a given resource can be mapped into the lifetime of some scope, we encapsulate this resource in a smart pointer and we're done. When this can't be done, we have to pass the resource between scopes. There are two possible directions for such transfer: up and down. A resource may be passed up from a procedure to the caller (returned), or it can be passed down from a caller to the procedure (as an argument). We assume that before being passed, the resource is owned by some type of owner object (e.g., a smart pointer).

<p>Passing a resource down to a procedure is relatively easy. We can simply pass a reference to the owner object (a smart pointer, in our case) and let the procedure acquire the ownership from it. We'll add a special method, <var>Release</var>, to our smart pointer to release the ownership of the resource.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>Node * NodePtr::Release ()
{
    Node * tmp = _p;
    _p = 0;
    return tmp;
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>The important thing about <var>Release</var> is that it zeroes the internal pointer, so that the destructor of <var>NodePtr</var> will not delete the object (<var>delete</var> always checks for a null pointer and returns immediately). After the call to <var>Release</var> the smart pointer no longer owns the resource. So who owns it? Whoever called it better provide a new owner!

<p>This is how we can apply this method in our program. Here, the node resource is passed from the <var>Parser</var>'s method <var>Expr</var> down to the <var>MultiNode</var>'s method <var>AddChild</var>.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>do
{
    _scanner.Accept();
    NodePtr pRight (Term ());
    pMultiNode-&gt;AddChild (pRight, (token == tPlus));
    token = _scanner.Token();
} while (token == tPlus || token == tMinus);</pre>
    </td></tr>
</table>
<!-- End Code -->
<p><var>AddChild</var> acquires the ownership of the node by calling the <var>Release</var> method and passes it immediately to the vector <var>_aChild</var> (if you see a problem here, read on, we'll tackle it later). 

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>void MultiNode::AddChild (NodePtr & pNode, bool isPositive)
{
    _aChild.push_back (pNode.Release ());
    _aIsPositive.push_back (isPositive);
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Passing a resource up is a little trickier. Technically, there's no problem. We just have to call <var>Release</var> to acquire the resource from the owner and then return it back. For instance, here's how we can return a node from <var>Parser::Expr</var>.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>Node * Parser::Expr ()
{
    // Parse a term
    NodePtr pNode (Term ());
    ...
    return pNode.Release ();
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>What makes it tricky is that now the caller of <var>Expr</var> has a naked pointer. Of course, if the caller is smart, he or she will immediately find a new owner for this pointer--presumably a smart pointer--just like we did a moment ago with the result of <var>Term</var>. But it's one thing to expect everybody to take special care of the naked pointers returned by <var>new</var> and <var>Release</var>, and quite a different story to expect the same level of vigilance with every procedure that happens to return a pointer. Especially that it's not immediately obvious which ones are returning strong pointers that are supposed to be deleted, and which return weak pointers that must not be deleted.

<p>Of course, you may chose to study the code of every procedure you call and find out what's expected from you. You might hope that a procedure that transfer ownership will be appropriately commented in its header file. Or you might rely on some special naming convention--for instance start the names of all resource-returning procedures with the prefix "Query" (been there!).

<p>Fortunately, you don't have to do any of these horrible things. There is a better way. Read on!

<p class=summary>To summarize, even though there are some big holes in our methodology, we have accomplished no mean feat. We have encapsulated all the resources following the First Rule of 
Acquisition. This will guarantee automatic cleanup in the face of exceptions. We have a crude method of transfering resources up and down between owners.

<h3>Ownership Transfer: Second Attempt</h3>

<p>So far our attempt at resource transfer through procedure boundaries have been to release the resource from its owner, pass it in its "naked" form and then immediately encapsulate it again. The obvious danger is that, although the passing happens within a few nanosecond in a running program, the code that accepts the resource may be written months or even years after the code that releases it. The two sides of the procedure barrier don't necessarily talk to each other.

<p>But who says that we have to "undress" the resource for the duration of the transfer? Can't we pass it together with its encapsulator? The short answer is a resounding yes! The longer answer is necessary in order to explain why it wouldn't work without some unorthodox thinking.


<p>First of all, if we were to pass a smart pointer "as is" from a procedure to the caller, we'd end up with a dangling pointer.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>NodePtr Parser::Expr ()
{
    // Parse a term
    NodePtr pNode = Term (); // &lt;- assignment
    ...
    return pNode; // &lt- by value
}

NodePtr Parser::Term ()
{
    NodePtr pNode = Factor (); // &lt;- assignment
    ...
    return pNode; // &lt- by value
}</pre>
    </td></tr>
</table>
<!-- End Code -->


<p>Here's why: Remember how objects are returned from procedures? First, a copy constructor is called to construct a temporary, then the assignment operator is called to copy this temporary into the caller's variable. If an object doesn't define its own copy constructor (or assignment operator), one will be provided for it by the compiler. The default copy constructor/assignment makes a shallow copy of the object. It means that default copying of a smart pointer doesn't copy the object it points to. That's fine, we don't want a copy of our resource. We end up, however, with two smart pointers pointing to the same resource. That's bad in itself. To make things even worse, one of them is going out of scope--the smart pointer defined inside the procedure. It will delete the object it points to, not realizing that its clone brother has a pointer to it, too. We've returned a smart pointer, all right, but it points to a deleted object.

<p>What we need is to enforce the rule that there may only be one owner of a given resource at a time. If somebody tries to clone a smart pointer, we have to steal the resource from the original owner. To  that end we need to define our own copy constructor and assignment operator.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>NodePtr::NodePtr (NodePtr &amp; pSource)
    : _p (pSource.Release ())
{}

NodePtr & NodePtr::operator= (NodePtr &amp pSource)
{
    if (_p != pSource._p)
    {
        delete _p;
        _p = pSource.Release ();
    }
}</pre>
    </td></tr>
</table>
<!-- End Code -->

<p>Notice that these are not your usual copy constructor and assignment operator. For one, they don't take <var>const</var> references to their source objects. They can't, because they modify them. And modify they do, drastically, by zeroing out their contents. We can't really call it "copy semantics," we call it "transfer semantics." We provide a class with transfer semantics when we give it a "transfer constructor" and overload its assigment operator such that each of these operations takes away the ownership of a resource from its argument.

<p>It's time to generalize our accomplishments. We need a template class that is a smart pointer with transfer semantics. We can actually find it in the standard library, in the header <span class="file">&lt;memory&gt;</span>, under the name <var>auto_ptr</var>. Instead of <var>NodePtr</var>, we'll start using <var>std::auto_ptr&lt;Node&gt;</var> whenever node ownership is concerned.

<p>
<!-- Sidebar -->
<table width="100%" border=0 cellpadding=5><tr>
<td width=10>&nbsp;</td>
<td bgcolor="#cccccc" class=sidebar>
The standards committee strugled with the definition of <var>auto_ptr</var> almost till the last moment. Don't be surprised then if your compiler's library contains an older version of this template. For instance, you might discover that your <var>auto_ptr</var> contains an ownership flag besides the pointer. Such implementation is now obsolete.
</td></table>
<!-- End Sidebar -->


<p>Let's begin with <var>UMinusNode</var>, which has to accept the ownership of its child node in the constructor. The child node is passed, of course, in an <var>auto_ptr</var>. We could retrieve it from the <var>auto_ptr</var> by calling its <var>release</var> method. We could then store the pointer and delete it in the destructor of <var>UminusNode</var>--all in the spirit of Resource Management. But there's a better way! We can embed an <var>auto_ptr</var> inside <var>UminusNode</var> and let <i>it</i> deal with  ownership chores.
<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class UMinusNode: public Node
{
public:
    UMinusNode (auto_ptr&lt;Node&gt; &amp; pNode)
        : _pNode (pNode) // &lt;- "transfer" constructor
    {}
    double Calc () const;
private:
    auto_ptr&lt;Node&gt; _pNode;
};</pre>
    </td></tr>
</table>
<!-- End Code -->
<p>Look what happened--there no longer is a need for <var>UMinusNode</var> to have a destructor, because embeddings are destroyed automatically. We don't have to call <var>release</var> on the argument to the constructor, because we can pass it directly to the "transfer" constructor of our embedded <var>auto_ptr</var>. Internally, the implementation of <var>UMinusNode::Calc</var> remains unchanged, because the syntax for accessing a pointer and an <var>auto_ptr</var> is identical.

<p>We can immediately do the same conversion with <var>FunNode</var>, <var>BinNode</var> and <var>AssignNode</var>. <var>BinNode</var> contains two <var>auto_ptr</var>s.

<!-- Code -->
<table width="100%" cellspacing=10><tr>
    <td class=codeTable>
<pre>class BinNode: public Node
{
public:
    BinNode (auto_ptr&lt;Node&gt; &amp; pLeft, auto_ptr&lt;Node&gt; &amp; pRight)
        : _pLeft (pLeft), _pRight (pRight)
    {}
protected: 
    auto_ptr&lt;Node&gt; _pLeft;
    auto_ptr&lt;Node&gt; _pRight;
};

class AssignNode : public BinNode