Jump to content

  • Log In with Google      Sign In   
  • Create Account

We need your feedback on a survey! Each completed response supports our community and gives you a chance to win a $25 Amazon gift card!


how to delete two objects that are circularly linked


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
13 replies to this topic

#1 sobeit   Members   -  Reputation: 440

Like
0Likes
Like

Posted 08 January 2014 - 01:35 AM

Hi there, recently I encounter a problem about circularly linked objects. Following are two classes declared in my small engine. Node is basically a hierarchical representation of transformation, and Entity is object in the game scene. Every Entity must have a node, each node can have several child nodes. What I want to do is deleting either of  entity or node will delete both of them, and also deleting a node will somehow notify its parent. Could anyone help with this? or is there a better structure to organize relationship between hierarchical transformation and game object? Thanks in advance.

Class Entity
{
   ~Entity()
   {}

   Node *m_node;
}

Class Node
{
   ~Node()
   {}
   Node *m_parent;
   vector<Node *> m_children;
   Entity *m_entity;
}


Sponsor:

#2 haegarr   Crossbones+   -  Reputation: 4604

Like
0Likes
Like

Posted 08 January 2014 - 01:53 AM

1.) Don't use the delete operator. Make the d'tor protected and provide and explicit destruction:

// deletes any dependents
void Node::destruct();

Notice that this way includes the invoked element to know about destruction automatically.

 

The routine can also be written to delete the own object as last task if you want to.

 

2.) Deleting the full hierarchy regardless at which point you tackle is IMHO not good. If the whole hierarchy is ever the target, then make the top element destructible and all child elements allow to get a pointer to the top element. E.g. one of

myNode->entity()->destructAll();

IMHO:

* A Node should be destructible but not deletable with the exception of friend classes;

* destruction should be strictly top done and only for child nodes;

* the Entity could be deletable.


Edited by haegarr, 08 January 2014 - 01:57 AM.


#3 sobeit   Members   -  Reputation: 440

Like
0Likes
Like

Posted 08 January 2014 - 02:46 AM

Thank you for your reply but I'm not sure what you mean by destructible. If I destruct a node, I delete whatever m_entity points to and set m_parent and m_entity to null, is this what you mean?



#4 taz0010   Members   -  Reputation: 277

Like
0Likes
Like

Posted 08 January 2014 - 03:29 AM

Are the references actually circular or are you just talking about a node which may belong to multiple entities? To handle the latter you can use a std::shared_ptr wrapper for your node objects. It will automatically count the number of references to the node and call the delete operator when the object containing the last reference is deleted.

 

Dealing with circular references is much harder. Some approaches are to use weak pointers (std::weak_ptr) to allow an object to know about another without having ownership (i.e. holding the weak reference will not prevent the object from being deleted). If you can't design the solution in this way, there are more elaborate methods where you scan your objects, detect the circular reference and delete objects which are unreachable in the graph. But it's normally much simpler to just not use (strong) circular references at all.



#5 haegarr   Crossbones+   -  Reputation: 4604

Like
2Likes
Like

Posted 08 January 2014 - 03:33 AM

Thank you for your reply but I'm not sure what you mean by destructible. If I destruct a node, I delete whatever m_entity points to and set m_parent and m_entity to null, is this what you mean?

 

Something like:

class Node {

friend class Entity;

protected: // <<< Node is protected from being deleted or destructed if not called from either Node or Entity

    ~Node();

    void destruct();
};

Node::~Node() {
    destruct();
}

void Node::destruct() {
    // iterating m_children and deleting them here
}


class Entity {

public: // <<< at top level things are public

    ~Entity();

    void destruct();

};

Entity::~Entity() {
    destruct();
}

void Entity::destruct() {
     delete m_node;
}

Edited by haegarr, 08 January 2014 - 03:36 AM.


#6 Katie   Members   -  Reputation: 1376

Like
0Likes
Like

Posted 08 January 2014 - 04:23 AM

When a parent is deleting a child, the first thing it does is set the child's parent pointer to null (ie; it detaches it from the tree) and then it deletes it. That breaks the cycle. The parent doesn't need to be told the node is going away, because it already knows -- it's doing it.

 

Now the child's destructor can say "if (parent) parent->i_am_being_deleted(this);" so if someone else deletes it, the parent can remove it from the child list.



#7 JohnnyCode   Members   -  Reputation: 339

Like
0Likes
Like

Posted 18 January 2014 - 01:43 AM

I am not quite sure what you mean by circular referencing in your very case. You have only parent and childs pointers in your node class. Do you mean a child can be parent of its parent?

In this case of referencing, when you delete a node that has childs, and you wish to delete whole subtree, you do not do it tree way, but a graph way. Tree is a certain typpe of graph, and circular dependency does not exist in trees. Consider graph A-B-C-A, and graph A-B-C-B . You are removing node B in case of graph two. That means you will remove node C as well. In case of graph one, you wish to remove node C, which will result in removing node A-B, entire graph.

But! Very important thing to know about not tree graphs is that hierarchy cannot be implemented to them. In your case of hiearchy, meaning you do not wish invalidated pointers access, you would remove the circle the node is part of. COnsider graph

A-B-C-D-E-F-D-A , two circles, removing a circle containing delted node will leave you with nodes that are valid.



#8 sobeit   Members   -  Reputation: 440

Like
0Likes
Like

Posted 18 January 2014 - 02:15 AM


I am not quite sure what you mean by circular referencing in your very case. You have only parent and childs pointers in your node class. Do you mean a child can be parent of its parent?

 

No, but thank you for your time. I mean Entity has pointer to Node, Node also has pointer to Entity. When you call destructor on Entity, it would call Node's destructor, Node's destructor would in turn call Entity's destructor, which is kinda "circular". 



#9 Bregma   Crossbones+   -  Reputation: 5505

Like
0Likes
Like

Posted 18 January 2014 - 07:42 AM


Entity has pointer to Node, Node also has pointer to Entity. When you call destructor on Entity, it would call Node's destructor, Node's destructor would in turn call Entity's destructor, which is kinda "circular".

That just doesn't make much sense to me.  Under what circumstances would the Node ever want to destroy the Entity?  If it's only ever the case you mention, well, the Node should not be destroying the Entity at all.

 

From your example, the Entity owns the Node.  The Entity should delete the Node when the Entity gets destroyed.  The Node does not own the Entity, and needs to do nothing with its Entity pointer when it gets destroyed.  It's just that simple.


Stephen M. Webb
Professional Free Software Developer

#10 samoth   Crossbones+   -  Reputation: 5039

Like
0Likes
Like

Posted 18 January 2014 - 08:12 AM


(1) Node is basically a hierarchical representation of transformation, and Entity is object in the game scene. Every Entity must have a node, each node can have several child nodes.

What I want to do is

(2) deleting either of entity or node will delete both of them, and also

(3) deleting a node will somehow notify its parent.

Circular ownership references are troublesome. It's best to avoid them alltogether.

 

(1) Sounds like Node as such has no right to exist, but several Entity objects may own the same node ---> use a shared_ptr<Node> in Entity. This gives a many-to-one relationship, and when the last Entity having a hold on a Node is destroyed, the now useless Node goes away, too. No need to do anything special.

(2) This is hard, if possible at all, and not easy to do in an easy, clean, unambiguous way. It is however also someting you likely don't need to (or don't want to) do either. Do you really need to delete entities by deleting nodes? Really? If that is so, find all the entities in the node by the back-pointer, remove them from whatever container owns all entities (so they're not double-deleted) and delete them. Don't touch the Node, the shared_ptr will take care of that, once it is not needed any more.

(3) This becomes somewhat obsolete, since there are no entities owning a node left when it's deleted (and otherwise, it is not valid to do so! It would leave orphaned entities around). But if you still want to achieve that, invoke a callback on each entity pointer from  Node's destructor.


Edited by samoth, 18 January 2014 - 08:16 AM.


#11 sobeit   Members   -  Reputation: 440

Like
0Likes
Like

Posted 18 January 2014 - 02:35 PM


Under what circumstances would the Node ever want to destroy the Entity?

Thanks for the reply. I haven't seriously thought about the use case, I just thought it would be convenient. But yes, I probably won't needs this kind of feature.



#12 sobeit   Members   -  Reputation: 440

Like
0Likes
Like

Posted 18 January 2014 - 02:40 PM


use a shared_ptr in Entity. This gives a many-to-one relationship

 

thanks for the reply. using shared_ptr might be a good option for me.



#13 JohnnyCode   Members   -  Reputation: 339

Like
0Likes
Like

Posted 19 January 2014 - 01:03 AM

 

(1) Node is basically a hierarchical representation of transformation, and Entity is object in the game scene. Every Entity must have a node, each node can have several child nodes.

What I want to do is

(2) deleting either of entity or node will delete both of them, and also

(3) deleting a node will somehow notify its parent.

 If this is a design requirement, and you can assure that entity-node is one-to-one relation, meaning an entity has exclusive node, and a node has exclusive entity, then, you could elegantly solve all requirements by inheritance. You can implement inheritance effect in pointer logic and in not deriving languages, just study what inheritance exactly is. With inheritance, if you delete a node, it will properly destroy entity, then node, and free memory that was allocated on the instance containing the node, the same if you delete entity.

 

CEntity* e= new CEntity(const node);

CEntity* e2= new CEntity(const node2);

Cnode* nd=new CNode();

 

delete (CNode*) e; // frees entity and node, calling destructors in correct order

delete nd; // frees only node, since mem manager is aware of how it was allocated



#14 samoth   Crossbones+   -  Reputation: 5039

Like
0Likes
Like

Posted 19 January 2014 - 06:18 AM


If this is a design requirement, and you can assure that entity-node is one-to-one relation, meaning an entity has exclusive node, and a node has exclusive entity

That's not what is required, however. The requirement is each entity has exactly one node, and each node may have several entities.

 

You can implement inheritance effect in pointer logic and in not deriving languages, just study what inheritance exactly is.

[...]
CEntity* e= new CEntity(const node);
[...]
delete (CNode*) e;

If there is no real inheritance, that's deleting the wrong type of object, so it's UB. It won't magically do what is intended either.

 

Although in this example, at least it might not crash, since the destructors are likely trivial. So calling the wrong destructor probably won't do much evil (and the standard allocator knows the size of the allocated block of raw memory). But it's still wrong, and a source of impossible to debug errors in the future (and woe if you overload the allocator, e.g. using C++1y sized operator delete some day in the future).


Edited by samoth, 19 January 2014 - 06:19 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS