Re: [boost] Shared Map

From: François Duranleau (duranlef_at_[hidden])
Date: 2007-08-07 11:37:06

On Tue, 7 Aug 2007, Anthony Williams wrote:

> "Jeremy Bruestle" <jeremy.bruestle_at_[hidden]> writes:
>
>> I've recently implemented a new collection type for a project of mine.
>>  It works identically to std::map, with the same algorithmic
>> guarantees, but additionally can be 'copied' in constant time.
[snip]
>> The trick is simple: the map is a red-black tree, but we get rid of
>> the explicit parent pointer for each red-black node.  This complicates
>> the code, but is algorithmically uninteresting since we always descend
>> from the root anyway and just need to track the parent as we go,
>> either in an explicit stack or through recursion (my current
>> implementation).  The key point however is that the lack of an
>> explicit parent allows us to use reference counting, and share
>> children.  Thus the copy from a to b simply copies the root node, and
>> adds an additional reference count.  All future changes do copy on
>> write for shared nodes (any with a ref count of 2 or more).
>
> How does this work with iterators? On a normal map you can get an iterator to
> an entry and it remains valid until that entry is deleted. Can you do this
> with your shared map? I'm inclined to think that any modification to the map
> would have to result in all iterators being invalidated, as they may now
> potentially refer to the wrong copy of a node.

I also wonder how he implements iterators without a pointer to the parent. 
AFAIK, that is one way to allow stepping from one element to the next (or 
the previous) from any node, with no knowledge of how we accessed that 
node. Without a parent pointer, aside from using threaded trees (which 
would created cycles of shared pointers), I don't know how to do it 
efficiently (keeping a stack inside the iterator would make them costly to 
copy, and would require O(log N) memory).

Another thing, could this shared_map be implemented in terms of 
Boost.Intrusive (IIRC, it has been accepted, though I didn't follow the 
review process very much)?

-- 
François Duranleau
LIGUM, Université de Montréal