Boost logo

Boost :

From: Chuck Messenger (chuckm_at_[hidden])
Date: 2003-05-30 10:56:08


Schoenborn, Oliver wrote:
>>From: Chuck Messenger [mailto:chuckm_at_[hidden]]
>>
>>>>No. A and B are completely symmetrical. They each equally
>>>>"own" the other.
>>>
>>>
>>>Not possible. This has nothing to do with NoPtr or
>>>boost::shared_ptr, it's even true for raw pointers. E.g.
>>>...
>>
>>Just look at my Node example -- you'll see that there is
>>indeed complete symmetry of ownership. There is a cyclic
>>ownership graph -- hence the
>>trouble with traditional smart pointers.
>
>
> ... Strict ownership means that only one object at any
> given time can be the owner. This is pretty straightforward and the raw
> pointer example shows that there is no such thing as cyclic strict ownership
> that works, at least within the above definition of ownership,

Which is why the strict ownership paradigm doesn't work with cyclic
structures. Inherently, in the general case, cyclic structures
*require* garbage collection (or to be more precise, some dynammic
programming cycle-finding algorithm, whether or not you call it "garbage
collection") to harvest stranded cycles of objects.

Yes, as Peter Dimov suggested, you can sort of "game" the problem by
dividing your structures into Vertex and Edge types, allowing for a
classic strict ownership hierarchy. But that just leaves the garbage
collection problem to the programmer.

What I'm trying to develop (or even better, find) is a workable C++
library which supports cyclic structures, handling garbage collection
for you, without resorting to a systemic (and non-portable) approach
like the Boehm collector. I want to build regular-old, C++ standard
libraries upon this cyclic library -- I don't want to require users of
my libraries to use my garbage collection system. It needs to be
perfectly invisible to the user (and ideally, as invisible as possible
to the library writer).

> and the
> common definition of cyclic (i.e. A uses B uses "the A that uses the B",
> where "uses" would be "owns" or "refers to", depending on your case). Not
> even a garbage collector could do it, because the gc is then an owner and
> you end up with shared ownership of A.

On the contrary, garbage collectors work fine with cyclic structures.
Had I been using the Boehm collector, it would have found and freed my
stranded cycle of objects, in the very example code I provided.

     - Chuck Messenger


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk