-1

I am trying to de-reference the 2D array inside the function islandPerimeter.
But I cannot understand why I am getting segfault for this.
Can someone point out what exactly I am doing wrong?

update: So this was a part of a problem from leetcode I was trying to solve.I now understand it is not 2D array but a pointer. I am still confused over the int**. can someone explain it? 

#include <stdio.h>

int islandPerimeter(int** grid, int gridSize, int gridColSize)
{
    int perimeter=0,points=4,i=0;

    for(int row=0;row<gridSize;++row)
    {
        for(int col=0;col<gridColSize;++col)
        {
            printf("%d ",grid[row][col]);
        }
    }
    return perimeter;
}


int main()
{
    int arr[4][5] = {{8,1,0,0,0},
                     {1,1,1,0,0},
                     {0,1,0,0,0},
                     {1,1,0,0,0}};

    islandPerimeter(arr,4,5);

    return 0;
}
Improve this question
6
  • 3
    int[][] is not the same as int ** Commented Mar 3, 2020 at 0:47
  • The compiler has no way to know the dimensions of the int** you pass in. I don't know why it compiled or segfaulted, but I can see how it would not work right without that info. Chris is right with his solution. Commented Mar 3, 2020 at 0:52
  • @donjuedo depending on the compiler and its flags it would have only issued a warning for the incompatible type. Commented Mar 3, 2020 at 0:54
  • 2
    int** grid --> int (*grid)[5] Commented Mar 3, 2020 at 0:56
  • int** grid is not a 2D array. grid is a pointer. Commented Mar 3, 2020 at 1:04

4 Answers 4

Reset to default
3

A Pointer to Array

An array is a distinct type in C. It is a sequential collections of elements of a given type. In C a 2D array is actually an array of 1D arrays. In your case, you have an array [4] of int [5] (e.g. 4 - 5-elements arrays of int commonly called a 2D array of int)

Where new programmers normally get confused is how an array is treated on access. When an array is accessed, it is converted to a pointer to the first element. C11 Standard - 6.3.2.1 Other Operands - Lvalues, arrays, and function designators(p3) (pay attention to the 4 exceptions)

In the case of a 1D array, that is simple, the array is converted to a pointer to the first element of the array (the pointer is simply int*). In the case of a 2D array, the same holds true, the array is converted to a pointer to the first element -- but that first element is a 1D array of 5-int. (the pointer is a pointer-to-array of int [5], formally int (*)[5])

You can pass the 2D array (in your case) as a parameter of either int grid[4][5], int grid[][5], or to reflect that the array is converted to a pointer to the first element, int (*grid)[5]. The key is you must always provide the number of elements in the final dimension for your array (with additional '*' allowed for circumstances not relevant here) The 5 (or number of elements) must be an integer constant which is known at compile-time unless using a Variable Length Array (VLA), which are the topic for a separate discussion.

The same rule that on access an array is converted to a pointer to its first element applies to each dimension in your array, be it a 2D array or a 6D array. C11 Standard - 6.5.2.1 Array subscripting(p3)

Additionally, know the difference between a pointer-to-array (e.g. int (*grid)[5]) and an array-of-pointers (e.g. int *grid[5]). The parenthesis are required due to C Operator Precedence, the [..] has higher precedence than '*' in this case, so to require that *grid (in int *grid[5]) be evaluated as a pointer (instead of as an array grid[5]) you enclose it is parenthesis (*grid). Thus resulting in a pointer-to-array of int [5], (int (*grid)[5]) instead of an array-of-pointers to int (5 of them) with int *grid[5].

A Pointer to Pointer

Contrast that with a pointer-to-pointer (e.g. int **, commonly called a double-pointer). You have two-levels of indirection represented by the two **. The pointer itself is a single-pointer -- to what? (another pointer, not to an array). You will generally use a double-pointer by first allocating a block of memory to hold some number of pointers, such as when you are dynamically allocating for an unknown number of allocated objects. This can be an unknown number of rows of an unknown number of columns of int or it can be an unknown number of strings, or a unknown number of structs, etc.. The key is your first level of indirection points to memory containing pointers.

Then for each of the available pointers you can allocate a block (e.g. in your case to hold 5 int and then assign the starting address for that block of memory to your first available pointer). You continue allocating for your columns (or strings or structs) and assigning the beginning address to each of your available pointers in sequence. When done, you can access the individual elements in your allocated collection using the same indexing you would for a 2D array. The difference between such a collection and a 2D array of arrays -- is the memory pointed to by each pointer need not be sequential in memory.

Telling Them Apart

The key to knowing which to use is to ask "What does my pointer point to?" Does it point to a pointer? Or, does it point to an array? If it points to another pointer, then you have a pointer-to-pointer. If the thing pointed to is an array, then you have a pointer-to-array. With that, you know what you need as a parameter.

Why the SegFault with int**

Type controls pointer arithmetic. Recall above, int** is a pointer-to-pointer, so how big is a pointer? (sizeof (a_pointer) - usually 8-bytes on x86_64, or 4-bytes on x86). So grid[1][0] is only one-pointer (8-bytes) away from grid[0][0]. What about the pointer-to-array? Each increment in the first index is a sizeof (int[5]) apart from the first. So in the case of a 4x5 array grid[1][0] is 5 * sizeof(int) (20-bytes) apart from grid[0][0].

So when attempting to access your array of arrays, using int**, beginning with grid[1][3] (or grid[1][4] on a 32-bit box) you are reading one-past the end of the 1st row of values. (you have offset by 8-bytes (one-pointer 8-bytes - skipping 2-int), placing you just before the 3rd integer in the 1st row, then offset 3 more integers placing you at what would be grid[0][5] one past the last value in the 1st row grid[0][4]. (this compounds with each row increment) The result is undefined and anything can happen.

When you pass the appropriate pointer-to-array, each increment of the row-index offsets by 20-bytes, placing you at the beginning of the next 1D array of values so iterating over each column remains within the bounds of that 1D array.

Think through it, and if you have further questions, just let me know and I'm happy to help further.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

int** grid is a pointer to pointer to int. It lacks information of the array width.

With C99 or C11 onwards with optional variable length arrays:

// int islandPerimeter(int** grid, int gridSize, int gridColSize)
int islandPerimeter(int gridSize, int gridColSize, int grid[gridSize][gridColSize]) {
  int perimeter=0;

  for(int row=0;row<gridSize;++row) {
    for(int col=0;col<gridColSize;++col) {
      printf("%d ",grid[row][col]);
    }
  }
  return perimeter;
}

Call with 

islandPerimeter(4, 5, arr);
Improve this answer

Comments

0

Try this

int islandPerimeter(int* grid, int gridSize, int gridColSize) {
    int perimeter = 0, points = 4, i = 0;

    for(int row=0; row < gridSize; ++row) {
        for(int col = 0; col < gridColSize; ++col) {
          printf("%d ",grid[row*gridColSize + col]);
        }
    }
    return perimeter;
}

You will have to change the call to

islandPerimeter((int *)grid, 4, 5);
Improve this answer

3 Comments

Note that the implementer must also change the declaration of arr and its initialization
@dvhh Would the declaration/initialization have to change? From how I understand it, the array is laid out contiguously in memory, so indexing it as in my answer should work.
Consider avoiding the cast. islandPerimeter(grid[0], 4, 5);
0

Let's say you wanted to leave your function as-is and instead change how the 2D array was initialized in main(or any other calling function). This is also what you would have to do if the array data was entered by a user or loaded from a file at runtime, so it's useful to know:

int main(void) {
    const int ROWS = 4;  //these don't have to be const;
    const int COLS = 5;
    const int data[20] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

    int** pointer_arr = malloc(ROWS * sizeof(int*)); //allocate space for each ptr
    //error check
    if (pointer_arr == NULL) {
        printf("Unsuccessful ptr-ptrarray allocation attempt\n");
        exit(0);
    }

    for (int i = 0; i < ROWS; ++i) {
        pointer_arr[i] = malloc(COLS * sizeof(int));  //allocate space for each int
        //error check with alternative indexing syntax (same as pointer_arr[i])
        if (*(pointer_arr + i) == NULL) {
            printf("Unsuccessful ptr-intarray allocation attempt\n");
            exit(0);
        }
    }
    //load each allocated int address space with an int from data:
    for (int i = 0; i < ROWS ; ++i) {
        for (int j = 0; j < COLS; ++j) {
            pointer_arr[i][j] = data[ROWS * i + j];
        }
    }
    //Now you can call your unaltered function and it will perform as expected: 
    islandperimeter(pointer_arr, ROWS, COLS);
    return 0;
}

Under normal conditions (when the program doesn't terminate at once) note that you would then have to manually free all that allocated memory, or suffer a memory leak.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.