Undefined behavior when deleting an element from dynamic array of structs

Question

I have an n sized array of structs dynamically allocated, and each position of the array is an array too, with different sizes for each position (an array of arrays).

I created a function to delete a given array[index] but I'm facing some undefined behavior, for example: If the array is of size 3, if I delete array[0],I can't access array[1]. This happens with other combinations of indexes too. The only way it works flawlessly is when I delete from end to start.

Here is the code I have: Structures:

typedef struct point{

    char id[5];
    char type[5];
    char color[10];
    int x;
    int y;
} Point;


typedef struct {

    char lineID[5];
    int nPoints;
    Point *pt;
}railData;

typedef struct railway {
    railData data;
}railway;

This is how the array was created:

headRail = (railway**)calloc(lineNum,sizeof(railway*));

And each Rail: headRail[i] = (railway*)calloc(pointsNum,sizeof(railway));

These are the functions to delete a rail:

railway **delRail(railway **headRail, int j)
{
    int nPts = 0;

    if (!headRail)
    {
        puts(ERRORS[NULLPOINTER]);
        return NULL;
    }

    // Number of rail points on jth rail

    nPts = headRail[j]->data.nPoints;

    // Free each rail point from jth rail
    for (int i = 0; i < nPts; ++i)
    {
        free(headRail[j][i].data.pt);
    }

    // Free allocated memory for jth rail 
    free(headRail[j]);

    return headRail;
}

And this is where I call the previous function:

railway **removeRail(railway **headRail)
{
    char userID[20];
    int index = 0;

    // Quit if no rails 
    if (!headRail)
    {
        backToMenu("No rails available!");
        return NULL;
    }

    // Get user input
    getString("\nRail ID: ",userID,MINLEN,MAXLEN); // MINLEN = 2 MAXLEN = 4



    // get index of the asked rail
    getRailIndex(headRail,userID,&index);

    if (index != NOTFOUND)
    {
        headRail = delRail(headRail, index);
        // Update number of rails in the array (global var)
        NUMOFRAILS--;

        backToMenu("Rail deleted!\n");
    }
    else
        backToMenu("Rail not found!");

    return headRail;
}

So my question is how can I modify my code so that when position i is eliminated, all other indexes are shifted left and the last position, which would be empty, is discarded (something like realloc but for shrinking)

Is what I'm asking doable without changing the array's structure?

Answer 1

When removing element i, do memmove all the data from i+1 to i to the end of the array and then realloc with the size decremented by 1.

Note that arrays in C do not track their size in any way, so you need to pass the size by an external way.

Your data abstraction is strange. I would expect that headRail[j][0].data.nPoints is used to store the number of points inside the headRail[j][0].data structure, yet there you store the count of headRails in the j row headRail[j][<this count>]. I would advise to rewrite the abstraction, have one "object" for the railway and another for hadling two dimensional arrays of railways with dynamic sizes in all directions.

Like:

railway **delRail(railway **headRail, int j)
{
    ...

    // this is strange, it's equal to
    // nPts = headRail[j][0].data.nPoints;
    // dunno if you mean that, 
    // or if [j][0].data.nPoints refers to the size of 
    // headRail[j][0].data.pt or to the size of the whole array
    size_t nPts = headRail[j]->data.nPoints;
    for (size_t i = 0; i < nPts; ++i) {
        free(headRail[j][i].data.pt);
    }
    free(headRail[j]);

    // note that arrays in C does not know how many elements are there in the array
    // so you typically pass that along the arguments, like
    // railway **delRail(railway **headRail, size_t railcount, int j);
    size_t headRailCount = lineNum; // some external knowledge of the size
    memmove(&headRail[j], &headRail[j + 1], (headRailCount - j - 1) * sizeof(*headRail));
    void *pnt = realloc(headRail, (headRailCount - 1) * sizeof(*headRail));
    if (pnt == NULL) return NULL; // that would be strange
    headRail = pnt; // note that the previous headRail is no longer valid
    --lineNum; // decrement that object where you store the size of the array

    return headRail;
}

What about some encapsulation and more structs instead of 2d array? 2d arrays are really a bit of pain for C, what about:

typedef struct {
    // stores a single row of rail datas
    struct railData_row_s {
        // stores a pointer to an array of rail datas
        railData *data;
        // stores the count of how many datas of rails are stored here
        size_t datacnt;
    // stores a pointer to an array of rows of rail datas
    } *raildatas;
    // stores the size of the pointer of rows of rail datas
    size_t raildatascnt;
} railway;

The count of mallocs will stay the same, but thinking about data will get simpler. And each pointer that points to an array of data has it's own size tracking variable. An allocation might look like this:

railway *rail_new(size_t lineNum, size_t pointsNum) {
   railway *r = calloc(1, sizeof(*r));
   if (!r) { return NULL; }

   // allocate the memory for rows of raildata
   r->raildatascnt = lineNum;
   r->raildatas = calloc(r->raildatascnt, sizeof(*r->raildatas));
   if (!t->raildatas) { /* error hadnling */ free(r); abort(); }

   // for each row of raildata
   for (size_t i = 0; i < r->raildatascnt; ++i) {
        struct railData_row_s * const row = &r->raildatas[i];

        // allocate the memory for the column of raildata
        // hah, looks similar to the above?
        row->datacnt = pointsNum;
        row->data = calloc(row->datacnt, sizeof(*row->data));
        if (!row->data) { /* error ahdnling */ abort(); }

   }

   return r;
}