Dynamic Memory Allocation :: Multi-dimensional Structures

Dynamic Memory Allocation :: Multi-dimensional Structures

• It's nice that we can create a ``flat" structure, like an array of 100 doubles. But what if we want to create a 2D array of doubles at runtime? This sounds like a difficult task, but it's actually simple!
• As an example, lets say we are reading in a file of x, y, z coordinates from a file of unknown length. The incorrect method to approach this task is to create an arbitrarily large 2D array with hopefully enough rows or entries. Instead of leaving our data structure to chance, let's just dynamically allocate, and re-allocate on the fly.
• First, let's define a few macros to keep our code looking clean:

  #define oops(s) { perror((s)); exit(EXIT_FAILURE); }
  #define MALLOC(s,t) if(((s) = malloc(t)) == NULL) { oops("error: malloc() "); }
  #define INCREMENT 10
  

  MALLOC macro simply takes in the pointer (s) to the memory space to be allocated (t). oops is called when malloc fails, returning the error code from malloc and exits the program. INCREMENT is the default amount of memory to allocate when we run out of allocated space.
• On to the dynamic memory allocation!

    double **xyz;
   int i;
  
   MALLOC(xyz, sizeof(double *) * INCREMENT);
   for (i = 0; i < INCREMENT; i++) {
     MALLOC(xyz[i], sizeof(double) * 3);
   }
  

  What's going on here? Our double pointer, xyz is our actual storage 2D array. We must use a double pointer, because we are pointing to multiple pointers of doubles! If this sounds confusing, think of it this way. Instead of each array entry having a real double entry, each array position contains a pointer to another array of doubles! Therefore, we have our desired 2D array structure.
• The first MALLOC call instructs malloc to create 10 double pointers in the xyz array. So each of these 10 array positions now has an unitializied pointer to data of type pointer to a double. The for loop goes through each array position and creates a new array at each position to three doubles, because we want to read in x, y, z coordinates for each entry. The total space we just allocated is 10 spaces of 3 doubles each. So we've just allocated 30 double spaces.
• What if we run out of space? How do we reallocate?

    double **tmp;
   int current_size, n;
  
   /* clip ... other code */
  
   if (current_size >= n) {
     if ((tmp = realloc(xyz, sizeof(double *) * (n + INCREMENT)) == NULL) {
       oops("realloc() error! ");
     }
     for (i = n; i < n + INCREMENT; i++) {
       MALLOC(tmp[i], sizeof(double) * 3);
     }
     n += INCREMENT;
     xyz = tmp;
   }
  

• What's going on here? Suppose our file of x, y, z coordinates is longer than 10 lines. On the 11th line, we'll invoke the realloc(). n is the current number of rows allocated. current_size indicates the number of rows we are working on (in our case, the expression would be 10 >= 10). We instruct realloc to reallocate space for xyz of (double *) type, or double pointers of the current size (n) plus the INCREMENT. This will give us 10 additional entries. Remember NEVER reallocate to the same pointer!!
• If realloc() succeeds, then we need to allocate space for the double array of size 3 to hold the x, y, z coordinates in the new xyz realloc'd array. Note the for loop, where we start and end. Then we cleanup by providing our new max array size allocated (n) and setting the xyz double pointer to the newly realloc'd and malloc'd space, tmp.
• Not as difficult as you might have imagined it to be, right? What if we're done with our array? We should free it!

    for (i = 0; i < n; i++) {
     free(xyz[i]);
   }
   free(xyz);
  

  The above code free's each entry in the xyz array (the actual double pointers to real data) and then we free the pointer to a pointer reference. The statements cannot be reversed, because you'll lose the pointer reference to each 3-entry double array!