Reliable Software Logo
 Home  >  C++ Resources  > Resource Management   >  Auto Vector

Strong Pointers and Resource Management in C++

Auto Vector

Standard library's support for Resource Management begins and ends with the auto_ptr. Not even the simplest containers support ownership semantics. You might think that combining auto_ptr with any of the standard containers would do the trick, but it doesn't. For instance, you might try
vector< auto_ptr<Item> > autoVector;

only to find out that you can't index it in a standard way. The construct

Item * item = autoVector [0];

will not compile. On the other hand, this construct

auto_ptr<Item> item = autoVector [0];
will result in the ownership transfer from autoVector to auto_ptr.

Fortunately, it's not that difficult to define a new template, auto_vector, that can both be compatible with the Standard Library and be ownership aware. I wrote a separate article about it.

You might be asking yourself the question; do we have to reimplement every single container from the standard library to make it Resource Management aware? Fortunately, not! It turns out that auto_vector satisfies most of the ownership needs. Once you have all your objects safely tucked in auto_vector, you can use all the rest of the standard containers for rearranging (weak) pointers.

Suppose, for instance, that you want sort a set of dynamically allocated Items. You store pointers to Items in auto_vector. Then you create a standard vector and fill it with (weak) pointers obtained from the auto_vector (use the above iterator). You can then use a standard library algorithm to sort this vector any way you want. (This intermediate vector is often called a permutation vector.) Similarly you can use standard maps, priority queues, heaps, hash tables, etc.

Code Inspection

If you follow strictly the rules of Resource Management, you'll never have problems with resource leaks or double deletions. You will also reduce the chances of accessing stray pointers. Then again, you won't have these problems either, if you just follow the traditional rules of always deleting the pointers allocated using new, never deleting them twice, etc. So what's the big deal?

There is one big difference between the two approaches. It's orders of magnitude easier to find the violations of the rules of Resource Management than it is to find traditional resource bugs. The idea is that the former can be found by simple code inspection or in a single test run, whereas the latter are hidden in rarely executed parts of code and show up only under heavy stress.

Imagine that you were to code review a piece of traditional software for possible memory leaks. First thing, of course, would be to grep for all occurrences of new. For each call to new, you'd have to find out what happens to the pointer to which the result of the allocation was assigned. You'd have to make sure that all possible execution paths lead to the eventual deletion of this pointer. You'd have to check for break statements, returns from the middle of a procedure, and exceptions. The original pointer may be assigned to another pointer, so you'd follow that pointer, too.

Contrast it with the review of a piece of code written according to the rules of Resource Management. Just like in the previous case, you'd start by grepping for new. But this time, you'd only have to inspect the closest vicinity of the call.

  • Is this a direct transfer to a strong pointer?
  • Or, are we inside a constructor of an object? Is the result of the call immediately stored within the object, with no exception prone code following it in the constructor?
  • If so, is there a corresponding delete in the destructor of the object?

Next, you'd grep for all the occurrences of release and perform the same checks.

The difference is between having to review and understand every single path of execution vs. making just a few localized tests. Doesn't it remind you of the difference between unstructured and structured programming? In principle, you could convince yourself of the correctness of a program with gotos. You'd just have to follow all possible branches. In a structured program, on the other hand, your can localize your inspection to structural blocks of code. Locality is the key in both cases.

Failure modes in Resource Management are also easier to debug. The most common bug is trying to access a strong pointer after it had released the ownership of the resource. This causes an immediate fault and is extremely easy to track.

Shared Ownership

Is it always easy to find or designate a single owner for each resource in your program? Surprisingly, yes! And if you're having trouble finding one, you have very likely discovered a design problem in your software. Having said that, there are certain cases when sharing ownership may be the best, or even the only, option.

The responsibilities of sharing are divided between the objects being shared and their clients. A shared resource must keep a reference count of its owners. The owner, on the other hand, must notify the shared object when it releases it. The last owner to release the resource is also responsible of freeing it.

The simplest implementation of sharing is for the shared object to inherit the reference counting behavior from the RefCounted class.

class RefCounted
{
public:
    RefCounted () : _count (1) {}
    int GetRefCount () const { return _count; }
    void IncRefCount () { _count++; }
    int DecRefCount () { return --_count; }
private:
    int _count;
};

In terms of Resource Management, a reference count is a resource. If you acquire it, you should release it, too. Once you realize this fact, the rest is easy. Just follow the first rule of acquisition--acquire the reference count in a constructor, release it in the destructor. There's even an equivalent of a smart pointer for sharing RefCounted objects.

template <class T>
class RefPtr
{
public:
    RefPtr (T * p) : _p (p) {}
    RefPtr (RefPtr<T> & p)
    {
        _p = p._p;
        _p->IncRefCount ();
    }
    ~RefPtr ()
    {
        if (_p->DecRefCount () == 0)
            delete _p;
    }
private:
    T * _p;
};

Notice that class T in this template does not necessarily have to be a descendant of RefCounted, but it must have methods IncRefCount and DecRefCount. Of course, a usable RefPtr should also have the standard overloads of the pointer-access operator. Adding transfer semantics to RefPtr is left as an exercise to the reader.

Ownership Networks

A linked list is an interesting case for Resource Management analysis. If you chose to make the list the principal owner of links, you end up implementing recursive ownership. Every link becomes the owner of its successor, and, transitively, the owner of the rest of the list. Here's the implementation of a link element using a smart pointer.

class Link
{
    // ...
private:
    auto_ptr<Link> _next;
};

It's best to encapsulate link manipulation inside a list class that deals with resource transfers in and out of it.

What about a doubly linked list? The safest approach is to designate one direction, e.g. forward, as the "ownership" direction.

class DoubleLink
{
    // ...
private:
    DoubleLink      *_prev;
    auto_ptr<DoubleLink> _next;
};

You should be careful, though, not to create circular linked lists.

Which brings us to an interesting topic--can Resource Management deal with circular ownership? Indeed, it can, using a version of a mark-and-sweep algorithm. Here's an example of a template class that implements this approach.

template<class T>
class CyclPtr
{
public:
    CyclPtr (T * p)
        :_p (p), _isBeingDeleted (false)
    {}
    ~CyclPtr ()
    {
        _isBeingDeleted = true;
        if (!_p->IsBeingDeleted ())
            delete _p;

    }

    void Set (T * p)
    {
        _p = p;
    }
    bool IsBeingDeleted () const { return _isBeingDeleted; }
private:
    T * _p;
    bool _isBeingDeleted;
};

Notice that we require class T to implement the IsBeingDeleted method, most likely by inheriting it from CyclPtr. Generalization to arbitrary ownership networks is straightforward.


NextNext: An example