I have a graph code written a year ago which does not work now (AFAIR it worked). The graph is implemented with a square matrix which is symmetric respectively to the diagonal. I have omitted a lot of code to keep it as clear as possible, and this is still enough for the error to persist.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct
{
int **matrix;
unsigned size;
} graph;
void init(graph *gptr, int *matrix[], unsigned size)
{
gptr->size = size;
gptr->matrix = malloc(gptr->size * sizeof(*gptr->matrix));
for (unsigned i = 0; i < gptr->size; i )
gptr->matrix[i] = malloc(gptr->size * sizeof(**gptr->matrix));
for (unsigned i = 0; i < gptr->size; i )
for (unsigned j = 0; j <= i; j )
gptr->matrix[i][j] = gptr->matrix[j][i] = matrix[i][j];
}
void add_vertex(graph *gptr, unsigned vertex)
{
for (unsigned i = 1; i < gptr->size; i )
if (gptr->matrix[i][0] == vertex) return;
gptr->size ;
gptr->matrix = realloc(gptr->matrix, gptr->size * sizeof(*gptr->matrix));
for (unsigned i = 0; i < gptr->size; i )
/* ERROR */
gptr->matrix[i] = realloc(gptr->matrix[i], gptr->size * sizeof(**gptr->matrix));
gptr->matrix[gptr->size - 1][0] = gptr->matrix[0][gptr->size - 1] = vertex;
for (unsigned i = 1; i < gptr->size; i )
gptr->matrix[gptr->size - 1][i] = gptr->matrix[i][gptr->size - 1] = -1;
}
#define EDGES 7
#define RANDOM(min, max) min rand() / ((RAND_MAX - 1) / (max - min))
#define MIN -1
#define MAX 9
int **getMatrix(unsigned size)
{
int **matrix = malloc(size * sizeof(*matrix));
for (unsigned i = 0; i < size; i )
{
matrix[i] = malloc((i 1) * sizeof(**matrix));
matrix[i][0] = i;
}
for (unsigned i = 1; i < size; i )
{
for (unsigned j = 1; j < i; j )
do
matrix[i][j] = RANDOM(MIN, MAX);
while (!matrix[i][j]);
matrix[i][i] = rand() % 2 - 1;
}
return matrix;
}
int main(void)
{
int **matrix = getMatrix(EDGES 1);
graph x;
init(&x, matrix, EDGES 1);
add_vertex(&x, EDGES 1);
}
At gptr->matrix[i] = realloc(gptr->matrix[i], gptr->size * sizeof(**gptr->matrix));
the program gets paused by an exception Trace/breakpoint trap
. I have googled for a while, and to me it's most likely there is something wrong with my reallocation, but I have no idea what's wrong. Besides, it works fine on clang
and even on online gcc 7.4
whereas fails to succeed on my gcc 8.1
. Can anyone see where I'm mistaken?
CodePudding user response:
On the first entry to add_vertex
, gptr->size == 8
and gptr->matrix
points to an array of 8 pointers to malloc'ed memory.
gptr->size ;
Now gptr->size == 9
.
gptr->matrix = realloc(gptr->matrix, gptr->size * sizeof(*gptr->matrix));
And now gptr->matrix
points to an array of 9 pointers. gptr->matrix[0] .. gptr->matrix[7]
are the valid malloc'ed pointers from before, and gptr->matrix[8]
contains uninitialized garbage.
for (unsigned i = 0; i < gptr->size; i )
/* ERROR */
gptr->matrix[i] = realloc(gptr->matrix[i], gptr->size * sizeof(**gptr->matrix));
Since gptr->size == 9
, this iterates 9 times, and on the 9th iteration, the garbage pointer gptr->matrix[8]
is passed to realloc
. Not good.
You could iterate the loop gptr->size - 1
times instead, and initialize gptr->matrix[gptr->size - 1] = malloc(...)
separately. Or to be a little lazy and avoid code duplication, you could initialize gptr->matrix[gptr->size - 1] = NULL
before this loop, keep it iterating gptr->size
times, and rely on the handy feature that realloc(NULL, sz)
is equivalent to malloc(sz)
.