Copy-on-write tree data structure

[Stephan Tobies]

[X-post and follow up]

Hi everyone,

I am looking for a good data structure that could be used to represent
families of trees with shared sub-trees and copy-on-write semantics.

On a very abstract level, I would like to have an API like this:

Let Node be a suitably defined data structure. Then the following
functions shall be supported:

void setNthChild(Nod e root, int n, Node subtree);

// A call to this function should take the tree rooted at root and set
// its nth child to be the tree rooted at subtree.
// Later changes to subtree must not change the tree rooted at root.

Node getNthChild(Nod e root, int n);

// This function shall return the nth child of root (if it exists).
// Later modifications of subtree rooted at the returned node must not
// change the tree rooted at root.

Of course, this could be implemented by creating copies both of the tree
rooted at subtree (for setNthChild) and the tree rooted at the returned
node (for getNthChild), but the costs for this will be prohibitive in my
application.

Hence, I would like to implement this using a suitable copy-on-write
strategy that makes copies of shared subtrees only when a shared subtree
is modifies.

Does anyone know a good data structure that would be suitable to be used
in this scenario?

Thanks in advace!

Best regards

Stephan Tobies
--
comp.lang.c.mod erated - moderation address: clcm@plethora.n et

[Howard]

Re: Copy-on-write tree data structure

[re-posted to comp.lang.c++,
because my stupid newsreader sent it to comp.lang.c,
which I'm not reading!]


That sounds like an awful lot of truble to attempt to save some memory. I
think that you might find that your "cost" may become just as great with any
copy-on-write scheme, especially in complexity and time, but perhaps even in
memory requirements.

Think about how you might accomplish it. Suppose you had some structure
(list?) in which you stored the relationships between all nodes which may
later need to be copied and the trees to which they originally referred.
When you make a change to a node, you will have to copy the entire tree
structure below that node into a whole new tree. But that's not all. You
probably have to copy the whole tree to which that node belongs, since
changing a child node in a tree amounts to changing every node directly up
the tree that contains it, and other items in your list could refer to those
ancestor nodes.

So now you've got multiple copies of entire trees lying around, only some of
which may ever get changed. In the original scheme, you had more copies,
but they would often be of much smaller trees, since they only need to copy
the subtree that gets returned.

Is this homework??? I'm puzzled by your requirements. Have you done any
analysis of why your cost is too high to make copies as needed? And why do
you have to return "immutable" copies? What do you do with them? Do they
ever get disposed, or do they hang around until the app quits?

You asked for a "data structure". Sounds like you need a whole design. Are
you asking for the structure of the items in the list I mentioned? Well,
that really depends on the structure of your nodes, and how you identify
them. (By ID, by pointer address?) I think that if you come up with a
working design, the structure will present itself.


-Howard

[user@domain.invalid]

Re: Copy-on-write tree data structure

Howard wrote:[color=blue]
> [re-posted to comp.lang.c++,
> because my stupid newsreader sent it to comp.lang.c,
> which I'm not reading!]
>[/color]

And it did so for a good reason - it had a Follow-Up to flag set to
comp.lang.c . See in there for my answer to your posting.

BR

Stephan