Task 1: Resizing arrays with realloc()

The supplied header file point_array.h defines the following structures to represent points in 3D space, and an array to contain them, similar to examples you have seen before:

typedef struct point
{
  double x, y, z; // location in 3D space
} point_t;

typedef struct 
{
  size_t len;      // number of points in the array
  point_t* points; // an array of len point_t structs
} point_array_t;

It also declares four functions for manipulating point_array_t arrays. Each takes a pointer to an array structure as their first argument. Notice the init and reset functions: these do a similar job to the create and destroy functions we have seen before, but with a slightly different interface. This style allows us to use array structs allocated on the stack, which can be useful.

// Safely initalize an empty array structure.
void point_array_init( point_array_t* pa );

// Resets the array to be empty, freeing any memory allocated if
// necessary.
void point_array_reset( point_array_t* pa );

// Append a point to the end of an array. If successful, return 0,
// else return 1;
int point_array_append( point_array_t* pa, point_t* p );

// Remove the point at index i from the array, reducing the size of
// the array by one. The order of points in the array may change.
int point_array_remove( point_array_t* pa, unsigned int i );

Example of use:

point_array_t A;
point_array_init( &A );

point_t p;
p.x = 0.0;
p.y = 1.0;
p.z = 2.0;

point_array_append( &A, &p );

// do some work with the array
// ...

// clean up
point_array_reset( &A );

In graphics-heavy programs like games, we often have arrays of 3D points that are very large, perhaps with hundreds of thousands or millions of points. For decent performance we need to be able to add points to the array very quickly. Notice that the array interface does not have a resize function: just an append for adding one point at a time. If we use the array resize method we have seen before - copying the old array into a new array that is one slot bigger - this will be very slow.

The only memory allocation standard library call we have seen so far is malloc(), which takes a single argument specifying how much memory it should allocate. Now we introduce the realloc() standard library call, which allows us to resize our chunk of storage. 

We pass realloc() the pointer we obtained from an earlier malloc() or realloc() and a new size, and it will reallocate a chunk of memory to us of the new size. If the memory allocation system can find enough space at the existing address, realloc() returns the original pointer to us. If the memory allocation system could only find enough space starting at another address, it will:

1. allocate the new chunk
2. copy the old chunk into the new chunk
3. free the old chunk
4. return a pointer to the new chunk

The description from the POSIX standard says:

void *realloc(void *ptr, size_t size);

The realloc() function shall change the size of the memory object pointed to by ptr to the size specified by size. The contents of the object shall remain unchanged up to the lesser of the new and old sizes. If the new size of the memory object would require movement of the object, the space for the previous instantiation of the object is freed. If the new size is larger, the contents of the newly allocated portion of the object are unspecified. If size is 0 and ptr is not a null pointer, the object pointed to is freed. If the space cannot be allocated, the object shall remain unchanged.

If ptr is a null pointer, realloc() shall be equivalent to malloc() for the specified size.

Upon successful completion with a size not equal to 0, realloc() shall return a pointer to the (possibly moved) allocated space. If size is 0, either a null pointer or a unique pointer that can be successfully passed to free() shall be returned. If there is not enough available memory, realloc() shall return a null pointer

This is exactly what we need for resizing arrays efficiently. realloc() will only copy the existing array contents to a new chunk of memory when it is forced to.

Notice that reallocation is still O(n) in the size of the array, since it may have to copy the array at any or every use. In practice it does a very good job of copying only occasionally, and often appears to be nearly amortized constant time.

Unstable remove

If you do not need to preserve the order of array items, you can remove items from arbitrary array indices in constant time. Operations that may reorder an array or list are called unstable operations. The fast, unstable array remove algorithm is:

1. Copy the item at the end of the array over the item you wish to remove.
2. Decrement the array length by 1.

This needs to be refined to handle empty arrays and other corner cases.

Requirements

1. Add and commit the single file "t1.c" that contains implementations of the four functions declared in point_array.h. It may contain other functions too, but remember you are aiming for high performance so you should probably keep things simple.
2. Use realloc() instead of malloc() for high performance.
3. Use a constant time unstable remove.

 

 

#include "point_array.h"#include <assert.h>#include <stdio.h>void point_array_init( point_array_t* pa ){int i=0;assert(pa != NULL);pa->len = 0;pa->points = NULL;}void point_array_reset( point_array_t* pa){pa->len = 0;free(pa->points);pa->points = NULL;}int point_array_append( point_array_t* pa, point_t* p){pa->points = (point_t*)realloc(pa->points, sizeof(point_t));if (pa->points == NULL){return 1;}pa->points[pa->len] = *p;++(pa->len);return 0;}/*void print(point_array_t *pa){int i;for(i=0;i<pa->len;++i){printf("%f %f %f\n",pa->points[i].x,pa->points[i].y,pa->points[i].z);}}*/int point_array_remove( point_array_t* pa, unsigned int i ){if(pa->len != 0 && (i < pa->len)){pa->points[i] = pa->points[pa->len - 1];--(pa->len);return 0;}else{return 1;}}/*int main(){point_array_t *p;p = (point_array_t*)malloc(10 * sizeof(point_array_t));point_array_init(p);point_t p1;