Thread: This code gives rise to segmentation fault

If you interpret my response as snarky, then I apologize. That was not my intention and your help has been much appreciated. I will look into your suggestions in a bit.

Yes when queueLength reaches maxLength, the queue is considered as being full. If there are better ways of implementing this, I'm open for it. I don't know whether "ring buffer" is the appropriate description for what I'm doing but at least it looks like one.

... (a "bit" later ) ...

I have now tried your code snippet and it works fine. However, when doing the same thing in my program, it doesn't work. The exact code I'm trying to compile is this:

Code:

#include <stdio.h>
#include <stdbool.h> // For using booleans
#include <stdlib.h>  // For using malloc


bool **worldArray;
bool **oceanArray;
int nRows, nCols;
char *inputRow;


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


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


//16: 291 20: 504
int QUEUE_LENGTH = 757;
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());
    
    free(worldArray[0]);
    free(oceanArray[0]);
    free(floodQueue);
    free(worldArray);
    free(oceanArray);
    
    return 0;
}


void allocateMemory() {
   int NROWS = nRows + 2, NCOLS = nCols + 2;
    worldArray = malloc(NROWS * sizeof *worldArray);
    worldArray[0] = calloc(NROWS * NCOLS, sizeof **worldArray);
    oceanArray = malloc(NROWS * sizeof *oceanArray);
    oceanArray[0] = calloc(NROWS * NCOLS, sizeof **oceanArray);
    floodQueue = (Pixel *) malloc(QUEUE_LENGTH * sizeof(Pixel));
    
    startQueue = 0;
    endQueue = 0;
    maxQueue = QUEUE_LENGTH - 1;
    for(int i = 0; i < NROWS; ++i) {
        worldArray[i] = worldArray[i - 1] + NCOLS;
        oceanArray[i] = oceanArray[i - 1] + NCOLS;
    }
    printf("Mallocs done.\n");
}


void extractInput() {
    inputRow = (char *) malloc ((nCols + 1) * sizeof(char));
    for(int row = 0; row < nRows; ++row) {
        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;
    }
    // Zeros along horizontal borders
    for(int col = 0; col <= nCols+1; ++col) {
        worldArray[0][col] = false;
        worldArray[nRows+1][col] = false;
    }
    printf("Input done.\n");
    free(inputRow);
}


void resetMask() {
    for(int i = 0; i <= nRows+1; ++i)
        for(int j = 0; j <= nCols+1; ++j) {
            oceanArray[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(oceanArray[row][col] != oceanArray[row][col+1])
                ++numSegs;
    for(int col = 0; col < nCols + 1; ++col)
        for(int row = 0; row < nRows+1; ++row)
            if(oceanArray[row][col] != oceanArray[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)
        return floodQueue[startQueue++];
    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();
        oceanArray[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]) && !oceanArray[row][col];
    return false;
}

It crashes in the extractInput() function. Very strange.

I didn't know this thing with sqeuence points was such an issue. I have always assumed that when coding say

Code:

int x = 5, y = 6;
int z = x++ + y++;

then it means that the compiler should first read the values of x and y, then add them and store in z and then increment them by 1. That as opposed to ++x and ++y where it would first increment the values of x and y and then add them together and store the result of the addition in z. I found a discussion about it here:


c++ - Undefined behavior and sequence points - Stack Overflow

But I guess this must be ok to use:

Code:

int A = someVectorOfInts[i++]

The purpose of doing this all is to learn and there I learned something.

You need to look at john.c's post again. Notice in particular that the loop starts at 1.
If you get errors, you need to post those errors rather than blundering on with your bad code.

Of course, I probably went through the code at least 15 times without seeing it! I knew that it should start from 1 so I completely overlooked it. Thank you for that, this is a little embarrassing I must say.


Now we are back to focusing on improving the performance and this new method of memory allocation had no effect on performance I'm afraid. It still stands on 0.4 seconds of CPU time with is far from the 0.02 seconds that is supposedly achievable with that gcc compiler.


I know that one could merge the edge finder / coastline evaluation with the floodfill algorithm so that the program counts the coastline segments as it floods the oceanArray.


I tried something else. This "queue"-thing confuses the lot of me to say the least. I have tried different ways to prevent the program from iterating through the queue as it seems to be hogging a heluva lot of CPU. I was thinking that the oceanMask matrix may contain that information so I figured that I could add

Code:

    if(oceanArray[element.x][element.y])
       return;

at the beginning of the pushQueue() function. That only improved performance by 0.01 seconds. So it was back to the drawing board again. The problem with oceanArray() is that there are unmasked pixels waiting in the queue so that method is pretty much a hit and miss and may save just a little bit of computations. I created another two-dimensional array in the same way as "oceanMask" and "worldArray" called "queueArray". Then I changed the "maskOcean()" function to:

Code:

void maskOcean(int row, int col) {
    Pixel pushElement;
    pushElement.x = row;
    pushElement.y = col;
    pushQueue(pushElement);
    while(queueLength > 0) {
        Pixel popElement;
        popElement = popQueue();
        oceanArray[popElement.x][popElement.y] = true;
        int offset[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
        for(int i = 0;i < 4;++i) {
           int maskX = popElement.x + offset[i][0];
           int maskY = popElement.y + offset[i][1];
            if(isToBeMasked(maskX, maskY)) {
                pushElement.x = maskX;
                pushElement.y = maskY;
                pushQueue(pushElement);
                queuedArray[maskX][maskY] = true;
            }
        }
    }
}

so now all of the pixels in the queue were flagged in the queuedArray array array. So I have

Code:

    if(queuedArray[element.x][element.y])
       return;

at the beginning of the pushQueue() function.


And guess what; the performance improved down to 0.06s!