Dynamic array in C - realloc

Question

Before you start

• I searched for “Questions with similar headings,” and although I found some very useful information, I just can't get it to work for me.

• This is related to homework. Although this is not the project itself. I have completed this, I just port it from java to C so that I can test using the professors module testing platform.

Good, dynamically allocated arrays. I know how to build them, 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 in the out array. After storing the vertex, I increment the length counter for future calls.

p1 is the vertex I'm going to add.

out [] is the array in which I should store it (which is always full)

length - current length

A vertex is defined as ..

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

This is what I use in java ..

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

This is what I considered possible to use in c ..

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

However, I continue to receive an error message that the object was not distributed dynamically.

I have found a solution that will resolve this. Instead of using Vertex *, I was going to switch to Vertex ** and save pointers against the top. However, after switching everything that I found out, I realized that the unit test would provide me with Vertex out [], in which everything should be stored.

I 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 them, the returned array has not changed.

Any help is appreciated.

Update - requested information

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

It was originally built with the number of vertices in my polygon. For example.

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

Where vertexInPolygon is the integer number of vertices in the polygon.

Length

was a typo that was supposed to be 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 vertices and increase the size by one.

Update

Thank you all for your help. 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 redistribute a space, it can move to a new location, so the return value from realloc() should not be the same as the input pointer. This may work unless there is another memory allocation when you add to the array, because realloc() will expand the existing allocation, while there is room for that, but it will fail as soon as you start allocating other data when reading vertices There are several 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 call:

 out = addPointerToArray(vertexToAdd, out, size); 

Alternatively, you can pass a pointer to an 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 call:

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

None of these rewrites address a subtle memory leak. The problem is that if you overwrite the value you pass to realloc() with the return value, but realloc() fails, you lose the pointer to the (still) allocated array - a memory leak. 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 results in (may lead to) quadratic behavior. You would be better off allocating a large chunk of memory - for example, double the allocated space:

 int newSize = *size * 2; 

If you are worried about redistribution, at the end of the reading cycle you can use realloc() to reduce the allocated space to the exact size of the array. However, there is a bit more accounting to do; you need values: the number of vertices allocated for the array, and the number of vertices actually used.

Finally, at the moment, at least note that you really have to be ruthless and use addPointerToArray() to add the first three entries to the array. I would probably use something similar to this (unverified) 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 realloc() property so that it executes malloc() if the pointer passes at zero. Instead, you can check array->list == 0 and use malloc() and then realloc() otherwise.

You may notice that this structure also simplifies the calling code; you no longer have to deal with a separate int *size; in the main program (and its memory allocation); size is effectively bound to the VertexList structure as num_inuse . Now the main program can 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 seems that this sequence will only cause memory allocation once, because the new size (old_size + 2) * 2 allocates 4 elements to the array for the first time. It is easy to redistribute by adding a new point or by refining the formula to (old_size + 1) * 2 , or ...

If you plan to recover from a memory allocation failure (and not just exit if that happens), then you must modify addPointerToArray() to return the status (successful, not successful).

In addition, the function name must be addPointToArray() or addVertexToArray() or even addVertexToList() .

Answer 2

I have a few suggestions for your consideration:
1. Do not use the same input and output parameter when using realloc , as it can return NULL in the event of a memory failure and a memory leak, as indicated earlier. realloc can return a new block of memory (thanks @Jonathan Leffler for pointing out, I skipped this). You can change your code to something in these lines:

 Vertex * new_out = realloc(out, newSize * sizeof(Vertex)); if( NULL != new_out ) { out = new_out; out[(*size)] = v1; } else { //Error handling & freeing memory } 

2. Add NULL checks for malloc calls and handles errors when a memory failure occurs.
3. Missing calls free .
4. Change the return type addPointerToArray() from void to bool to indicate whether the addition is complete. If realloc fails, you can return a failure, say false, otherwise you can return success, say true.
Other comments related to excessive copies, etc., have already been noted by @MatthewD.
And few good observations @Jonathan Leffler (: Hope this helps!

Answer 3

Your trial program is great for me. I am using gcc 4.1.1 on Linux.

However, if your actual program is similar to your sample program, it is quite inefficient!

For example, your program copies a lot of memory: copies of the structure - initializing out , passing vertices to addPointerToArray() , copying memory through realloc() .

Skip structures using a pointer, not by copying.

If you need to significantly increase the size of your list, you might be better off using a linked list, tree, or some other structure (depending on which access you will need later).

If you just need a vector type, the standard method for implementing dynamic-size vectors is to allocate a block of memory (for example, a place for 16 vertices) and double its size each time you run out of space. This will limit the number of required reallocks.

Answer 4

Try these changes, it should work.

 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 call a function like

 addPointerToArray(vertexToAdd, &out, size); 

• There is an easy way to fix this type of problem (you may already know this). When you pass an argument to a function, think about what exactly is happening on the stack, and then combine the fact that all the changes you make to the variables present on the stack will disappear when you exit the function. This thinking should solve most of the issues associated with passing arguments.

• Starting with the optimization part, choosing the right data structure is critical to the success of any project. As mentioned above, a list of links is a better data structure for you than an array.