C++ managing memory on the stack (linked lists)

Question

sorry to post the spaghetti code, but I don't know where the error is coming from. This function is supposed to mimic a simplified version of the file inclusion aspect of c++. It copy pastes the contents of all files with a #include (and recursively on the contents of the included file).

In order to ensure that 2 files don't recursively include each other, I created a linked list that stores every single file included previously. Files included afterwards will be checked against this linked list to ensure that a file does not include a previous file. We are not allowed to dynamically allocate so we must use memory from the stack for the linked list. I heard that this could cause memory problems with the linked list when variables go out of scope.

The problem is, parts of my linked list are being overwritten by random things. If you note the cout statements, a result could be something like this

Previous flist: input.txt

newnode filename: file1.txt

new flist: file1.txt

Previous flist: WHATEVER DOESNT MATTER (weird, it took on the value of string filename)

newnode filename: file2.txt

new flist: file2.txt

Previous flist: file2.txt (working as intended)

newnode filename: file3.txt

new flist: file3.txt

Previous flist: random symbols (huh? is this from random memory in the stack?)

newnode filename: file4.txt

new flist: file4.txt

Previous flist: file4.txt (working as intended)

newnode filename: file5.txt

new flist: file5.txt

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>

using namespace std;

struct Node { 
    string fileName;
    Node *link;
};

string extractfilename (string str) 
{
    string filename;

    if ((str.substr(10,1)) == "/" )
    {
        filename = str.substr((str.find_last_of("/"))+1,(str.length()) - (str.find_last_of("/"))-2);
        return filename;            
    } // if     
    else if ( (str.find_last_of("/")) != -1)
    {
        filename = str.substr((str.find_last_of("/")) + 1, (str.length()) - (str.find_last_of("/")) - 2);   
        return filename;
    } // else if 
    else
    {
        filename = str.substr(10,(str.length())-11);
        return filename;
    } // else

    return "ERROR";
}

void check_overlap (string filename, Node *flist)
{  
    while (flist != NULL)
    {
        if (flist->fileName == filename)
        {
            cerr << "Recursive include is being attempted. Terminating program." << endl;
            exit ( -1 );
        }
        flist = flist->link;
    }
}

void processOneFile( istream &in, ostream &out, Node *flist, string prefixDir )
{
    string str;
    getline(in,str);

    while(!(in.fail()))
    {
        string checkinclude = "";
        string checkabsolute = "";
        string prefix = "";
        string filename = "WHATEVER DOESNT MATTER";    
        string relpath = "";

        int checkrelative = 0;    
        int lastof = 0;    
        int length = str.length();

        if ( length > 11)
        {    
            checkinclude = str.substr(0,8);
            checkabsolute = str.substr(10,1);
            checkrelative = str.find_last_of("/");
        }    

        if (checkinclude == "#include")
        {
            ifstream newinput;
            filename = extractfilename(str);

            // PROBLEM WITH THIS ************
            //check_overlap(filename,flist) CAUSES INFINITE LOOP DUE TO DANGLING POINTERS?      
            Node newnode;

            cout << "Previous flist:    "<< flist->fileName << endl;

            newnode.fileName = filename;
            newnode.link = flist;
            Node surrogate_flist = newnode;

            cout << "newnode filename: "<< newnode.fileName << endl;       
            cout << "New flist:         "<< surrogate_flist.fileName << endl;
            cout << endl;
            // PROBLEM WITH THIS **************

            if (checkabsolute == "/" )
            {
                lastof = str.find_last_of("/");
                prefix = str.substr(10,lastof - 9);                    
                newinput.open((prefix + filename).c_str());

                if (!(newinput.is_open()))
                {
                    cout << prefix+filename << " cannot be opened" << endl;
                    exit( -1) ;
                }

                processOneFile(newinput,out,&surrogate_flist,prefix);
                newinput.close();
            } // if        
            else if ( checkrelative != -1)
            {
                relpath = str.substr(10, checkrelative - 9);        
                newinput.open((prefixDir+relpath+filename).c_str());

                if (!(newinput.is_open()))
                {
                    cout << prefixDir + relpath + filename << " cannot be opened" << endl;
                    exit( -1) ;
                }

                processOneFile(newinput,out,&surrogate_flist,(prefixDir+relpath));
                newinput.close();
            } // else if
            else
            {
                newinput.open((prefixDir + filename).c_str());

                if (!(newinput.is_open()))
                {
                    cout << prefixDir +filename << " cannot be opened" << endl;
                    exit( -1) ;
                }

                processOneFile(newinput,out,&surrogate_flist,prefixDir);
                newinput.close();
            } // else
        } // if
        else
        {
            out << str << endl;
        } // else
        getline(in,str);
    } // while
} // processOneFile

Thanks

EDIT: Use of the node structure and linked lists is a requirement

Implicit dynamic allocation from string functions is allowed

added main and "complete" compilable code

You cannot dynamically allocate, but you are using pointers? If you are referencing variables, and they go out of scope (i.e. whatever function they were in returns), they will be popped off the stack and you will get gibberish at their former memory locations (if that is how you are storing them). In any case, the system manages the stack; you can only manage the heap (dynamic allocation) — RageD
It seems to me that the only way to allocate the arbitrary number of nodes you'd need using only automatic variables would be to recurse for each include file you come across and not return from any of these recursive calls until the entire list is completed and processed. So when you recurse to process a new include file, to get back to processing the original source file you'd have to recurse further with the right set of state instead of returning back (which is how normal recursion would get the original state back). That's a bit tricky (though I don't doubt it can be done). — Michael Burr
Interesting problem, though - whoever assigned this problem seems to have at least a bit of evil in him... — Michael Burr
As a suggestion, I'd probably work on a partial solution first that scaned a single source file for the #include directives and processed those without descending into processing the included files. Once I had this simpler problem solved, then I'd try to tackle adding in processing the files included by in the original... — Michael Burr
I took the liberty of editing your code block to be a bit more readable (proper indentation). — Sven

Sven Sven · Accepted Answer · 2011-06-17T06:36:19

Given the requirement to use a linked list, you must use recursion. It would be something like this:

struct Node
{
    string value;
    Node *link;
};

void Process(Node *front)
{
    Node newNode;
    newNode.link = front;
    if( /* some condition */ )
        return; // end recursion
    else
        Process(&newNode);
}

The first invocation to Process would simply be Process(NULL); to indicate an empty list. Add additional parameters to include the rest of your state, of course (I'm not here to do your homework for you ;)).

The important thing is that you do not modify front->link, because your new node will not be valid once the function returns and must therefore not become visible to the caller. So you must build this list in reverse (each recursive call adds a node to the front).

You are already doing something similar to this, so your problem may lie elsewhere. Without complete, compilable code it's hard to determine where, however.

C++ managing memory on the stack (linked lists)

1 Answers