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?

Too much missing, post a minimal reproducible example. AFAIK, it is a simple as MAXLEN is too big. — chux
– chux, Commented Jan 6, 2019 at 19:26
At a minimum, you need to post your struct definitions. And, you should probably post the rest of your code as well. — Craig Estey
– Craig Estey, Commented Jan 6, 2019 at 19:27

KamilCuk · Accepted Answer · 2019-01-06 20:45:13Z

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;
}

edited Jan 6, 2019 at 20:45

answered Jan 6, 2019 at 19:40

KamilCuk

146k8 gold badges84 silver badges154 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

returnNULL Over a year ago

I didn't know about memmove but it seems like the way to go. But it doesn't work, shouldn't memmove be in a loop ? Like, for ( k = j + 1; k < headrailcount; ++k) memmove(&headRail[j-1], &headRail[j], sizeof headRail[j]); Because the way you did it, it seems like you're trying to fit in the jth position all the memory right to j. As for the data abstraction, thanks for the tips, got the memo. But it would mean changing the entire project

KamilCuk Over a year ago

Och, memmove it's a short thinking of loop, when shifting data inside an array. It's equal to for (size_t i = j; i < headRailCount - 1; ++i) { headRail[i] = headRail[i + 1]; } Och you are right, i forgot about sizeof. Basically, you remove element number j. But realloc will "remove"/strip the last element. So you need to move all elements that are greater than j+1 one element to the left, so you can remove the last one in the array. Then realloc will shorten the memory, thus remove/invalidate the memory behind the last element.

Collectives™ on Stack Overflow

Undefined behavior when deleting an element from dynamic array of structs

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related