LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices


Reply
  Search this Thread
Old 08-30-2006, 05:51 PM   #16
xhi
Senior Member
 
Registered: Mar 2005
Location: USA::Pennsylvania
Distribution: Slackware
Posts: 1,065

Rep: Reputation: 45

that has got to be the most disturbed exaplanation i have ever heard.
 
Old 08-31-2006, 07:27 AM   #17
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by sundialsvcs
Separate from either one of these two interfaces, there's "the destructor," which to my way of thinking should be used only to clean-up this object data-structure; not anything that might be related to it. In other words, if you want to "kill Billy," you might have to call "billy.commit_suicide()," not ~billy().

Finally, it is especially important in destructor-logic to guard against recursion and any stale pointers.
I haven't implemented the destructor in any of the classes; the children are deleted via the auto_ptr that they belong to, which belong to the parent. I think it's a fairly natural interface.

The way I protect against recursion and stale pointers is rejecting addition of a child if it's owned. That way, only one node should be the owner of any given node. Since something can't be destructed if it's owned, the owner won't be left with a stale pointer. If a node has children when it's destructed, those are destructed also, making the need for a reference to a parent dissapear.

The main reason for deleting a whole branch is the fact that they can branch into children AND into peers. i.e.
Code:
X--Y              X--Y              X--Y
|  |                 |              |  |
|  Y                 Y              |  Y
|                                   |
X--Y   remove->   X--Y    (or)->    X (moved up)
|  |              |  |
|  Y--Z           |  Y--Z           X--Y
|  |              |  |                 |
|  Y--Z           |  Y--Z              Y--Z
|                 |                    |
X                 X                    Y--Z
Rather than try to figure out which makes more sense; move an X up and have it adopt the orphan Ys, or promote the orphan Ys to become peers of Xs, I think it's more intuitive that if the X at the top (without an owner) gets destructed, so does everything below it. You can't just go and delete the second X; it's owned by the first. This forces the user to deal with branches as independent units, making them isolate something before destroying it. In your terms, it's comparable to taking it out back behind the barn instead of killing it while it's playing with its siblings.
Quote:
Originally Posted by xhi
that has got to be the most disturbed exaplanation i have ever heard.
I agree, but it's still funny...
ta0kira

Last edited by ta0kira; 08-31-2006 at 07:38 AM.
 
Old 08-31-2006, 09:35 AM   #18
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 115Reputation: 115
I don't see peers in that graph, only parents and children. My two valid options was to either automatically detach from the parent and delete the whole branch, or to just assert "Don't do that. It's not allowed". You are also probably overusing auto_ptr, and actually reimplementing that functionality yourself anyway. auto_ptr prevents two pointers from containing the same value (except 0). One of the main uses of pointers in C++ is that pointers can be shared, but objects are unique.
 
Old 08-31-2006, 11:45 AM   #19
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
I think the best explanation of it is that it's a linked list where the elements can have child elements, who are also linked lists, etc., but you don't have random access. It's like having a bidirectional container; one element is connected to the next, etc. All of the Xs are peers, all of the Ys are peers, etc. It's generally intended for linear meta-sectioned documents, such as source code.

It will all make a lot more sense when I throw together some documentation, which I am working on.
ta0kira
 
Old 08-31-2006, 01:46 PM   #20
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by tuxdev
My two valid options was to either automatically detach from the parent and delete the whole branch, or to just assert "Don't do that. It's not allowed".
I'll think through that first idea; it wouldn't preclude the current behavior of destruction of an ownerless node. I'd still use the Destruct() interface, however, because the whole tree will have to auto-delete itself upon end of scope. I'd really only have to change 1 line of code for your first idea...
ta0kira
 
Old 08-31-2006, 02:11 PM   #21
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 115Reputation: 115
Using a C++ builtin is almost always better than trying to roll your own, simply because it leads to a much more intuitive interface that plays naturally with the rest of C++. The major issue with Destruct() is that it should never fail and it isn't a builtin. If Destruct() ends up returning void, it is no better than delete, and if it doesn't, it isn't simply a one-line difference with no real advantage anyway because it would never fail.

I'm unsure why scope is involved right this very instant...

Last edited by tuxdev; 08-31-2006 at 02:12 PM.
 
Old 08-31-2006, 04:01 PM   #22
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by mhcox
The default node destructor and the boost::shared_ptr will handle most (all?) of the memory management you need.
Sorry; I missed this the first time around. I'm using auto_ptr (to maintain standard C++) much like you show, except they store the first child and the next node, making it like a branching linked list.
Quote:
Originally Posted by tuxdev
The major issue with Destruct() is that it should never fail and it isn't a builtin. If Destruct() ends up returning void, it is no better than delete, and if it doesn't, it isn't simply a one-line difference with no real advantage anyway because it would never fail.

I'm unsure why scope is involved right this very instant...
I'm unsure what you mean by fail. Do you mean it should be a unilateral destruct decision by the user? Delete would work fine for that, but that's the whole point I am making; that's not the behavior I'm looking for. If you mean it shouldn't throw an exception, then it won't any more than delete itself would.

I tossed around your idea to make the node automatically bow out of the tree upon its deletion. At first I thought it would work, but I found that it would make the Destruct() function less stable and less controllable. I think you'd really need to read through the code to understand. I wouldn't expect you to read it at this point, however, as it is still undocumented.

Scope is involved because when the base reaches end of scope it needs to delete the entire tree. If I overrode 'delete' to remove branches upon their deletion it would be stuck disassembling itself when it doesn't need to, introducing more room for things to go wrong. For that reason, I still need an internal 'delete' interface while maintaining an interface for the user to destruct branches logically. 'delete', as an operator, has an implied meaning like all the others; I find giving it some sort of nuance other than incidental cleanup to be more confusing. In any case, the user will need something separate to work with.
ta0kira
 
Old 08-31-2006, 04:13 PM   #23
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 115Reputation: 115
And it all comes back to ownership...

The root node supposedly owns all of the nodes under it(directly or indirectly), right? Therefore, refering to the root node is tantamount to refering to the whole tree. What I'm thinking about says that if you say "delete child", then it needs to tell everybody who cares "Goodbye, I'm not available anymore", and then destroy everything it owns. Essentially, wiping itself and any knowledge that it can be used of itself out of existence. The second option is to simply assert that "delete child" is an illegal operation and do nothing cause it is going to die anyway at some point.

Also, when the root node falls of the stack, it does need to clean up after itself, which includes every node it directly or indirectly owns. Otherwise, it is a memory leak.

Last edited by tuxdev; 08-31-2006 at 04:14 PM.
 
Old 08-31-2006, 06:56 PM   #24
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
Understood. We are talking about nearly the same thing, except for I'd like two separate functions:


tuxdev's way-
'delete' = remove the node from the tree if it's not the base, then delete it and all children.

Delete Node X: 'delete X;', which removes X from its tree and deletes.

Delete Tree X: 'delete X;', which calls 'delete' on each child, cascading down causing recursive disassembly, which is unneeded room for error. See above.


ta0kira's way-
'delete' = delete the node and all of its children. For internal use only.

'Destruct()' = makes sure the node is detached already, then calls 'delete'. See above. If still attached, doesn't do anything. Returns the outcome to the user.

Delete Node X: 'Destruct(X);', which deletes the node if it's a base, otherwise leaves it alone. The user must remove the node first because there are many methods to remove it; can't choose one for them.

Delete Tree X: 'delete X;', which calls 'delete' on each child, cascading down. This doesn't cause recursive disassembly, and is left separate from the user destruct interface.


As we've discussed, the nodes "shouldn't" be created on the stack, therefore ideally should belong to an auto_ptr, etc., on the stack, which will call 'delete' when it goes out of scope (auto_ptr is a friend of the node, so it can do that.) I'd like 'delete' to be the internal interface and 'Destuct()' to be the public interface which wraps around 'delete' with a safety check, whereas you'd like 'delete' to take care of both the user and internal by presuming the corrective action. The user and the lib require two different actions; there's no point in trying to pretend it's one, if for no other reason than it makes the lib less stable.
ta0kira

PS A return value can be safely ignored from my 'Destruct()' function; an 'assert' can't be ignored.

Last edited by ta0kira; 08-31-2006 at 07:14 PM.
 
Old 08-31-2006, 07:18 PM   #25
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 115Reputation: 115
Umm, In pratically every tree implementation I've come across, Node == Tree. The approach that I was thinking about goes along goes along the lines of:

Somebody: Momma, die
Momma: Grandma, I'll be gone for a while (and never comming back)
Grandma: OK... Who are you? (Grandma forgot who Momma is)
Momma: Billy, die
Billy: Bobby, die
<Bobby dies>
<Billy dies>
<Momma dies>

To prevent infinite function calls bouncing up and down, detachment should happen in operator delete(), and the child deletion should happen in the destructor, using ::delete.

Alternatively, it could go like

Somebody: Momma, die
Momma: You can't kill me, you have to kill Grandma and Grandma will kill me

OR

Somebody: Grandma, die
Grandma: Momma, die
Momma: Billy, die
Billy: Bobby, die
<Bobby dies>
<Billy dies>
<Momma dies>
<Grandma dies>

Here, the risk is that the program doesn't know whether or not the deletion actually happened, but it doesn't really matter anyway cause it is going to get cleaned up when the ultimate parent gets deleted. This is also the way to go if deleting a descendent is considered illegal and should not ever happen under normal circumstances.

We definitely are not to be understanding each other

Last edited by tuxdev; 08-31-2006 at 07:23 PM.
 
Old 08-31-2006, 10:21 PM   #26
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
Quote:
Originally Posted by tuxdev
Alternatively, it could go like

Somebody: Momma, die
Momma: You can't kill me, you have to kill Grandma and Grandma will kill me
This is about how it works now...

Quote:
Originally Posted by tuxdev
We definitely are not to be understanding each other
We're getting pretty close to agreeing on what's going on and what should be going on.

I thought about the whole "remove self on delete" again, and decided to put a "just in case" in the base class destructor. The reason I decided on this is that although the destructor is protected, the most derived class will technically be able to be deleted with 'delete'. This is an unsafe work-around to how I intended it to work. The way I see it working now is that instead of the tree "burning" from one end to another, it "falls apart" into its smallest pieces, which then "burn up" individually.

The main problem is that the node removal functions are pure virtual in the base class, and at the point the destructor is called the most derived object isn't entirely intact, making it a call to a pure virtual causing a crash. I'm working that out now. Maybe I'll just move it to the implementation class...
ta0kira
 
Old 08-31-2006, 11:01 PM   #27
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
As luck would have it, destructors (apparently) use the virtual function definition of the current class, ignoring any subsequent overrides. This means that by putting a remove call in the destructor of the implementation class it calls its OWN remove command, regardless of if the user overrode it in their class.

So here's the compromise (well, there isn't really one on my part; the self-removal is a needed fallback):

Self-removal in the delete function of the implementation base class just in case the user does something fairly bizarre. In order for it to be needed, however, they'd have to create a node, give another node ownership of it, then delete it via a pointer to the original class. That would require a static_cast or a pointer to the node stored before it was made a child.

I still keep my 'Destruct()' function. Let's see them try to delete a node without it since the destructor of all returns from child access functions are protected. If they are using some other parallel structure or are dealing with nodes in forms outside of my library, the node will remove itself upon its own deletion. If they access the nodes via the library's access functions, then they are stuck using the 'Destruct()' method. They will need a parallel structure in any case because my tree is only intended for data parsing and data exportation. Thanks for the intelligent discussion!
ta0kira
 
Old 09-01-2006, 12:01 AM   #28
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 115Reputation: 115
Is your destructor virtual? If it is, "this" should be dynamically bound, and therefore other virtual functions should work properly.

Since deleting an owned object is an illegal action in this architecture, and at best really bizarre, you are free to assume that the user won't do that, as long as you have an assert() to code in that assumption. Destruction is something that should never, ever, fail and therefore it is safe to assume that it won't, again if you code that assumption in explicitly with assert(). You don't need to bail out programmers who misuse your library, you are only expected to warn the programmers that they are doing something that they aren't supposed too.

Also, you should tap into as many of the builtin features that C++ has to offer, because not only is that the most intuitive interface, it also allows template code function properly e.g. the STL. Can you create a std::vector of trees the way it is right now?

I guess that sums up my two major points of the whole thread, hopefully in the most understandable way. I should probably go try and code my ideas because using English to explain complicated programming concepts seems quite awful.
 
Old 09-01-2006, 12:47 AM   #29
ta0kira
Senior Member
 
Registered: Sep 2004
Distribution: FreeBSD 9.1, Kubuntu 12.10
Posts: 3,078

Original Poster
Rep: Reputation: Disabled
I've figured out a way to get rid of the 'Destruct()' function. It's hard to explain, but 'delete' now has a dual purpose which I think is intuitive. Basically what it comes down to is this: each node is owned by its previous node. If it doesn't have a previous node, it's owned by its parent. If it doesn't have a parent, it's the base of a tree. If you delete something that's owned, there's going to be something to reference whatever you move up the chain when deleting something; i.e., if you delete a node, the next element moves up into its place. If it's NOT owned, nothing will be able to reference whatever would move up to take it's place; therefore, the entire tree (base + next + children) is deleted. It will make sense once I document it
Code:
Delete a branch which is on a tree:

X--Y              X--Y
|  |              |  |
|  Y              |  Y
|                 |
X--Y   <-delete   X (moved up)
|  |
|  Y--Z           ~--~
|  |                 |
|  Y--Z              ~--~
|                    |
X                    ~--~
Code:
Delete the base of a tree:

X--Y   <-delete   ~--~
|  |              |  |
|  Y              |  ~
|                 |
X--Y              ~--~
|  |              |  |
|  Y--Z           |  ~--~
|  |              |  |
|  Y--Z           |  ~--~
|                 |
X                 ~
BTW, I'd argue against STL being the most intuitive interface. std::vector will not work; in fact I just removed the last trace of the STL from the basic lib because I think it detracts from it.
ta0kira
 
Old 09-01-2006, 11:47 AM   #30
tuxdev
Senior Member
 
Registered: Jul 2005
Distribution: Slackware
Posts: 2,012

Rep: Reputation: 115Reputation: 115
I think that way of doing things makes sense for this not-really-a-tree data structure, with all this conversation mostly applying to the standard n-ary tree drawn the standard way. Deleting a node seems like it is removing a function in a C source file, or removing a case in a switch statement, or even the switch statement itself.

I'd argue that a class that can't be used with the STL is borderline useless, and is probably reinventing the wheel again (of course, there isn't anything wrong with reinventing the wheel if that's what you aiming for).
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off



Similar Threads
Thread Thread Starter Forum Replies Last Post
Bad file problem--can't delete (or anything else) David the H. Linux - General 2 05-12-2006 06:28 AM
remove bad sector form fat? nitin403 Mandriva 1 05-27-2005 03:20 AM
how do I copy a whoel folder form one directory to another form the command line? zwyrbla Linux - Newbie 8 08-24-2004 06:40 PM
delete content form a file bru Programming 1 04-30-2004 07:41 AM
Event driven object-to-object: C++ template class mecanism ( NOT STL or STDC++) bretzeltux Programming 2 12-23-2003 02:45 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

All times are GMT -5. The time now is 02:56 AM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration