c++ Unable to use functions on Nodes in a vector

Question

I am trying to make a c++ program that emulates parts of a linux filesystem.

I have a vector<Node*>. In order to add to it I have to first create a Node* that I then .push_back() to the vector, right? Is it possible to .push_back() without having to first create another Node* to push_back()?

Another problem is that I cannot invoke any methods on the nodes inside of the vector<Node*>. In order to do anything with them like, say, use a GetName() method on it, I have to first create a Node* with the index of the vector that has the data I want to use. I am fairly certain that this way of going about it is what's causing me so much grief.

What's killing me right now is that when I test all the associated methods in a separate main.cpp file, they all cooperate and do what I want. When I run them through a TEST_CASE however, they misbehave and cause a crash. I can't think of anything that could be causing these problems mostly because they behave in a main method.

For Reference, here's all my code: node.hpp:

#ifndef NODE_HPP
#define NODE_HPP
using namespace std;
#include <string>
#include <vector>
class Node {
    private:
        char type;
        string name;
        vector<Node*> children;
        Node* parent;
        void RemoveHelper(Node* subtree);
    public:
        Node(string name, char type);
        Node();
        ~Node();
        void AddChild(Node* child);
        void AddChild(string name, char type);
        bool RemoveChild(string name);
        void SetParent(Node* parent);
        void SetType(char type);
        Node* GetChild(string name);
        vector<Node*> GetChildren();
        Node* GetParent();
        char GetType();
        string GetName();
};

#endif

node.cpp:

#include <iostream>
#include <string>
#include <vector>
using namespace std;

#include "node.hpp"

void Node::RemoveHelper(Node* subtree){
    for (int j = 0; j < subtree->GetChildren().size(); j++){
        //cout << j << " ";
        Node* n = subtree->GetChildren()[j];
        if (!n->GetChildren().empty()){
            for (int i = 0; i < n->GetChildren().size(); i++){
                //cout << i << endl;
                RemoveHelper(subtree->GetChildren()[i]);
                subtree->RemoveChild(n->GetName());
            }
        }
    }
}

Node::Node(){
    name = "";
    type = ' ';
    parent = nullptr;
}

Node::Node(string name, char type){
    this->name = name;
    this->type = type;
    parent = nullptr;
}

Node::~Node(){
    children.clear();
}

void Node::AddChild(string name, char type){
    Node* n = new Node(name, type);
    AddChild(n);
    delete n;
}

void Node::AddChild(Node* child){
    children.push_back(child);
}

bool Node::RemoveChild(string name){
    Node* n = GetChild(name);
    for (int i = 0; i < children.size(); i++){
        if (n == children[i]){
            RemoveHelper(children[i]);
            children.erase(children.begin()+i);
            //delete n;
            return true;
        }
    }   
    return false;
}

void Node::SetParent(Node * parent){
    this->parent = parent;
}

void Node::SetType(char type){
    this->type = type;
}

Node* Node::GetChild(string name){
    for (int i = 0; i < children.size(); i++){
        Node* n = children[i];
        if (n->GetName() == name){
            //delete n;
            return children[i];
        }
        //delete n;
    }
    return nullptr;
}

vector<Node*> Node::GetChildren(){
    return children;
}

Node* Node::GetParent(){
    return parent;
}

char Node::GetType(){
    return type;
}

string Node::GetName(){
    return name;
}

filesystem.hpp:

#ifndef FILESYSTEM_HPP
#define FILESYSTEM_HPP
using namespace std;
#include <string>
#include "node.hpp"

class FileSystem {
    private:
        Node* root;
        Node* currentDirectory;
        void AddNode(Node* newNode);
        Node* FindNode(string name);
    public:
        FileSystem();
        ~FileSystem();
        string mkdir(string name);
        string touch(string name);
        string pwd();
        string ls();
        string rm(string name);
        string mv(string from, string to);
        string cd(string dirname);
};

#endif

filesystem.cpp

#include <iostream>
#include <string>
using namespace std;

#include "filesystem.hpp"
#include "node.hpp"

void FileSystem::AddNode(Node* newNode){
    currentDirectory->AddChild(newNode);
    currentDirectory->GetChild(newNode->GetName())->SetParent(currentDirectory);
}

Node* FileSystem::FindNode(string name){
    return currentDirectory->GetChild(name);
}

FileSystem::FileSystem(){
    root = new Node("root", 'd');
    currentDirectory = root;
}

FileSystem::~FileSystem(){
    for (int i = root->GetChildren().size(); i > i; i--){
        Node* n = root->GetChildren()[i];
        root->RemoveChild(n->GetName());
        //delete n;
    }
    delete root;
    
    for (int i = currentDirectory->GetChildren().size(); i > 0; i--){
        Node* n = currentDirectory->GetChildren()[i];
        currentDirectory->RemoveChild(n->GetName());
        delete n;
    }
    delete currentDirectory;
}

string FileSystem::mkdir(string name){
    if (currentDirectory->GetChild(name) == nullptr){
        Node* n = new Node(name, 'd');
        AddNode(n);
        
        return "directory " + name + " created successfully";
    }
    return "Error: " + name + " exists";
}

string FileSystem::touch(string name){
    if (currentDirectory->GetChild(name) == nullptr){
        currentDirectory->AddChild(name, 'f');
        return "file " + name + " created successfully";
    }
    return "Error: " + name + " exists";
}

// I know that this only works for up to 3 directories. That's fine for this project.
string FileSystem::pwd(){
    string ret = "/" + root->GetName();
    if (root != currentDirectory){
        if (currentDirectory->GetParent() != root){
            ret += "/" + currentDirectory->GetParent()->GetName();
        }
        ret += "/" + currentDirectory->GetName();
    }
    return ret;
}

string FileSystem::ls(){
    string ret = "";
    for (int i = 0; i < currentDirectory->GetChildren().size(); i++){
        Node* n = currentDirectory->GetChildren()[i];
        ret += n->GetType();
        ret += " " + n->GetName() + "\n";
        //delete n;
    }
    return ret;
}

string FileSystem::rm(string name){
    if (currentDirectory->RemoveChild(name)){
        return name + " removed successfully";
    }
    return "No such file or directory";
}

string FileSystem::mv(string from, string to){
    currentDirectory->AddChild(to, currentDirectory->GetChild(from)->GetType());
    currentDirectory->RemoveChild(from);
    return "file/dir renamed successfully";
}

string FileSystem::cd(string dirname){
    cout << currentDirectory->GetChild("dir");
    if ((dirname == ".." && currentDirectory == root) || dirname == currentDirectory->GetName()){
        return "can't change to directory " + dirname;
    }
    else if (dirname == ".."){
        currentDirectory = root;
    }
    else if (currentDirectory->GetChild(dirname) == nullptr){
        return "can't change to directory " + dirname;
    }
    else{
        currentDirectory = currentDirectory->GetChild(dirname);
    }
    return pwd();
}

One of the test files:

#include "catch/catch.hpp"
#include "../filesystem.hpp"

TEST_CASE("Test creating a file system")
{
    FileSystem fs;
    CHECK ("/root" == fs.pwd());
    CHECK ("" == fs.ls());
}

TEST_CASE ("Test touch and mkdir")
{
    FileSystem fs;
    CHECK ("file file1 created successfully" == fs.touch("file1"));
    CHECK ("Error: file1 exists" == fs.touch("file1"));
    CHECK ("file file2 created successfully" == fs.touch("file2"));
    CHECK ("directory dir1 created successfully" == fs.mkdir("dir1"));
    CHECK ("Error: dir1 exists" == fs.mkdir("dir1"));
    CHECK ("Error: dir1 exists" == fs.touch("dir1"));
    CHECK ("f file1\nf file2\nd dir1\n" == fs.ls());
    CHECK ("/root" == fs.pwd());
}

If there is anything else anyone catches that could help avoid other issues I haven't caught yet, that would also be greatly appreciated.

Answer 1

Your problem is not that you can't invoke methods on nodes inside of vector of children. Your problem is that you're trying to invoke Node methods on random memory, because you have deleted the nodes beforehand and the memory now contains whatever.

You have to understand the difference between an object and a pointer to the object. Pointer is not an object, it's just its address. You can store the address of the object in multiple places and all those places would point to the very same object.

In your particular case you're storing a bunch od addresses of Node objects in the vector called children. So when you add a child to your Node, you create a new object (this is what new does), but then you just store the address of that object. When you store an address to the object, the object itself is not touched. This is similar to a situation when you give your mail address to someone. They may do whatever with that address. If that person gives your address to someone else you don't feel it nor does your clone spawn somewhere.

So when you stored the address of that new child in children vector, this newly created child is not copied anywhere, it stays exactly where you created it at the address you were given back as a result of new operator and which you subsequently stored in children.

So you must not delete freshly created child just after you add it to your Node. You must wait with deletion until you remove that particular child from the Node.

---

Back to your case:

The problem is in this code:

void Node::AddChild(string name, char type){
    Node* n = new Node(name, type);
    AddChild(n);
    delete n;  // <-- HERE'S THE ISSUE
}

What the above code does is:

1. It creates a new Node
2. It stores pointer to that Node in variable n
3. It now executes AddChild which stores the pointer into children vector
4. It deletes the Node it created in step 1. From that very moment the stored pointer doesn't point to any Node, it points to garbage. It's now a so called dangling pointer.

To fix the immediate issue you should stop deleting the Node just after insertion. You should delete the node after it's removed from children, i.e. in Node::RemoveChild method:

bool Node::RemoveChild(string name){
    Node* n = GetChild(name);
    for (int i = 0; i < children.size(); i++){
        if (n == children[i]){
            RemoveHelper(children[i]);
            children.erase(children.begin()+i);
            delete n;  // <-- YOU WANT THIS DELETE, HERE YOU DELETE THE NODE
            return true;
        }
    }   
    return false;
}

---

But, the above is just an immediate fix. The real proper option is to actually use smart pointers. Usually std::unique_ptr is the right one (and at first glance it indeed seems correct in your case). Smart pointers remove the need of explicit deletion

The first step would be to change the children vector definition:

vector<std::unique_ptr<Node>> children;

The next step would be to modify your Node::AddChild method:

void Node::AddChild(string name, char type){
    AddChild(std::make_unique<Node>(name, type));
}

Then in all other places when you assingn to some Node* you do

Node* n = `THE_THING_GIVING_YOU_NODE`.get();