473,230 Members | 1,481 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,230 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
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
Jul 22 '05 #1
2 4029
[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

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.

BR

Stephan
Jul 22 '05 #3

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Andreas Kuntzagk | last post by:
Hi, There are three ways to (shallow)copy a list l I'm aware of: >>> l2=list(l) >>> l2=l >>> l2.copy.copy(l) Are there any differences? Are there more (reasonable) ways? I think the first...
15
by: A | last post by:
Hi, A default copy constructor is created for you when you don't specify one yourself. In such case, the default copy constructor will simply do a bitwise copy for primitives (including...
3
by: mescaline | last post by:
//Consider the simple program with inheritance, plain init for A, copy ctr for B #include <iostream> using namespace std; class Base{ public: Base(){cout << "Base, default" << endl;}...
8
by: Joe Cipale | last post by:
I have a class defined as follows: public: char Date; char weight; char Workout; char Event; TDaily* nxt_Daily; I have defined my constructor/copy methods as shown:
14
by: trying_to_learn | last post by:
i am on the chapter on copy construction in C++ in the code (see below), the author says if u pass the object by value as in HowMany h2 = f(h); ....then a bitwise object is created w/o calling...
7
by: Kelly Mandrake | last post by:
I've implemented a class with operator+ overloaded and I also provided my own copy constructor; The problem is my copy constructor is being called twise and I dont understand why. I believe the...
3
by: Eric Lilja | last post by:
Hello! Consider the following complete program (with sample output). There's something wrong with my call to std::copy() in the copy constructor of the Unit class. It fails to copy the list. I...
12
by: Mark E. Fenner | last post by:
Hello all, I have a code where my inner loop looks like: allNew = for params in cases: newObj = copy(initialObject) newObj.modify(params) allNew.append(newObj) return allNew
26
by: saxenavaibhav17 | last post by:
what is Deep Copy, Shallow copy and Bitwise copy, Memberwise copy? and what is the difference between them? pls help vaibhav
10
by: campos | last post by:
"Effective C++ 3rd Edition" Item 6, P39 ------------------------------------------------------- class Uncopyable { protected: // allow construction Uncopyable() {} // and...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE...
0
by: stefan129 | last post by:
Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....
0
by: DolphinDB | last post by:
The formulas of 101 quantitative trading alphas used by WorldQuant were presented in the paper 101 Formulaic Alphas. However, some formulas are complex, leading to challenges in calculation. Take...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: Aftab Ahmad | last post by:
So, I have written a code for a cmd called "Send WhatsApp Message" to open and send WhatsApp messaage. The code is given below. Dim IE As Object Set IE =...

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.