Aliasing pointers: using "weakness" to strengthen your code

In one of my earlier articles introducing programming with Boost libraries, I had demonstrated some simple techniques using boost::shared_ptr to share dynamically allocated object instances across scopes, and manage the life cycle of such objects effectively. This was an important step in the direction of eliminating memory leaks. But this was not a complete answer to all forms of memory leaks. This article helps you distinguish between "owning" and "aliasing" semantics for pointers and introduces another class from Boost's smart pointer stable - the boost::weak_ptr. Although not a smart pointer itself, the weak_ptr adds important capability that is vital in handling memory issues and thread safety of objects.

Imagine that you are building a linked list, and you decide to store the "head" node as a shared_ptr<Node> and encapsulate inside this node, the life cycle management of all the nodes in the entire list. That way, when the "head" node goes out of scope, all the other nodes are automatically deleted. How can you do it? Well, the head pointer stores a shared_ptr<Node> pointing to the first node, the first node stores a shared_ptr<Node> pointing to the second node, and so on.

Here is the code, and it works.

#include <iostream>
#include <boost/shared_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

This works remarkably well, and by now your penchant for using shared_ptr and RAII is seeing you write elegant code and wish away memory leaks. And then you are asked to enhance your linked list to a doubly linked list. With a deft, touch you make the necessary changes - and you are up and running again ...

#include <iostream>
#include <boost/shared_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    shared_ptr<Node> prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = head;
    next2->prev = next1;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

... except that you have a memory leak. Believe it or not, what I promised a couple of articles ago was a fib - you can leak memory without even so much as nibbling on a pointer, and in spite of having wrapped all your heap memory in shared_ptr. Run it and you'll not see any of the messages from the destructor of Node. Come to think of it and you'll know the reason.

In the function getList, initially, the nodes head, next1 and next2 each have a reference count of 1 (at line 22, 23 and 24 respectively). Next at line 26, next1 has its ref-count bumped up to 2. In the following line 27, next2 has its ref-count bumped up to 2. So far so good - the real fun starts now. In the next line 28, head has its ref-count bumped to 2, and finally next1 has its ref-count bumped to 3. When this function returns, each of the Smart pointers have their reference counts decreased by 1. But head is copied as a return value - so the decrement nullifies, and when we reach main function at line 35, its reference count remains 2. At this point, the reference count of next1 and next2 are 2 and 1 respectively - but these objects are no longer in scope - completely encapsulated by head. At the end of the main function's scope, the ref-count of head will drop back a notch to 1 - it will not get to 0 - necessary for its internal pointer to get "destructed" and trigger the destruction of its subsequent nodes.

What caused the problem? We only introduced three lines of code - lines 11, 28 and 29 - so the problem would have to be here in these three lines.

Why did all hell break lose? Because, we used the shared_ptr indiscriminately. The shared_ptr implements a "shared ownership" idiom. In this case, head "owns" the next1 node - meaning that before head is completely "destructed", it would have ensured complete "destruction" of next1. But next1 does not own head - it only has an alias to head, in the form of the member prev. But by making it into a shared_ptr<Node>, we have unwittingly made next1 the owner of head. So we hit the chicken-and-egg problem. To reiterate what we just said about ownership semantics - before head is completely "destructed", it should ensure complete "destruction" of next1, and before next1 is completely "destructed", it should ensure complete "destruction" of head. Of course that's an impossible scenario. So we need a different construct for handling the semantics of an aliasing pointer. Here is the code example again with some changes that work reasonably well.

#include <iostream>
#include <boost/shared_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    shared_ptr<Node> *prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = &head;
    next2->prev = &next1;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

At this point of time, you decide to remove the first node of the list head. As part of the process, you must do something like this:

int main() {
    shared_ptr<Node> new_head;
    {
        shared_ptr<Node> head = getList();
        new_head = head->next;
        new_head->prev = 0;
    }

    return 0;
}

The statement at line 6, is crucial because if prev is not set to 0 at this point, an accidental dereferencing of new_head->prev at a later point in the code will bomb. At the end of the scope, at line 7, the head goes out of scope and is "destructed". What if this automatically set the prev member pointing to it to be NULL. Then we could afford to forget to write new_head->prev = 0, without facing any dire consquences.

The boost::weak_ptr is tailor-made for the purpose shown here - it models a "non-owning alias" which is automatically set to a null state when the object it points to is destructed. For this, weak_ptr always works in conjunction with a shared_ptr, and always points to an object via the shared_ptr that owns it. The following example should make all this clear:

#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;
using boost::weak_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    weak_ptr<Node> prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = head;
    next2->prev = next1;

    return head;
}

int main() {
    shared_ptr<Node> head = getList();
    if ( head )
        cout << "Got head" << endl;

    return 0;
}

The weak_ptr maintains a reference to a shared_ptr owning the object. But it does not bump the reference count of a shared_ptr - therefore any number of weak_ptr's can point to a shared_ptr, without affecting its life cycle in anyway. If the shared_ptr goes out of scope and the underlying object is destructed - the weak_ptr's are automatically "updated" about this change through the reference to the shared_ptr that it maintains.

In an informal way, weak_ptr's are to shared_ptr's, what soft links are to hard links on a Unix file system.

You can check the state of the underlying object through the weak_ptr, using the weak_ptr::expired() member function. You can also construct an owning reference - a shared_ptr which contributes to the reference count of the original shared_ptr - through the weak_ptr::lock() member function. This can indirectly be used to check the same condition as weak_ptr::expired() does. To understand that - look at the final example here:

#include <iostream>
#include <boost/shared_ptr.hpp>
#include <boost/weak_ptr.hpp>

using std::cout;
using std::endl;
using boost::shared_ptr;
using boost::weak_ptr;

struct Node {
    int n_;
    shared_ptr<Node> next;
    weak_ptr<Node> prev;

    Node(int n = 0) : n_(n) {
    }

    ~Node() {
        cout << "~Node() invoked for " << n_ << endl;
    }
};

shared_ptr<Node> getList() {
    shared_ptr<Node> head( new Node(0) );
    shared_ptr<Node> next1( new Node(1) );
    shared_ptr<Node> next2( new Node(2) );

    head->next = next1;
    next1->next = next2;
    next1->prev = head;
    next2->prev = next1;

    return head;
}

int main() {
    shared_ptr<Node> new_head;
    weak_ptr<Node> alias;
    {
        shared_ptr<Node> head = getList();
        new_head = head->next;
        alias = head;
    }

    assert(alias.expired());

    alias = new_head;
    shared_ptr<Node> new_head2 = alias.lock();
    assert(new_head2.use_count() == 2); // because new_head and new_head2 share ownership

    return 0;
}

The lock method is particularly crucial when sharing an object across threads. Some threads might only have an aliasing reference to the shared object in the form of a weak_ptr. This can be used to great effect. At any time when such a thread needs to share ownership of this object - it can call lock on the weak_ptr. It will get a non-null shared_ptr only if the object is still valid, and otherwise it will get a null shared_ptr.

Notice that the weak_ptr provides no ways of dereferencing the underlying pointer through it. So there are no overloaded -> or * operators for example. If you need to use these operators - use the lock method to try and get a shared_ptr and then apply these methods on the shared_ptr. In fact - a weak_ptr is not a smart pointer - I call it a "smarter" pointer.