Copy-on-write tree data structure

Collapse
This topic is closed.
X
X
 
  • Time
  • Show
Clear All
new posts
  • Stephan Tobies

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

    #2
    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



    Comment

    • user@domain.invalid

      #3
      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

      Comment

      Working...