In C, how to store and free in the heap a multidimensional map, with rows and columns?

Question

I'm trying to build a data structure, using the C language, which allows me to record strings (representing altitude values) whose data describe some characteristics of points in a map. Each point should have, in addition to the characteristics described by the corresponding string, also a coordinate corresponding to the longitude (column) and one corresponding to the latitude (row).

I would like to output this map as an empty structure by allocating memory in the heap for the rows and columns. The idea is that you have a pointer to a pointer to a pointer to char, for which you allocate memory for an array of pointers to pointers to char, each pointing to the beginning of a row. Each pointer to pointer to char contained in the first array must then have memory allocated for an array of pointers to char.

This will be the basic structure. There is no need at this stage to allocate strings for each of the pointers to char, because the strings will be constructed by reading a text file and then "pointed" to by assigning the addresses corresponding to their beginning. I've tried allocating memory in such a way that pointer arrays are treated as NULL-terminated arrays of pointers, i.e. using a null pointer instead of a nul-byte to define the end of the row array and the end of each series of points on the columns. Based on tests, this strategy worked well: using pointer arithmetic (ie not indexing the arrays with counters) and two integer counters, it resulted in an exact number of rows and, for each row, an exact number of columns.

However, when I have to free memory instead, Valgrind warns me that my code is producing an invalid free of some memory blocks.

valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes -s -v ./the_program

Is the Valgrind's invocation I used.

The following is the code: can anyone see my error? What am I missing?

int allocate_memory_for_map_structure(void) // The real function (but what is
                                            // reality?) takes a pointer to some
                                            // data stored in the data segment,
                                            // e.g. values for "width" and
                                            // "height".
{
    char    ***map;
    char    ***swap;
    char    ***swap2;
    char    ***start;
    int     count;
    int     width;
    int     height;

    width = 100; // could be any integer value passed to the function
    height = 75; // same as above
    map = malloc((height + 1) * sizeof(*map));
    if (map == NULL)
        return (-1);
    count = 0;
    swap = map;
    while (count < height){
        *swap = malloc((width + 1) * sizeof(**swap));
        if (*swap == NULL)
            return (clean_lines_in_map_structure(map));
        swap++;
        count++;
    }
    *swap = NULL;
    /*
    test_outcome_of_allocation(map); // I will not add this function's code to the
                                     // question. However, it was a simple test
                                     // that correctly counted the number of rows and
                                     // columns stoppin iterations when NULL
                                     // was reached by dereferencing incremented pointers.
    */
    start = map;
    swap2 = map;
    while (*swap != NULL){
        map = swap;
        swap++;
        free(*map);
    }
    free(start);
    return (0);
}

I'm interested in understanding how to do it, but even more I'm interested in understanding my mistake: why what I wrote causes an invalid freeing of memory?

Answer 1

Using double pointers initialize and free the array entries is cumbersome and error prone. You should instead use the array syntax.

You seem to rely on null pointer sentinels for the matrix boundaries. This can work but passing the matrix dimensions seems more reliable.

Note that there is a typo in if (*map == NULL): it should be if (*swap == NULL).

Here is a modified version:

int clean_lines_in_map_structure(char ***map) {
    for (int i = 0; map[i]; i++) {
        free(map[i]);
    }
    free(map);
    return -1;
}

int allocate_memory_for_map_structure(void) // The real function (but what is
                                            // reality?) takes a pointer to some
                                            // data stored in the data segment,
                                            // e.g. values for "width" and
                                            // "height".
{
    int width = 100; // could be any integer value passed to the function
    int height = 75; // same as above
    char ***map = malloc(sizeof(*map) * (height + 1));
    if (map == NULL)
        return -1;
    for (int i = 0; i < height; i++) {
        map[i] = malloc(sizeof(*map[i]) * (width + 1));
        if (map[i] == NULL)
            return clean_lines_in_map_structure(map);
        // intialize the matrix entries
        for (int j = 0; j < width + 1; j++)
            map[i][j] = NULL;
    }
    map[height] = NULL;
    /* The following two instructions are here only for test. */
    test_outcome_of_allocation(map); // I will not add this function's code to the
                                     // question. However, it was a simple test
                                     // that correctly counted the number of rows and
                                     // columns stoppin iterations when NULL
                                     // was reached by incrementing pointers.
    clean_lines_in_map_structure(map);
    return 0;
}