Jarrad Waterloo wrote:

I am very interested in such a family of smart pointers as I deeply believe that weak_ptr isn't a real solution to cyclical references as your scenario illustrates. Some questions if you don't mind. Will resources be cleaned up in a deterministic manner ie. When the last master of A or B is deleted on the stack will it immediately cleanup A and B? If that is not the case, is there a gc_cleanup() method that would have to be called in code or in a background thread?

The code I have tries to perform a direct removal. If there are no circular references in the pointer, this is trivial and simply a case of calling the delete operator. In the case that the last reference to class A from the execution thread is erased, but at least one other class still refers to this class A, the cleanup() function is invoked. This function attempts to remove the class if it has indeed become unreachable. The cleanup function is potentially very expensive: o(n^2) though this can be optimized to o(n * log(n)) which is on my todo. Because of the expensiveness, there are ways to control the cleanup() function, by temporary suspending it or choosing a different policy (immediate = run cleanup immediately, thread = run cleanup in separate thread, oom = don't run cleanup unless an out of memory condition occurs via std::new_handler). The cleanup function has many points where it releases locks, to allow other threads to continue creating and modifying references while a cleanup is running. The cleanup() function can be manually called, with a force flag, which forces the cleanup() to happen even if a batch is active. The cleanup() does not run if a cleanup is already active.

Can it handle object graphs of arbitrary/any complexity or does it only work with hierarchies?

The code can handle any complexity, basically the garbage collector traverses the list of references between the objects. At the start of a cleanup, each pointer starts out marked white. Every pointer with a parent that is directly reachable (i.e. has at least one intrusive_ptr pointing to it, has been allocated on the stack or has not ever been reachable before) is marked grey. Then the garbage collector loops through the grey elements one at a time, marks it black and marks any pointers originating from objects pointed to by this pointer grey. It repeats until no more grey marked pointers are available, at which point the white list contains only unreachable pointers. The garbage collector does not allocate any heap memory, apart from memory allocated by an empty std::list class and boost::mutex::scoped_lock, both of which are none as far as I know. Since the garbage collector can't make an educated guess about where to start breaking down a cycle, what it does is make every pointer in the cycle point to null, which brings down the reference_counters on the pointed-to objects to 0, causing them to be deleted. Code using this pointer type may therefore never assume pointers are still valid during their destructor.

Please don't keep me, the boost user community, waiting.

I'll prepare the current code to be uploaded in the vault, so people can have a look at the current implementation (which means I have to change the make (bsd make using openbsd make includes) to a gmake (gnu make) and have to include copyright notices on the code). Currently, the code still lacks (proper) documentation and some code is a bit ad-hoc, so the code is not submission ready. I should be ready in a couple of hours to post the code and will post a reply in this thread when it is up. Ariane

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 ---