0

I have this assignment in which I have to define a Tree class which has a nested private Node class.
The problem is that I cannot use neither smart pointers nor std::vector nor copy operator and copy assignment. And all I am allowed to use are raw pointers.
So I wrote the class and tested it with valgrind to check if I have memory leak, and I did. I know that the memory leak may come from Node class because I don't free _children but when I do that, I get a segmentation fault.
I really don't know how to fix this problem.

Thank you in advanced.

  • Check to make sure the things you're `delete` -ing are, in fact, things that were `new` -ed. Passing in addresses of stack variables in `main` is a giant flag that indicates your mixing dynamic and automatic objects, and that usually spells disaster. Also, your usage of &this->_children` is a huge red flag, since the return value of that participates in pointer arithmetic that is going to invoke *undefined behavior* with this: `_info->getChildren()[index] = childTree;` Ouch. – WhozCraig Nov 10 '19 at 10:10
  • @WhozCraig i don't really have another way to not pass the adress for `ins` method. Because the copy constructor must be disabled and by my knowledge, there isn't really another way to do this.... If you know another way to write `ins` method, I would be so thankful. –  Nov 10 '19 at 10:17
  • I can compile and run the code without segfault, also using the deleting destructor. So how can I reproduce the problem? – Tobias Wollgam Nov 10 '19 at 10:28
  • @TobiasWollgam simply in Node class, you remove the default destructor and replace it with `~Node() {delete [] _children;}` –  Nov 10 '19 at 10:35
  • That was what I mean with deleting destructor. Runs without segfault. So are you sure that the code you give us has still the problem? – Tobias Wollgam Nov 10 '19 at 10:40
  • @TobiasWollgam yes I am sure. I just tested one more times and I get the segmentation fault –  Nov 10 '19 at 10:44
  • Which compiler? I tried gcc-9.2 and clang 9, both works. – Tobias Wollgam Nov 10 '19 at 10:51
  • @TobiasWollgam me too. I can send you the code if you want –  Nov 10 '19 at 11:08

2 Answers2

0

well it is not the cleanes code with lots of ways for memory to leak. Here is one I think you are getting issues with:

Tree() : _info(nullptr) {} 
...
~Tree() {
    delete _info;
  }

But of course, there are more places where things can go wrong:

Tree& operator= (Tree&& t) // check _info not null before calling delete _info

In words- your class Tree has two constructors. One that accepts a value of type T: Tree(T data). This constuctor does create a new node. This is the constructor you use to create a Tree in your main() function.

There is another constructor you have: a default one. This is the constructor that is called when you create child nodes from a class Node: _children = new Tree<T,N>[N];

This default constuctor of Tree() : _info(nullptr) does not create a new _info node.

When the program is finished and destructors are called - there is an attempt to delete nullptr.

Simple fix is to change Tree destructor:

~Tree() {
    if (_info) delete _info;
  }

You Node::_children is an array of Trees yet, when you call getChildren you return an array of pointers. So call to ins is likely corrupts memory. Or it may work by accident.

Better change getChildren to either return a ref to an elemet as: Tree& getChildren(int index) { return _children[index]; }

Or change the def of _children to be Tree** _children; With initialization as _children = new Tree<T,N>*[N];

AbbysSoul
  • 393
  • 1
  • 7
  • 1
    `if (_info) delete _info;` - the `if` test is pointless. `delete _info;` where `_info` is `nullptr` is both viable and completely allowed by the language standard. It effectively becomes a no-op. This isn't the issue. – WhozCraig Nov 10 '19 at 10:08
  • I still get the same result with this modification –  Nov 10 '19 at 10:11
  • well the check does have its place. For more details, plz see: https://stackoverflow.com/questions/6731331/is-it-still-safe-to-delete-nullptr-in-c0x so it does depend on the function provided. Which Valgrind is allowed to change. Although I have not checked if it does :) I updated my answer with more analysis. – AbbysSoul Nov 10 '19 at 10:23
  • @AbbysSoul I am not sure but I think the problem may come from `ins` method. because I pass the adress of every object in main and if I delet ins method and change the destructor of node class to `delete[] _children`, I wouldn't have memory leaks. –  Nov 10 '19 at 10:26
0
T** getChildren() { return &this->children; }

returns the address of the children member. Later on , you use that address via dereference through array indexing by doing this:

_info->getChildren()[index] = childTree;

This is invoking undefined behavior. To address this:

Change you're member to be:

Tree** _children;

Change your ctor to be:

Node(T data) 
    : _data( std::move(data) )
    , _children(new Tree<T,N>*[N]())
    , _isWord(false)
{
}

and note both the array of pointer syntax as well as the value-initialization of the elements, which will zero-fill the array.

Finally, change the getChildren() member to simply be:

Tree** getChildren() { return this->_children; }

That should alleviate your UB, and with it your fault. Not going to sugar coat this. The manual memory management in this is error prone and problematic. You'd be far better off using at least smart pointers, if not outright concrete objects where warranted. But it is what it is.

Alternative

Lose the dynamic children allocation entirely. It's size is already fixed by compile-time specification of N. So use that.

The member becomes simply:

Tree* _children[N];

The ctor can still value-initialize by doing this:

Node(T data) 
    : _data( std::move(data) )
    , _children()
    , _isWord(false)
{
}

And completely remove the delete [] children; entirely from the destructor;

WhozCraig
  • 65,258
  • 11
  • 75
  • 141
  • Thank you for your answer. I would like to know (if you have the time to explain) which type of violations I am doing here and maybe if I could fix them. Although in this case with all of this restriction that my teacher made me to do, I don't think that would be possible –  Nov 10 '19 at 10:34
  • @Mohammadreza Naming more than anything, though now as I see it, you're names that would be violations in the global namespace are not, in fact, in the global namespace. A good read on naming restrictions [can be seen here](https://en.cppreference.com/w/cpp/language/identifiers). Bookmark that entire site; you won't find better for a C++ reference. – WhozCraig Nov 10 '19 at 10:37
  • thank you. I will definitely read and change my namings accordingly. i always search for better programming styles that respects the language standards –  Nov 10 '19 at 10:42
  • Just one more question, If I do it the alternative way, isn't there a limit size in stack. because I heard that the stack has only 2Mb of capacity –  Nov 10 '19 at 11:16
  • The underlying `Tree` objects will be larger, yes. Available stack space is entirely dependent to your implementation, and is often configurable. If you really want use dynamic management, then a `std::vector` coudl be a viable alternative. Best of luck. – WhozCraig Nov 10 '19 at 11:19