Matt Calabrese wrote:
On 4/10/07, Ariane van der Steldt <ariane@stack.nl> 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 ---