471,855 Members | 1,288 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,855 software developers and data experts.

Copy-on-write tree data structure

[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(Node 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(Node 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

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.moderated - moderation address: cl**@plethora.net
Jul 22 '05 #1
2 3891
[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.

Jul 22 '05 #2
Howard wrote:
[re-posted to comp.lang.c++,
because my stupid newsreader sent it to comp.lang.c,
which I'm not reading!]

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.


Jul 22 '05 #3

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Andreas Kuntzagk | last post: by
15 posts views Thread by A | last post: by
3 posts views Thread by mescaline | last post: by
8 posts views Thread by Joe Cipale | last post: by
14 posts views Thread by trying_to_learn | last post: by
7 posts views Thread by Kelly Mandrake | last post: by
3 posts views Thread by Eric Lilja | last post: by
12 posts views Thread by Mark E. Fenner | last post: by
26 posts views Thread by saxenavaibhav17 | last post: by
10 posts views Thread by campos | last post: by
reply views Thread by NeoPa | last post: by
reply views Thread by aboka | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.