Dynamic Array in C - realloc

Question

I know how to build Dynamically allocated arrays, but not how to grow them.

for example I have the following interface..

void insertVertex( vertex p1, vertex out[], int *size);

This method takes a vertex and stores it into the out array. After storing the vertex I increase the count of length for future calls.

p1 - is the vertex I'm going to add.

out[] - is the array I need to store it in (which is always full)

length - the current length

Vertex is defined as..

typedef struct Vertex{
int x;
int y;
} Vertex;

This is what I'm using in Java..

Vertex tempOut = new Vertex[size +1];
//Code to deep copy each object over
tempOut[size] = p1;
out = tempOut;

This is what I believed I could use in c..

out = realloc(out, (*size + 1) * sizeof(Vertex));
out[(*size)] = p1;

However, I keep on receiving an error message that the object was not allocated dynamically.

I found a solution that will resolve this.. Instead of using Vertex* I was going to switch to Vertex** and store pointers vs. vertex. However, after switching everything over I found out that I over looked the fact that the unit test will be providing me a Vertex out[] that everything has to be stored in.

I have also tried the following with no luck.

Vertex* temp = (Vertex *)malloc((*size + 1) * sizeof(Vertex));
for(int i = 0; i < (*size); i++)
{
temp[i] = out[i];
}
out = temp;

However, no matter what I do when I test after both of these the array returned has not changed.

Update - Requested information

out - is defined as an array of Vertex (Vertex out[])

It is originally built with the number of vertex in my polygon. For example.

out = (Vertex *)malloc(vertexInPolygon * sizeof(Vertex))

Where vertexInPolygon is an integer of the number of vertex in the polygon.

length was a typo that should have been size.

Size is an integer pointer

int *size = 0;

Each time a vertex is in the clipping plane we add it to the array of vertex and increase the size by one.

Update

To better explain myself I came up with a short program to show what I'm trying to do.

#include <stdio.h>
#include <stdlib.h>

typedef struct Vertex {
    int x, y;
} Vertex;

void addPointerToArray(Vertex v1, Vertex out[], int *size);

void addPointerToArray(Vertex v1, Vertex out[], int *size)
{
    int newSize = *size;
    newSize++;
    
    out = realloc(out, newSize * sizeof(Vertex));
    out[(*size)] = v1;
    
    //  Update Size
    *size = newSize;
}

int main (int argc, const char * argv[])
{
    //  This would normally be provided by the polygon
    int *size = malloc(sizeof(int)); *size = 3;
    
    //  Build and add initial vertex
    Vertex *out = (Vertex *)malloc((*size) * sizeof(Vertex));
    Vertex v1; v1.x = 1; v1.y =1;
    Vertex v2; v2.x = 2; v2.y =2;
    Vertex v3; v3.x = 3; v3.y =3;
    
    out[0] = v1;
    out[1] = v2;
    out[2] = v3;
    
    //  Add vertex
    //  This should add the vertex to the last position of out
    //  Should also increase the size by 1;
    Vertex vertexToAdd; vertexToAdd.x = 9; vertexToAdd.y = 9;
    addPointerToArray(vertexToAdd, out, size);
    
    for(int i =0; i < (*size); i++)
    {
        printf("Vertx: (%i, %i) Location: %i\n", out[i].x, out[i].y, i);
    }
   
}

Answer 1

One long-term problem is that you are not returning the updated array pointer from the addPointerToArray() function:

void addPointerToArray(Vertex v1, Vertex out[], int *size)
{
    int newSize = *size;
    newSize++;

    out = realloc(out, newSize * sizeof(Vertex));
    out[(*size)] = v1;

    //  Update Size
    *size = newSize;
}

When you reallocate space, it can move to a new location, so the return value from realloc() need not be the same as the input pointer. This might work while there is no other memory allocation going on while you add to the array because realloc() will extend an existing allocation while there is room to do so, but it will fail horribly once you start allocating other data while reading the vertices. There are a couple of ways to fix this:

Vertex *addPointerToArray(Vertex v1, Vertex out[], int *size)
{
    int newSize = *size;
    newSize++;

    out = realloc(out, newSize * sizeof(Vertex));
    out[(*size)] = v1;

    //  Update Size
    *size = newSize;
    return out;
}

and invocation:

out = addPointerToArray(vertexToAdd, out, size);

Alternatively, you can pass in a pointer to the array:

void addPointerToArray(Vertex v1, Vertex **out, int *size)
{
    int newSize = *size;
    newSize++;

    *out = realloc(*out, newSize * sizeof(Vertex));
    (*out)[(*size)] = v1;

    //  Update Size
    *size = newSize;
}

and invocation:

out = addPointerToArray(vertexToAdd, &out, size);

Neither of these rewrites addresses the subtle memory leak. The trouble is, if you overwrite the value you pass into realloc() with the return value but realloc() fails, you lose the pointer to the (still) allocated array - leaking memory. When you use realloc(), use an idiom like:

Vertex *new_space = realloc(out, newSize * sizeof(Vertex));
if (new_space != 0)
    out = new_space;
else
    ...deal with error...but out has not been destroyed!...

Note that using realloc() to add one new item at a time leads to (can lead to) quadratic behaviour. You would be better off allocating a big chunk of memory - for example, doubling the space allocated:

int newSize = *size * 2;

If you are worried about over-allocation, at the end of the reading loop, you can use realloc() to shrink the allocated space to the exact size of the array. However, there is then a bit more book-keeping to do; you need to values: the number of vertices allocated to the array, and the number of vertices actually in use.

Finally, for now at least, note that you should really be ruthlessly consistent and use addPointerToArray() to add the first three entries to the array. I'd probably use something similar to this (untested) code:

struct VertexList
{
    size_t    num_alloc;
    size_t    num_inuse;
    Vertex   *list;
};

void initVertexList(VertexList *array)
{
    // C99: *array = (VertexList){ 0, 0, 0 };
    // Verbose C99: *array = (VertexList){ .num_inuse = 0, .num_alloc = 0, .list = 0 };
    array->num_inuse = 0;
    array->num_alloc = 0;
    array->list      = 0;
}

void addPointerToArray(Vertex v1, VertexList *array)
{
    if (array->num_inuse >= array->num_alloc)
    {
        assert(array->num_inuse == array->num_alloc);
        size_t new_size = (array->num_alloc + 2) * 2;
        Vertex *new_list = realloc(array->list, new_size * sizeof(Vertex));
        if (new_list == 0)
            ...deal with out of memory condition...
        array->num_alloc = new_size;
        array->list      = new_list;
    }
    array->list[array->num_inuse++] = v1;
}

This uses the counter-intuitive property of realloc() that it will do a malloc() if the pointer passed in is null. You can instead do a check on array->list == 0 and use malloc() then and realloc() otherwise.

You might notice that this structure simplifies the calling code too; you no longer have to deal with the separate int *size; in the main program (and its memory allocation); the size is effectively bundled into the VertexList structure as num_inuse. The main program might now start:

int main(void)
{
    VertexList array;
    initVertexList(&array);
    addPointerToArray((Vertex){ 1, 1 }, &array);  // C99 compound literal
    addPointerToArray((Vertex){ 2, 2 }, &array);
    addPointerToArray((Vertex){ 3, 3 }, &array);
    addPointerToArray((Vertex){ 9, 9 }, &array);

    for (int i = 0; i < array->num_inuse; i++)
        printf("Vertex %d: (%d, %d)\n", i, array->list[i].x, array->list[i].y, i);

    return 0;
}

(It is coincidental that this sequence will only invoke the memory allocation once because the new size (old_size + 2) * 2 allocates 4 elements to the array the first time. It is easy to exercise the reallocation by adding a new point, or by refining the formula to (old_size + 1) * 2, or ...

If you plan to recover from memory allocation failure (rather than just exiting if it happens), then you should modify addPointerToArray() to return a status (successful, not successful).

Also, the function name should probably be addPointToArray() or addVertexToArray() or even addVertexToList().