Allocate contiguous memory

Question

I'm trying to allocate a large space of contiguous memory in C and print this out to the user. My strategy for doing this is to create two pointers (one a pointer to double, one a pointer to pointer to double), malloc one of them to the entire size (m * n) in this case the pointer to pointer to double. Then malloc the second one to the size of m. The last step will be to iterate through the size of m and perform pointer arithmetic that would ensure the addresses of the doubles in the large array will be stored in contiguous memory. Here is my code. But when I print out the address it doesn't seem to be in contiguous (or in any sort of order). How do i print out the memory addresses of the doubles (all of them are of value 0.0) correctly?

/* correct solution, with correct formatting */


/*The total number of bytes allocated was:  4
0x7fd5e1c038c0 - 1
 0x7fd5e1c038c8 - 2
 0x7fd5e1c038d0 - 3
 0x7fd5e1c038d8 - 4*/

 double **dmatrix(size_t m, size_t n);

int main(int argc, char const *argv[])
{
    int m,n,i;
    double ** f;
    m = n = 2;  
    i = 0;

    f = dmatrix(sizeof(m), sizeof(n));

    printf("%s %d\n", "The total number of bytes allocated was: ", m * n);
    for (i=0;i<n*m;++i) {
        printf("%p - %d\n ", &f[i], i + 1);
    }
    return 0;
}

double **dmatrix(size_t m, size_t n) {

    double ** ptr1 = (double **)malloc(sizeof(double *) * m * n);
    double * ptr2 = (double *)malloc(sizeof(double) * m);

    int i;
    for (i = 0; i < n; i++){
        ptr1[i] = ptr2+m*i;
    }


    return ptr1;
}

WhozCraig WhozCraig · Accepted Answer · 2012-11-03T22:01:34

Remember that memory is just memory. Sounds trite, but so many people seem to think of memory allocation and memory management in C as being some magic-voodoo. It isn't. At the end of the day you allocate whatever memory you need, and free it when you're done.

So start with the most basic question: If you had a need for 'n' double values, how would you allocate them?

double *d1d = calloc(n, sizeof(double));
// ... use d1d like an array (d1d[0] = 100.00, etc. ...
free(d1d);

Simple enough. Next question, in two parts, where the first part has nothing to do with memory allocation (yet):

How many double values are in a 2D array that is m*n in size?
How can we allocate enough memory to hold them all.

Answers:

There are m*n doubles in a m*n 2D-matrix of doubles
Allocate enough memory to hold (m*n) doubles.

Seems simple enough:

size_t m=10;
size_t n=20;
double *d2d = calloc(m*n, sizeof(double));

But how do we access the actual elements? A little math is in order. Knowing m and n, you can simple do this

size_t i = 3; // value you want in the major index (0..(m-1)).
size_t j = 4; // value you want in the minor index (0..(n-1)).
d2d[i*n+j] = 100.0;

Is there a simpler way to do this? In standard C, yes; in C++ no. Standard C supports a very handy capability that generates the proper code to declare dynamically-sized indexible arrays:

size_t m=10;
size_t n=20;
double (*d2d)[n] = calloc(m, sizeof(*d2d));

Can't stress this enough: Standard C supports this, C++ does NOT. If you're using C++ you may want to write an object class to do this all for you anyway, so it won't be mentioned beyond that.

So what does the above actual do ? Well first, it should be obvious we are still allocating the same amount of memory we were allocating before. That is, m*n elements, each sizeof(double) large. But you're probably asking yourself,"What is with that variable declaration?" That needs a little explaining.

There is a clear and present difference between this:

double *ptrs[n];  // declares an array of `n` pointers to doubles.

and this:

double (*ptr)[n]; // declares a pointer to an array of `n` doubles.

The compiler is now aware of how wide each row is (n doubles in each row), so we can now reference elements in the array using two indexes:

size_t m=10;
size_t n=20;
double (*d2d)[n] = calloc(m, sizeof(*d2d));
d2d[2][5] = 100.0; // does the 2*n+5 math for you.
free(d2d);

Can we extend this to 3D? Of course, the math starts looking a little weird, but it is still just offset calculations into a big'ol'block'o'ram. First the "do-your-own-math" way, indexing with [i,j,k]:

size_t l=10;
size_t m=20;
size_t n=30;
double *d3d = calloc(l*m*n, sizeof(double));

size_t i=3;
size_t j=4;
size_t k=5;
d3d[i*m*n + j*m + k] = 100.0;
free(d3d);

You need to stare at the math in that for a minute to really gel on how it computes where the double value in that big block of ram actually is. Using the above dimensions and desired indexes, the "raw" index is:

i*m*n = 3*20*30 = 1800
j*m   = 4*20    =   80
k     = 5       =    5
======================
i*m*n+j*m+k     = 1885

So we're hitting the 1885'th element in that big linear block. Lets do another. what about [0,1,2]?

i*m*n = 0*20*30 =    0
j*m   = 1*20    =   20
k     = 2       =    2
======================
i*m*n+j*m+k     =   22

I.e. the 22nd element in the linear array.

It should be obvious by now that so long as you stay within the self-prescribed bounds of your array, i:[0..(l-1)], j:[0..(m-1)], and k:[0..(n-1)] any valid index trio will locate a unique value in the linear array that no other valid trio will also locate.

Finally, we use the same array pointer declaration like we did before with a 2D array, but extend it to 3D:

size_t l=10;
size_t m=20;
size_t n=30;
double (*d3d)[m][n] = calloc(l, sizeof(*d3d));
d3d[3][4][5] = 100.0;
free(d3d);

Again, all this really does is the same math we were doing before by hand, but letting the compiler do it for us.

I realize is may be a bit much to wrap your head around, but it is important. If it is paramount you have contiguous memory matrices (like feeding a matrix to a graphics rendering library like OpenGL, etc), you can do it relatively painlessly using the above techniques.

Finally, you might wonder why would anyone do the whole pointer arrays to pointer arrays to pointer arrays to values thing in the first place if you can do it like this? A lot of reasons. Suppose you're replacing rows. swapping a pointer is easy; copying an entire row? expensive. Supposed you're replacing an entire table-dimension (m*n) in your 3D array (l*n*m), even more-so, swapping a pointer: easy; copying an entire m*n table? expensive. And the not-so-obvious answer. What if the rows widths need to be independent from row to row (i.e. row0 can be 5 elements, row1 can be 6 elements). A fixed l*m*n allocation simply doesn't work then.

Best of luck.

Allocate contiguous memory

2 Answers