CODEWITHSUNDEEP
cgraphdynamic-memory-allocationbreakpointsrealloc
Kaiyakha
Kaiyakha

Reputation: 1913

Trace/breakpoint trap during reallocation

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?

Upvotes: 2

Views: 237

Answers (1)

Nate Eldredge
Nate Eldredge

Reputation: 58518

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).

Upvotes: 1

Related Questions