I am using realloc to adjust the size of an array of structs containing 3 points x, y and z. This struct is encapsulated inside another struct that contains the array, the length of the array and a "reserved" value that is used for a pre-allocation strategy for even faster performance when it is evident that more structs of points will be appended to the struct array.
I am compiling with a Makefile that looks like this:
CFLAGS = -g -Wall
LIBS = -lm
default: echo "You must specify a target, e.g. file1, file2"
file2:
gcc $(CFLAGS) -o $@ test.c file2.c $(LIBS)
I have a function to initialize an empty array structure, one to reset the array to be empty and free any dynamically allocated memory, one to append a point to the end of the array and one to remove a point designated by the index value.
I am getting two errors that I cannot find the cause of. One is that my code returns a non-zero status code of 1 and the other is the length seems to be off by one when I append a few thousand points.
I am letting the append function do all the work but if I should be allocating dynamic memory in initialization, please tell me so. I am pretty sure that my reset and remove functions are working as they are supposed to. Please take a look at append as well.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <math.h>
#include <assert.h>
typedef struct point
{
int x, y, z;
} point_t;
typedef struct
{
// number of points in the array
size_t len;
// pointer to an array of point_t structs
point_t* points;
size_t reserved;
} point_array_t;
void point_array_initial( point_array_t* pa )
{
assert(pa);
pa->len = 0;
pa->reserved = 0;
pa->points=NULL;
}
void point_array_reset( point_array_t* pa )
{//just free the array and set pa to NULL
assert(pa);
pa->points = memset(pa->points, 0, sizeof(point_t)*(pa->len));
pa->len = 0;
pa->reserved=0;
free(pa->points);
pa->points=NULL;
}
int point_array_append( point_array_t* pa, point_t* p )
{
assert(pa);
assert(p);
if(pa == NULL)//something wrong with intialization or reset
{
return 1;
}
if(p == NULL)//nothing to append
{
return 1;
}
//append the first point
if(pa->len == 0)
{
pa->len=1;
pa->reserved=pa->len*2;
pa->points = malloc(sizeof(point_t)* (pa->reserved));
if(pa->points == NULL)//malloc failed
{
return 1;
}
pa->points[pa->len-1].x = p->x;
pa->points[pa->len-1].y = p->y;
pa->points[pa->len-1].z = p->z;
}
if (pa->reserved > pa->len )
{
pa->len+=1;
pa->points[pa->len-1].x = p->x;//insert at index 0
pa->points[pa->len-1].y = p->y;
pa->points[pa->len-1].z = p->z;
}
//when we run out of space in reserved (len has caught up)
else if(pa->reserved == pa->len)
{
pa->len+=1;
pa->reserved=pa->len*2;
pa->points=realloc(pa->points, sizeof(point_t)*(pa->reserved));//doubling size of array
pa->points[pa->len-1].x = p->x;//TODO: change formula to find insertion point
pa->points[pa->len-1].y = p->y;
pa->points[pa->len-1].z = p->z;
}
return 0;
}
int point_array_remove( point_array_t* pa, unsigned int i )
{
assert(pa);
if (i >= pa->len)//out of bounds
{
return 1;
}
if(pa->len==0)//0 elements trying to remove from empty array
{
//pa->len=0;
//free(pa->points);
//pa->points=NULL;
return 1;
}
else if(pa->len ==1)//remove only element
{
pa->len-=1;//no copying required, just shorten
pa->points=realloc(pa->points, sizeof(point_t)*(pa->len));
//free(pa->points);
//pa->points=NULL;
}
else//array size is longer than 1 or 0
{
pa->points[i].x = pa->points[pa->len-1].x;
pa->points[i].y = pa->points[pa->len-1].y;
pa->points[i].z = pa->points[pa->len-1].z;
pa->len-= 1;//shorten array size
pa->reserved = pa->len*2;
pa->points=realloc(pa->points, sizeof(point_t)*(pa->len));//could reallocate for reserve here to increase speed.
}
return 0;
}
an else is missing after the if(pa->len == 0) body in the append function: the first point is appended twice.
Note that you have too many special cases in this function. It can be simplified into just a one test: if the array is too small, reallocate it, and append the point.
Other simplifications are possible:
the test if (pa->len == 0)//0 elements trying to remove from empty array is redundant with the previous one.
take advantage of the fact that realloc(NULL, size) is equivalent to malloc(size) and realloc(p, 0) to free(p), and free(NULL) is OK.
beware that realloc() may fail, even when shrinking the block.
you should only shrink the array when it becomes too sparse, not for every call to point_array_remove.
Here is a simpler version:
#include <assert.h>
#include <stdlib.h>
typedef struct point {
int x, y, z;
} point_t;
typedef struct {
size_t len; // number of valid points in the array
size_t reserved; // allocated number of points in the array
point_t *points; // pointer to an array of point_t structs
} point_array_t;
void point_array_initial(point_array_t *pa) {
assert(pa);
pa->len = 0;
pa->reserved = 0;
pa->points = NULL;
}
void point_array_reset(point_array_t *pa) {
assert(pa);
free(pa->points);
pa->len = 0;
pa->reserved = 0;
pa->points = NULL;
}
int point_array_append(point_array_t *pa, const point_t *p) {
point_t *points;
assert(pa);
assert(p);
// no need to test pa nor p, asserts would already abort
points = pa->points;
if (pa->len >= pa->reserved || points == NULL) {
// reallocate of points array is too small
size_t newsize = pa->reserved;
if (newsize < pa->len)
newsize = pa->len;
if (newsize < 1)
newsize = 1;
newsize += newsize;
points = realloc(points, newsize * sizeof(*points);
if (points == NULL)
return 1;
pa->points = points;
pa->reserved = newsize;
}
// append point structure
points[pa->len++] = *p;
return 0;
}
int point_array_remove(point_array_t *pa, unsigned int i) {
point_t *points;
assert(pa);
if (i >= pa->len || pa->points == NULL) { //out of bounds or invalid array
return 1;
}
if (pa->len - i > 1) {
memmove(&pa->points + i, &pa->points + i + 1,
sizeof(*pa->points) * (pa->len - i - 1));
}
pa->len--;
if (pa->reserved >= pa->len * 3) {
size_t newsize = pa->len * 2;
// shorten the array with care.
// note that the array will be freed when it becomes empty
// no special case needed.
points = realloc(pa->points, sizeof(*points) * newsize);
if (points != NULL) {
pa->points = points;
pa->reserved = newsize;
}
}
return 0;
}