> Gregory Colvin wrote:
[snip]
>> There are a few attempts laying around various places in Boost, but >> I've lost track of where they all are, how they all work, and what >> their relative advantages and disadvantages are. If someone could >> pull this information together it might help to get this discussion >> out of the cycle it seems caught in ;->
[snip]
> Very briefly, here's what I've found so far -- please tear it apart at > will: > [snip] > > 4. shared_cyclic_ptr - by Larry Evans. See > http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr. > This one seems to be under active development right (new > version uploaded a day or two ago). Again, I haven't studied > this one yet. About the "discovery" problem, Larry writes: > "[it] works around this by using a smart ptr enumerator > function specialized for each type of container". As I > understand this, it means that shared_cyclic_ptr objects > must either be within objects owned by another shared_cyclic_ptr > (as with sp_collector), or they can be in "tagged" STL > containers, e.g.: > > template <typename T> struct SpecialList : public list<T>, > public SpecialTag { }; > > That would be a best case. Or, it might be necessary to do > something much messier, like this: > > template <typename T> struct SpecialList { > // Implement wrapper for each std::list function... > private: > list<T> list_; > }; > > Perhaps Larry can comment.
As illustrated in:
shared_cyclic_ptr.zip (boost/shared_cyclic_ptr/shared_cyclic_ptr.hpp) in class:
scoped_cyclic_container < Container , Element , cyclic_count_gc<GcMethod,ip_offset_iterator> > , public Container <shared_cyclic_ptr <Element ,cyclic_count_gc<GcMethod,ip_offset_iterator> > > , private detail ::mk_proxiters_descriptor_static ::proxiter_record the scoped_cyclic_container does not include the STL container (the Container), instead it inherits it. This is simply to make the interface the same without having to forward all method calls. The container is "tagged" by inheritance from proxiter_record. However, it's clearer in:
http://groups.yahoo.com/group/boost/files/shared_cyclic_ptr/stl_container.cpp In that file, the function of proxiter_record is done by:
prox_container_allocator<Value> in:
mod::vector <Value ,Allocator=prox_children ::detail_iterators ::prox_container_allocator<Value> >
NOTE:
One reason for this change is to see if the prox_children design pattern (that's what I started calling it) could be adapted for use with stl with as little change as possible. Hence, by just specializing the container allocator, and then changing all container code to use a prox_container_allocator<Value> ::root_pointer in place of the "root pointer" to the container, all containers would be garbage collected. Since, I assumed, each container must have some type of "root pointer" in its implementation, it should work for all stl containers. For uncollected containers, allocator<Value>::root_pointer would simply be a do-nothing pointer-wrapper around a Value*. The ONLY reason for making the root_pointer a pointer-wrapper is to enable storing:
1) a constructor for the "smart ptr enumerator function" mentioned above 2) an offset from whatever "subject" (using the GOF terminology ) contains the container. "WHOA...!" you say, "what is this 'subject"? I thought we were talking about the constructor for an stl-like container?" Well, that's where Detlef's genius appears. This "subject" is actually created during construction of a static variable (so it's constructed before the start of main). The SOLE purpose of this variable,
namespace prox_children { descriptor_builder<Subject> descriptor_builder<Subject> ::this_descriptor ; } is to create a prox_children::prox_descriptor for Subject which precisely describes the smart pointers in Subject which contain pointers to objects to be garbage collected. This description consists of a map of maker_proxiter_abs* to offsets within subject where the proxies are located. Thus, given:
Subject* a_subj offset a_offset mk_proxiter_abs* a_maker the collector can enumerate all the proxies contained in a_subj which are of a particular type, i.e. the type corresponding to the a_maker. For example, for a vector<T>, the corresponding a_maker would produce an iterator somehow derived from vector<T>::iterator, and for list<T>, the a_maker would produce an iterator from list<T>::iterator. For a scalar proxy, prox_scalar_typed<T,ownership_policies>, the iterator simply calculates ((char*)a_subj)+a_offset and casts it to prox_scalar_typed<T,ownership_policies>*. This desription of the iterator for prox_scalar_typed is essentially what Detlef described in his 92 article.
[snip] > > Those are all the relevant cyclic ptr efforts I'm aware of. > > Breaking it down another way: these are the parameters of any cyclic > ptr lib: > > 1. Standard C++ portability > > shared_cyclic_ptr - I imagine so. Yes. > > 2. Discovery method: > > > shared_cyclic_ptr - not sure.
creates a "prox_descriptor" for each different class to be garbage collected. The collector then uses these prox_descriptor's to enumerate the pointers within an object. This means that there must be some way to associate a descriptor with each gc'ed object. This is easy to do if the type of the collector knows the object's type. In that case, the descriptor is prox_children::prox_description_of<T>::ptr() for any type, T. With shared_ptr, the type information is stored within the counted_base* in the derived class, counted_base_impl<T,D> (at least it was at the time shared_cyclic_ptr.zip was written). Hence, shared_ptr could be adapted to find cycles with very little additional overhead.
BTW, the prox_descriptor performs the same function as Boehm's GC_descr:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/boehm-gc/include/gc_typed.h?rev=1.2&content-type=text/x-cvsweb-markup
hence, if Boehm's could be modified to use prox_descriptor instead, the descriptor creation would be almost automatic (you'd still have to declare the static:
descriptor_builder<Subject>::this_descriptor
[snip] > > 3. Efficiency of pointer copying: > > shared_cyclic_ptr - Probably like shared_ptr.
Yes.
> > 4. Restrictions on the location of pointers ("internal" and > "external" -- an internal pointer is one which will be > destroyed when the owning object is destroyed -- generally, > and unless otherwise indicated, there are no restrictions on > where external pointers may be stored): > > Boehm - absolutely none.
If an object to be collected is pointed to from the root, either indirectly or directly, by an object allocated with GC_local_malloc_atomic, then it won't be collected. Of course, this is an error on the programmer's part. For example, he at one time during his development knew the object was atomic, but as his program evolved, it became non-atomic, but he forgot to change it.
I only bring this up to ease comparison with shared_cyclic_ptr.
[snip]
> > shared_cyclic_ptr - probably like juju_ptr, except that the > STL container wrappers may not be "thin" (i.e. e.g. > special iterators may be required).
If there is a pointer path between gc'ed object, A, and another gc'ed object B, and that path is broken with a pointer other than a prox_scalar_void<...> or prox_container_allocator<T>::root_pointer or a pointer in a container whose "root pointer" is a prox_container_allocator<T>::root_pointer, then A or B may not be collected.
This means the programmer must explicitly specify which pointers are used in garbage collection. In constrast, with the Boehm collector (BC), (I think) a default allocator is specified which creates a gc'ed object. If the programmer doesn't want this, he either specifies atomic allocation (meaning the pointee is not to be collected and does not contain the any pointers to collectable objects) or uncollectable allocation (the object is not collected, but may contain pointers to collectable objects):
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/boehm-gc/include/gc.h?rev=1.9&content-type=text/x-cvsweb-markup
The atomic allocation in BC corresponds to a raw pointer in stl_container.cpp. Uncollectable allocation in BC corresponds to prox_scalar_void <proxies ::owner_single >, and the collectable allocation in BC corresponds to prox_scalar_void <proxies ::owner_shared >.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost