Thread: This code gives rise to segmentation fault

  1. #1
    Registered User
    Join Date
    Nov 2015
    Posts
    72

    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.
    Last edited by bot; 12-28-2017 at 10:29 AM.

  2. #2
    Registered User
    Join Date
    Jun 2011
    Posts
    4,509
    You may want to run your code through a debugger to find the problem. You are likely accessing memory you aren't allowed to.

    You should not cast malloc, and you should check the return value of malloc for success.

  3. #3
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    A quick look suggests you may not be respecting your borders.
    Should the initial maskOcean call be 0,0?
    Should the evaluateCoastLength function be starting row and col at 0?
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  4. #4
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    I'm unable to troubleshoot with the debugger because I don't have access to the data that gives rise to the exception. The program is compiled and tested on a website and all you get is whether it failed or succeeded on the tests (26 of them).

    So instead of
    Code:
    bool **worldArray;
        worldArray = (bool**) malloc((nRows + 2)* sizeof(bool*));
           for(int i = 0; i <= nRows + 1; ++i)
                worldArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
    ...
    I should use:
    Code:
    bool **worldArray;
    bool (*worldArray)[nRows+2] = malloc(sizeof * bool[nRows+2] * (nCols+2)));
    ...
    ?
    Last edited by bot; 12-28-2017 at 11:11 AM.

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    Quote Originally Posted by bot View Post
    The program is compiled and tested on a website
    Can you give a link to the problem description on the website?
    (And did you see my previous post?)
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  6. #6
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    Quote Originally Posted by john.c View Post
    A quick look suggests you may not be respecting your borders. Should the initial maskOcean call be 0,0? Should the evaluateCoastLength function be starting row and col at 0?
    The variables nRows and nCols are the number of rows and columns of the map that is fed into the program. I let the program surround the the map with a border of 0's. So the actual matrix has (nRows+2) x (nCols+2) elements. The 0's mean that it starts from index 0. The 2Dimensional arrays have indices ranging from 0 to nCols+1 and 0 to nRows+1 respectively.

    The program should respect these boundaries, the routine:
    Code:
    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;
    }
    ensures that, and the routine

    Code:
    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;
    }
    

    only goes to nCols+1 because it compares element i with element i+1. It counts edges between land and water by sweeping horizontally and vertically on the masked coast that is generated by a flood fill algorithm.
    Last edited by bot; 12-28-2017 at 11:08 AM.

  7. #7
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    See page 9 of the following document for problem description:

    http://challenge.csc.kth.se/2011/problems.pdf

  8. #8
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    Taking a closer look this time, I note that you are making inputRow 1 char too small. Since you're reading it as a string, it needs a space for the terminating '\0'.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  9. #9
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    Yes, yes, that solved my problem and the website accepted my program. Thank you! Tank you!

    It also runs fine now in the Windows environment.

    I find it rather strange that it doesn't crash consistently in a Linux environment.

  10. #10
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    Quote Originally Posted by bot View Post
    I find it rather strange that it doesn't crash consistently in a Linux environment.
    It's a mystery! And a pain in the, well, just a pain.

    You probably want to malloc inputRow before the loop and free it afterwards. And you may as well make it local. You should, of course, make pretty much all of your variables local, but you probably know that. And we often use shortcuts when solving programming contest problems.

    You can allocate your 2D arrays more efficiently like this (allocating the data portion contiguously and then assigning the row pointers). And by callocing the data, you don't need to manually zero out the worldArray border (or "reset" floodArray and removalMask).
    Code:
    void allocateMemory() {
        floodQueue = malloc(QUEUE_LENGTH * sizeof *floodQueue);
        startQueue = 0;
        endQueue = 0;
        maxQueue = QUEUE_LENGTH - 1;
    
        int NROWS = nRows + 2, NCOLS = nCols + 2;
        worldArray = malloc(NROWS * sizeof *worldArray); // row pointer array
        worldArray[0] = calloc(NROWS * NCOLS, sizeof *worldArray[0]); // data
        floodArray = malloc(NROWS * sizeof *floodArray);
        floodArray[0] = calloc(NROWS * NCOLS, sizeof *floodArray[0]);
        removalMask = malloc(NROWS * sizeof *removalMask);
        removalMask[0] = calloc(NROWS * NCOLS, sizeof *removalMask[0]);
        for(int i = 1; i < NROWS; ++i) { // assign row pointers
            worldArray[i] = worldArray[i - 1] + NCOLS;
            floodArray[i] = floodArray[i - 1] + NCOLS;
            removalMask[i] = removalMask[i - 1] + NCOLS;
        }
    }
    Then in main, you free them like this:
    Code:
        free(worldArray[0]);  // free data
        free(worldArray);     // free row pointers
        free(floodArray[0]);
        free(floodArray);
        free(removalMask[0]);
        free(removalMask);
        free(floodQueue);
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  11. #11
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    Yes, I actually am in the process of optimizing the code. Something in the program that I was thinking that was using CPU cycles is the requeue() function. I was thinking that shuffling data back and forth all the time must cost CPU. So I tried instead to use something that looks like a ringbuffer instead, i.e. replacing popQueue(), pushQueue() and requeue() with:

    Code:
    int queueLength = 0;
    
    void pushQueue(Pixel element) {
        for(int q = startQueue; q < startQueue + queueLength; ++q)
           if(element.x == floodQueue[q % maxQueue].x)
              if(element.y == floodQueue[q % maxQueue].y)
                 return;
        floodQueue[endQueue] = element;
        endQueue = ++endQueue % maxQueue;
        if(queueLength == maxQueue)
           startQueue = ++startQueue % maxQueue;
        else
           ++queueLength;
    }
    
    
    Pixel popQueue() {
        if(queueLength > 0) {
           --queueLength;
           int popIndex = startQueue;
           startQueue = ++startQueue % maxQueue;
           return floodQueue[popIndex];
        } else {
            printf("Empty queue, popQueue() abuse!\n");
            Pixel nonPixel;
            nonPixel.x = -1;
            nonPixel.y = -1;
            return nonPixel;
        }
    }
    But that lowered performance instead. The first program takes 0.4 seconds to compute and with the replacement it now takes 2.4 seconds to compute! I don't understand the slowdown. It seems that frequent calls to the modulus operator hogs more CPU than calling to memory. I tried unwinding that for-loop that checks for element uniqueness in the queue, i.e.:

    Code:
    void pushQueue(Pixel element) {
        int queueExtension = startQueue + queueLength;
        if (queueExtension > maxQueue) {
           int endPoint = queueExtension % maxQueue;
            for(int q = startQueue; q < maxQueue; ++q)
               if(element.x == floodQueue[q].x)
                  if(element.y == floodQueue[q].y)
                     return;
            for(int q = 0; q < endPoint; ++q)
               if(element.x == floodQueue[q].x)
                  if(element.y == floodQueue[q].y)
                     return;
        else
            for(int q = startQueue; q < endQueue; ++q)
               if(element.x == floodQueue[q].x)
                  if(element.y == floodQueue[q].y)
                     return;
        }
        floodQueue[endQueue] = element;
        endQueue = ++endQueue % maxQueue;
        if(queueLength == maxQueue)
           startQueue = ++startQueue % maxQueue;
        else
           ++queueLength;
    }
    and that improved performance back to 0.49s, which is still worse than the first program. I know that this problem can be solved with a performance of 0.02s and I am far from that

    I will look into the malloc/calloc routines tomorrow. Yes, I was taking a few shortcuts. Other enhancements would also be to handle exceptions etc, but here we assume that the input is always correct and focus on performance only.
    Last edited by bot; 12-28-2017 at 08:21 PM.

  12. #12
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    I think you should use
    Code:
    worldArray[i] = worldArray[i - 1 + NCOLS];
    instead of
    Code:
    worldArray[i] = worldArray[i - 1] + NCOLS;

    As I understand, 2-dimensional arrays are stored as a 1-dimensional vector in memory, so the contents of the next row is located at worldArray[i - 1 + NCOLS]. But I don't understand that assignment; by that logic worldArray[i - 1 + NCOLS] should be equal worldArray[i - 1 + 2 * NCOLS] and so on which doesn't make any sense to me. Perhaps the assignment should be worldArray[i] = &worldArray[i - 1] + NCOLS ? I'm a bit confused here.


    Anyway, your modification compiles and runs fine in a Windows environment but not in a Linux environment (segmentation fault), I'm baffled!


    I have rewritten the code, I have found that floodArray is no longer needed, it is a remnant from another algorithm that I used that traced boundaries, an algorithm that I scrapped. And I found that oceanArray is a better name than removalMask which is another remnant from when the world was analyzed island by island that were removed one by one as the program worked its way through the world.




    But still, I assume that this only improves performance of the memory allocation and not the computations, should it work properly in that Linux environment.
    Last edited by bot; 12-28-2017 at 09:23 PM.

  13. #13
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    Quote Originally Posted by bot View Post
    I think you should use
    Code:
    worldArray[i] = worldArray[i - 1 + NCOLS];
    instead of
    Code:
    worldArray[i] = worldArray[i - 1] + NCOLS;
    No. It's correct the way I originally demonstrated. Try it on Linux that way and it shouldn't crash. Even on Windows it's still an error the way you're doing it, but I guess it just doesn't happen to access unallocated memory. Or, if you're using two different machines, one could be 64 bit (presumably the Linux) and the other 32-bit. That might make a difference.

    In your previous code (that you may not be using anymore) you had a sequence point error (possible undefined behavior). You're not allowed to modify an object more than once per sequence point, but this does so twice:
    Code:
        endQueue = ++endQueue % maxQueue;
    It should be recoded as:
    Code:
        endQueue = (endQueue + 1) % maxQueue;
    Same with the two other similar lines.

    The way you're handling queueLength looks a little fishy to me. When it reaches maxQueue, that would seem to be an unrecoverable error, but you adjust startQueue and keep going.

    Anyway, you should maybe post your current code.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

  14. #14
    Registered User
    Join Date
    Nov 2015
    Posts
    72
    Sorry but it doesn't compile at all on any platform with "worldArray[i] = worldArray[i - 1] + NCOLS;", I hope you are aware that this is an array of booleans, not integers. I had a little hope to gain some performance and lower memory usage by using booleans but perhaps this is not the case eh? The Windows environment is 64-bit but I could launch a 32 bit environment. The Linux environment uses gcc version gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 20160609 with the following flags:
    Code:
    -g -O2 -std=gnu99 -static {files} -lm
    and I cannot change that.

    Replacing lines containing "endQueue = ++endQueue % maxQueue;" with "endQueue = (endQueue + 1) % maxQueue;" didn't improve performance one bit.

    I'm not sure what's so fishy about queueLength. I have defined startQueue as the index at which the first element in the queue resides and endQueue as the index at which the next element will be added when calling pushQueue(element). That way these indices will know where to be if the queue is empty; startQueue == endQueue either means that the queue is full or is empty. So instead of rearranging the queue to prevent indices from exceeding the limit as shown above, I let the indices spinning round round round like in a ring without really touching the elements in the queue. But invoking the modulus for each index in the uniqueness test seems to hog a lot of CPU cycles.

    So the fastest version of my program looks like this:

    Code:
    #include <stdio.h>
    #include <stdbool.h>
    #include <stdlib.h>
    
    
    bool **worldArray;
    bool **oceanArray;
    int nRows, nCols;
    char *inputRow;
    
    
    typedef struct {
        int x;
        int y;
    } Pixel;
    
    
    void allocateMemory();
    void extractInput();
    void resetMask();
    
    
    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());
        
        for (int i = 0; i < nRows + 2; ++i) {
            free(worldArray[i]);
            free(oceanArray[i]);
        }
        free(floodQueue);
        free(worldArray);
        free(oceanArray);
        
        return 0;
    }
    
    
    void allocateMemory() {
        worldArray = (bool **) malloc((nRows + 2)* sizeof(bool *));
        oceanArray = (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));
            oceanArray[i] = (bool *) malloc((nCols + 2) * sizeof(bool));
        }
    }
    
    
    void extractInput() {
        for(int row = 0; row < nRows; ++row) {
            inputRow = (char *) malloc ((nCols + 1) * 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) {
                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;
    }
    I have made the queue length as small as possible. In order to use my ring buffer instead, remove the functions requeue(), popQueue() and pushQueue() and replace them with the functions in the first textbox in post #11 at the end. You may want to declare an int named queueLength = 0 at the top of the code. If you want to improve the ringbuffer as discussed, then replace the pushQueue() function with the function in the second textbox of post #11.

    The new method of allocating memory looks like so:

    Code:
    ...
    
    bool **worldArray;
    bool **oceanArray;
    int nRows, nCols;
    
    ...
    
    
    int main(int argc, const char * argv[]) {
        if(scanf("%d%d", &nRows, &nCols) == 2) {
            allocateMemory();
    
    
        ...
        
        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] = malloc(NROWS * NCOLS, sizeof *worldArray[0]);
        oceanArray = malloc(NROWS * sizeof *oceanArray);
        oceanArray[0] = calloc(NROWS * NCOLS, sizeof *oceanArray[0]);
        
        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];
        }
    }
    (no need to calloc the worldArray as it will be filled with data anyway, only the surrounding border indices need to. The oceanArray otoh needs to...)

    Some relevant testdata can be found in the following beezipped tarball:

    http://challenge.csc.kth.se/2011/testdata.tar.bz2
    Last edited by bot; 12-29-2017 at 09:17 AM.

  15. #15
    Registered User
    Join Date
    Dec 2017
    Posts
    627
    I never said that correcting the sequence point error would improve performance. It simply makes your program correct, if that kind of thing matters to you.

    Obviously the change that you made could not possibly degrade performance as much as you say. The degradation must be due to something else. The only way I could possibly tell is if you posted both versions of your code.

    I realize the queue is a ring buffer. But queueLength is apparently the total number of queue elements that are in use. If it is equal to queueSize then the queue is full. Please think about it before responding and don't get so snarky.

    About the 2D array allocation. It is correct. You must be doing something wrong. Your way of doing it obviously makes no sense at all:
    Code:
    worldArray[i] = worldArray[i - 1 + NCOLS];
    Think about it. The whole point is to calculate the next pointer value from the previous pointer value. The previous pointer value is worldArray[i - 1], which we therefore must add something to. The correct thing to add is NCOLS.

    Try this:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    #define NROWS  5
    #define NCOLS 10
    
    int main() {
        bool **a = malloc(NROWS * sizeof *a);
        a[0] = calloc(NROWS * NCOLS, sizeof **a);
        // Note that this loop must start at 1, not 0 !
        for (int i = 1; i < NROWS; i++)
            a[i] = a[i - 1] + NCOLS;
    
        for (int r = 0; r < NROWS; r++)
            for (int c = 0; c < NCOLS; c++)
                a[r][c] = (r % 2 + c % 2) % 2 == 0;
    
        for (int r = 0; r < NROWS; r++) {
            for (int c = 0; c < NCOLS; c++)
                printf("%2d ", (int)a[r][c]);
            putchar('\n');
        }
    
        free(a[0]);
        free(a);
        return 0;
    }
    Since you don't seem to appreciate my help, this is the last time I will look at this thread.
    Good luck.
    The world hangs on a thin thread, and that is the psyche of man. - Carl Jung

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SDL code generating Segmentation fault
    By Kotik in forum Game Programming
    Replies: 4
    Last Post: 04-16-2014, 01:01 AM
  2. Why this code gives a segmentation fault error?
    By xianwen in forum C Programming
    Replies: 2
    Last Post: 11-13-2011, 08:09 PM
  3. Segmentation Fault (Can Someone look at my code?)
    By jtkosh in forum C Programming
    Replies: 12
    Last Post: 09-27-2011, 07:06 PM
  4. Help with Segmentation fault - in simple code
    By ramchan in forum C Programming
    Replies: 8
    Last Post: 03-01-2009, 09:07 AM
  5. Help with code segmentation fault
    By blindleaf in forum C Programming
    Replies: 2
    Last Post: 04-10-2003, 03:00 PM

Tags for this Thread