[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

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.moderated - moderation address: cl**@plethora.net