Re: [boost] Re: Cyclic smart pointers (holy grail: the uber-pointer)

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2003-05-29 10:25:56

Chuck Messenger wrote:
> 
> Larry Evans wrote:
[snip]
>> Right.  scoped_cyclic_ptr (in shared_cyclic_ptr.zip) works around this by
>> using a smart ptr enumerator
>> function specialized for each type of container.  The specialized 
>> function
>> is then used to access all the smart ptrs in the container (via the 
>> begin() end()
>> iterator class).
> 
> 
> OK, I see.
> 
> In fact, it seems like you don't need any special smart ptr enumerator 
> function.  All you do is: you use derived-from versions of the std 
> containers, so you can maintain an up-to-date list of references to each 
> one.  During GC, for each such container c, "for (it = c.begin(); it != 
> c.end(); ++it)", you treat *it as a Rangeable -- any {C} references in 
> the range [&*it, &*it + sizeof(*it) - 1] are flagged as internal.
Not quite.  The scoped_cyclic_ptr was designed to work-around a limitation
of Detlef's method:
   http://www.cs.kent.ac.uk/people/staff/rej/cgi-bin/searchbib?pattern=Detl92
This limitation was that it didn't document how than handle container
classes.  It only documented how scalars were handled.  The adaptation
in scoped_cyclic_ptr (and stl_container) is, as you mentioned, to store
a pointer and offset into a prox_descriptor (see stl_container.cpp)
for each type which contains a proxy (i.e. smart pointer) or a container
of proxies.  The pointer and offset is stored by the CTOR for either scalar proxies
(prox_scalar_typed<...>) or the prox_indirect_typed forming part of any
container of proxies (e.g. the test::m_vec_ptest_shared).  The pointer points
to an instance of maker_proxiter_abs which produces an iterator over proxies
contained in a subject class (subject is term used for pointee or referent
in GOF) given the start of a subject.  (I know, its too complicated, but
I can't think of how to simplify it.  Any ideas?)
> 
> Nice!
> 
Thanks.
[snip]
> 
> Is stl_container.cpp an experimental Boost lib?  Where can I get it?
It's in:
   http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/stl_container.cpp
You'll also need the col_io library in:
   http://groups.yahoo.com/group/boost/files/col_io/
and then there's a simple trace_scope.hpp which I'll upload.
> I like your "iterate through tagged STL containers" method.  The library 
> writer (the one using the cyclic smart pointer system) has to take care 
> to store {C} objects only in appropriately tagged containers.  But they 
> get to use any containers they want.
> 
> Not too shabby.
Thanks.
> 
> I'd love to examine your scoped_cyclic_ptr lib -- to see if I can make 
> use of it.  Perhaps I can help you flesh out requirements, if it's close 
> enough to what I need.  Is it available for download?
That's at:
   http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/shared_cyclic_ptr.zip
It uses an earlier version of method to enumerate pointers in an object.  It also
demonstrates how to adapt shared_ptr for to use the method.  It also shows
that the enumeration method is pretty much independent of the collection method because
it uses two different methods (one using Detlef's, or offset_iterator method and
one using Colvin's or assign_op_switch) to implement the same gc method (Lin's local
mark-scan).  BTW, Lin's method suffers from quadratic behavior with nested cycles
as pointed out in Bacon's paper (I think I made a reference to that earlier.  I know
I did in a post responding to one of Terekov's posts).  The work-around is
lazy-local mark-scan which maintains a queue of possible garbage nodes.  Anyway,
I had a version of this also, but it's been rm'ed from boost long ago.

See if the current stl_container.cpp can at least traverse your pointer graph correctly.
If it can, then it's easy to use any of the cyclic rc algorithms
(i.e. lazy local mark scan, eager local mark scan, global mark scan).