Array for valid knight moves in chess (C)

Question

for my college project I was asked to write the function: chessPosArray*** validKnightMoves(). The question specifies the function should return a two dimensional dynamic array of pointers to arrays of the possible positions the knight can land on from each starting position on the board.

when I attempt to print what is in the array the program doesn't print anything and exits with code -1073741819

Here is the Code:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef char chessPos[2];

typedef struct _chessPosArray 
{
    unsigned int size;
    chessPos* positions;
} chessPosArray;

chessPosArray*** validKnightMoves();
void checkKnightMoves(chessPosArray*** arrptr, int row, int col);

int main() 
{
    chessPosArray ***arr = validKnightMoves();

    printf("%d\n", arr[3][3]->size);

    return 0;
}

chessPosArray*** validKnightMoves() 
{
    /// To make a two dimensional dynamic array we will make an array for the rows - each row will point to an array of columns
    chessPosArray*** arr = malloc(sizeof(**arr) * 8);
    if (arr == NULL)
    {
        printf("allocation falliure");
        exit(1);
    }

    for(int i = 0; i < 8; i++) //each column will have a pointer to a pointer 
    {
        arr[i] = (chessPosArray**)malloc(sizeof(*arr) * 8);
        if (arr[i] == NULL)
        {
            printf("allocation falliure");
            exit(1);
        }
    }
    
    for (int i = 0; i < 8; i++) //here we will check each space on the board too see where the knight can move from it (using a function)
    {
        for(int j = 0; j < 8; j++) 
        {
            checkKnightMoves(arr, i, j);
        }
    }
    
    return arr;
}

void checkKnightMoves (chessPosArray *** arrptr, int row, int col) //This function will check all possible movments for the knight
{
    int newx, newy;
    int counter = 0;
    int physicalsize = 1;

    int dx[8] = { 2, 2, 1, 1, -1, -1, -2, -2 };
    int dy[8] = { 1, -1, 2, -2, 2, -2, 1, -1 };
    
    arrptr[row][col]->positions = (chessPos*)malloc(sizeof(chessPos));
    if (arrptr[row][col]->positions == NULL)
    {
        printf("allocation falliure");
        exit(1);
    }

    for(int i = 0; i < 8; i++) 
    {
        newx = row + dx[i];
        newy = col + dy[i];

        if(newx > 0 && newy > 0 && newx <= 8 && newy <= 8) 
        {
            if(counter > physicalsize) 
            {
                realloc(arrptr[row][col]->positions, sizeof(chessPos) * 2);
                if (arrptr[row][col]->positions == NULL)
                {
                    printf("reallocation faliure");
                    exit(1);
                }
                physicalsize *= 2;
            }
            
            sprintf(arrptr[row][col]->positions[counter], "%c%c", newx+'A'-1, newy + '0');
            counter++;
        }
    }

    arrptr[row][col]->size = counter;
}

My main should have printed the number 8 as this is the amount of valid moves the knight can take from that position but it did not print anything.

Answer 1

There may be other issues, but this one is definitely incorrect:

if(counter > physicalsize) 
{
    realloc(arrptr[row][col]->positions, sizeof(chessPos) * 2);
    if (arrptr[row][col]->positions == NULL)
    {
        printf("reallocation failure");
        exit(1);
    }
    physicalsize *= 2;
}

Two problems there:

1. You always realloc storage for only two chessPos values. It appears that what you were actually trying to do is double the size of the storage.

2. You don't store the returned pointer. realloc can actually move your data to a new memory location. It returns a pointer to the start of the reallocated memory, which may or may not be the same pointer.

So, this should be something like:

if(counter > physicalsize) 
{
    int newsize = physicalsize * 2;
    chessPos* positions = arrptr[row][col]->positions;
    positions = realloc(positions, sizeof(chessPos) * newsize);
    if (positions == NULL)
    {
        printf("reallocation faliure");
        exit(1);
    }
    arrptr[row][col]->positions = positions;
    physicalsize = newsize;
}

On an unrelated note, the 'valid' test before this is checking newx <= 8 && newy <= 8 which is incorrect. The value 8 is not a valid position. You should test newx < 8 && newy < 8.

---

But you're not out of the woods yet. This 3-star-programmer approach is muddying the waters and you actually failed to allocate storage for your chessPos objects at all. What you've done is allocate 8 rows of 8 columns of uninitialized pointers.

If you run the program in a debugger, you'll find that it crashes on this call:

arrptr[row][col]->positions = malloc(sizeof(chessPos));

Why? Well, when you dereference arrptr[row][col] to access the positions field, you're following a pointer into the unknown and anything can happen.

I recommend you simplify your program to store your data as a chessPosArray** instead. The allocation looks like this:

chessPosArray** validKnightMoves() 
{
    chessPosArray** arr = malloc(sizeof(*arr) * 8);
    if (arr == NULL)
    {
        printf("allocation falliure");
        exit(1);
    }

    for(int i = 0; i < 8; i++)
    {
        arr[i] = (chessPosArray*)malloc(sizeof(*arr[i]) * 8);
        if (arr[i] == NULL)
        {
            printf("allocation falliure");
            exit(1);
        }
    }
    
    for (int i = 0; i < 8; i++)
    {
        for(int j = 0; j < 8; j++) 
        {
            checkKnightMoves(arr, i, j);
        }
    }
    
    return arr;
}

And then you make the appropriate changes to checkKnightMoves. That means accessing fields via the . operator instead of ->. e.g.

arrptr[row][col].positions = malloc(sizeof(chessPos));

And so on...

---

But, you're STILL not out of the woods!

This right here has a buffer overflow:

sprintf(arrptr[row][col].positions[counter], "%c%c", newx+'A'-1, newy + '0');

Why? Because sprintf writes a null-terminated string. Your data type only has storage for 2 characters, but this call writes 3. There's no need to use sprintf at all here. Instead, just:

chessPos* pos = &arrptr[row][col].positions[counter];
pos[0] = newx + 'A';
pos[1] = newy + '0';

But now, don't expect that to be a string you can pass via %s in a printf call. It's not null-terminated. Perhaps what you actually wanted was to use sprintf but make your data type large enough:

typedef char chessPos[3];

---

Is that all? Maybe. You do still have memory leaks, because your program doesn't clean up. At least it doesn't crash.

You should debug further. Note that I picked up all these issues by just turning on GCC's address sanitizer with -fsanitize=address. It's a very useful tool. I also recommend enabling all warnings with -Wall.