Thread: Splitting dynamically allocated 2D arrays

Hi all,
This is probably a very easy question, but it is late at night and I am very much stumped.

I have the following dynamically allocated 2D array:

Code:

int num_rows = 100;
int num_cols = 3;
    
double **myArray= (double**)malloc( sizeof(double *) * num_rows);
for(i = 0; i < num_rows; i++) {
    myArray[i] = (double*)malloc( sizeof(double) * num_cols);  
}

After sorting the array based on the values in column 1,:

Code:

qsort(myArray, num_rows, sizeof(myArray[0]), comp_function);

int comp_function(const void* a, const void* b) {
         double **p1 = (double**)a;
         double **p2 = (double**)b;
         double *arr1 = *p1;
         double *arr2 = *p2;

    return arr1[0] - arr2[0];
}

I need to split the array into two halves so that I can pass each separately into another function that accepts a type double ** pointer.

What is the most efficient way of splitting the array? Is it possible to keep the original double ** pointer for the first half of the array and then assign a new double ** pointer to the second half of the array?

Thanks in advance for your help!

Originally Posted by CodeNovice

I need to split the array into two halves so that I can pass each separately into another function that accepts a type double ** pointer.

It's a 2-d array, so there is more than one way to split it in half. I'm guessing, since you have 100 rows and 3 columns, you want to split it into two 2-d arrays of 50 rows and 3 columns each. Clarifying this would be good, however. This affects how you can split it, since you are in row-major order. I will assume this type of split.

Originally Posted by CodeNovice

What is the most efficient way of splitting the array?

You shouldn't worry about efficiency until you can prove through good, real data (such as profiling tools), that the splitting of these 2-d arrays is a serious bottleneck in your program. Premature optimization is the root of all evil. That aside, the answer to your question really depends. Do you just need to split it temporarily, in one small area of code? Or do you need to keep them as two separate 2-d arrays for a considerable duration, or to be used throughout a large portion of the program?

Originally Posted by CodeNovice

Is it possible to keep the original double ** pointer for the first half of the array and then assign a new double ** pointer to the second half of the array?

Yes, the easy way is to "lie" and say that you have two 2-d arrays of 50 rows each:

Code:

int p1_num_rows = num_rows / 2;
int p2_num_rows = num_rows - p1_n_elements;
double **p1 = &myArray[0];
double **p2 = &myArray[p1_num_cols];

do_something(p1, p1_num_rows, num_cols);
do_something(p2, p2_num_rows, num_cols);

This basically fakes two separate arrays. It's fine for, say, splitting the array into different chunks to be sorted in different threads. But you must always remember that you can not call free(p2) since p2 does not point to an address returned by any alloc function (malloc/calloc/realloc). Only p1 can be freed. That is why I suggest using this for simpler stuff. In a complex program, keeping track of which sub-arrays can be freed will become complex.

The other method, which is a little more complex on the surface, makes a lot of things easier since you can treat p1 and p2 as two completely separate, individually allocated arrays. Something like:

Code:

double p1_num_rows = num_rows / 2;
double p2_num_rows = num_rows - p1_num_rows;
double **p2;

p2 = allocate p2_num_rows pointers-to-double;
loop to copy second half of myArray into p2 -- this should be a shallow copy since you only need to move the pointer to the row data
realloc p1 to only have p1_num_rows pointers-to-double -- make sure to use a temp pointer in case realloc fails

A few more notes on malloc:
1. Don't cast malloc.
2. Don't use the type in the sizeof expression, use the variable, like

Code:

double **myArray= malloc(sizeof(*myArray) * num_rows);
for(i = 0; i < num_rows; i++) {
    myArray[i] = malloc(sizeof(*myArray[i]) * num_cols);

That way, if myArray ever changes to a float, int, char, etc, you only need to change the declaration and the malloc statements will still allocate the correct size.