The code roughly works like this: given in input a matrix and the value of it's columns and rows the algorithm searches the shortest path with a preference for certains cells to move on.
Here is the part of the code I am talking about:
/* Function to find the shortest path in the matrix using BFS */
void findShortestPath(Matrix *matrix, Result *bestResult) {
int numRows = matrix->rows;
int numCols = matrix->cols;
int **visited = (int **)malloc(numRows * sizeof(int * ));
int i, newDistance, newBadCells, newNegativeCells, row, col, distance, badCells, negativeCells;
int dx[] = {
-1,
1,
0,
0
};
int dy[] = {
0,
0,
-1,
1
};
BFSNode currentNode;
BFSNode *queue = (BFSNode *)malloc(numRows * numCols * sizeof(BFSNode));
int queueSize = 0;
char *path;
char *check = "";
for (i = 0; i < numRows; i++) {
visited[i] = (int *)malloc(numCols * sizeof(int));
memset(visited[i], 0, numCols * sizeof(int));
}
enqueue(queue, &queueSize, createBFSNode(0, 0, 0, 0, 0, ""));
while (queueSize > 0) {
qsort(queue, queueSize, sizeof(BFSNode), priorityCompare);
currentNode = dequeue(queue, &queueSize);
row = currentNode.point.row;
col = currentNode.point.col;
distance = currentNode.distance;
badCells = currentNode.badCells;
negativeCells = currentNode.negativeCells;
path = currentNode.path;
if (row == numRows - 1 && col == numCols - 1) {
if (bestResult->distance == -1 || distance < bestResult->distance) {
bestResult->distance = distance;
bestResult->badCells = badCells;
bestResult->negativeCells = negativeCells;
free(bestResult->path);
bestResult->path = strdup(path);
} else if (distance == bestResult->distance && negativeCells > bestResult->negativeCells) {
bestResult->badCells = badCells;
bestResult->negativeCells = negativeCells;
free(bestResult->path);
bestResult->path = strdup(path);
}
continue;
}
visited[row][col] = 1;
for (i = 0; i < 4; i++) {
int newRow = row + dy[i];
int newCol = col + dx[i];
if (isValidMove(matrix, newRow, newCol, visited)) {
char *newPath = (char *)malloc((strlen(path) + 2) * sizeof(char));
if (newPath == NULL) {
fprintf(stderr, "Memory allocation error.\n");
exit(EXIT_FAILURE);
}
strcpy(newPath, path);
if (i == 0) {
newPath[strlen(path)] = 'O';
} else if (i == 1) {
newPath[strlen(path)] = 'E';
} else if (i == 2) {
newPath[strlen(path)] = 'N';
} else if (i == 3) {
newPath[strlen(path)] = 'S';
}
newPath[strlen(path) + 1] = '\0';
newDistance = distance + 1;
newBadCells = badCells + (matrix->matrix[newRow][newCol] == 0);
newNegativeCells = negativeCells + (matrix->matrix[newRow][newCol] == -1);
enqueue(queue, & queueSize, createBFSNode(newRow, newCol, newDistance, newBadCells, newNegativeCells, newPath));
visited[newRow][newCol] = 1;
}
}
if (path == check) {} else {
free(path);
}
}
for (i = 0; i < numRows; i++) {
free(visited[i]);
}
free(visited);
free(queue);
}
This variable that causes a memory leak is newPath but it's not that simple, let me explain
The memory allocation works like this: The queue starts with an empty/starter node with no memory allocated for the path Then for every node following that a path is allocated as "newPath" each time before enqueueing the node and it's later on freed as "path" when dequeueing the node.
Through debugging I have found out that the amount of **free**() is one short than the **malloc**() amount so it ends up not being able to free one block of memory
All the other memory is allocated and freed correctly
I've tried many different implementations to solve the problem but they all failed doing so
Some of them were:
while (queueSize > 0) {
qsort(queue, queueSize, sizeof(BFSNode), priorityCompare);
currentNode = dequeue(queue, & queueSize);
row = currentNode.point.row;
col = currentNode.point.col;
distance = currentNode.distance;
badCells = currentNode.badCells;
negativeCells = currentNode.negativeCells;
/* With a switch check if it's the first node or not then free path before the new value is assigned */
path = currentNode.path;
or
freeing path an additional time after the while is ended
EDIT Hopefully the indentation is fixed now
newPath is freed through path as they share the same memory allocation
Could any of you help me figure out a way to fix this issue? Thank you all for your time and help!
When you accept a result as the (to-date) best, you do this (in both control paths):
free(bestResult->path); bestResult->path = strdup(path);
and then continue to the next iteration of the loop. Thus, you skip the code that frees the path of the current node, and that node object is then lost. That's your leak. You could in fact leak more than one allocated object, depending on the input.
I suppose you are performing that strdup() instead of a simple assignment because the current node's path may sometimes be a pointer to a string literal, which downstream code consuming the shortest path result must not try to free. But this has forced you to make several distortions to your code. Instead, why not prevent any node containing such a path pointer in the first place?
Additional recommendations:
don't rely on the caller-provided initial contents of *bestResult unless that's really what you mean to do. I'm inclined to think it's not, but that's hard to say.
avoid simulating multi-dimensional arrays via arrays of pointers. You cannot use variable-length arrays in C90, but you can still simulate 2D arrays on top of 1D arrays, and this can be both cleaner and faster.
declare your variables in the narrowest possible scope.
do not declare multiple variables in the same statement.
prefer to assign initial values to your variables in their declarations when that is feasible
do not cast the result of malloc etc.
prefer calloc() over malloc() + memset-to-zero.
generally speaking, compute allocation sizes based on the variable to which you are assigning the resulting pointer. This is more resilient and less error-prone than hard-coding a data type in the size calculation.
Generally speaking, don't say sizeof(char), as this is 1 by definition.
prefer to minimize code duplication. This is a fair justification for a small number of unneeded computations.
consider not writing to the out parameter until you have a final value for it. This preserves the caller's original value in the event that the function fails.
consider declaring pointer parameters as pointers to const objects when the function indeed can promise to not modify the pointed-to object.
find a better way to do that path concatenation.
For example,
/* Function to find the shortest path in the matrix using BFS */
void findShortestPath(const Matrix *matrix, Result *bestResult) {
static const int dx[] = { -1, 1, 0, 0 };
static const int dy[] = { 0, 0, -1, 1 };
static const char dir[][2] = { "O", "E", "N", "S" };
int numRows = matrix->rows;
int numCols = matrix->cols;
// Note: this restructuring will require changes to isValidMove(), too:
int *visited = calloc(numRows * numCols, sizeof(*visited));
#define VISITED(r, c) (visited[(r) * numCols + (c)])
BFSNode *queue = malloc(numRows * numCols * sizeof(*queue));
int queueSize = 0;
enqueue(queue, &queueSize, createBFSNode(0, 0, 0, 0, 0, strdup("")));
// Reproduce the original code's dependence on the initial value
// of *bestResult:
Result workingBest = *bestResult;
// Alternatively:
// Result workingBest = { -1, 0, 0, NULL }; // check element order
while (queueSize > 0) {
qsort(queue, queueSize, sizeof(*queue), priorityCompare);
BFSNode currentNode = dequeue(queue, &queueSize);
int row = currentNode.point.row;
int col = currentNode.point.col;
// Check member order:
Result result = {
currentNode.distance,
currentNode.badCells,
currentNode.negativeCells,
currentNode.path
};
if (row == numRows - 1 && col == numCols - 1) {
if ((workingBest.distance == -1)
|| (result.distance < workingBest.distance)
|| (result.distance == workingBest.distance
&& result.negativeCells > workingBest.negativeCells)) {
free(workingBest.path);
workingBest = result;
}
continue;
}
VISITED(row, col) = 1;
int i;
for (i = 0; i < 4; i++) {
int newRow = row + dy[i];
int newCol = col + dx[i];
if (isValidMove(matrix, newRow, newCol, visited)) {
char *newPath = malloc(strlen(result.path) + 2);
if (newPath == NULL) {
fprintf(stderr, "Memory allocation error.\n");
exit(EXIT_FAILURE);
}
sprintf(newPath, "%s%s", result.path, dir[i]);
int newDistance = result.distance + 1;
int newBadCells = result.badCells + (matrix->matrix[newRow][newCol] == 0);
int newNegativeCells = result.negativeCells + (matrix->matrix[newRow][newCol] == -1);
enqueue(queue, &queueSize, createBFSNode(
newRow, newCol, newDistance, newBadCells, newNegativeCells, newPath));
VISITED(newRow, newCol) = 1;
}
}
free(result.path);
}
free(visited);
free(queue);
*bestResult = workingBest;
#undef VISITED
}