title: C: using realloc for high performance with an array of structs
body: <p>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.<br>
  I am compiling with a Makefile that looks like this:</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>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.  </p>
  
  <p>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.<br>
  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.  </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;stdint.h&gt;
  #include &lt;string.h&gt;
  #include &lt;math.h&gt;
  #include &lt;assert.h&gt;
  
  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-&gt;len = 0;
      pa-&gt;reserved = 0;
      pa-&gt;points=NULL;
  }   
  
  
  void point_array_reset( point_array_t* pa )
  {//just free the array and set pa to NULL
  
      assert(pa);
  
      pa-&gt;points = memset(pa-&gt;points, 0, sizeof(point_t)*(pa-&gt;len));
      pa-&gt;len = 0;
      pa-&gt;reserved=0;
      free(pa-&gt;points);
      pa-&gt;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-&gt;len == 0)
      {
          pa-&gt;len=1;
          pa-&gt;reserved=pa-&gt;len*2;
          pa-&gt;points = malloc(sizeof(point_t)* (pa-&gt;reserved));
          if(pa-&gt;points == NULL)//malloc failed
          {
              return 1;
          }
  
          pa-&gt;points[pa-&gt;len-1].x = p-&gt;x;
          pa-&gt;points[pa-&gt;len-1].y = p-&gt;y;
          pa-&gt;points[pa-&gt;len-1].z = p-&gt;z;
      }
  
      if (pa-&gt;reserved &gt; pa-&gt;len )
      {
          pa-&gt;len+=1;
          pa-&gt;points[pa-&gt;len-1].x = p-&gt;x;//insert at index 0
          pa-&gt;points[pa-&gt;len-1].y = p-&gt;y;
          pa-&gt;points[pa-&gt;len-1].z = p-&gt;z;
  
      }
      //when we run out of space in reserved (len has caught up)
      else if(pa-&gt;reserved == pa-&gt;len)
      {
          pa-&gt;len+=1;
          pa-&gt;reserved=pa-&gt;len*2;
          pa-&gt;points=realloc(pa-&gt;points, sizeof(point_t)*(pa-&gt;reserved));//doubling size of array
          pa-&gt;points[pa-&gt;len-1].x = p-&gt;x;//TODO: change formula to find insertion point
          pa-&gt;points[pa-&gt;len-1].y = p-&gt;y;
          pa-&gt;points[pa-&gt;len-1].z = p-&gt;z;
      }
  
  
  
      return 0;
  }
  
  
  int point_array_remove( point_array_t* pa, unsigned int i )
  {
  
      assert(pa);
      if (i &gt;= pa-&gt;len)//out of bounds
      {
          return 1;
      }   
  
      if(pa-&gt;len==0)//0 elements trying to remove from empty array
      {
          //pa-&gt;len=0;
          //free(pa-&gt;points);
          //pa-&gt;points=NULL; 
          return 1;
      }
      else if(pa-&gt;len ==1)//remove only element
      {
          pa-&gt;len-=1;//no copying required, just shorten
          pa-&gt;points=realloc(pa-&gt;points, sizeof(point_t)*(pa-&gt;len));
          //free(pa-&gt;points);
          //pa-&gt;points=NULL;
      }
      else//array size is longer than 1 or 0
      {
          pa-&gt;points[i].x = pa-&gt;points[pa-&gt;len-1].x;
          pa-&gt;points[i].y = pa-&gt;points[pa-&gt;len-1].y;
          pa-&gt;points[i].z = pa-&gt;points[pa-&gt;len-1].z;  
          pa-&gt;len-= 1;//shorten array size
          pa-&gt;reserved = pa-&gt;len*2;
          pa-&gt;points=realloc(pa-&gt;points, sizeof(point_t)*(pa-&gt;len));//could reallocate for reserve here to increase speed.
      }   
  
      return 0;
  }
  </code></pre>