Thread: This code gives rise to segmentation fault

The following program is supposed to solve the coast problem:

Code:

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool **worldArray;
bool **removalMask;
bool **floodArray;
int nRows, nCols;
char *inputRow;

typedef struct {
    int x;
    int y;
} Pixel;

void allocateMemory();
void extractInput();
void resetMask();

int QUEUE_LENGTH = 10000;
Pixel *floodQueue;
int startQueue;
int maxQueue;
int endQueue;
void requeue();
void pushQueue(Pixel element);
Pixel popQueue();

void maskOcean(int row, int col);
bool isToBeMasked(int row, int col);

int evaluateCoastLength();



int main(int argc, const char * argv[]) {
    if(scanf("%d%d", &nRows, &nCols) == 2) {
        allocateMemory();
        extractInput();
        resetMask();
    } else {
        printf("Invalid map size!\n\n");
        return -1;
    }
    maskOcean(0,0);

    printf("%d\n", evaluateCoastLength());
    
    for (int i = 0; i < nRows + 2; ++i) {
        free(worldArray[i]);
        free(floodArray[i]);
        free(removalMask[i]);
    }
    free(floodQueue);
    free(floodArray);
    free(worldArray);
    free(removalMask);
    
    return 0;
}



void allocateMemory() {
    worldArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
    removalMask = (bool **) malloc((nRows + 2)* sizeof(bool *));
    floodArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
    floodQueue = (Pixel *) malloc(QUEUE_LENGTH * sizeof(Pixel));
    startQueue = 0;
    endQueue = 0;
    maxQueue = QUEUE_LENGTH - 1;
    for(int i = 0; i <= nRows + 1; ++i) {
        worldArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
        floodArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
        removalMask[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
    }
}

void extractInput() {
    for(int row = 0; row < nRows; ++row) {
        inputRow = (char *) malloc (nCols * sizeof(char));
        if(!(scanf("%s", inputRow))) {
            printf("Input error!\n");
        }
        for(int col = 0; col < nCols; ++col) {
            if(inputRow[col] == '0')
                worldArray[row+1][col+1] = false;
            else
                worldArray[row+1][col+1] = true;
        }
        // Zeros along vertical borders
        worldArray[row+1][nCols+1] = false;
        worldArray[row+1][0] = false;
        free(inputRow);
    }
    // Zeros along horizontal borders
    for(int col = 0; col <= nCols+1; ++col) {
        worldArray[0][col] = false;
        worldArray[nRows+1][col] = false;
    }
}

void resetMask() {
    for(int i = 0; i <= nRows+1; ++i)
        for(int j = 0; j <= nCols+1; ++j) {
            removalMask[i][j] = false;
            floodArray[i][j] = false;
        }
}

int evaluateCoastLength() {
    int numSegs = 0;
    for(int row = 0; row < nRows + 1; ++row)
        for(int col = 0; col < nCols+1; ++col)
            if(removalMask[row][col] != removalMask[row][col+1])
                ++numSegs;
    for(int col = 0; col < nCols + 1; ++col)
        for(int row = 0; row < nRows+1; ++row)
            if(removalMask[row][col] != removalMask[row+1][col])
                ++numSegs;
    return numSegs;
}

void requeue() {
    if(startQueue > 0) {
        int counter = 0;
        for (int i = startQueue; i < endQueue; ++i)
            floodQueue[counter++] = floodQueue[i];
        startQueue = 0;
        endQueue = counter;
    }
}

void pushQueue(Pixel element) {
    for(int q = startQueue; q < endQueue; ++q)
       if(element.x == floodQueue[q].x)
          if(element.y == floodQueue[q].y)
             return;
    if(endQueue == maxQueue) {
        if(startQueue == 0)
            popQueue();
        requeue();
    }
    floodQueue[endQueue] = element;
    ++endQueue;
}

Pixel popQueue() {
    if(startQueue < endQueue) {
        ++startQueue;
        return floodQueue[startQueue -1];
    } else {
        printf("Empty queue, popQueue() abuse!\n");
        Pixel nonPixel;
        nonPixel.x = -1;
        nonPixel.y = -1;
        return nonPixel;
    }
}

void maskOcean(int row, int col) {
    Pixel pushElement;
    pushElement.x = row;
    pushElement.y = col;
    pushQueue(pushElement);
    while(startQueue < endQueue) {
        Pixel popElement;
        popElement = popQueue();
        removalMask[popElement.x][popElement.y] = true;
        int offset[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i < 4;++i) {
            if(isToBeMasked(popElement.x + offset[i][0], popElement.y + offset[i][1])) {
                pushElement.x = popElement.x + offset[i][0];
                pushElement.y = popElement.y + offset[i][1];
                pushQueue(pushElement);
            }
        }
    }
}
bool isToBeMasked(int row, int col) {
    if((row >= 0)&&(row<=nRows+1))
        if((col >= 0)&&(col<=nCols+1))
            return !(worldArray[row][col]) && !removalMask[row][col];
    return false;
}

The data-file to be evaluated may look like so:

PHP Code:

10 10
0100010100
0111001100
1000110010
0011100011
0111111110
0100000010
0111110000
0000011000
0111110000
0000000100 


A typical run is done by having that matrix in a text file and running:

coastProgram < dataFile.txt

So this is supposed to look like an archipelago where the 1s denote land and 0s denote water. These elements are shaped as squares in a grid and the length of the coastline is to be evaluated with lakes inside the landmasses omitted. The grid size varies between 1x1 and 1000 x 1000.

I think I have solved the problem and it does the job on all the data I have tried.

But there is some data where it crashes with a segmentation fault. I don't have access to that data unfortunately. Does anyone know what potential weakness in the code that may give rise to the segmentation fault?

It works for the most part in a Linux environment using gcc but crashes almost all the time in Visual Studio 2013.