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