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

From: Larry Evans (jcampbell3_at_[hidden])
Date: 2003-05-29 09:13:50

Peter Dimov wrote:
> Larry Evans wrote:
> 
>>Chuck Messenger wrote:
>>
>>>The basic idea is to intercept all memory allocations -- p = new X;
>>>-- 
>>>saving the info with "map[p] = sizeof(X);".  To find the
>>>interconnections between objects, you do this:
>>>
>>>    for (map_type::iterator it = map.begin(); it != map.end(); ++it)
>>>        { char *p = it->first;
>>>        unsigned size = it->second;
>>>        for (char *v = p; v + 4 <= p + size; v += 4) {
>>>            char *q = *(reinterpret_cast<char **>(v));
>>>            if (map.count(q)) {
>>>                // connection detected from object p to object q
>>>            }
>>>        }
>>>    }
>>
>>This is similar to Mirek Fidler's code:
>>
> 
> http://groups.google.com/groups?q=OGC2+-+major+improvement+group:comp.lang.c%2B%2B.moderated&hl=en&lr=&ie=UTF-8&group=comp.lang.c%2B%2B.moderated&selm=3DCD36C3.4090502%40nospam_prodigy.net&rnum=1
> 
> If by "similar to" you mean "derived from" or "inspired by" (an euphemism
> for "plagiarized" or "borrowed" which is itself an e. f. "stolen") then no,
> it is not "similar". sp_collector.cpp is written entirely from scratch. It
I very much apologize for the possible implication made by my poor choice
of words.
> is not even derived from or inspired by (no quotes) Greg's cyclic_ptr
> although of course as the implemented algorithm is basically the same there
> are obvious similarities.
> 
> FWIW, it is not similar (no quotes) to Mirek Fidler's code, either. I just
> checked.
By similarity, I was referring to the fact that each allocated object
had it's size stored somewhere (it->second in the above) and that
the memory was scanned in each object to see if it contained
another pointer ( or a word that could be interpreted as pointer. e.g.
in sp_collector this, I believe, the:
   reinterpret_cast<shared_ptr_layout const *>(p)

in scan_and_count).  Fidler also used a similar method to cylic_ptr's
(and Christopher's "global rc mark-scan") to determine roots by
finding all objects pointed to by root pointers (by subtracting the count
due to pointers from the heap).  This is again, similar to sp_collector
as you noted above.  Of course this is again based on an incomplete
understanding of sp_collector.  After a closer look, I didn't notice
any comment about finding roots, as with Fidler's method.  This make quess
that sp_collector avoided actually decrementing the reference counts, as
in Christopher's and cyclic_ptr) and only stored the count's in
a map (the map2_type).  Then, during the heap scan, a check was made to
see if the reference count was == that in the map2_type, and if so, then
the object was garbage (since map2_type contains internal counts).  OK,
now I'm realizing I need to spend more time understanding sp_collector.
Maybe you could clarify.  Maybe Fidler could make any corrections
of my understanding of his code too.

I in no way meant to imply anything negative.  I apologize for any
ambiguity.