Debugging a bad_alloc error c++

Question

When I run my code everything seems to be working fine but after a certain number of timesteps (usually ~100, but a different number each time) I get the error:

"terminate called after throwing an instance of 'std::bad_alloc' "

Not really sure how to go about debugging this as it doesn't happen at the same point each time the code runs. I will post my code but it's quite long and is admittedly a bit of a mess (this is my first real attempt at writing a program in c++), but I will try and explain the structure and where I would expect the most likely place for the origin of the error to be.

The basic structure is that I have an array of "birds" (a class I define) that choose how to update themselves at every time step by some quite complicated calculation. In doing so it regularly calls the function getVisualState to update a linked list that every bird stores as its "visual state". I believe this is the only time I allocate any memory dynamically during the simulation, so I guess there's a pretty good chance this is the source of the error. The function Bird::resetVisualState() should clear the allocated memory after it's been used (but it doesn't seem like I am running out of memory, at least monitoring it in the task manager).

If anyone can see anything they think may be the source of the problem that would be fantastic, or if not just any suggestions for how I should actually debug this!

#include <iostream>
#include <cmath>
#include <gsl/gsl_rng.h>
#include <gsl/gsl_randist.h>
#include <ctime>
#include <vector>
#include <algorithm>
#include <fstream>

#include "birdClasses.h"

using namespace std;

/*
nBirds, nSteps, nF, v, dt, birdRad defined in "birdClasses.h"
*/

//define other parameters.
const int nSensors = 20;
const int nMoves = 3; //no. possible moves at each step.
double dTheta = 15*M_PI/180.0; //angle that birds can change their orientation by in a timestep.
double moves[nMoves] = {-dTheta, 0, dTheta}; //possible moves.
double noise = 0.0;
double initBoxX = 20, initBoxY = 20; //size of initial box particles are placed in.
double sensorFrac[nSensors];
double sensorRef[nSensors];
double sensorRange = 2*M_PI/((double)nSensors);
int counter = 0;

int nps = numStates(nMoves,nF);
int *possibleStates = new int[nps];


//variables to record positions and orientations.
double xPositions[nSteps][nBirds], yPositions[nSteps][nBirds], orientations[nSteps][nBirds];

//array to keep track of which collisions are possible.
int couldCollide[nF][nBirds][nBirds];

//function prototypes
bool checkCollision(int i, int nFut, Bird *birds, double xi, double yi);
unsigned long int getVisualState(Bird *birdList, int nFut, int i, double cX, double cY, double cAng);
void updateTree(double exploreX, double exploreY, double exploreO, Bird *bird, int bn, int nFut);

int main()
{
    sensorRef[0] = sensorRange;
    for(int u=1; u<nSensors; u++) sensorRef[u] = sensorRef[u-1] + sensorRange;

    //set up GSL random number generator.
    const gsl_rng_type * Tr;
    gsl_rng * RNG;
    gsl_rng_env_setup();
    Tr = gsl_rng_default;
    RNG = gsl_rng_alloc (Tr);
    gsl_rng_set(RNG,time(NULL));

    //set up output
    ofstream output("output.txt");

    //initialize birds in a box randomly, all with the same orientation.
    Bird birdList[nBirds];

    for(int i=0; i<nBirds; i++) {
        birdList[i].set_position(gsl_ran_flat(RNG,0,initBoxX),gsl_ran_flat(RNG,0,initBoxY));
    }


    //ACTUAL CODE

    int uniqueVisStates[nMoves];
    double cX, cY, fX, fY, exploreX, exploreY, exploreO;


    //main time step loop
    for(int ts=0; ts<nSteps; ts++) {

        //save current positions
        for(int i=0; i<nBirds; i++) {
            xPositions[ts][i] = birdList[i].get_xPos();
            yPositions[ts][i] = birdList[i].get_yPos();
            orientations[ts][i] = birdList[i].get_orientation();
            birdList[i].updateFuture();
        }

        //update list of possible collisions.
        for(int nFut=0; nFut<nF; nFut++) {
            for(int i=0; i<nBirds; i++) {
                cX = birdList[i].get_xPos(); cY = birdList[i].get_yPos();
                counter = 0;
                for(int j=0; j<nBirds; j++) {
                    if(i==j) {
                        continue;
                    } else {
                        fX = birdList[j].get_futureX(nFut); fY = birdList[j].get_futureY(nFut);
                        if((cX-fX)*(cX-fX)+(cY-fY)*(cY-fY) < ((nFut+1)*v*dt+2*birdRad)*((nFut+1)*v*dt+2*birdRad)) {
                                couldCollide[nFut][i][counter]=j;
                                counter++;
                        }
                    }
                }
                if(counter < nBirds) couldCollide[nFut][i][counter]=-1;
            }
        }

        //loop over birds to choose how they update their orientation.
        for(int bn=0; bn<nBirds; bn++) {
            //loop over possible moves bird can make NOW.

            for(int l=0; l<nMoves; l++) {
                uniqueVisStates[l]=0;
            }

            for(int mn=0; mn<nMoves; mn++) {
                for(int l=0; l<nps; l++) {
                    possibleStates[l]=0;
                }
                counter = 0;
                exploreO = birdList[bn].get_orientation() + moves[mn];
                exploreX = birdList[bn].get_xPos() + cos(exploreO)*v*dt;
                exploreY = birdList[bn].get_yPos() + sin(exploreO)*v*dt;
                updateTree(exploreX,exploreY,exploreO,&birdList[0],bn,0);
                vector<int> visStates (possibleStates,possibleStates+counter);
                vector<int>::iterator it;
                sort (visStates.begin(),visStates.end());
                it = unique(visStates.begin(),visStates.end());
                uniqueVisStates[mn] = distance(visStates.begin(),it);

            }
            int maxInd = 0, maxVal = uniqueVisStates[0];
            for(int h=1; h<nMoves; h++) {
                if(uniqueVisStates[h] > maxVal) {
                    maxInd = h; maxVal = uniqueVisStates[h];
                } else if(uniqueVisStates[h]==maxVal) {
                    if(abs(moves[h])<abs(moves[maxInd])) {
                        maxInd = h;
                    }
                }
            }
            birdList[bn].update_Orientation(moves[maxInd]);
            birdList[bn].update_Pos(birdList[bn].get_xPos()+cos(birdList[bn].get_orientation())*v*dt,birdList[bn].get_yPos()+sin(birdList[bn].get_orientation())*v*dt);
        }

        for(int bn=0; bn<nBirds; bn++) birdList[bn].finishUpdate();
        cout << ts << "\n";
    }

    //OUTPUT DATA INTO A TEXT FILE.
    for(int ts=0; ts<(nSteps-1); ts++) {
        for(int bn=0; bn<nBirds; bn++) {
            output << xPositions[ts][bn] << " " << yPositions[ts][bn] << " " << orientations[ts][bn] << "\n";
        }
    }

    delete[] possibleStates;


    return 0;
}

bool checkCollision(int i, int nFut, Bird *birds, double xi, double yi) {
    int cond = 1; int index, counti=0;
    while(cond) {
        index = couldCollide[nFut][i][counti];
        if(index==-1) break;
        double xj = birds[index].get_futureX(nFut);
        double yj = birds[index].get_futureY(nFut);
        if((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj) < 4*birdRad*birdRad) {
            return 1;
        }
        counti++;
        if(counti==nBirds) break;
    }
    return 0;
}

unsigned long int getVisualState(Bird *birdList, int nFut, int i, double cX, double cY, double cAng) {
    //finds the visual state of bird i based on its current "exploring position" and the predicted positions of other birds at timestep nFut.
    //visual state is defined by discretizing the bird's field of view into nSensors (relative to current orientation) and creating a vector of
    //0s and 1s depending on whether each sensor is < half covered or not. This is then converted to an integer (as we are actually interested only
    //in the number of unique visual states.
    double relX, relY, relDist, dAng, s, dTheta, ang1, ang2;
    //clear current visual state.
    birdList[i].resetVisualState();

    for(int j=0; j<nBirds; j++) {
        if(i==j) continue;
        relX = birdList[j].get_futureX(nFut)-cX;
        relY = birdList[j].get_futureY(nFut)-cY;
        relDist = sqrt(relX*relX+relY*relY);
        dAng = acos((cos(cAng)*relX+sin(cAng)*relY)/relDist);
        dTheta = atan(birdRad/relDist);
        s = cos(cAng)*relY - sin(cAng)*relX;
        if( s<0 ) dAng = 2*M_PI-dAng;
        ang1 = dAng - dTheta; ang2 = dAng + dTheta;
        if( ang1 < 0 ) {
            birdList[i].addInterval(0,ang2);
            birdList[i].addInterval(2*M_PI+ang1,2*M_PI);
        } else if( ang2 > 2*M_PI ) {
            birdList[i].addInterval(0,fmod(ang2,2*M_PI));
            birdList[i].addInterval(ang1,2*M_PI);
        } else {
            birdList[i].addInterval(ang1,ang2);
        }
    }
    Node *sI = birdList[i].get_visualState();
    birdList[i].cleanUp(sI);
    int ind1, ind2;
    for(int k=0; k<nSensors; k++) sensorFrac[k]=0.0; //initialize.
    while(sI->next->next != 0) {
        ang1 = sI->value; ang2 = sI->next->value;
        ind1 = floor(ang1/sensorRange); ind2 = floor(ang2/sensorRange);
        if(ind2==nSensors) ind2--; //this happens if ang2 = 2pi (which can happen a lot).
        if(ind1==ind2) {
            sensorFrac[ind1] += (ang2-ang1)/sensorRange;
        } else if(ind2-ind1==1) {
            sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange;
            sensorFrac[ind2] += (ang2-sensorRef[ind1])/sensorRange;
        } else {
            sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange;
            sensorFrac[ind2] += (ang2-sensorRef[ind2-1])/sensorRange;
            for(int y=ind1+1;y<ind2;y++) sensorFrac[y] = 1.0;
        }
        sI=sI->next->next;
    }
    //do final interval separately.
    ang1 = sI->value; ang2 = sI->next->value;
    ind1 = floor(ang1/sensorRange); ind2 = floor(ang2/sensorRange);
    if(ind2==nSensors) ind2--; //this happens if ang2 = 2pi (which can happen a lot).
    if(ind1==ind2) {
        sensorFrac[ind1] += (ang2-ang1)/sensorRange;
    } else if(ind2-ind1==1) {
        sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange;
        sensorFrac[ind2] += (ang2-sensorRef[ind1])/sensorRange;
    } else {
        sensorFrac[ind1] += (sensorRef[ind1]-ang1)/sensorRange;
        sensorFrac[ind2] += (ang2-sensorRef[ind2-1])/sensorRange;
        for(int y=ind1+1;y<ind2;y++) sensorFrac[y] = 1.0;
    }
    int output = 0, multiplier = 1;
    for(int y=0; y<nSensors; y++) {
        if(sensorFrac[y]>0.5) output += multiplier;
        multiplier *= 2;
    }

    return output;
}

void updateTree(double exploreX, double exploreY, double exploreO, Bird *bird, int bn, int nFut) {
    double o,x,y;
    if(checkCollision(bn,nFut,bird,exploreX,exploreY)) return;
    int vs = getVisualState(bird,nFut,bn,exploreX,exploreY,exploreO);
    possibleStates[counter] = vs;
    counter++;
    if(nFut < (nF-1)) {
        for(int m=0; m<nMoves; m++) {
            o = exploreO + moves[m];
            x = exploreX + cos(o)*v*dt;
            y = exploreY + sin(o)*v*dt;
            updateTree(x,y,o,bird,bn,nFut+1);
        }
    } else {
        return;
    }
}

"birdClasses.h":

#ifndef BIRDCLASSES_H_INCLUDED
#define BIRDCLASSES_H_INCLUDED

#include <iostream>
#include <cmath>

using namespace std;

//DEFINE SOME GLOBAL PARAMETERS OF THE SIMULATION
const int nBirds = 50;
const int nF = 6; //number of future timesteps to consider.
const int nSteps = 200;
const double v = 20, dt = 0.1, birdRad = 0.2;

int numStates(int numMoves, int nFut) {
    int num = 1; int multiplier = numMoves;
    for(int i=1; i<nFut; i++) {
        num += multiplier;
        multiplier *= numMoves;
    }
    return num;
}

//Node class is just for a linked list (used in constructing the visual states),
class Node {
public:
    int identifier; // 0 is left side of interval, 1 is right side
    double value; //angular value.
    Node *next; //pointer to the next interval.
    void display(Node *start);
};

//printout linked list if necessary (mainly for debugging purposes).
void Node::display(Node *start) {
    if(start != 0) {
        double inter = start->value;
        cout << inter << " ";
        display(start->next);
    }
}

//bird class.
class Bird {
    double currX, currY;
    double updatedX, updatedY;
    double currOrientation;
    double futureX[nF], futureY[nF];
    Node *visualState;
public:
    Bird() {
        currOrientation=0.0; currX = 0.0; currY = 0.0;
        visualState = new Node;
        visualState->value = 0.0;
        visualState->next = new Node;
        visualState->next->value = 0.0;
        visualState->next->next = 0;
    }
    Bird(double x, double y, double o) {
        currX = x; currY = y; currOrientation = o;
        visualState = new Node;
        visualState->value = 0.0;
        visualState->next = new Node;
        visualState->next->value = 0.0;
        visualState->next->next = 0;
    }
    void set_position(double x, double y) {
        currX = x; currY = y;
    }
    double get_xPos() {
        return currX;
    }
    double get_yPos() {
        return currY;
    }
    double get_orientation() {
        return currOrientation;
    }
    double get_futureX(int ts) {
        return futureX[ts];
    }
    double get_futureY(int ts) {
        return futureY[ts];
    }
    //return pointer to first node.
    Node* get_visualState() {
        return visualState;
    }
    void updateFuture() {
        //use current orientation and position to update future positions.
        for(int i=0; i<nF; i++) {
            futureX[i] = currX + v*(i+1)*cos(currOrientation)*dt;
            futureY[i] = currY + v*(i+1)*sin(currOrientation)*dt;
        }
    }
    void update_Pos(double x, double y) {
        updatedX = x;
        updatedY = y;
    }
    //run this after all birds have updated positions:
    void finishUpdate() {
        currX = updatedX;
        currY = updatedY;
    }
    void update_Orientation(double o) {
        currOrientation += o;
    }

    //add the interval defined by [l r] to the visual state.
    void addInterval(double l, double r) {
        int placed = 0; double cL = 0.0; double cR = 0.0;
        if(visualState->value==0.0 && visualState->next->value==0.0) { //then this is first interval to place.
            visualState->value = l;
            visualState->next->value = r;
            placed = 1;
            return;
        }
        Node *curr_L = visualState;
        Node *prev_L = visualState;
        while(placed==0) {
            cL = curr_L->value;
            cR = curr_L->next->value;
            if(l<cL && r<cL) { //add new interval before this one.
                Node *newRoot = new Node;
                newRoot->value = l;
                newRoot->identifier = 0;
                newRoot->next = new Node;
                newRoot->next->value = r;
                newRoot->next->next = curr_L;
                if(curr_L == visualState) {
                    visualState = newRoot;
                } else {
                    prev_L->next->next = newRoot;
                }
                placed = 1;
            } else if(l <= cL && r >= cR) {
                curr_L->value = l;
                curr_L->next->value = r;
                placed = 1;
            } else if(l <= cL && r <= cR) {
                curr_L->value = l;
                placed = 1;
            } else if(l >= cL && r <= cR) {
                placed = 1; //dont need to do anything.
            } else if(l >= cL && l<=cR && r >= cR) {
                curr_L->next->value = r;
                placed = 1;
            }

            if(l > cR && r > cR) {
                if(curr_L->next->next != 0) {
                    prev_L = curr_L;
                    curr_L = curr_L->next->next;
                } else {
                    Node *newEndL = new Node;
                    newEndL->value = l;
                    newEndL->identifier = 0;
                    newEndL->next = new Node;
                    newEndL->next->value = r;
                    newEndL->next->identifier = 1;
                    newEndL->next->next = 0;
                    curr_L->next->next = newEndL;
                    placed = 1;
                }
            }
        }
    }
    //remove any overlaps.
    void cleanUp(Node *start) {
        Node *NP, *NNP; NP = start->next->next;
        if(NP==0) return;
        NNP = start->next->next->next->next;
        double cL = start->value, cR = start->next->value, nL = start->next->next->value, nR = start->next->next->next->value;

        if(nL < cR) {
            if(nR > cR) {
                start->next->value = nR;
            }

            start->next->next = NNP;

        }
        if(NNP!=0) cleanUp(NP);
    }
    //reset the visual state.
    void resetVisualState() {
        Node *cNode = visualState;
        Node *nNode = visualState->next;
        while(nNode != 0) {
            delete cNode;
            cNode = nNode;
            nNode = nNode->next;
        }
        delete cNode;
        delete nNode;
        visualState = new Node;
        visualState->identifier = 0;
        visualState->value = 0.0;
        visualState->next = new Node;
        visualState->next->identifier = 1;
        visualState->next->value = 0.0;
        visualState->next->next = 0;
        return;
    }
};

#endif // BIRDCLASSES_H_INCLUDED

Answer 1

I think this is a logic bug and not necessarily memory related.

In void addInterval(double l, double r) you declare

Node *curr_L = visualState;
Node *prev_L = visualState;

These pointers will now point to whatever the member visualState is pointing to.

later on you are changing visualState to point to a newly created Node

Node *newRoot = new Node;
// ....
if(curr_L == visualState) {
  visualState = newRoot;

but your pointers curr_L and prev_L will still point to whatever visualState was pointing to before. The only time you change those pointers is at

if(curr_L->next->next != 0) {
  prev_L = curr_L;
  curr_L = curr_L->next->next;

which is the same as

if(WHATEVER_VISUAL_STATE_USED_TO_POINT_TO->next->next != 0) {
  prev_L = curr_L;
  curr_L = curr_L->next->next;

Is this your intention? You can follow the assignment of curr_L by looking for *curr_L = * in your editor.

I would suggest testing your code on a small data sample and make sure your code follows your intentions. Use a debugger or trace outputs. Use
valgrind if you have access to it, I think you will appreciate valgrind.

Answer 2

or if not just any suggestions for how I should actually debug this!

You can try to set catchpoint in gdb to catch std::bad_alloc exception:

(gdb) catch throw bad_alloc

(See Setting Catchpoints)

If you are able to reproduce this bad_alloc in gdb you can then look at bt to see possible reason of this exception.