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.