Re: [boost] interest poll: smart pointers that handle circular references

From: Ariane van der Steldt (ariane_at_[hidden])
Date: 2007-04-11 00:27:46

Matt Calabrese wrote:
> On 4/10/07, Ariane van der Steldt <ariane_at_[hidden]> wrote:
> 
>>I was wondering if there's interest in a smart pointer, which is able to
>>cope with circular references. I think it would make a nice addition to
>>the smart_ptr classes already in boost.
>>
>>The code I have aims to solve this problem, by using two types of
>>pointers. The execution thread will work with boost::intrusive_ptr
>>(which are allocated on the stack) while classes wishing to point to
>>other classes, will use a new type of pointer (named 'reference') that I
>>designed. This pointer is aware of the owner of the pointer, in addition
>>of the object it points to.
>>
> 
> 
> I might be more interested if I more clearly saw your proposed design and
> solution. Could you provide a brief code example, even if it is just
> pseudo-code, and detail exactly what the user witnesses (I.e. when
> destruction occurs, etc.)? As well, what is the "non-standard"
> initialization you speak of?

Hmm, I admit the "non-standard" initialization is a badly chosen way to 
describe it. What I meant to say is that the reference constructor 
requires a parameter, the owner of the reference: if class A contains a 
reference with name ptr to class B, the constructor of class A needs be 
thus:
A::A() : ptr(*this) { }
which creates a variable ptr pointing to null, which knows its parent is 
*this.
Had I stated this constructor:
A::A(my_class* other) : ptr(*this, other) { }
I would have created a ptr pointing to other.

Had ptr been a boost::shared_ptr, this would have been the two constructors:
A::A() : ptr() { }
A::A(my_class* other) : ptr(other) { }
but then, circular references would not be detected.

I have some actual code from one of my test cases at the end of my post.

Basically, the reference class has been designed to mimic the behaviour 
of shared_ptr. The referenced class is present to handle reference 
counters, reachability and provide a virtual destructor for the garbage 
collector. I'm not really happy that the name differs only one character.

The garbage collector is a form of a mark sweep collector, the 
tri-colour variant to be specific.
The basic algorithm is described on wikipedia:
http://en.wikipedia.org/wiki/Mark_and_sweep#Basic_algorithm
This implementation means that, in a multithreading environment,
other threads can still create and destroy references while the
garbage collector is running.

Here's sample code using the reference system.

--- small_loop.cc ---
#include "small_loop.h"

#include <string>

#include <boost/test/unit_test.hpp>

#include <reference/reference.h>

namespace small_loop
{
        int test_class_count = 0;

        class test_class : public reference::referenced
        {
                public:
                        const std::string id;
                        reference::reference<test_class> next;
        
                        test_class(std::string id) :
                                id(id),
                                /* construct reference owned by *this */
                                next(*this)
                        {
                                ++test_class_count;
                                return;
                        }

                        test_class(std::string id,
                                        const test_class& rhs) :
                                id(id),
                                /* construct reference owned by *this */
                                next(*this)
                        {
                                ++test_class_count;
                                /* assignment */
                                next = rhs.next;
                                return;
                        }

                        ~test_class() throw ()
                        {
                                --test_class_count;
                                return;
                        }
        };

        void test()
        {
                /* Construction of reachable test_class. */
                boost::intrusive_ptr<test_class> test0 =
                        new test_class("#00");
                {
                        /* Construction of reachable test_class. */
                        boost::intrusive_ptr<test_class> test1 =
                                new test_class("#01");
                        /* Construction of reachable test_class. */
                        boost::intrusive_ptr<test_class> test2 =
                                new test_class("#02");

                        BOOST_CHECK_EQUAL(test_class_count, 3);

                        /* test_class->next is a pointer to test_class.
                         * The following lines assign the next pointers
                         * to form a circular list. */
                        test0->next = test1;
                        test1->next = test2;
                        test2->next = test1;
                        /* test1 and test2 go out of scope, triggering
                         * the garbage collector, since they contain a
                         * circular reference.
                         * However, the garbage collector will not erase
                         * any of these 3 instances, since they are
                         * reachable from test0.
                         *
                         * The garbage collector is called twice,
                         * first when test2 goes out of scope and the
                         * second time when test1 goes out of scope. */
                }
                BOOST_CHECK_EQUAL(test_class_count, 3);

                /* The next statement runs the garbage collector,
                 * which will actually remove all 3 created test
                 * instances, since the last pointer to it has
                 * gone out of scope.
                 * If the line 'test2->next = test1' had not been
                 * present, the delete operator would have been
                 * called, instead of the garbage collector,
                 * since there would not be any circular references
                 * present. */
                test0 = 0;
                BOOST_CHECK_EQUAL(test_class_count, 0);
                return;
        }
}
--- end of small_loop.cc ---